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

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

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

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

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

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

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

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

Выполнила:

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

Воронеж 2001

Содержание

Введение

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

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

.1 Теория делимости

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

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

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

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

.5.1 Свойства сравнений

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

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

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

.7 Конечные поля

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.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, с оценкой количества итераций, необходимых для разложения большого числа на простые сомножители (скорость «взлома» шифра) и ограничением в зависимости от этого на длину ключа при заданном уровне технических характеристик компьютера; обеспечение возможности работы как с ранее сгенерированными ключами, хранящимися в файле, так и со сгенерированными непосредственно при работе.

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

Описать криптографическую систему с открытым ключом Р. Ривеста, А. Шамира, Л. Эйдельмана 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 Функция Эйлера

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

Таблица 1

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

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

j(81) = 81-27 = 54

j(5) = 5-1 = 4

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

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

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

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

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

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

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

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

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

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

a º b (mod m).

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

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

2 Делимости 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).

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

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

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

Действительно, пусть₁ º 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].

.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 есть j(m), то число чисел приведённой системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть j(m).

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

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

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

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

Действительно, чисел ax будет столько же, сколько и чисел x, т.е. j(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^j(m) º 1 (mod m).

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

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

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

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

ar₁ º r₁ (mod m), ar₂ º r₂ (mod m), ..., ar_c º r_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).

.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.

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

В этом случае при решении сравнения 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,= r₁q₁ +r₂, 0 < r₂ < r₁,₁ = r₂q₂ + r₃, 0 < r₃ < r₂,₂ = r₃q₃ + r₄, 0 < r₄ < r₃,

…………………………_k-2 = r_k-1q_k-1 + r_k, 0 < r_k < r_k-1,_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). Имеем

= 1290816*0 + 1181,

= 1181*1092 + 1164,

= 1164*1 + 17,

= 17*68 + 8,

= 8*2 + 1,

= 1*8 + 0.

Таблица 2

= 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 для сравнения

* 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.

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

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

gⁿ = e.

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

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

^gm = e .

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

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

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

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

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

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

(2) Если 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

* а = 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 целых чисел по простому модулю р.

= 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 поля Н однозначно представляется в виде

= 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, то

^q-1 = 1 .

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

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

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

= 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 - натуральное число, то

^{q - 1} = 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. Тогда элементы

, 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. Тогда

^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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Е : случайное целое число, также размещаемое в открытом каталоге. Используется для кодирования сообщений, посылаемых получателю, который должен убедиться, что Е взаимно просто с числом j(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). Заметим, однако, что по определению мы имеем EDº1 [mod j(n)], откуда следует, что ED=1+k*j(n) для некоторого целого k. Таким образом,

