1

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет прикладной математики и механики

Кафедра технической кибернетики и автоматического регулирования

ДИПЛОМНАЯ РАБОТА

Тема: «Разработка и реализация математической модели двухключевой криптосистемы»

Выполнила:

студентка 6 курса в/о Юрковская О.И.

Воронеж 2001

Содержание

Введение

1. Постановка задачи

2. Математические основы построения RSA-криптосистемы

2.1 Теория делимости

2.2 Простые числа. Разложение на простые сомножители

2.3 Функция Эйлера

2.4 Мультипликативная функция

2.5 Основные понятия теории сравнений

2.5.1 Свойства сравнений

2.5.2 Вычеты. Полная и приведенная системы вычетов

2.5.3 Теоремы Эйлера и Ферма

2.6 Сравнения с одним неизвестным. Вычисление мультипликативного обратного

2.7 Конечные поля

2.7.1 Характеристика поля

2.7.2 Существование конечного поля

2.7.3 Мультипликативная группа конечного поля

2.8 Шифрование потока данных

3. Системы с открытым ключом

3.1 Принцип работы RSA-криптосистемы

3.2 Управление ключами

3.2.1 Генерация ключей

3.2.2 Накопление ключей

3.2.3 Распределение ключей

4. Криптографический анализ асимметричных систем шифрования

5. Работа с программой RSA

5.1 Описание программы

5.2 Требования к техническим средствам и шифруемым файлам

5.3 Вычислительный эксперимент

Заключение

Список использованных источников

Приложение 1

Приложение 2

Приложение 3

Введение

Проблема защиты информации путем её преобразования, исключающего её прочтение посторонним лицом, волновала человеческий ум с давних времен. Данная проблема в значительной степени решается использованием криптографии.

С широким распространением письменности криптография стала формироваться как самостоятельная наука. Криптография - наука о методах преобразования информации в целях ее защиты от незаконных пользователей [7]. Почти одновременно с криптографией возникла также наука о методах раскрытия зашифрованной информации - криптоанализ. Криптография занимается поиском и исследованием математических методов преобразования информации. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей [4].

Основные направления использования криптографических методов - передача конфиденциальной информации по каналам связи (например, электронная почта), установление подлинности передаваемых сообщений, хранение информации (документов, баз данных) на носителях в зашифрованном виде.

С развитием информационных технологий проблемы защиты информации начинают интересовать все большее число людей. Это утверждение справедливо как в отношении рядовых пользователей, работающих за домашним компьютером, так и компаний, использующих корпоративные сети. Особенно остро вопрос защиты и безопасного использования компьютеров встает при подключении к Internet. Для многих компаний важно не только защитить свои локальные сети от вторжения извне, но и организовать надежные и безопасные каналы связи с филиалами через общедоступную сеть Internet. Кроме того, перед корпоративными заказчиками весьма остро стоит проблема гарантированной доставки сообщений по электронной почте таким образом, чтобы посторонние лица не могли перехватить, подделать или использовать в своих интересах передаваемую информацию. Своего решения ждут также задачи, связанные с электронной коммерцией, так как ее широкомасштабное внедрение невозможно без принятия особых мер по обеспечению безопасности и конфиденциальности сообщений [9].

Для шифрования информации и организации защиты сетей в России активно используются западные продукты. Это разного рода программы защиты от несанкционированного доступа, а также шифрования файлов, -- начиная от Norton Utilities и архиваторов типа PKZIP и заканчивая серьезными приложениями уровня PGP (Pretty Good Private). Даже обычные текстовые редакторы и электронные таблицы содержат те или иные криптографические средства. Широкое распространение получили также межсетевые экраны, средства построения виртуальных частных сетей (Virtual Private Network), организация закрытых каналов обмена информацией и т. д. [9].

Комплекс криптографических методов должен сочетать как удобство, гибкость и оперативность использования, так и надежную защиту от злоумышленников циркулирующей в ИС информации [4].

Наиболее популярна криптосистема RSA, разработанная в 1977 г. и получившая название в честь её создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана. Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин его популярности на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).

Безопасность RSA обусловлена сложностью разложения большого числа на простые сомножители. На сегодняшний день не существует эффективных алгоритмов разложения числа на сомножители [1]. С помощью длины ключа можно регулировать время разложения числа на простые сомножители, которое с увеличением длины ключа будет расти и при определенной длине выйдет за пределы реального. В то же время произведение двух больших простых чисел или возведение большого числа в степень при использовании «быстрых» алгоритмов - несложная задача, занимающая несколько минут машинного времени при достаточно большой величине ключа [1].

Целью данной дипломной работы является разработка алгоритма и реализация математической модели шифра RSA, с оценкой количества итераций, необходимых для разложения большого числа на простые сомножители (скорость «взлома» шифра) и ограничением в зависимости от этого на длину ключа при заданном уровне технических характеристик компьютера; обеспечение возможности работы как с ранее сгенерированными ключами, хранящимися в файле, так и со сгенерированными непосредственно при работе.

Постановка задачи

Описать криптографическую систему с открытым ключом Р. Ривеста, А. Шамира, Л. Эйдельмана RSA.

Оценить ее криптостойкость, основанную на сложности разложения числа на простые сомножители.

Оценить количество операций, необходимых для шифрации и дешифрации информации; в зависимости от этого и от криптостойкости системы дать рекомендацию на длину ключа.

Написать алгоритм, реализующий криптосистему RSA. Использовать сгенерированные ранее ключи, хранящиеся в файле.

Написать алгоритм дешифрования итерациями для криптосистемы RSA, используя готовые ключи небольшой длины.

2. Математические основы построения RSA - криптосистемы [3]

Создатели криптографической системы RSA воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо.

Рассмотрим математические результаты, положенные в основу этого алгоритма.

2.1 Теория делимости

Здесь и далее будем рассматривать целые числа, обозначая их малыми латинскими буквами (a, b, c, d и т. д.).