(c_i)^D º (M_i)^ED = (M_i)^[1+k*j(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 и j(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], которым перехватчик может пытаться решить проблему, состоит в нахождении j(n), поскольку в этом случае D может быть легко вычислено из соотношения

ED º 1 [mod j(n)]

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

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

видно, что по j(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)] ,=  [ (p+q) - (p-q) ] .

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

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

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

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

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

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

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

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

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

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

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

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

Это самый ответственный процесс в управлении ключами. К нему предъявляются два требования: оперативность и точность распределения и скрытность распределяемых ключей.

Распределение ключей между пользователями реализуется двумя разными подходами [4]:

1 путём создания одного или нескольких центров распределения ключей.

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

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

В этом случае проблема состоит в том, чтобы надёжно удостоверить подлинность субъектов.

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

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

3 возможность отказа от центра распределения ключей

4 взаимное подтверждение подлинности участников сеанса

5 подтверждение достоверности сеанса механизмом запроса - ответа, использование для этого программных или аппаратных средств использование при обмене ключами минимального числа сообщений.

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

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

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

Среди асимметричных (открытых) криптосистем наиболее широкое распространение получила криптографическая система RSA. В этой системе получатель сообщения выбирает два больших простых числа p и q так, чтобы произведение n = pq находилось за пределами вычислительных возможностей. Исходное сообщение М может иметь произвольную длину в диапазоне 1<M<n. Шифрованный текст C, соответствующий сообщению М, может быть получен в виде

C  M^e (mod n) .

Исходный текст М восстанавливается из шифрованного C обратным преобразованием

M  C^d (mod n) .

Получатель выбирает e и d так, чтобы выполнялись условия:

(e, ) = 1

ed  1 (mod )

где  - функция Эйлера, равная (p - 1)(q - 1);

(a, b) - наибольший общий делитель двух чисел.

То есть e и d являются в мультипликативной группе обратными величинами в арифметике вычетов по mod .

Очевидно, что главной целью криптографического раскрытия является определение секретного ключа (показателя степени при C - значения d).

Известны три способа, которыми мог бы воспользоваться криптоаналитик, для раскрытия величины d по открытой информации о паре {e, n}.

Факторизация n

Разложение величины n на простые множители позволяет вычислить функцию  и, следовательно, скрытое значение d, используя уравнение

ed  1 (mod ).

Различные алгоритмы такого разложения изложены в [1]. Наиболее быстрый алгоритм, известный в настоящее время, может выполнить факторизацию n за число шагов порядка

(ln n)   .

Анализ этого выражения показывает, что число n, имеющее 200 десятичных цифр, будет хорошо защищено от известных методов раскрытия.

Прямое вычисление

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

x = p + q = n + 1 - ,

y = (p - q)² = x² - 4n.

Зная , можно определить x и, следовательно, y, зная x и y, простые p и q можно определить из следующих соотношений:

p = ,

q = .

Прямая оценка d

Третий способ криптоанализа состоит в непосредственном вычислении величины d. Аргументация этого способа основана на том, что, если d выбрано достаточно большим, чтобы простой перебор был неприемлем, вычисление d не проще факторизации n, поскольку, если d известно, то n легко факторизуется. Это можно показать следующим образом. Если d известно, то можно вычислить величину, кратную функции Эйлера, используя условие

ed - 1 = k,

где k - произвольное целое число.

Факторизацию n можно выполнить, используя любое значение, кратное  [1]. Дешифровщик, с другой стороны, может попытаться найти некоторую величину d’, которая была бы эквивалентна скрытой величине d, использованной при разработке шифра. Если существует много таких d’, то можно попытаться использовать прямой перебор, чтобы раскрыть шифр. Но все d’ различаются множителем, равным [p-1, q-1] и если этот множитель вычислен, то n можно факторизовать. Таким образом, нахождение d столь же сложно, что и факторизация n.

Таким образом, основная задача криптоанализа асимметричных систем шифрования сводится, в основном, к задаче разложения на множители (факторизация). Эта задача является одной из основных в теории чисел и формулируется следующим образом:

пусть нам дано целое число n>0, и требуется, если это возможно, найти два числа a и b, таких, что ab = n. На самом деле имеются две различные задачи: первая, называемая тестом на простоту - это проверка того, существуют ли такие a и b; вторая, называемая разложением - это задача их нахождения. Рассмотрим обе эти задачи.

Первый детерминистический тест.

Этот тест основан на малой теореме Ферма, которая утверждает, что если p - простое число, то a^p-1  1 (mod p) для всех a, 1<a<p.

Таким образом, тест состоит в выборе числа а, меньшего b и проверке

b на принадлежность классу простых чисел согласно условию a^b-1  1 (mod b) в соответствии с приведенным выражением. Практически требуется проверить только несколько значений a. Выбор а, равным 3, позволяет выявить все составные числа. Тем не менее известно, что этот тест пропускает составные числа Кармайкла (например число 561 =3 х 11 х 17).

Рекомендуется порядка 100 тестов, чтобы надежно убедиться, что данное число простое.

Второй детерминистический тест.

Разделим число “b” последовательно на 2, 3, ..., . Если при каком-нибудь делении мы получим нулевой остаток, то число “b” составное, а делитель и частное являются его сомножителями; в противном случае b - простое.

Поскольку необходимо выполнить  делений, то время проверки простоты числа “b” равно O().

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

Третий детерминистический тест.

Число “b” просто тогда и только тогда, когда b | {(b-1)! + 1}. Факториал (b-1)! и проверка делимости (b-1)!+1 для больших “b” уничтожает всякий интерес к этому тесту. Если ‘b’ имеет 100 десятичных цифр, то (b-1)! состоит примерно из 100¹⁰² цифр.

Все приведенные выше тесты были детерминистическими. Это означает, что для заданного числа “b” мы всегда получаем ответ, является ли оно простым или составным. Если заменить слово «всегда» на «с некоторой вероятностью», то оказывается возможным построить вероятностные тесты, которые называют также тестами псевдопростоты.

Первый вероятностный тест.

Этот тест позволяет выявить все составные числа Кармайкла. Выбирается случайное число a в диапазоне от 1 до b-1 и проверяется выполнение условий.

(a, b) = 1, J(a, b)  a^(b-1)/2 (mod b),

где J(a, b) символ Якоби.

Символ Якоби определяется следующими соотношениями:

J(a, p) = 1, если x²  a (mod p) имеет решения в Z_p,

J(a, p) = -1, если x²  a (mod p) не имеет решения в Z_p,

где Z_p - кольцо вычетов по модулю p.

Если b - простое число, условия приведенные выше, всегда выполняются, а если b - составное, то они не выполняются с вероятностью . Поэтому выполнение k тестов гарантирует, что ответ неправилен с вероятностью 2^-k.

Второй вероятностный тест.

Поскольку число b, которое должно быть простым, всегда нечетное, то его можно представить в виде

b = 2^rs + 1,

где s - четное число. Затем в тесте выбирается случайным образом число a в диапазоне от 1 до b-1 и проверяется выполнение условий

a^s  1 (mod b),

  -1 (mod b) для 0 < j <r.

Оба теста используются для проверки числа на принадлежность классу простых и требуют порядка О(log₂b) операций над большими числами.

Третий вероятностный тест.

Для заданного b выбираем случайным образом m, 1<m<b. Если m | b, то тест выдает ответ “b - составное число”, в противном случае - "не удалось определить".

Вероятность того, что выдается ответ “b - составное число”, равна вероятности того, что m | b. Если d(b) число делителей b и m - случайно выбрано в пределах 1<m<b, то вероятность этого равна p = [d(b) - 2]/b.

Это очень слабый тест.

Четвертый вероятностный тест.

Для заданного “b” выбираем случайным образом m, 1<m<b. Если (b, m)1, то тест выдает ответ “b - составное число”, в противном случае - "не удалось определить".

Если b составное число, то количество чисел m<b, для которых тест выдает ответ “b - составное число”, равно b - . Это число велико, если b имеет маленькие простые делители. Если b = pq, где p, q - большие простые числа, то вероятность того, что число b - простое очень мала и поэтому этот тест не лучше предыдущего.

Пятый вероятностный тест.

Это тест сильной псевдопростоты. Пусть заданы b и m. Пусть

b- 1 = t2^S,

где t - нечетное число и рассмотрим числа  для  (x_r - наименьший по абсолютной величине остаток по модулю b).

Если либо x₀ = 1, либо найдется индекс i, i<S, такой, что х_i = 1, то b называется сильно псевдопростым по основанию m и тест выдает ответ "не удалось определить", в противном случае ответ b составное число. Этот тест успешно применяется и к псевдопростым числам, таким как b=561. Если тест сильной псевдопростоты выдает ответ “b - составное число”, то b - составное число.

Докажем это от противного. Предположим, что b - нечетное простое число. Покажем по индукции, что  1 (mod b) для , что будет противоречить условию теоремы.

Очевидно, что это справедливо для r = S по теореме Ферма. Предполагая справедливость утверждения для i, нетрудно видеть, что оно справедливо для i-1, потому что равенство

влечет за собой, что возводимое в квадрат число равно ±1. Но -1 не подходит по условию (иначе бы тест выдал ответ "не удалось определить").

Доказано, что если b - составное число, то вероятность того, что тест выдаст ответ "b - составное число" не меньше  [1].

Разложение на множители больших целых чисел.

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

Метод основывается на идее Лежандра, если U²  V² (mod b) 0<U, V<b, U  V(mod b), то b делит (U - V)(U + V), но не делит ни (U - V), ни (U + V); поэтому (U-V, b) - наибольший общий делитель чисел U-Vи b, является нетривиальным делителем b и может быть легко вычислен с помощью алгоритма Евклида. Поиск таких U и V происходит в два этапа.

Пусть мы хотим разложить на множители число b. Пусть n =  - максимальное число, не превосходящее , и вычислим числа a_k = (n + k)² - b для небольших k (числа k могут быть и отрицательными).

Пусть {q_i, i = 1, 2, …, j} - множество небольших простых чисел, которые могут делить выражение вида x² - b (т.е. b является квадратом по модулю q_i). Такое множество обычно называется мультипликативной базой В. Запомним все числа a_k, которые могут быть разложены по мультипликативной базе, т.е. записаны в виде

    .

Такие a_k называются В-числами. С каждым В-числом a_k связывается вектор показателей

Если мы найдем достаточно много В-чисел, чтобы множество соответствующих векторов показателей было линейно зависимо по модулю 2

(любое множество из j+2 В-чисел обладает этим свойством), то можно будет представить нулевой вектор в виде суммы векторов показателей некоторого множества S, скажем

Определим целые числа

 i = 0, 1, …, j,

,

.

Из сказанного выше следует, что U²  V²(mod b) и (U-V, b) может быть нетривиальным делителем b.

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

С^ej(mod n)=C.

Т. е. противник просто проводит j раз зашифрование на открытом ключе перехваченного шифротекста. Это выглядит следующим образом: (С^e)^e)^e..)^e(mod n)=С^ej(mod n)). Найдя такое j, противник вычисляет C^e(j-1)(mod n) (т.е. j-1 раз повторяет операцию зашифрования) - это значение и есть открытый текст M. Это следует из того, что С^ej(mod n)=(C^e(j-1)(mod n))e=C. Т. е. некоторое число C^e(j-1)(mod n) в степени e дает шифротекст С. А это открытый текст M.

Пример. p=983, q=563, e=49, M=123456.

C=M⁴⁹(mod n)=1603, C497(mod n)=85978, C498(mod n)=123456, C499(mod n)=1603.

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

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

Программа, разработанная в среде Delphi 4, представляет собой проект с названием RSA.dpr и содержит 8 программных модулей (*.pas) и 8 соответствующих им форм (*.dfm). Опишем их более подробно:

Таблица 3

Опишем более подробно процедуры генерации ключей.

При выборе пункта Work/Keys_Generation простые числа p и q генерируются псевдослучайно. P, q проверяются на простоту с помощью вероятностного или детерминированного теста. Далее числа переводятся в десятичную систему счисления. Вычисляется их произведение n = p * q и функция Эйлера  = (p - 1)(q - 1). Так как ключи записываются в файлы при каждом вызове процедуры генерации и в программе предусмотрена возможность использования ключей из файла, некоторые элементы шифрации и дешифрации вычисляются здесь же и записываются в файлы Secret и UnSecret соответственно. Это секретный ключ d: ed  1 (mod n) (используемый для дешифрации) и открытый ключ e: (e, ) = 1.

Шифрация происходит следующим образом: каждый символ исходного текста представляется своим кодом в таблице ASCII-кодов. Далее программа работает с этим кодом как с числом, представленным в виде строки. Зашифрованное сообщение S’=S^E mod N представляет собой строку, которая записывается в файл Cipher. Таким образом, файл Cipher состоит из строк, каждая из которых является зашифрованным символом исходного текста.

При дешифрации последовательно обрабатываются строки файла Cipher: S=S’^E mod N. Полученное S представляет собой код ASCII. По нему несложно получить символ исходного текста.

Процедура дешифрования итерациями состоит в следующем: зашифрованный текст M последовательно шифруется с помощью открытого ключа, пока снова не будет получено M. Если это произошло на i+1 итерации, то результат, полученный на i итерации, и будет исходным сообщением [7], т. е. M₁ = M, …, M_i+1 = (M_i)^Е mod N, где Е - открытый ключ, N - модуль (произведение двух простых чисел). Если M_i+1 = M, то M_i - исходный текст.

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

Для нормальной работы программы необходим компьютер Pentium с объемом диска 1Гб , 16 Мб ОП и тактовой частотой 100 МГц. Требования к операционной системе: Windows-98 или Windows NT.

Программа вместе с необходимыми ей файлами ключей устанавливается в каталог New_RSA в любое место диска. Возможна работа программы как из среды Delphi 4(5), так и при отсутствии среды программирования при наличии файла RSA.exe.

Программа RSA зашифровывает файлы с расширением *.txt или без расширения, содержащие текстовую информацию. Любой символ файла будет интерпретирован как текст по таблице ASCII-кодов. Поэтому файлы, использующие другую кодировку, будут обработаны неправильно.

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

В программе RSA реализована возможность шифрации как существующих на диске, так и созданных во время работы с программой файлов. Запуск программы можно осуществить двумя способами: запустить файл RSA.exe из командной строки или, находясь в среде программирования Delphi, открыть файл проекта RSA.dpr и выполнить команду Run (F9). На экране появляется главная форма (рис. 1).

Рис. 1. Главная форма программы RSA

Пункт меню File содержит подпункты Open, Save, Save_as, Close для работы с файлами. Выберем пункт File\Open. На экране появляется диалоговое окно выбора файла (рис. 2).

Рис. 2. Диалоговое окно выбора файла

Выбираем из списка предложенных файлов Test2 и нажимаем Open. В окне главной формы появляется текст файла (рис. 3).

Рис. 3. Главная форма, содержащая текст выбранного файла

Заметим, что пункты главного меню Work/Cipher, Work/Decipher недоступны для выбора. Теперь можно выбрать Work/FromFile. Опция Work/Cipher стала доступна: выберем ее. Шифрация началась и на экране появилось окно, отображающее количество зашифрованных данных (рис. 4).

Рис. 4. Окно-индикатор процесса шифрации

При завершении шифрации текст в окне редактора главной формы приобрел следующий вид (рис. 5).

Рис. 5. Зашифрованный текст в окне главной формы

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

Расшифровать можно также любой файл, ранее зашифрованный этой программой. Для этого следует открыть его (File/Open) и выбрать пункт меню Work/Decipher. В результате дешифрации в окне появляется дешифрованное сообщение (рис. 7).

Рис. 7. Результат дешифрации в окне главной формы

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

Рис. 8. Сообщение об ошибке при попытке некорректной дешифрации

Рассмотрим другие возможности программы.

При выборе пункта меню Work/Keys_Generation появляется окно выбора теста простоты (рис. 9).

Рис. 9. Выбор способа проверки числа на простоту

Выбираем вероятностный способ. Начинается генерация ключей. Все время генерации на экране находится предупреждение “процесс генерации может занять несколько минут”. При завершении генерации предупреждение исчезает. Опция Work/Cipher стала доступной для выбора.

Пункт меню AntiRSA демонстрирует возможность раскрытия шифра системы RSA. В данном случае используются следующие ключи:

N = 47053

M = 46620

D = 16813 - открытый ключ

E = 19837 - секретный ключ [7]

При выборе пункта меню AntiRSA на экране появляется окно (рис. 11).

Рис. 11. Форма для взлома шифра RSA

Если выбрать кнопку Взломать или Зашифровать, предварительно не вводя сообщения, на экране появится окно (рис. 12).

Рис. 12. Сообщение об ошибке при отсутствии исходного текста для шифрации