Сумма, разность и произведение двух целых чисел также является числом целым, но частное от деления a на b может быть как целым, так и не целым.

В случае, когда частное от деления a на b - целое, обозначим его q, имеем a = bq, т. е. a равно произведению b на целое. Мы говорим тогда, что a делится на b или что b делит a. При этом a называем кратным числа b и b - делителем числа a. В дальнейшем будем рассматривать лишь положительные делители чисел.

Всякое целое a представляется единственным способом через положительное целое b в виде

a = bq + r ; 0 <=r <b . (*)

Число q называется неполным частным, а число r - остатком от деления a на b.

Всякое целое, делящее одновременно целые a и b, называется их общим делителем. Наибольший из общих делителей называется общим наибольшим делителем и обозначается символом НОД (a, b), или просто (a, b). Если (a, b) = 1, то a и b называются взаимно простыми.

Для разыскания общего наибольшего делителя применяется алгоритм Евклида.

Пусть a и b - положительные целые. Согласно (*) находим ряд равенств:

a = bq₁ + r₂ , 0 < r₂ < b ,

b = r₂q₂ + r₃ , 0 < r₃ < r₂ ,

r₂ = r₃q₃ + r₄ , 0 < r₄ < r₃ , (**)

………………………………

r_n-2 = r_n-1q_n-1 + r_n , 0 < r_n < r_n-1 ,

заканчивающийся, когда получаем некоторое r_n+1 = 0 . Последнее неизбежно, так как ряд b, r₂, r₃, … как ряд убывающих целых не может содержать более чем b положительных. Рассматривая равенства (**) сверху вниз, убеждаемся, что общие делители чисел a и b одинаковы с общими делителями чисел r₂ и r₃, чисел r₃ и r₄, …, чисел r_n-1 и r_n, наконец, с делителями одного числа r_n. Одновременно с этим имеем:

(a, b) = (b, r₂) = (r₂, r₃) = … = (r_n-1, r_n) = r_n .

Приходим к следующим результатам:

Совокупность общих делителей чисел a и b совпадает с совокупностью делителей их общего наибольшего делителя.

Этот общий наибольший делитель равен r_n, т. е. последнему не равному нулю остатку алгоритма Евклида.

Пример. Применим алгоритм Евклида к отысканию (525, 231). Находим



Здесь последний положительный остаток r₄ = 21. Значит, (525, 231) = 21.

2.2 Простые числа. Разложение на простые сомножители

Число 1 имеет только один положительный делитель, именно 1. В этом отношении число 1 в ряде натуральных чисел стоит особо.

Всякое целое, большее единицы, имеет не менее двух делителей, именно 1 и самого себя; если этими делителями исчерпываются все положительные делители целого числа, то оно называется простым. Целое, большее 1, имеющее кроме 1 и себя самого другие положительные делители, называется составным.

Наименьший отличный от единицы делитель целого, большего единицы, есть число простое.

Наименьший отличный от единицы делитель составного числа a (он будет простым) не превосходит .

Число простых чисел бесконечно велико. Справедливость этой теоремы следует из того, что каковы бы ни были различные простые p₁, p₂, …, p_k, можно получить новое простое, среди них не заключающееся. Таковым будет простой делитель суммы p₁p₂ … p_k+1, который, деля всю сумму, не может совпадать ни с одним из простых p₁, p₂, …, p_k.

Всякое целое а или взаимно просто с данным простым p, или же делится на p. Действительно, (a, p), будучи делителем p, может быть равно 1, или p. В первом случае a взаимно просто с p, во втором a делится на p.

Если произведение нескольких сомножителей делится на p, то, по крайней мере, один из сомножителей делится на p.

Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом, если отвлечься от порядка следования сомножителей.

Действительно, пусть а - целое, большее единицы; обозначив буквой p₁ его наименьший простой делитель, имеем a = p₁a₁. Если a₁>1, то, обозначив буквой p₂ его наименьший простой делитель, имеем a₁ = p₂a₂. Если a₂>1, то подобно этому находим a₂ = p₃a₃ и т. д., пока не придем к какому-либо a_n, равному единице. Тогда a_n-1 = p_n. Перемножая все найденные равенства и производя сокращение, получим следующее разложение а на простые сомножители:

a = p₁p₂ … p_n .

Допустим, что для того же самого а существует и второе разложение на простые сомножители a = q₁q₂ … q_s. Тогда

p₁p₂…p_n = q₁q₂…q_s .

Правая часть этого равенства делится на q₁. Следовательно, по крайней мере, один из сомножителей левой части должен делиться на q₁. Пусть, например, p₁ делится на q₁ (порядок нумерации сомножителей не важен). Тогда p₁ = q₁ (p₁ кроме 1 делится только на p₁). Сокращая обе части равенств на p₁ = q₁, имеем p₂p₃…p_n = q₂q₃…q_s. Повторяя прежнее рассуждение применительно к этому равенству, получим p₃ … p_n = q₃ … q_s и т. д., пока, наконец, в одной части равенства, например в левой, не сократятся все сомножители. Но одновременно должны сократиться и все сомножители правой части, так как равенство 1 = q_n+1 … q_s при q_n+1, …, q_s, превосходящих 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому.

2.3 Функция Эйлера

Функция Эйлера (а) определяется для всех целых положительных а и представляет собою число чисел ряда 0, 1, ..., а-1, взаимно простых с a.

Таблица 1

a	2	3	4	5	6	7	8	9	10	11	12
(a)	1	2	2	4	2	6	4	6	4	10	4

В частности, будем иметь (p^a) = p^a - p^a-1 , (p) = p-1.

Примеры. (60) = 60

(81) = 81-27 = 54

(5) = 5-1 = 4

2.4 Мультипликативная функция

Функция (а) называется мультипликативной, если она удовлетворяет двум следующим условиям:

Эта функция определена для всех целых положительных a и не равна нулю по меньшей мере при одном таком a.

Для любых положительных взаимно простых a₁ и a₂ имеем:

(а₁ a₂) = (а₁) (а₂) .

2.5 Основные понятия теории сравнений

2.5.1 Свойства сравнений

Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое назовём модулем.

Каждому целому числу отвечает определённый остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m.

Сравнимость чисел a и b по модулю m записывается:

a b (mod m).

Сравнимость чисел a и b по модулю m равносильна:

Возможности представить a в виде a = b + mt, где t - целое.

Делимости a b на m.

Действительно, из a b (mod m) следует

a = mq + r, b = mq₁ + r, 0<= r <m,

откуда a - b = m (q - q₁), a = b + mt, t = q - q₁.

Обратно, из a = b + mt, представляя b в виде

b = mq₁ + r , 0 <=r <m ,

выводим a = mq + r, q = q₁ + t , т.е. a b (mod m).

Оба утверждения доказаны.

Два числа, сравнимые с третьим, сравнимы между собой.

Сравнения можно почленно складывать.

Действительно, пусть

A₁ b₁ (mod m) , a₂ b₂ (mod m) , …, a_k b_k (mod m) (1).

Тогда a₁ = b₁ + mt₁ , a₂ = b₂ + mt₂ , …, a_k = b_k + mt_k (2),

Откуда a₁ + a₂ + … + a_k = b₁ + b₂ + … + b_k + m (t₁ + t₂ + … + t_k), или

a₁ + a₂ + … + a_k b₁ + b₂ + … + b_k (mod m).

Сравнения можно почленно перемножать.

Рассмотрим (1) и (2). Перемножая почленно равенства (2), получим:

a₁ a₂ …a_k b₁ b₂ …b_k + mN,

где N - целое.

Отсюда: a₁ a₂ …a_k b₁ b₂ …b_k (mod m).

Обе части сравнения можно возвести в одну и ту же степень.

Обе части сравнения можно умножить на одно и то же целое число.

Действительно, перемножив сравнение a b (mod m) с очевидным сравнением k k (mod m), получим ak bk (mod m).

Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.

Действительно, из a b (mod m), a = a₁d , b = b₁d , (d, m) = 1 следует, что разность a - b, равная (a₁ - b₁)d, делится на m, т. е. a₁ b₁ (mod m) [3].

2.5.2 Вычеты. Полная и приведенная системы вычетов

Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.

Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа.

Соответственно m различным значениям r имеем m классов чисел по модулю m.

Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом.

Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Чаще всего в качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты 0, 1, ..., m-1 или также абсолютно наименьшие вычеты. Последние, как это следует из вышеизложенного, в случае нечетного m представляются рядом

, ..., -1, 0, 1, ..., ,

а в случае чётного m каким-либо из двух рядов

, ..., -1, 0, 1, ..., ,

, ..., -1, 0, 1, ..., .

Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, а так как их m, т.е. столько же, сколько и классов, то в каждый класс наверно попадёт по одному числу.