При вводе исходного сообщения (число), следует учитывать, что оно должно быть меньше N, иначе появится следующее сообщение (рис. 13).

Рис. 13. Сообщение об ошибке при величине исходного текста, превышающей длину ключа

Введем сообщение 3456 и выберем кнопку Зашифровать. Зашифрованное сообщение появится в окне (рис. 14).

Рис. 14. Результат шифрации

Теперь можно выбрать кнопку Взломать и наблюдать за результатами взлома. Число итераций, необходимых для взлома, и результаты итераций отображаются на экране (рис. 15).

Для получения краткой информации о программе можно выбрать пункт меню Help/About. На экране появится форма (рис. 16).

Для получения справки о работе с программой следует выбрать пункт меню Help/Help. На экране появится форма (рис. 17).

Рис. 15. Результат взлома шифра RSA

Рис. 16. Форма, содержащая краткую информацию о программе

Рис. 17. Форма, содержащая справочную информацию о возможностях программы и особенностях работы с ней

Здесь можно найти справочную информацию о программе.

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

Вычислительный эксперимент показал следующие соотношения:

·   При использовании архиватора ARJ исходный текст сжимается на 48,6 %; зашифрованный файл сжимается на 1 %.

·   При использовании архиватора RAR исходный текст сжимается на 51,09 %; зашифрованный файл сжимается на 1,04 %.

·   При использовании архиватора ZIP исходный текст сжимается на 51,31 %; зашифрованный файл сжимается на 0,93 %.

Заключение

Таким образом, в данной работе были рассмотрены математические основы, включающие в себя теоремы Эйлера, Ферма, сравнимость простых чисел по модулю, вычисление обратной мультипликативной функции.

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

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

В зависимости от степени секретности информации и с учетом криптостойкости дана рекомендация на длину ключа.

Разработана программа, реализующая схему шифрования RSA, с возможностью шифрации и дешифрации файлов, использующих кодировку ASCII. Программа разработана в среде программирования Delphi 4 на языке Object Pascal.

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

Главным достоинством криптосистем с открытым ключом является их потенциально высокая безопасность: нет необходимости ни передавать, ни сообщать кому-либо значение секретных ключей, ни убеждаться в их подлинности [6].

Алгоритм криптосистемы с открытым ключом можно использовать в трёх направлениях.

1 Как самостоятельные средства защиты передаваемых и хранимых данных

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

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

Однако алгоритмы, лежащие в основе криптосистем с открытым ключом, имеют следующие недостатки:

·   генерация новых секретных и открытых ключей основана на генерации новых больших простых чисел, а проверка простоты чисел занимает много машинного времени;

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

Для практической реализации алгоритмов RSA полезно знать оценки трудоёмкости разложения простых чисел различной длины, сделанные Шроппелем [2].

Таблица 4

Сами авторы RSA рекомендуют использовать следующие размеры модуля n:

1 768 бит - для частных лиц

2 1024 бит - для коммерческой информации

3 2048 бит - для особо секретной информации

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

В настоящее время алгоритм RSA активно реализуется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях (в браузерах Интернет от Microsoft и Netscape) .

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

мультипликативный криптосистема шифрование

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

1 А.Г. Акритас Основы компьютерной алгебры с приложениями: пер. с венгерского. - М.: Мир, 1994. - 456 с.

2 Компьютерная алгебра. Символьные и алгебраические вычисления / Под ред. Б. Бухбергер, Дж. Коллинз, Р. Лоос , М.: Мир, 1986. - 557 с.

3 Виноградов И. М. Основы теории чисел - М.: Наука, 1981. - 176 с.

4 Баричев С. Криптография без секретов., 1998. - 43 c.

5 Нечаев В.И. Элементы криптографии: Основы теории защиты информации: Учебное пособие. - М.: Высшая школа, 1999. - 108 с.

6 Воронков Б.Н., Тупота В.И. Методическое пособие по разработке средств защиты информации в вычислительный сетях. - Воронеж: Типография ВГУ, 2000. - 112 с.

7 Жельников В. Криптография от папируса до компьютера. - М.:ABF, 1996. - 336 с.

8 Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях / Под ред. В.Ф. Шаньгина. - М.: Радио и связь, 1999. - 328 с.

9 Кузьминский М. Повседневные средства безопасной работы// Открытые системы, 2000, №12. - 12 - 19 с.

10Введение в криптографию / Под общ. ред. Ященко В.В. - М.:МЦНМО, “ЧеРо”, 1998. - 272 с.

Приложение 1

Текст основной программы RSA

unit MainProg;

interface, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,, Menus;=76; {76 бит в шифр-коде}

HC=75; {75 бит в коде Хэмминга}=152; {152 бит в общем слове}=64; {64 бит в секретном ключе}=record {тип-несекретные ключи}:string; {N-произведение двух простых чисел}:string; {E-взаимно простое с функцией Эйлера от N};=record {тип-секретные ключи}:string; {P-простое число}:string; {Q-простое число}:string; {D-мультипликатив. обратное к Е по модулю

ф.Эйлера от N};

TMainForm = class(TForm): TMainMenu;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;

Memo1: TMemo;: TOpenDialog;: TSaveDialog;

procedure Open1Click(Sender: TObject);Close1Click(Sender: TObject);Save1Click(Sender: TObject);Saveas1Click(Sender: TObject);About1Click(Sender: TObject);AntiRSA1Click(Sender: TObject);KeysGeneration1Click(Sender: TObject);FromFile1Click(Sender: TObject);Bol(a1,b1:string):integer;Deln(a3:string);Sum(a2,b2:string):string;Mins(a5,b5:string):string;Umn(a4,b4:string):string;Divis(a6,b6:string):string;Modulo(a7,b7:string):string;Hamcode;Dhamm;Recod:string;Der1(a11,b11,c11:string):string;GenKeys;Cipher1Click(Sender: TObject);Decipher1Click(Sender: TObject);Help2Click(Sender: TObject);Close2Click(Sender: TObject);FormActivate(Sender: TObject);

{ Private declarations }

{ Public declarations };: TMainForm;, Cipflag: boolean;:array[0..IC]of string; {массив двоичных кодов}:array[0..IC]of boolean; {информационный код}:array[0..HC]of boolean; {код Хэмминга}:array[0..IC,0..HC]of boolean; {порождающая матрица кода Хэмминга}:array[0..HC,0..WL]of boolean; {проверочная матрица кода Хэмминга}:array[0..WL]of boolean; {входной код на приемном блоке}:packed array[0..skd]of boolean; {бинарный код секретного ключа}:packed array[0..skd*2]of boolean; {бинарный код несекретного ключа}