Если (a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b - любое целое, тоже пробегает полную систему вычетов по модулю m.

Действительно, чисел ax +b будет столько же, сколько и чисел x, т.е. m. Согласно предыдущему утверждению остаётся , следовательно, только показать, что любые два числа ax₁ + b и ax₂ + b, отвечающие несравнимым x₁ и x₂, будут сами несравнимы по модулю m.

Но допустив, что ax₁ + b ax₂ + b (mod m), мы придём к сравнению ax₁ = ax₂ (mod m), откуда, вследствие (a, m) = 1, получим

x₁ x₂ (mod m),

что противоречит предположению о несравнимости чисел x₁ и x₂.

Числа одного и того же класса по модулю m имеют с модулем один и тот же общий наибольший делитель. Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем.

Взяв от каждого такого класса по одному вычету, получим приведённую систему вычетов по модулю m. Приведённую систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведённую систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0, 1, ..., m-1. Так как среди этих чисел число взаимно простых с m есть (m), то число чисел приведённой системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть (m).

Пример. Приведённая система вычетов по модулю 42 будет 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Любые (m) чисел, попарно несравнимые по модулю m и взаимно простые с модулем, образуют приведённую систему вычетов по модулю m.

Действительно, будучи несравнимыми и взаимно простыми с модулем, эти числа тем самым принадлежат к различным классам, содержащим числа, взаимно простые с модулем, а так как их (m), т.е. столько же, сколько и классов указанного вида, то в каждый класс наверно попадёт по одному числу.

Если (a, m) = 1 и x пробегает приведённую систему вычетов по модулю m, то ax тоже пробегает приведённую систему вычетов по модулю m.

Действительно, чисел ax будет столько же, сколько и чисел x, т.е. (m). Согласно предыдущему свойству остаётся, следовательно, только показать, что числа ax по модулю m несравнимы и взаимно просты с модулем. Первое следует из свойства сравнений (если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m) для чисел более общего вида ax + b, второе же следует из (a, m) = 1, (x, m) = 1.

2.5.3 Теоремы Эйлера и Ферма

Теорема Эйлера (2. 5. 3. 1).

При m>1 и (a, m) = 1 имеем a^(m) 1 (mod m).

Доказательство. Действительно, если x пробегает приведённую систему вычетов

x = r₁, r₂, ..., r_c ; c = (m),

составленную из наименьших неотрицательных вычетов, то наименьшие неотрицательные вычеты ₁, ₂, ..., _с чисел ax будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (1).

Перемножая почленно сравнения

ar_{1 1} (mod m), ar_{2 2} (mod m), ..., ar_{c c} (mod m),

получим а^с 1 (mod m).

Теорема Ферма (2. 5. 3. 2).

При p простом и а, не делящимся на p, имеем

a^p-1 1 (mod p). (2)

Доказательство. Эта теорема является следствием теоремы Эйлера при m = p. Теореме Ферма можно придать более удобную форму, умножая обе части сравнения (2) на а, получим сравнение a^p a (mod p), справедливое уже при всех целых а, так как оно верно и при а, кратном p. Теорема доказана.

Теорема (2. 5. 3. 3). Если n = pq, (p и q - отличные друг от друга простые числа), то (n) = (p-1)(q-1).

Теорема (2. 5. 3. 4). Если n = pq, (p и q отличные друг от друга простые числа) и x простое относительно p и q, то x⁽ⁿ⁾ = 1 (mod n).

2.6 Сравнения с одним неизвестным. Вычисление мультипликативного обратного [6]

Чтобы вычислить мультипликативную обратную величину а^-1 для ненулевого а, необходимо решить сравнение

a * x 1 (mod n) .

Это эквивалентно нахождению таких значений x и k, что

ax = n * k +1,

где x и k - целые числа. Решение этой задачи иногда существует, а иногда его нет.

Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку 5 *3 = 15 1(mod 14). С другой стороны число 2 не имеет обратной величины по модулю 14.

В общем случае сравнение

a^-1 x (mod n)

имеет единственное решение, если a и n - взаимно простые числа.

Если числа a и n не являются взаимно простыми, тогда сравнение

a^-1 x (mod n)

не имеет решения.

Сформулируем основные способы нахождения обратных величин.

1. Проверить поочередно значения 1, 2, …, n-1, пока не будет найден a^-1 такой, что a * a^-1 1 (mod n).

Пусть n=7, a=5. Требуется найти x a^-1 (mod n)

a * x 1 (mod n) или 5*x 1 (mod 7).

Подставляя вместо x значения от 1 до n - 1 = 7 - 1 = 6 и вычисляя a * x(mod n), получаем при x=3, a * x = 5 * 3 = 15 1 (mod 7). Следовательно, a^-1 = 3.

2. Если известна функция Эйлера (n), то можно вычислить

a^-1 a^{(n) - 1} (mod n),

используя алгоритм быстрого возведения в степень.

Пусть n=7, a=5. Найти x a^-1 (mod n) = 5^-1 (mod 7).

Модуль n=7 -простое число. Поэтому функция Эйлера (n) = (7) = n-1 = 6. a^-1 = a^{(n) - 1} (mod n) = 5^6-1 (mod 7) = 3.

Итак, x = a^-1 = 3.

3. Если функция Эйлера не известна, то можно использовать расширенный алгоритм Евклида.

В этом случае при решении сравнения a * x 1 (mod m), где (a, m) =1 алгоритм Евклида позволяет найти x (-1)^k-1 Q_k-1 (mod m), где Q_k-1 - знаменатель предпоследней подходящей дроби разложения в цепную дробь.

Цепная дробь имеет вид:

= {q₀, q₁, q₂, …, q_k}.

Введем обозначения q_i - частное, r_i - остаток, тогда алгоритм нахождения q_i можно представить в виде следующей цепочки равенств:

a = mq₀ +r₁, 0 < r₁ < m,

m = r₁q₁ +r₂, 0 < r₂ < r₁,

r₁ = r₂q₂ + r₃, 0 < r₃ < r₂,

r₂ = r₃q₃ + r₄, 0 < r₄ < r₃,

…………………………

r_k-2 = r_k-1q_k-1 + r_k, 0 < r_k < r_k-1,

r_k-1 = r_kq_k +0.

Поскольку остатки r_i от делений в алгоритме Евклида образуют строго убывающую последовательность натуральных чисел, то обеспечивается сходимость алгоритма. При этом получаем, что r_k - есть общий делитель чисел a и m делит и r_k = (a, m).

Последовательности {P_n} и {Q_n} числителей и знаменателей подходящих дробей к цепной дроби определяются рекуррентно

P_-2 = 0, P_-1 = 1, P_n = q_nP_n-1 + P_n-2, для n>=0,

Q_-2 = 1, Q_-1 = 0, Q_n = q_nQ_n-1 + Q_n-2, для n>=0. [6]

Пример . Решить сравнение: 1181x 1(mod 1290816). Имеем

1181 = 1290816*0 + 1181,

1290816 = 1181*1092 + 1164,

1181 = 1164*1 + 17,

1164 = 17*68 + 8,

17 = 8*2 + 1,

8 = 1*8 + 0.

Таблица 2

n	-2	-1	0	1	2	3	4	5
qn			0	1092	1	68	2	8
Pn	0	1	0	1	1	69	139	1181
Qn	1	0	1	1092	1093	75416	1151925	1290816

k = 5, x = (-1)⁴ * 1151925 = 1151925.

В самом деле 1181 * 151925 1 (mod 1290816).

Для решения более сложный сравнений

ax = b (mod n), b 1

используется следующий прием. Сначала решают уравнение

a * y 1 (mod n),

то есть определяют

y a^-1 (mod n),

а затем находят

x a^-1b (mod n) y * b (mod n). [6]

Пример . Найти x для сравнения

5 * x = 9 (mod 23).

Получаем y = 5^-1 14 (mod 23), затем находим

x = 14 * 9 (mod 23) = 126 (mod 23) = 11,

x = 11.

2.7 Конечные поля [5]

Определение. Поле F= < F, +, x, 0, 1 > называют конечным, если F- множество его элементов - конечно.

Обозначение. F, - символ для обозначения конечного поля из q элементов, F* - мультипликативная группа не равных нулю элементов поля F. Если а - элемент некоторого кольца, а n - неотрицательное целое число, то n*а - n-кратное элемента a.

Примеры:

1. Если. p - простое число, то Z/(p) - кольцо классов вычетов по модулю p - конечное поле из p элементов:

{0}_P, {1}_P, {2}_P, ..., {p -1}_P. (*)

Если a, b Z, то {a}_p = {b}_p a b (mod p).

Для краткости при указанном p элементы ряда (*) обозначаем знаками

0, 1, 2, …, p-1.

2. Пусть p = 5, тогда таблицы сложения и умножения элементов поля Fs

Определение. Число элементов конечной группы называют ее порядком. Порядком элемента g G=<=G, *, e> называют наименьшее натуральное число n с условием

gⁿ = e.

Теорема Лагранжа.

Если m - порядок группы G=<G,*,e>, g - элемент группы G, то

^gm = e .

Если n - порядок элемента g группы <G, *, e>, m N, то

g^m = e m 0 (mod n) .

Доказательство.

Если g₁, g₂, …, g_m - все элементы группы G, g - элемент группы G, то g*g₁, g*g₂, …, g*g_m - также все элементы той же группы. Поэтому

g*g₁*g*g₂*…*g*g_m ;

отсюда легко выводится первое утверждение.

Если m = n * q + r, то

g^m = g^{n * q + r} = g^r .

Это и доказывает второе утверждение.

2.7.1 Характеристика поля

Теорема 2.7.1.1. Если F_q = < F, +, х, 0, 1 > - конечное поле из q элементов,1 - единица поля, то для любого элемента а из F

q * а = 0, (2.7.1.1)

в частности, q * 1 = 0.

Доказательство. Равенство (2.7.1.1) следует из теоремы Лагранжа, так как q (число элементов) - порядок аддитивной группы поля F_q.

Определение. Пусть F = < F, +, х, 0, 1 > - поле. Если для любого натурального m

m * 1 0,

то характеристикой поля F называют число 0, а поле F называют полем нулевой характеристики. Если для какого-либо натурального числа m m * 1= 0, то наименьшее число т с таким свойством называют характеристикой поля F.

Пример. Любое числовое поле - поле нулевой характеристики. Кольцо классов вычетов кольца Z целых чисел по простому модулю p - поле характеристики р.

Теорема 2.7.1.2. Если F - подполе поля Н, то характеристики полей F и Н равны.

Доказательство. Утверждение теоремы следует из того, что единица поля является единицей своего подполя.

Пример бесконечного поля конечной характеристики

Пусть p - простое число и F - поле; поле Н рациональных дробей над полем F является расширением поля F и, следовательно, имеет ту же характеристику, что и само поле F.

В частности, если характеристика поля F равна p, то и характеристика поля Н равна p.

Теорема 2.7.1.3. Характеристика поля F ненулевой характеристики есть число простое.

Доказательство. Предположим, что характеристика т конечного поля F есть число составное:

m = a * b; 0 < a < m; 0 < b < m.

По свойству кратных единицы поля

m * 1 = (а * 1) * (b * 1),

с другой стороны, m * 1 = 0. А так как поле не имеет делителей нуля, то или a * 1 = 0, или b * 1 = 0, что невозможно при а <т и b < т..

Теорема 2.7.1.4. Если p - характеристика конечного поля F= < F, +, х, 0, 1 > и m, n, k, l - натуральные числа, то

(1) m * 1 = n * 1 m n (mod p),

(2) (m * 1) + (n * 1) = k * 1 m + n k (mod p),

(3) (m * 1) x (n * 1) = l * 1 m * n = l (mod p).

Доказательство.

(1) Так как p - характеристика поля F, то по теореме Лагранжа

(m - n) * 1 = 0 p | (m - n).

(2) По свойству кратных имеем

(m * 1) + (n + 1) = (m + n) * 1.

Отсюда и из (1) следует (2). Аналогично доказывается утверждение (3).

Теорема 2.7.1.5. Всякое конечное простое поле F = < F, +, х, 0, 1 > характеристики p изоморфно кольцу классов вычетов кольца Z целых чисел по простому модулю р.

Доказательство. Любое подполе поля F содержит элементы

0 = 0 * 1, 1 = 1 * 1, 2 * 1, ..., (p - 1) * 1 (2.7.1.5)

В силу теоремы 2.7.1.4 сумма, разность, произведение любых элементов ряда (2.7.1.5) и обратный элемент к любому ненулевому элементу этого множества принадлежат тому же множеству. Поэтому множество элементов (2.7.1.5) относительно операций "+" и "х" образует подполе поля F, а так как F простое поле (т. е. поле, не содержащее других подполей, кроме самого поля F), то это подполе совпадает с полем F.

Определим отображение , множества (2.7.1.5) на множество классов вычетов кольца целых чисел Z по простому модулю p условием:

: m * 1 {m}_p.

Легко проверить, что - взаимно однозначное отображение, которое сумму и произведение элементов поля F переводит в сумму и произведение образов этого отображения.

Теорема 2.7.1.6. Всякое конечное поле F характеристики p содержит простое подполе из p элементов и является его конечным расширением.

Доказательство. По теореме 2.7.1.2 характеристика простого подполя поля F равна р. Но конечное поле заведомо является конечным расширением любого своего подполя.

Теорема 2.7.1.7. Число элементов конечного поля Н = Fq характеристики p есть степень его характеристики.

Доказательство. Пусть F_p - простое подполе поля H. По теореме 2.7.1.6 поле Н содержит элементы h₁, h₂, …, h_n (базис), такие, что любой элемент h поля Н однозначно представляется в виде

h = a₁ * h₁ + a₂ * h₂ + … + a_n * h_n,

где a₁, a₂, …, a_n - элементы поля Fp. Но число разных наборов < a₁, a₂, …, a_n > элементов поля Fp равно pⁿ. Поэтому q = pⁿ.

Теорема 2.7.1.8. Пусть Н - поле характеристики p; k N; a, b Н. Тогда

(a + b) ^p = a ^p + b ^p ,

(a - b) ^p = a ^p - b ^p .

Если b 0, то _p^k _k

= k .

Доказательство. Докажем первое утверждение теоремы индукцией по k. При k = 1 имеем

А так как p - простое число, то при 1 n р-1

0 (mod p).

Поэтому * a^p-n bⁿ = 0,

если 1 < n < p - 1. Следовательно,

(a + b)^p = a^P + b^p.

Переход от k к k+1 тривиален.

Так как (a - b)^p = (a + (-b))^p = a^p + (-b)^p, то второе утверждение теоремы для нечетного p очевидно, а для p = 2 легко выводится, поскольку 1 = -1. Остальные утверждения теоремы проверяются непосредственно.

2.7.2 Существование конечного поля

Теорема 2.7.2.1. Если p - простое число, n - натуральное число, q = pⁿ, то поле разложения Н над полем Fp многочлена х^q - х есть конечное поле из q элементов.

Доказательство. Полагаем f = x^q - x. Если x и y - корни многочлена f, то, как легко проверить, пользуясь теоремой 2.7.1.8, сумма, разность, произведение и частное (при y0 ) также являются корнями того же многочлена. Поэтому множество корней многочлена f является подполем поля Н. В силу теоремы 2.7.1.1 Поэтому производная многочлена f и сам многочлен f взаимно просты. Отсюда следует, что его корни все различны.

Теорема 2.7.2.2. Для любого натурального n и простого p существует конечное поле из pⁿ элементов.

Доказательство. Следует из теоремы 2.7.2.1.

2.7.3 Мультипликативная группа конечного поля

Теорема 2.7.3.1. Если F_q=<F_q,+,x,0,1>- конечное поле, a F_q, a 0, то

a^q-1 = 1 .

Доказательство. Равенство следует из теоремы Лагранжа, так как q-1 - число элементов мультипликативной группы поля F_q.

Определение. Пусть F_q = < F_q , +, x, 0, 1 > - конечное поле; a F_q, a 0.

Наименьшее натуральное число с условием

a= 1 (2.7.3.1)

называют порядком элемента а поля F_p .

Обозначение. ord а - порядок элемента а.

Теорема 2.7.3.2. Если а - элемент мультипликативной группы поля F_q, то:

ord а q - l и, более того, ord a | q - 1,

другими словами, порядок ненулевого элемента поля F_q - делитель числа q - 1;

б) в тех же предположениях, если n - натуральное число, то