security:Skey; {запись-секретные ключи}:Dkey; {запись-несекретные ключи}:File; {файл секретных ключей}:File; {файл несекретных ключей},wer:longint; {число ошибок в принятом слове}:string; {функция Эйлера},f3:file of char; {исходный файл, дешифрованный файл}:TextFile; {шифрованный файл},jd:integer; {счетчик},cp:integer; {переменная для ASCII-кодов}:string; {переменная для ASCII-кодов}:boolean; {флаг метода теста числа на простоту

- вероятностный, 0 - детерминированный}:char; {считываемый символ}

implementationDecipher, Cipher, Choose, AntiRSA, Wait, About, Help;TMainForm.Bol(a1,b1:string):integer;{Сравнение абсолютных величини b1 <0-'=', 1-'>', 2-'<'>}:integer; {переменная сравнения},sd2:integer; {сравниваемые цифры - тип <целое>}

sr1,sr2:string[1]; {сравниваемые цифры - тип <строчное>},ks2:integer; {длины сравниваемых чисел}:integer; {переменная ошибки}:=0;:=length(a1); {запоминаем длину a1}:=length(b1); {запоминаем длину b1}(ks1<>0) or (ks2<>0) do {пока не пройдем самое большое число}

begin:=0;:=0;ks1>0 then begin

sr1:=copy(a1,ks1,1); {копируем цифру 1-го числа для преобр.}sr1<>'-' then val(sr1,sd1,cd); {преобр. цифру 1-го числа в тип}

end; {<целое>}ks2>0 then begin:=copy(b1,ks2,1);sr2<>'-' then val (sr2,sd2,cd);{преобр. цифру 2-го числа в тип}; {<целое>}abs(sd1)>abs(sd2)f:=1if abs(sd1)<abs(sd2) then f:=2;ks1>0 then ks1:=ks1-1;ks2>0 then ks2:=ks2-1;

end;:=f; {значению ф-ции присваиваем значение результир. переменной f}

end;TMainForm.Deln(a3:string); {удаляем нули спереди}:boolean; {флаг наличия минуса}

kn,ac:integer; {kn-кол-во нулей спереди, ac-анализируемая цифра числа}:integer; {переменная ошибки процедуры val}:string; {переменная для работы с числом}

begin:=''; {инициализируем a31}:=a3; pos('-',a31)<>0 {если <-> в числе есть,}

then m:=true {то m-истина}m:=false; {иначе m-ложно}(copy(a31,1,1),ac,cd); {копир. в перем. ac анализир. цифру и переприсв.}

{тип-integer}(length(a31)>0) do {пока длина строки числа a31 не пустая}

begin

{копир. в перем. ac анализир. цифру и переприсв.}

val(copy(a31,1,1),ac,cd); {тип-integer}not((ac>=49)and(ac<=57)) {если ac-ноль, то} delete(a31,1,1); {из строки a31 удалить 1-й символ}

end;m then a31:='-'+a31; {если в числе есть минус, то добавить его}:=''; {спереди в результат}:=a31; {инициализируем a3 и возвращаем a3 без нулей спереди}

end;TMainForm.Sum(a2,b2:string):string; {суммирование a2+b2}

var:integer; {переменная переполнения},s2:integer; {складываемые цифры чисел a2 и b2 тип-<целое>}:integer; {сумма цифр s1 и s2 тип-<целое>}:integer; {переменная ошибки процедуры val},ks2:integer; {длины складываемых чисел a2 и b2},sk2:string[1]; {складываемые цифры чисел a2 и b2 тип-<строчное>}:string[1]; {сумма цифр s1 и s2 тип-<строчное>}:boolean; {флаг смены знака на противоположный},bb2,rez,bfr:string; {переменная для выполнения операции <сложение>}:=length(a2); {загружаем в ks1 длину числа a2}:=length(b2); {загружаем в ks2 длину числа b2}:=''; {инициализируем результирующую переменную}

if ((pos('-',a2)<>0)and(pos('-',b2)<>0)) or {если a2 и b2 одинаковы по}

((pos('-',a2)=0)and(pos('-',b2)=0)) then {знаку, то}

begin:=false; {флаг смены знака-ложный}:=0; {обнуляем переменную переполнения}not((ks1=0)and(ks2=0)) do {пока не пройдены все цифры склад.чисел}

begin:=0;:=0;:=0;:=copy(a2,ks1,1); {вычисляем младшую цифру из a2}

if ks1>0 then {если цифры a2 не пройд., то}sk1<>'-' then {если выбранная цифра не минус, то}(sk1,s1,cd); {переводим ее в тип <целое>}:=copy(b2,ks2,1); {вычисляем младшую цифру из a2}ks2>0 then {если цифры a2 не пройд., то}sk2<>'-' then val(sk2,s2,cd); {переводим ее в тип <целое>}:=abs(s2)+d; {прибавляем ко 2-му слаг. перемен. переполнения}

if (abs(s1)+abs(s2))>=10 then {если сумма абс. значений

цифр двух чисел >=10, то}

begin:=abs(s1)+abs(s2)-10; {от нее отнимем 10 и}

d:=1; {переменная переполнения равна 1}if (abs(s1)+abs(s2))<10 then {если сумма абс. значений

цифр 2-х чисел <10, то}:=abs(s1)+abs(s2); {суммируем 2 выбр. цифры}:=0; {и перем. переполн. обнулим};(s3,sk3); {результирующую цифру переведем в тип <строчное>}:=sk3+rez; {и добавим ее спереди строки результата}ks1>0 then {если число a2 не пройдено до конца, то}:=ks1-1; {перейдем к более старшей цифре}ks2>0 then {если число b2 не пройдено до конца, то}:=ks2-1; {перейдем к более старшей цифре}; {цикл while}d<>0 then begin {если переменная переполнения <>0, то}:= '1'+rez; {добавим спереди строки результата '1'}:=0; {обнулим переменную переполнения};{if then}begin {иначе, если a2 и b2 неравнозначны}Bol(b2,a2)=1 {сравним выч. числа}begin fl:=true; {знак меняем на противоположный от a2}:=b2; {переприсваиваем}:=a2; {переприсваиваем}

endbegin fl:=false;:=a2;:=b2;;:=length(bb1);:=length(bb2);:=0;not((ks1=0)and(ks2=0)) do:=0;:=0;:=0;:=copy(bb1,ks1,1);ks1>0if sk1<>'-' then val(sk1,s1,cd);:=copy(bb2,ks2,1);ks2>0if sk2<>'-' then val(sk2,s2,cd);:=abs(s2)+d;(abs(s1)-abs(s2))<0begin s3:=abs(s1)+10-abs(s2);:=1;begin s3:=abs(s1)-abs(s2);:=0;;(s3,sk3);:=sk3+rez;ks1>0 then ks1:=ks1-1;ks2>0 then ks2:=ks2-1;; {while}; {if else}(pos('-',a2)=0)and(fl) then rez:='-'+rez;

Deln(rez);:=rez;;

function TMainForm.Mins(a5,b5:string):string; {разность a5-b5}:boolean; {наличие минуса}pos('-',b5)<>0 then begin(b5,pos('-',b5),1);:=true;begin:='-'+b5;:=false;;:=sum(a5,b5);m then b5:='-'+b5delete(b5,pos('-',b5),1);;TMainForm.Umn(a4,b4:string):string; {целочисленное умножение},s2,s3,i,j:integer;,ks1,ks2:integer;,sk2,sk3:string[1];:boolean;,bfr:string;:integer;:=length(a4);:=length(b4);:='0';not(ks2=0) do:=0;:=0;:=0;:='';:=length(a4);:=copy(b4,ks2,1);ks2>0 thensk2<>'-' then val(sk2,s2,cd);:=abs(s2);not(ks1=0) do:=0;:=copy(a4,ks1,1);ks1>0 thensk1<>'-' then val(sk1,s1,cd);(abs(s1)*abs(s2)+d)>=10 then:=(abs(s1)*abs(s2)+d)-((abs(s1)*abs(s2)+d)div 10)*10;:=(abs(s1)*abs(s2)+d)div 10;(abs(s1)*abs(s2)+d)<10 then:=abs(s1)*abs(s2)+d;:=0;;(s3,sk3);:=sk3+rez;ks1>0 then ks1:=ks1-1;; {while}d<>0 then

str(d,sk3);:=sk3+rez;

d:=0;;j:=1 to length(b4)-ks2 do

rez:=rez+'0';:=sum(bfr,rez);

if ks2>0 then ks2:=ks2-1;; {while}((pos('-',a4)<>0)and(pos('-',b4)=0))or {выставим знаки}

((pos('-',a4)=0)and(pos('-',b4)<>0))bfr:='-'+bfr;(bfr);:=bfr;;TMainForm.Divis(a6,b6:string):string; {целочисленное деление a6 div b6}

var,bfr1,bfr2,rez:string;:string;:string[1];,ig,cd:integer;

beginbol(b6,'0')<>0 then:='0';:='0';kp:=1 to length(a6) do:=bfr+copy(a6,kp,1);:='0';bol(bfr,b6)<>2 do:=mins(bfr,b6);:=sum(kp1,'1');;

val(kp1,ig,cd);(ig,kp2);

if (bol(rez,'0')<>0)and(bol(bfr,b6)=2)(bol(kp1,'0')=0) rez:=rez+'0'if bol(kp1,'0')<>0rez:=rez+kp2;; {for}(rez);((pos('-',a6)<>0)and(pos('+',b6)=0))or

((pos('+',a6)=0)and(pos('-',b6)<>0))

then rez:='-'+rez;

divis:=rez;; {if then};TMainForm.Modulo(a7,b7:string):string; {взятие от a7 остатка

по модулю b7}:string;:='';:=mins(a7,umn(divis(a7,b7),b7));(modulo1);:=modulo1;;TMainForm.Hamcode; {вычисление кода Хэмминга}

var,jh:integer;:integer;

beginih:=hc downto 0 do[ih]:=false;jh:=ic downto 0 do[ih]:=hamming[ih] xor(prmx[jh,ih]and coderc[jh]);;;TMainForm.Dhamm; {восстановление ошибок по коду Хэмминга},j1,c,kn,a,b,d:integer;:array[0..wl] of boolean; {вектор ошибок}:array[0..hc] of boolean; {синдром}:boolean;i1:=hc downto 0 do[i1]:=false;j1:=wl downto 0 do[i1]:=se[i1] xor(incode[j1]and prmx1[i1,j1]);;i1:=wl downto 0 do:=0;j1:=hc downto 0 dose[j1]=prmx1[j1,i1] then c:=c+1;c=hc+1ve[i1]:=trueve[i1]:=false;;:=0;i1:=wl downto 0 dove[i1] then wer:=wer+1;:=km+1;i1:=wl downto 0 dove[i1] thenwer=1 then[i1]:=incode[i1]xor ve[i1];;TMainForm.Recod:string; {перевод двоичного кода в десятичное число}:integer;:string;:='0';l1:=wl downto hc+1 doincode[l1] then:=sum(recod1,b[l1-ic]);:=recod1;;TMainForm.Der1(a11,b11,c11:string):string; {вычисление a11 в степенипо модулю c11},buf,buf1:string;,b13,b12,b14,kt:string;:string;,bd:integer;:=b11;:=76;bol(bfs,b[bd])=2 do:=bd-1;:=mins(bfs,b[bd]);:=a11;:=bd-1;bd>=0 dobol(bfs,b[bd])=2buf:=modulo(umn(buf,buf),c11)begin:=modulo(umn(buf,buf),c11);:=modulo(umn(a11,buf),c11);

bfs:=mins(bfs,b[bd]);

end;(buf,1,length(buf)-length(c11));

bd:=bd-1;;:=buf;

end;TMainForm.GenKeys; {генерация ключей},cj:integer; {счетчики циклов}

bc:longint; {переменная для генерации большого случайного числа}:longint; {число генераций},ksy:integer; {счетчики циклов}:string; {основание теста Ферма}:boolean; {вспомогательные переменные},Q1,E1,D1:string; {ключевые числа},qm,an,bn,buf:string; {вспомогательные переменные}:array[0..1]of string; {вспомогат. переменные для алгоритма Евклида}

begin.Timer1.Enabled:=true;(Sekret,'SekrKey');(UnSekret,'UnSKey');[0]:=true;

{генерация P1}:=0;ci:=1 to skd do:=random(5000);.SetFocus;cj:=0 to randt1 do.ProcessMessages;:=random(65535);;(bc mod 2)=0 then bc:=0bc:=1;bc=1 then skbin[ci]:=trueskbin[ci]:=false;; {for ci}

P1:='0';cj:=0 to skd do {преобразуем в десятичный вид}

if skbin[cj] then P1:=sum(P1,b[cj]);P1[length(P1)]='5'P1:=sum(P1,'2');

prov:=''; {проверка на простоту}

prov:=der1('8',mins(P1,'1'),P1);