a^q - ¹ = 1; (2.7.3.2)

в) если n - натуральное число и а - любой элемент поля F_q, то

а^q = а .

Доказательство.

а) Следует из теоремы Лагранжа.

б) Любой делитель числа q - 1 делит число qⁿ - 1.

в) Следует из б).

Замечание. Если q = p - простое число, то элемент а поля F_q можно рассматривать как класс вычетов кольца Z по простому модулю p с представителем а:

а = {а}_p ,

где a Z, 0 а р-1.

Условие (2.7.3.1) в этом случае равносильно условию:

a 1 (mod p) .

Поэтому порядок любого элемента a мультипликативной группы поля F_q есть вместе с тем показатель, которому принадлежит целое число а по простому модулю р.

Теорема 2.7.3.3. Пусть а -- ненулевой элемент порядка поля F_q; n, m N. Тогда

a^m = aⁿ m n (mod ).

Доказательство. В самом деле, по теореме Лагранжа

a^m-n = 1 | m - n.

Теорема 2.7.3.4. Пусть а - ненулевой элемент порядка поля F_q. Тогда элементы

1, a, a², …, a (2.7.3.4)

поля F_q все различны.

Доказательство. Следует из теоремы 2.7.3.3.

Теорема 2.7.3.5. Пусть а - ненулевой элемент порядка поля F_q. Тогда элементы (2.7.3.4) - суть все корни многочлена x- 1. (2.7.3.5)