prov:=mins(prov,'1');:=true;bol(modulo(prov,P1),'0')<>0 doP1[length(P1)]='3'P1:=sum(P1,'4')P1:=sum(P1,'2');

prov:=der1('8',mins(P1,'1'),P1);

prov:=mins(prov,'1');; {while}not ftest then:='3';(bol(modulo(P1,qs),'0')<>0)and

(bol(umn(qs,qs),P1)=2) doqs[length(qs)]='3'qs:=sum(qs,'4')qs:=sum(qs,'2');(bol(umn(qs,qs),P1)=0)or

(bol(modulo(P1,qs),'0')=0)beginP1[length(P1)]='3'P1:=sum(P1,'4')P1:=sum(P1,'2');:=false;;; {if}flag;

{генерация Q1}:=0;ci:=1 to skd do:=random(5000);.SetFocus;cj:=0 to randt1 do.ProcessMessages;:=random(65535);;(bc mod 2)=0 then bc:=0bc:=1;bc=1 then skbin[ci]:=trueskbin[ci]:=false;; {for ci}

Q1:='0';cj:=0 to skd do {преобразуем в десятичный вид}

if skbin[cj] then Q1:=sum(Q1,b[cj]);Q1[length(Q1)]='5'Q1:=sum(Q1,'2');

prov:='';:=der1('8',mins(Q1,'1'),Q1);

prov:=mins(prov,'1');:=true;bol(modulo(prov,Q1),'0')<>0 doP1[length(Q1)]='3'Q1:=sum(Q1,'4')Q1:=sum(Q1,'2');

prov:=der1('8',mins(Q1,'1'),Q1);

prov:=mins(prov,'1');; {while}not ftest then:='3';(bol(modulo(Q1,qs),'0')<>0)and

(bol(umn(qs,qs),Q1)=2) doqs[length(qs)]='3'qs:=sum(qs,'4')qs:=sum(qs,'2');(bol(umn(qs,qs),Q1)=0)or

(bol(modulo(Q1,qs),'0')=0)beginQ1[length(Q1)]='3'Q1:=sum(Q1,'4')Q1:=sum(Q1,'2');:=false;;; {if}flag;

{генерация E1}[0]:=true;:=0;ci:=1 to skd do:=random(5000);cj:=0 to randt1 do:=random(65535);(bc mod 2)=0 then bc:=0bc:=1;bc=1 then skbin[ci]:=trueskbin[ci]:=false;;:='0';cj:=0 to skd do

if skbin[cj]E1:=sum(E1,b[cj]);

eyl:=umn(mins(P1,'1'),mins(Q1,'1'));

qs:='0';[0]:='0';[1]:='1';[0]:=E1;[1]:=eyl;

while bol(am[1],'0')<>0 do

qs:=divis(am[0],am[1]);:=am[0];

delete(am[0],1,length(am[0])-length(eyl)-1);(am[1],1,length(am[1])-length(eyl)-1);

am[0]:=am[1];[1]:=mins(buf,umn(am[1],qs));

end;bol(am[0],'1')<>0

then begin:=sum(E1,'2');

am[0]:=E1;;bol(am[0],'1')=0;

{генерация D1}:='1';:='1';:=eyl;:='2';bol(qm,'1')<>0 dobol(modulo(qm,qs),'0')=0 thenbol(modulo(qm,qs),'0')=0 do:=divis(qm,qs);:=umn(mins(qs,'1'),an);:=umn(qs,bn);;bol(modulo(qs[length(qs)],'2'),'0')=0qs:=sum(qs,'1')qs:=sum(qs,'2');bol(umn(qs,qs),qm)<>2qs:=qm;; {while}

D1:=der1(E1,mins(divis(umn(eyl,an),bn),'1'),eyl);

security.P:=P1;.Q:=Q1;.D:=D1;.N:=umn(P1,Q1);

dkeys.E:=E1;

{Запись ключей в файл}

Reset(UnSekret);(UnSekret,Filesize(UnSekret));(UnSekret,dkeys,SizeOf(dkeys));(UnSekret);(Sekret);(Sekret,Filesize(Sekret));(Sekret,security,SizeOf(security));

CloseFile(Sekret);

{переменная сигнализирует о том, что генерация состоялась}

KeyFlag:=true;KeyFlag then.Cipher1.Enabled:=true;.Decipher1.Enabled:=true;.Open1.Enabled:=true;EFOpenError do ShowMessage('файл ключей не найден'); EInOutError do ShowMessage('нельзя записывать в этот файл');

end;.Timer1.Enabled:=false;;

{$R *.DFM}TMainForm.Open1Click(Sender: TObject);OpenDialog1.Execute then:='RSA--'+OpenDialog1.FileName;.Open1.Enabled:=false;.Close1.Enabled:=true;.Clear;.Lines.LoadFromFile(OpenDialog1.FileName);;KeyFlag then.Enabled:=true;.Enabled:=true;;.Enabled:=false;;TMainForm.Close1Click(Sender: TObject);;;TMainForm.Save1Click(Sender: TObject);OpenDialog1.FileName<>''Memo1.Lines.SaveToFile(SaveDialog1.FileName)Saveas1Click(Sender);KeyFlag and (not CipFlag) then CipherForm.Enabled:=true;.Enabled:=false;.Enabled:=true;;TMainForm.Saveas1Click(Sender: TObject);Memo1.Lines.Count<>0with SaveDialog1 doExecute then begin.Lines.SaveToFile(FileName);:='RSA--'+ExtractFileName(FileName);;.Enabled:=true;KeyFlag and (not CipFlag) then CipherForm.Enabled:=true;.Enabled:=false;.Enabled:=true;;TMainForm.About1Click(Sender: TObject);about:TAboutBox;:=TAboutBox.Create(Self);about.ShowModal;about.Free;;;TMainForm.AntiRSA1Click(Sender: TObject);.ShowModal;;TMainForm.KeysGeneration1Click(Sender: TObject);

var:integer;{заполнение массива двоичных кодов}

b[0]:='1';i:=1 to IC do[i]:=umn(b[i-1],'2');.ShowModal;;TMainForm.FromFile1Click(Sender: TObject);

begin {ключи для генерации извлекаются из файла}