Доказательство. При любом натуральном k

(a^k)= (a)^k = 1,

поэтому все элементы ряда (2.7.3.4) - корни многочлена (2.7.3.5). Но многочлен степени над полем имеет в поле не более корней.

Замечание. Утверждение теоремы 2.7.3.5, справедливое для элементов конечных полей, может быть несправедливо для элементов некоторых колец.

Пример. Рассмотрим Z/₈. Элемент 3 кольца классов вычетов целых чисел Z по модулю 8 имеет порядок 2. Элементы 1,2,3,7 все различны и все они корни многочлена x² -1 в этом кольце.

Ведем обозначение: (x^y)^z будем записывать в виде (x^y) z.

Теорема 2.7.3.6. Пусть а - ненулевой элемент поля F_q порядка ; k N. Тогда

ord a^k = ,

в частности, ord а^k = (k, ) = 1.

Доказательство. Введем обозначение: m = ord а^k. Тогда

a^km = 1.

По теореме Лагранжа | km. Поэтому

,

а так как

,

то .

С другой стороны,

(a^k) = (a) = 1.

Поэтому

m | ,

откуда и получаем, что

m = ord a^k = .

Теорема 2.7.3.7. Если а - элемент поля F_q порядка , то число всех элементов поля F, порядка равно .

Доказательство. Всякий элемент порядка поля F_q есть корень многочлена x- 1. По теореме 2.7.3.5 элементы (2.7.3.4) - все корни этого многочлена. По теореме 2.7.3.6 среди них элементов порядка столько, сколько чисел, взаимно простых с среди чисел ряда 0, 1, 2, ..., - 1.

По определению функции Эйлера это число равно .

Теорема 2.7.3.8. Если - натуральный делитель числа q -1, то число элементов поля F_q порядка равно , в частности, число элементов порядка q - 1 поля F_q равно (q-1).

Доказательство. Обозначим символом число элементов порядка поля F_q. По теореме 2.7.3.2 имеем

. (2.7.3.8.1)

По теореме 2.7.3.7

, (2.7.3.8.2)

Но в силу тождества Гаусса для функции Эйлера

. (2.7.3.8.3)

Из соотношений (2.7.3.8.1) и (2.7.3.8.3) следует, что

.

В силу (2.7.3.8.2) , если .

Теорема 2.7.3.9. Мультипликативная группа ненулевых элементов конечного поля F_q циклично.

Доказательство. В самом деле, порядок такой группы равен q - 1. А по теореме 2.7.3.8 число элементов порядка q - 1 в этой группе равно (q - 1). Таким образом, в мультипликативной группе ненулевых элементов поля F_q имеется по меньшей мере один элемент порядка q-1.

На этих математических фактах и основан популярный алгоритм RSA.

2.8 Шифрование потока данных [6]

Все практически применяемые криптографические методы связаны с разбиением сообщения на большое число частей фиксированного размера, каждая из которых шифруется отдельно [7]. Это существенно упрощает задачу шифрования, т. к. сообщения обычно имеют различную длину. Можно выделить следующие основные методы шифрования: побитовое шифрование потока данных (рис. 1), побитовое шифрование потока данных с обратной связью по зашифрованному (рис. 2) и по исходному сообщению (рис. 3), поблочное шифрование потока данных с прямой (рис. 4) и обратной связью (рис. 5).

При пассивных вторжениях, пользователи, не имеющие полномочий, просто наблюдают за сообщениями, передаваемым по линиям связи, не изменяя самих сообщений. При активных вторжениях, регулярные сообщения могут быть удалены, модифицированы, отсрочены, перенаправлены, защищены повторно, или сформированы ложные сообщения. В результате активных вторжений восстановление исходного текста проблематично. Поэтому криптографическая система RSA предусматривает поблочное (нелинейное) шифрование потока данных и шифрование блоками (рис. 6).

Один из основных принципов хорошего криптографического алгоритма состоит в том, чтобы малое изменение исходного текста или ключа приводило к значительному изменению шифрованного текста.

Рис. 1. Схема побитового шифрования потока данных

Рис. 2 Схема побитового шифрования потока данных с обратной связью по зашифрованному сообщению

Рис. 3 Схема побитового шифрования потока данных с обратной связью по исходному сообщению



Рис. 4 Схема поблочного шифрования потока данных

Рис. 5 Схема поблочного шифрования потока данных с обратной связью

Рис. 6 Схема шифрования блоками

Рис. 7 Схема шифрования блоками с обратной связью

При блочном шифровании исходный текст сначала разбивается на равные по длине блоки бит. К блокам применяется зависящая от ключа функция шифрования для преобразования их в блоки шифровки такой же длины [7].

Главное свойство блочного шифрования состоит в том, что каждый бит блока текста шифровки является функцией почти всех бит соответствующего блока открытого текста, и никакие два блока открытого текста не могут быть представлены одним и тем же блоком текста шифровки. Основное преимущество простого блочного шифрования состоит в том, что в хорошо сконструированной системе небольшие изменения открытого текста или ключа вызывают большие и непредсказуемые изменения в тексте шифра.

Достоинство блочных шифров состоит в том, что желающим их расколоть криптоаналитикам при достаточной длине блока ничего не остается, как вести атаку прямым подбором ключа, т. к. надежда отгадать кусок исходного текста большой длины весьма химерична.

Недостаток этого шифра связан с размножением ошибок внутри блока. Результатом изменения одного бита в принятом блоке шифровки будет неправильное расшифровывание всего блока.

3. Системы с открытым ключом

Любая передаваемая нами информация может быть представлена в виде последовательности двоичных цифр; это - сообщение [1]. Любая последовательность из n цифр, которая может быть передана, называется кодовым словом.

Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Как бы ни были сложны и надёжны криптографические системы их слабое место при практической реализации проблема распределения ключей. Для того, чтобы был возможен обмен конфиденциальной информацией между двумя субъектами ИС, ключ должен быть сгенерирован одним из них, а затем каким-то образом, опять же в конфиденциальном порядке, передан другому. То есть в общем случае для передачи ключа опять же требуется использование какой - то криптосистемы [4].

Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом (СОК). Понятие криптосистем открытого ключа было впервые введено Диффи и Хелманом в 1976 г.

В системах с открытым ключом используются два ключа - открытый и закрытый, которые математически связаны друг с другом. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения.

Для того, чтобы гарантировать надежную защиту информации, к системам с открытым ключом (СОК) предъявляются два важных и очевидных требования [6]:

преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа

определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.

Согласно этим схемам, каждый пользователь помещает в открытый каталог процедуру шифрования Е (чтобы другие подписчики использовали ее для кодирования сообщений, адресованных этому пользователю), но держит в секрете детали соответствующей процедуры D дешифровки.

Очевидно, что эти методы основаны на наблюдении, что процедура шифрования и соответствующий ключ не должны быть такими же, как процедура дешифровки и соответствующий ей ключ. Чтобы такая система имела право на существование, должен найтись простой метод, позволяющий получать процедуры Е и D друг от друга. Желательно, чтобы процедуры Е и D обладали следующими свойствами [1]:

Если М - открытый текст сообщения, то Е и D должны быть такими, что D[E(M)] = M, т. е. дешифровка зашифрованного текста М дает М.

Как Е, так и D могут быть легко вычислены.

Знание Е не приводит к легкому способу вычисления D.

Для каждого сообщения М должно быть E[D(M)] = M. Это полезно для реализации подписей.

Например, если пользователь В хочет послать частное сообщение М пользователю А, то пользователь В находит процедуру Е_А в открытом каталоге пользователя А (как в телефонном справочнике) и передает С = Е_А(М) в открытую, зная, что только А может декодировать это, пользуясь секретной процедурой D_A.

Все известные на сегодняшний день криптосистемы с открытым ключом опираются на один из следующих типов необратимости преобразований [6]:

разложение больших чисел на простые множители;

вычисление логарифма в конечном поле;

вычисление корней алгебраических уравнений в конечном поле.

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом для открытых систем.

3.1 Принцип работы RSA - криптосистемы [1]

Покажем, как работает RSA - криптосистема. Получатель вычисляет следующие величины:

p, q : выбраны два больших простых числа, которые держатся в секрете;

n : произведение p, q, которое помещается в открытый каталог;

Е : случайное целое число, также размещаемое в открытом каталоге. Используется для кодирования сообщений, посылаемых получателю, который должен убедиться, что Е взаимно просто с числом (n) = (p-1)(q-1); D : целое число, используемое получателем для декодирования, также держится в секрете.