try(Sekret,'SekrKey');(Sekret);(UnSekret,'dkeys');(UnSekret);not eof(Sekret) do(Sekret,security,SizeOf(sekret));not eof(UnSekret) do(UnSekret,dkeys,SizeOf(dkeys));(Sekret);(UnSekret);.Enabled:=true;.Enabled:=true;:=true;EFOpenError do ShowMessage('файл ключей не найден');;;TMainForm.Cipher1Click(Sender: TObject);,j:integer;:string; {шифрблок}:string; {несекретный ключ N}:string; {несекретный ключ Е}(UnSekret,'dkeys');(UnSekret);not eof(UnSekret) do(UnSekret,dkeys,SizeOf(dkeys));:=dkeys.N;:=dkeys.E;(UnSekret);(f1,OpenDialog1.FileName);(f1);(f2,'cipher');(f2);.Show;:=false;.Enabled:=false;i:=0 to Memo1.Lines.Count-1 doj:=1 to Length(Memo1.Lines[i]) do(f1,Memo1.Lines[i][j]);:=chr(13);(f1,ch);;(f1);(f1);.Gauge1.MaxValue:=FileSize(f1)+1;.Gauge1.Progress:=0;

{------------------Шифрация----------------}.Gauge1.Progress:=CipherForm.Gauge1.Progress+1;not eof(f1) do(f1,ch);:=ord(ch);(temp,tc1);:=der1(tc1,e,key);(f2,kodblock);; {добавление кодов Хэмминга}i:=HC downto 0 do(f2,Hamming[i]); .Gauge1.Progress:=CipherForm.Gauge1.Progress+1;.ProcessMessages;;(f1);(f2);(f2);:='0';.Clear;.Lines.LoadFromFile('cipher');(f2);.Close;:=true;.Enabled:=false;.Enabled:=true;EFOpenError do ShowMessage('файл ключей не найден');EInOutError do ShowMessage ('нельзя записывать в этот файл');;:=true;;TMainForm.Decipher1Click(Sender: TObject);:set of '0'..'9';

i,j:integer;,sim1,cdb:string; {переменная для преобразования символов}

key,key1,key2,dm,kodblock:string; {ключи},cd:integer; {переменные для ASCII-кодов}:boolean;(Sekret,'SekrKey');(Sekret);not eof(Sekret) do(Sekret,security,SizeOf(sekret));:=security.P;:=security.Q;:=security.D;:=umn(mins(key1,'1'),mins(key2,'1'));(Sekret);:=true;:=['0','1','2','3','4','5','6','7','8','9'];(f2,'cipher');(f2);i:=0 to Memo1.Lines.Count-1 do(f2,Memo1.Lines[i]);;(f2);(f2);Memo1.Lines[0][1] in set1 {проверка шифра}fileflag:=truefileflag:=false;fileflag then(f3,'decipher');(f3);.Show;:=False;.Enabled:=false;.Gauge1.MaxValue:=CipherForm.Gauge1.MaxValue;.Gauge1.Progress:=0;

{---------------------Дешифрация-------------------}.ProcessMessages;.Gauge1.Progress:=DecipherForm.Gauge1.Progress+1;:=0;:=WL;not eof(f2) do(f2,j);(f2,incode[i]);j>0 theni=0 then:=cp+1;:=WL+1;

Dhamm; {корректировка блоков по кодам Хэмминга}

sim:='';:=der1(cdb,dm,umn(key1,key2));(f3);length(sim)>0 do(length(sim) mod 3)<>0begin:=copy(sim,1,length(sim) mod 3);(sim1,asc,cd);(sim,1,length(sim) mod 3);begin:=copy(sim,1,3);(sim1,asc,cd);(sim,1,3);;asc>0 then(f3,filesize(f3));:=chr(asc-1);(f3,ch);;; {while}; {if}:=i-1;:=j+1;.ProcessMessages;.Gauge1.Progress:=DecipherForm.Gauge1.Progress+1;; {while not eof(f2)}(f2);(f3);.Close;:=true;.Decipher1.Enabled:=false;.Cipher1.Enabled:=true;.Clear;.Lines.LoadFromFile('decipher');(f3);{then}begin('этот файл не является шифром');.Enabled:=false;(f2);;EFOpenError do ShowMessage('файл ключей не найден');EInOutError do ShowMessage('нельзя записывать в этот файл');;:=true; ;TMainForm.Help2Click(Sender: TObject);.Enabled:=true;.ShowModal;;TMainForm.Close2Click(Sender: TObject);CipFlag thenClick(Sender);:=false;;:='RSA';.Open1.Enabled:=true;.Clear;;TMainForm.FormActivate(Sender: TObject);:=false;:=false;

end;.

Приложение 2

Текст модуля выбора теста простоты

unit Choose;, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,, ExtCtrls;= class(TForm): TRadioGroup;: TButton;Button1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TChooseForm;MainProg, Wait;

{$R *.DFM}TChooseForm.Button1Click(Sender: TObject);:=ChooseForm.RadioGroup1.ItemIndex=0;.ShowModal;.GenKeys;.Close;.Close;;.

Приложение 3

Текст модуля взлома шифра RSA

unit AntiRSA;

interface, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,;= class(TForm): TLabel;: TEdit;: TButton;: TLabel;: TEdit;: TButton;: TLabel;: TEdit;: TButton;: TLabel;: TLabel;Button1Click(Sender: TObject);Button2Click(Sender: TObject);Edit1Change(Sender: TObject);Button3Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TAntiR;,e,n,m:string;,ss,sss:string;:integer;MainProg;

{$R *.DFM}TAntiR.Button1Click(Sender: TObject);

{процедура шифрации сообщения}:integer;:='16813'; {открытый ключ}:='47053'; {произведение p, q}:='19837'; {секретный ключ}:='46620'; {функция Эйлера}

if Edit1.Text=''begin('Где сообщение?');.SetFocus;if MainForm.Bol(Edit1.Text,n)=1

then begin('Сообщение должно быть меньше 47053');

Edit1.SetFocus;begin:=MainForm.Der1(Edit1.Text,e,n);:=StrToInt(s);.Deln(s);.Text:=IntToStr(code);.Refresh;;;TAntiR.Button2Click(Sender: TObject);

{процедура взлома шифра}:boolean;:integer;:=false;:=1;:=s;{зашифровываем шифр открытым ключом}:=MainForm.Der1(s,e,n);:=StrToInt(ss);:=IntToStr(code);

if Edit2.Text=ss {проверка зашифрованного результата i-той итерации на совпадение с шифром}

then begin:=StrToInt(s);.Text:=IntToStr(code);:=True;begin:='';:=ss;:=StrToInt(ss);.Text:=IntToStr(code);.Refresh;

end;:=j+1; {подсчет совершенных итераций}

Label5.Caption:=IntToStr(j);.Refresh;flag;;TAntiR.Edit1Change(Sender: TObject);.Text:='';.text:='';.Caption:='';;TAntiR.Button3Click(Sender: TObject);;;.