Подведём итоги: получатель знает p, q, D, образующие секретный ключ, отправитель знает сообщение М, каждый знает открытый ключ n и Е.

Сообщение М, передаваемое получателю, прежде всего преобразуется в цифровую форму некоторой стандартной несекретной процедурой. В частности, можно использовать присвоения а=00, в=01, с=02, d=03, e=04, ..., z=25, .=26, ,=27, ?=28, ;=29, т.е. каждая буква заменяется двузначным числом. Например, сообщение «computer algebra» должно быть переписано в виде «0214121520 1904170011 0604011700». Конечно, если сообщение длинное, то оно разбивается на блоки. Длина каждого блока такова, что его численное значение не превосходит n. Важно, чтобы каждый блок M_i сообщения находился в области 0<=M_i<=n-1 поскольку в противном случае невозможно отличить его от любого большего целого числа, сравнимого с ним по модулю n. Практически модуль n выбирается большим, порядка 200 десятичных цифр, так что могут использоваться блоки размером до 10²⁰⁰.

Отправитель берёт каждый блок сообщения M_i , смотрит на открытые ключи Е и n и передаёт c_i (mod n), где 0<=M_i<=n-1. Получатель получает c_i и вычисляет (c_i)^D(mod n). Заметим, однако, что по определению мы имеем ED1 [mod (n)], откуда следует, что ED=1+k*(n) для некоторого целого k. Таким образом,

(c_i)^D (M_i)^ED = (M_i)^[1+k*(n)] M_i (mod n),

где последнее равенство получено из теоремы Эйлера (2.5.3.1). Таким образом, получатель определил блок первоначального сообщения M_i.

Пример. Как упоминалось выше, используя присвоения а=00, b=01, c=02, d=03, e=04, ..., z=25, .=26, ,=27, ?=28, ;=29, сообщение «computer algebra» мы переписываем в виде «0214121520 1904170011 0604011700»

Выбирая p=3, q=11, мы имеем n=3*11=33 и (n)=20. Более того, мы выбираем Е=7, и в этом случае D=3. Теперь каждый блок сообщения M_i состоит из двузначного числа, и зашифрованное сообщение получается по формуле

c_i (M_i)⁷ (mod 33).

А именно, мы получаем последовательность чисел 29, 20, 12, 27, 26, 13, 16, 08, 00, 11, 30, 16, 01, 08, 00, которая и передаётся. Для того, чтобы восстановить блок переданного сообщения (который в нашем случае представляет просто букву), получатель должен возвести каждое двузначное число в куб по модулю 33.

Несанкционированный перехватчик сообщения в рассмотренном примере должен вычислить D, мультипликативное обратное числа Е по модулю (p-1)(q-1). Однако, чтобы сделать это, перехватчик должен найти p и q по n=pq, находящемуся в открытом каталоге. Отметим, что p и q выбираются так, чтобы у них было одинаковое количество цифр, поэтому у n цифр вдвое больше. Более того, они должны быть выбраны так, чтобы у p-1 был достаточно большой сомножитель, обозначим его f, и у f-1 также должен быть достаточно большой сомножитель. Аналогичные ограничения накладываются на q. Это гарантирует, что открытый текст не может быть найден с помощью итераций шифрования быстрее, чем случайным поиском. Дешифрование итерациями - это процесс, когда шифрованный текст С последовательно шифруется снова, до тех пор, пока не получим вновь С, т.е. полагаем с_{1 =} с и вычисляем

c_i+1 (c_i)^E (mod n),

пока не получим c_i+1 = c. Тогда c_i = M.

Другой способ [2], которым перехватчик может пытаться решить проблему, состоит в нахождении (n), поскольку в этом случае D может быть легко вычислено из соотношения

ED 1 [mod (n)]

Однако следующие соображения показывают, что этот подход не проще чем попытки разложить n. Если известно (n), то p и q могут быть найдены следующим образом. Из соотношений

(n) = (p-1)(q-1) = pq - (p+q) +1 = n - (p+q) +1

видно, что по (n) легко находится p + q. Более того, соотношения

(p-q)*2 = (p+q)*2 - 4pq = (p+q)*2 - 4n

показывают, что, зная n и p+q, легко получить p-q. Тогда p и q даются формулами:

p = [ (p+q) + (p-q)] ,

q = [ (p+q) - (p-q) ] .

Таким образом, любая попытка найти (n) эквивалентна решению сложной проблемы разложения n на множители.

3.2 Управление ключами

Кроме выбора подходящей для конкретной ИС криптографической системы, важная проблема управление ключами. Как бы ни была сложна и надёжна сама криптосистема, она основана на использовании ключей [4]. Если для обеспечения конфиденциального обмена информацией между двумя пользователями процесс обмена ключами тривиален, то в ИС, где количество пользователей составляет десятки и сотни, управление ключами серьёзная проблема.

Под ключевой информацией понимается совокупность всех действующих в ИС ключей [4]. Если не обеспечено достаточно надёжное управление ключевой информацией, то завладев ею, злоумышленник получает неограниченный доступ ко всей информации.

Управление ключами информационный процесс, включающий в себя три элемента: генерацию ключей, накопление ключей, распределение ключей.

3.2.1 Генерация ключей

Не стоит использовать неслучайные ключи с целью лёгкости их запоминания. В серьёзных ИС используются специальные аппаратные и программные методы генерации случайных ключей [4]. Степень случайности их генерации должна быть достаточно высокой. Идеальным генератором являются устройства на основе натуральных» случайных процессов. Например, появились серийные образцы генерации ключей на основе белого радиошума.

3.2.2 Накопление ключей

Под накоплением ключей понимается организация их хранения, учёта и удаления [4]. Секретные ключи никогда не должны записываться в явном виде на носителе, который может быть считан или скопирован.

В достаточно сложной ИС один пользователь может работать с большим объёмом ключевой информации, и иногда даже возникает необходимость организации мини-баз данных по ключевой информации. Такие базы данных отвечают за принятие, хранение, учёт и удаление используемых ключей.