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

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

2015-08-07

279.48 KB

5 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


27

PAGE  70

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

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

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

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

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

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

Тема:  «Разработка и реализация математической модели

двухключевой криптосистемы»

                   

Зав. кафедрой:

профессор, д. т. н. ……… ………………………………………………  Лозгачев Г. И.

Рецензент:

директор испытательного центра

сертификации и аттестации

«Безопасные информационные

технологии», к. т. н. …………………………………………………………Тупота В. И.

Руководитель:

ст. преподаватель … ……………………………………………………  Воронков Б. Н.

Выполнила:

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

Воронеж

2001 

Содержание

Введение   ……………………………………………………………………...

3

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

5

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

6

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

6

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

7

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

8

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

9

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

9

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

9

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

10

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

12

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

              ного обратного   ……………………………………………………..

12

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

14

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

15

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

18

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

18

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

21

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

25

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

26

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

28

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

28

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

29

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

29

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

30

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

37

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

37

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

38

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

39

Заключение   …………………………………………………………………..

47

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

49

Приложение 1   ………………………………………………………………..

50

Приложение 2   ………………………………………………………………..

69

Приложение 3   ………………………………………………………………..

70

Введение

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

        С широким распространением письменности криптография стала формироваться как самостоятельная наука. Криптография – наука о методах преобразования информации в целях ее защиты от незаконных пользователей [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 = bq1 + r2 ,          0 < r2 < b ,

b = r2q2 + r3 ,         0 < r3 < r2 ,

                                            r2 = r3q3 + r4 ,        0 < r4 < r3 ,           (**)

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

                                      rn-2 = rn-1qn-1 + rn ,        0 < rn < rn-1 ,

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

(a, b) = (b, r2) = (r2, r3) = … = (rn-1, rn) = rn .

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

  •  Совокупность общих делителей чисел a и b совпадает с совокупностью делителей их общего наибольшего делителя.
  •  Этот общий наибольший делитель равен rn, т. е. последнему не равному нулю остатку алгоритма Евклида.

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

  1.  231
  2.  2                    525 = 231*2 + 63,
  3.  63                              231 = 63*3 + 42,
  4.  3                               63 = 42*1 + 21,
  5.  42                                         42 = 21*2.
  6.  1
  7.  21
  8.  2

0

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

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

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

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

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

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

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

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

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

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

        Действительно, пусть а – целое, большее единицы; обозначив буквой p1 его наименьший простой делитель, имеем a = p1a1. Если a1>1, то, обозначив буквой p2 его наименьший простой делитель, имеем a1 = p2a2. Если a2>1, то подобно этому находим a2 = p3a3 и т. д., пока не придем к какому-либо an, равному единице. Тогда an-1 = pn. Перемножая все найденные равенства и производя сокращение, получим следующее разложение а на простые сомножители:

a = p1p2pn .

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

p1p2pn = q1q2qs .

Правая часть этого равенства делится на q1. Следовательно, по крайней мере, один из сомножителей левой части должен делиться на q1. Пусть, например, p1 делится на q1 (порядок нумерации сомножителей не важен). Тогда p1 = q1 (p1 кроме 1 делится только на p1). Сокращая обе части равенств на p1 = q1, имеем p2p3…pn = q2q3…qs. Повторяя прежнее рассуждение применительно к этому равенству, получим p3pn = q3qs и т. д., пока, наконец, в одной части равенства, например в левой, не сократятся все сомножители. Но одновременно должны сократиться и все сомножители правой части, так как равенство 1 = qn+1qs при qn+1, …, qs, превосходящих 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому.

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

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

 a

2

3

4

5

6

7

8

9

10

11

12

(a)

1

2

2

4

2

6

4

6

4

10

4

        Пусть        a =    каноническое разложение числа а.

Тогда имеем                (а) = а (1 - ,

или также                     (а) = .

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

ПРИМЕРЫ.   (60) = 60

                       (81) = 81-27 = 54

                       (5) = 5-1 = 4

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

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

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

                                                  1 a2) =  1) 2) .

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

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 = mq1 + r,              0<= r <m,

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

                                                                      

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

                                b = mq1 + r ,            0 <=r <m ,

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

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

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

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

a1  b1 (mod m) ,  a2  b2 (mod m) , …,  ak  bk (mod m)    (1).

Тогда            a1 = b1 + mt1 , a2 = b2 + mt2 ,  …, ak = bk + mtk             (2),

             Откуда a1 + a2 + … + ak = b1 + b2 + … + bk + m (t1 + t2 + … + tk), или

              a1 + a2 + … + ak  b1 + b2 + … + bk (mod m).

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

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

a1 a2 …ak  b1 b2 …bk + mN, где N – целое.

Отсюда: a1 a2 …ak  b1 b2 …bk (mod m).

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

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

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

Действительно, из a  b (mod m),  a = a1d ,  b = b1d ,  (d, m) = 1 следует, что разность ab, равная (a1b1)d, делится на m, т. е. a1  b1 (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. Согласно предыдущему утверждению остаётся , следовательно, только показать, что любые два числа ax1 + b и ax2 + b, отвечающие несравнимым x1 и x2, будут сами несравнимы по модулю m.

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

                                                  x1  x2 (mod m),

что противоречит предположению о несравнимости чисел x1 и  x2.

        Числа одного и того же класса по модулю 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 = r1, r2, ..., rc ;               c = (m),

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

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

             ar1  1 (mod m),       ar2  2 (mod m),       ...,         arc  c (mod m),

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

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

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

                                                     ap-1  1 (mod p).                                (2)

Доказательство.   Эта теорема является следствием теоремы Эйлера при m = p. Теореме Ферма можно придать более удобную форму, умножая обе части сравнения (2) на а, получим сравнение             ap  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(n) = 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.

  1.  Если известна функция Эйлера (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) = 56-1 (mod 7) = 3.

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

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

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

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

= {q0, q1, q2, …, qk}.

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

a = mq0 +r1,   0 < r1 < m,

m = r1q1 +r2,   0 < r2 < r1,

r1 = r2q2 + r3,   0 < r3 < r2,

r2 = r3q3 + r4,   0 < r4 < r3,

…………………………

rk-2 = rk-1qk-1 + rk,       0 < rk < rk-1,

rk-1 = rkqk +0.

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

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

P-2 = 0,   P-1 = 1,   Pn = qnPn-1 + Pn-2,  для  n>=0,

Q-2 = 1,   Q-1 = 0,   Qn = qnQn-1 + Qn-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.

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)4 * 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 имеют вид

        +    0   1   2   3   4                                          x    1   2   3   4

        0    0   1   2   3   4                                          1    1   2   3   4

        1    1   2   3   4   0                                          2    2   4   1   3

        2    2   3   4   0   1                                          3    3   1   4   2

        3    3   4   0   1   2                                          4    4   3   2   1

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

gn = e.

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

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

gm = e .

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

gm = e     m  0 (mod n) .

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

  1.  Если g1, g2, …, gm – все элементы группы G, g – элемент группы G, то g*g1, g*g2, …, g*gm – также все элементы той же группы. Поэтому

g*g1*g*g2*…*g*gm ;

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

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

gm = gn * q + r = gr .

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

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

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

q * а = 0,        (2.7.1.1)

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

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

        Определение. Пусть 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, то по теореме Лагранжа

(mn) * 1 = 0      p | (mn).

(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 есть степень его характеристики.

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

h = a1 * h1 + a2 * h2 + … + an * hn,

где a1, a2, …, an - элементы поля Fp. Но число разных наборов < a1, a2, …, an > элементов поля Fp равно pn. Поэтому q = pn.

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

                                                               k          k          k

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

                                                                                                   k          k          k

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

Если b  0, то

                                                            pk               k

 =  k   .

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

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

0 (mod p).

Поэтому                                      * ap-n bn = 0,

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

(a + b)p = aP + bp.

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

                                  k                    k        k            k

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

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

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

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

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

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

 

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

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

aq-1 = 1   .

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

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

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

a= 1         (2.7.3.1)   

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

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

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

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

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

q – 1;

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

                                                  n

aq  – 1 = 1;             (2.7.3.2)

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

                                                                n

аq    = а .

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

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

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

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

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

а = {а}p ,    где  a Z,  0 а  р-1.

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

a  1 (mod p) .

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

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

am = an  m  n (mod ).

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

am-n = 1      | m – n.

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

1, a, a2, …, a          (2.7.3.4)               

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

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

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

x- 1.         (2.7.3.5)        

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

(ak)= (a)k = 1,

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

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

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

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

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

ord ak = ,

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

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

akm = 1.

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

,

а так как

,

то                                                       .

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

(ak)      =  (a)    = 1.

Поэтому

m |   ,

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

m = ord ak = .

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

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

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

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

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

Доказательство. Обозначим символом  число элементов порядка  поля Fq. По теореме 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.    Мультипликативная группа ненулевых элементов конечного поля Fq циклично.

Доказательство. В самом деле, порядок такой группы равен q - 1. А по теореме 2.7.3.8 число элементов порядка q - 1 в этой группе равно (q - 1). Таким образом, в мультипликативной группе ненулевых элементов поля Fq имеется по меньшей мере один элемент порядка 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]:

  1.  Если М – открытый текст сообщения, то Е и D должны быть такими, что D[E(M)] = M, т. е. дешифровка зашифрованного текста М дает М.
  2.  Как Е, так и D могут быть легко вычислены.
  3.  Знание Е не приводит к легкому способу вычисления D.
  4.  Для каждого сообщения М должно быть E[D(M)] = M. Это полезно для реализации подписей.

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

        Все известные на сегодняшний день криптосистемы с открытым ключом опираются на один из следующих типов необратимости преобразований [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. Важно, чтобы каждый блок Mi сообщения находился в области 0<=Mi<=n-1 поскольку в противном случае невозможно отличить его от любого большего целого числа, сравнимого с ним по модулю n. Практически модуль n выбирается большим, порядка 200 десятичных цифр, так что могут использоваться блоки размером до 10200.

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

                                  (ci)D  (Mi)ED = (Mi)[1+k*(n)]  Mi (mod n),

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

ПРИМЕР.   Как упоминалось выше, используя присвоения а=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. Теперь каждый блок сообщения Mi состоит из двузначного числа, и зашифрованное сообщение получается по формуле

                                                ci  (Mi)7 (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 = с и вычисляем  

                                                     ci+1  (ci)E (mod n),

пока не получим ci+1 = c. Тогда ci = 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]. Если не обеспечено достаточно надёжное управление ключевой информацией, то завладев ею, злоумышленник получает неограниченный доступ ко всей информации.

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

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

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

                                                                 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C  Me (mod n) .

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

M  Cd (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 = (pq)2 = x2 – 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 - простое число, то ap-1  1 (mod p) для всех a, 1<a<p.

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

b на принадлежность классу простых чисел согласно условию ab-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)! состоит примерно из 100102 цифр.

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

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

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

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

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

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

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

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

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

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

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

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

b = 2rs + 1,

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

as  1 (mod b),

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

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

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

        Для заданного 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 = t2S,

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

        Если либо x0 = 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].

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

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

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

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

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

                                                                       

                    .

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

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

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

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

     i = 0, 1, …, j,

,

.

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

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

Сej(mod n)=C.

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

ПРИМЕР.   p=983, q=563, e=49, M=123456.

C=M49(mod n)=1603, C497(mod n)=85978, C498(mod n)=123456, C499(mod n)=1603.

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

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

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

Модули

(*.pas)

Формы

(*.dfm)

Назначение

MainProg

MainForm

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

About

AboutBox

Информационное окно. Форма появляется при выборе пункта меню Help/About.

Cipher,

Decipher

CipherForm,

DecipherForm

Формы и модули, визуально отражающие количество зашифрованной (расшифрованной) информации. Форма появляется при выборе пунктов главного меню Work/Cipher или Work/Decipher.

Wait

WaitForm

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

Choose

ChooseForm

Выбор теста простоты. Форма появляется перед генерацией ключей при выборе пункта главного меню Work/Keys_Generation.

AntiRSA

AntiR

Модуль содержит процедуры, реализующие раскрытие шифра RSA дешифрованием итерациями. Форма появляется при выборе пункта главного меню AntiRSA.

Help

HelpForm

Помощь в работе с программой. В окне редактора формы содержатся необходимые инструкции для работы. Форма появляется при выборе пункта главного меню Help/Help.

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

        При выборе пункта 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’=SE mod N представляет собой строку, которая записывается в файл Cipher. Таким образом, файл Cipher состоит из строк, каждая из которых является зашифрованным символом исходного текста.

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

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

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

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

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

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

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

        В программе 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).

Рис. 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).

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

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

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

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

Рис. 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].

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

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

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

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

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

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

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

lg n

Число операций

Примечания

50

100

200

400

800

1.4* 1010

  1.  * 1015 

1.2 * 1023

2.7 * 1034

1.3 * 1051

Раскрываем на суперкомпьютерах

На пределе современных технологий

За пределами современных технологий

Требует существенных изменений в

технологии

Не раскрываем

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

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

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

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

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

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

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

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

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

  1.  Компьютерная алгебра. Символьные и алгебраические вычисления / Под ред.

   Б. Бухбергер, Дж. Коллинз, Р. Лоос , М.: Мир, 1986. - 557 с.

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

  1.  Баричев С. Криптография без секретов. – М.: bar@glasnet.ru, 1998. – 43 c.

  1.  Нечаев В. И. Элементы криптографии: Основы теории защиты информации:

Учебное пособие. – М.: Высшая школа, 1999. – 108 с.

  1.  Воронков Б. Н., Тупота В. И. Методическое пособие по разработке средств  

   защиты информации в вычислительный сетях. – Воронеж: Типография ВГУ,  

   2000. – 112 с.

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

   336 с.

  1.  Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. Защита информации в ком-

 пьютерных системах и сетях / Под ред. В. Ф. Шаньгина. – М.: Радио и связь,

   1999. – 328 с.

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

  1.  Введение в криптографию / Под общ. ред. Ященко В. В. – М.:МЦНМО,    

     “ЧеРо”, 1998. – 272 с.

    

Приложение 1.   Текст основной программы RSA

unit MainProg;

interface

uses

 Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

 StdCtrls, Menus;

const

  IC=76;    {76 бит в шифр-коде}

  HC=75;    {75 бит в коде Хэмминга}

  WL=152;   {152 бит в общем слове}

  SKD=64;   {64 бит в секретном ключе}

type

Dkey=record                       {тип-несекретные ключи}

     N:string;                    {N-произведение двух простых чисел}

     E:string;                    {E-взаимно простое с функцией Эйлера от N}

  end;

  Skey=record                     {тип-секретные ключи}

     P:string;                    {P-простое число}

     Q:string;                    {Q-простое число}

     D:string;                    {D-мультипликатив. обратное к Е по модулю

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

  end;

 TMainForm = class(TForm)

   MainMenu1: TMainMenu;

   File1: TMenuItem;

   Work1: TMenuItem;

   AntiRSA1: TMenuItem;

   Help1: TMenuItem;

   Close1: TMenuItem;

   Open1: TMenuItem;

   Save1: TMenuItem;

   Saveas1: TMenuItem;

   Close2: TMenuItem;

   FromFile1: TMenuItem;

   KeysGeneration1: TMenuItem;

   Cipher1: TMenuItem;

   Decipher1: TMenuItem;

   About1: TMenuItem;

   Help2: TMenuItem;

   Memo1: TMemo;

   OpenDialog1: TOpenDialog;

   SaveDialog1: TSaveDialog;

   procedure Open1Click(Sender: TObject);

   procedure Close1Click(Sender: TObject);

   procedure Save1Click(Sender: TObject);

   procedure Saveas1Click(Sender: TObject);

   procedure About1Click(Sender: TObject);

   procedure AntiRSA1Click(Sender: TObject);

   procedure KeysGeneration1Click(Sender: TObject);

   procedure FromFile1Click(Sender: TObject);

   function  Bol(a1,b1:string):integer;

   procedure Deln(a3:string);

   function Sum(a2,b2:string):string;

   function Mins(a5,b5:string):string;

   function Umn(a4,b4:string):string;

   function Divis(a6,b6:string):string;

   function Modulo(a7,b7:string):string;

   procedure Hamcode;

   procedure Dhamm;

   function Recod:string;

   function Der1(a11,b11,c11:string):string;

   procedure GenKeys;

   procedure Cipher1Click(Sender: TObject);

   procedure Decipher1Click(Sender: TObject);

   procedure Help2Click(Sender: TObject);

   procedure Close2Click(Sender: TObject);

   procedure FormActivate(Sender: TObject);

 private

   { Private declarations }

 public

   { Public declarations }

 end;

var

 MainForm: TMainForm;

 KeyFlag, Cipflag: boolean;

 b:array[0..IC]of string;                 {массив двоичных кодов}

 coderc:array[0..IC]of boolean;           {информационный код}

 hamming:array[0..HC]of boolean;          {код Хэмминга}

 prmx:array[0..IC,0..HC]of boolean;       {порождающая матрица кода Хэмминга}

 prmx1:array[0..HC,0..WL]of boolean;      {проверочная матрица кода Хэмминга}

 incode:array[0..WL]of boolean;           {входной код на приемном блоке}

 skbin:packed array[0..skd]of boolean;    {бинарный код секретного ключа}

 esbin:packed array[0..skd*2]of boolean;  {бинарный код несекретного ключа}

 security:Skey;            {запись-секретные ключи}

 dkeys:Dkey;               {запись-несекретные ключи}

 Sekret:File;              {файл секретных ключей}

 UnSekret:File;            {файл несекретных ключей}

 km,wer:longint;           {число ошибок в принятом слове}

 eyl:string;               {функция Эйлера}

 f1,f3:file of char;       {исходный файл, дешифрованный файл}

 f2:TextFile;              {шифрованный файл}

 id,jd:integer;            {счетчик}

 temp,cp:integer;          {переменная для ASCII-кодов}

 tc1:string;               {переменная для ASCII-кодов}

 ftest:boolean;            {флаг метода теста числа на простоту

                           1 - вероятностный, 0 - детерминированный}

 ch:char;                  {считываемый символ}                       

implementation

uses Decipher, Cipher, Choose, AntiRSA, Wait, About, Help;

function TMainForm.Bol(a1,b1:string):integer;{Сравнение абсолютных величин

                                             a1 и b1 <0-'=', 1-'>', 2-'<'>}

var

  f:integer;              {переменная сравнения}

  sd1,sd2:integer;        {сравниваемые цифры - тип <целое>}

  sr1,sr2:string[1];      {сравниваемые цифры - тип <строчное>}

  ks1,ks2:integer;        {длины сравниваемых чисел}

  cd:integer;             {переменная ошибки}

begin

  f:=0;

  ks1:=length(a1);                {запоминаем длину a1}

  ks2:=length(b1);                {запоминаем длину b1}

  while(ks1<>0) or (ks2<>0) do    {пока не пройдем самое большое число}

     begin

        sd1:=0;

        sd2:=0;

        if ks1>0 then begin

           sr1:=copy(a1,ks1,1);       {копируем цифру 1-го числа для преобр.}

           if sr1<>'-' then val(sr1,sd1,cd); {преобр. цифру 1-го числа в тип}

        end;                                                        {<целое>}

        if ks2>0 then begin

           sr2:=copy(b1,ks2,1);

           if sr2<>'-' then val (sr2,sd2,cd);{преобр. цифру 2-го числа в тип}

        end;                                                        {<целое>}

        if abs(sd1)>abs(sd2)

           then f:=1

           else if abs(sd1)<abs(sd2) then f:=2;

        if ks1>0 then ks1:=ks1-1;

        if ks2>0 then ks2:=ks2-1;

     end;

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

end;

procedure TMainForm.Deln(a3:string);         {удаляем нули спереди}

var

  m:boolean;          {флаг наличия минуса}

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

  cd:integer;         {переменная ошибки процедуры val}

  a31:string;         {переменная для работы с числом}

begin

  a31:='';                       {инициализируем a31}

  a31:=a3;

  if pos('-',a31)<>0             {если <-> в числе есть,}

     then m:=true                {то m-истина}

     else m:=false;              {иначе m-ложно}

  val(copy(a31,1,1),ac,cd); {копир. в перем. ac анализир. цифру и переприсв.}

                                                                {тип-integer}

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

     begin

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

        val(copy(a31,1,1),ac,cd);                               {тип-integer}

        if not((ac>=49)and(ac<=57))        {если ac-ноль, то}

           then delete(a31,1,1);           {из строки a31 удалить 1-й символ}

     end;

  if m then a31:='-'+a31;       {если в числе есть минус, то добавить его}

  a3:='';                                            {спереди в результат}

  a3:=a31;           {инициализируем a3 и возвращаем a3 без нулей спереди}

end;

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

var

  d:integer;              {переменная переполнения}

  s1,s2:integer;          {складываемые цифры чисел a2 и b2 тип-<целое>}

  s3:integer;             {сумма цифр s1 и s2 тип-<целое>}

  cd:integer;             {переменная ошибки процедуры val}

  ks1,ks2:integer;        {длины складываемых чисел a2 и b2}

  sk1,sk2:string[1];      {складываемые цифры чисел a2 и b2 тип-<строчное>}

  sk3:string[1];          {сумма цифр s1 и s2 тип-<строчное>}

  fl:boolean;             {флаг смены знака на противоположный}

  bb1,bb2,rez,bfr:string; {переменная для выполнения операции <сложение>}

begin

  ks1:=length(a2);         {загружаем в ks1 длину числа a2}

  ks2:=length(b2);         {загружаем в ks2 длину числа b2}

  rez:='';                 {инициализируем результирующую переменную}

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

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

     begin

        fl:=false;         {флаг смены знака-ложный}

        d:=0;              {обнуляем переменную переполнения}

       while not((ks1=0)and(ks2=0)) do {пока не пройдены все цифры склад.чисел}

           begin

              s1:=0;

              s2:=0;

              s3:=0;

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

              if ks1>0 then               {если цифры a2 не пройд., то}

                 if sk1<>'-' then         {если выбранная цифра не минус, то}

                    val(sk1,s1,cd);       {переводим ее в тип <целое>}

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

              if ks2>0 then               {если цифры a2 не пройд., то}

                 if sk2<>'-' then val(sk2,s2,cd); {переводим ее в тип <целое>}

              s2:=abs(s2)+d;  {прибавляем ко 2-му слаг. перемен. переполнения}

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

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

                 begin

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

                    d:=1;                     {переменная переполнения равна 1}

                 end

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

                                                     цифр 2-х чисел <10, то}

                         begin

                            s3:=abs(s1)+abs(s2);   {суммируем 2 выбр. цифры}

                            d:=0;                  {и перем. переполн. обнулим}

                         end;

              str(s3,sk3);    {результирующую цифру переведем в тип <строчное>}

              rez:=sk3+rez;            {и добавим ее спереди строки результата}

              if ks1>0 then            {если число a2 не пройдено до конца, то}

                 ks1:=ks1-1;                   {перейдем к более старшей цифре}

              if ks2>0 then            {если число b2 не пройдено до конца, то}

                 ks2:=ks2-1;                   {перейдем к более старшей цифре}

           end;     {цикл while}

        if d<>0 then begin               {если переменная переполнения <>0, то}

                        rez:= '1'+rez;  {добавим спереди строки результата '1'}

                        d:=0;           {обнулим переменную переполнения}

                     end;

     end  {if then}

     else begin             {иначе, если a2 и b2 неравнозначны}

             if Bol(b2,a2)=1             {сравним выч. числа}

                then begin fl:=true;     {знак меняем на противоположный от a2}

                           bb1:=b2;      {переприсваиваем}

                           bb2:=a2;      {переприсваиваем}

                     end

                else begin fl:=false;

                           bb1:=a2;

                           bb2:=b2;

                     end;

             ks1:=length(bb1);

             ks2:=length(bb2);

             d:=0;

             while not((ks1=0)and(ks2=0)) do

                begin

                   s1:=0;

                   s2:=0;

                   s3:=0;

                   sk1:=copy(bb1,ks1,1);

                   if ks1>0

                      then if sk1<>'-' then val(sk1,s1,cd);

                   sk2:=copy(bb2,ks2,1);

                   if ks2>0

                      then if sk2<>'-' then val(sk2,s2,cd);

                   s2:=abs(s2)+d;

                   if (abs(s1)-abs(s2))<0

                      then begin s3:=abs(s1)+10-abs(s2);

                                 d:=1;

                           end

                      else begin s3:=abs(s1)-abs(s2);

                                 d:=0;

                           end;

                   str(s3,sk3);

                   rez:=sk3+rez;

                   if ks1>0 then ks1:=ks1-1;

                   if ks2>0 then ks2:=ks2-1;

                end;   {while}

          end;   {if else}

  if (pos('-',a2)=0)and(fl) then rez:='-'+rez;

  Deln(rez);

  Sum:=rez;

end;

function TMainForm.Mins(a5,b5:string):string;    {разность a5-b5}

var

  m:boolean;   {наличие минуса}

begin

  if pos('-',b5)<>0 then begin

                            delete(b5,pos('-',b5),1);

                            m:=true;

                         end

                    else begin

                            b5:='-'+b5;

                            m:=false;

                         end;

  mins:=sum(a5,b5);

  if m then b5:='-'+b5

       else delete(b5,pos('-',b5),1);

end;

function TMainForm.Umn(a4,b4:string):string;   {целочисленное умножение}

var

  s1,s2,s3,i,j:integer;

  cd,ks1,ks2:integer;

  sk1,sk2,sk3:string[1];

  fl:boolean;

  rez,bfr:string;

  d:integer;

begin

  ks1:=length(a4);

  ks2:=length(b4);

  bfr:='0';

  while not(ks2=0) do

     begin

        d:=0;

        s2:=0;

        s3:=0;

        rez:='';

        ks1:=length(a4);

        sk2:=copy(b4,ks2,1);

        if ks2>0 then

                    if sk2<>'-' then val(sk2,s2,cd);

        s2:=abs(s2);

        while not(ks1=0) do

           begin

              s1:=0;

              sk1:=copy(a4,ks1,1);

              if ks1>0 then

                          if sk1<>'-' then val(sk1,s1,cd);

              if (abs(s1)*abs(s2)+d)>=10 then

                 begin

                    s3:=(abs(s1)*abs(s2)+d)-((abs(s1)*abs(s2)+d)div 10)*10;

                    d:=(abs(s1)*abs(s2)+d)div 10;

                 end

                 else

                    if (abs(s1)*abs(s2)+d)<10 then

                       begin

                          s3:=abs(s1)*abs(s2)+d;

                          d:=0;

                       end;

              str(s3,sk3);

              rez:=sk3+rez;

              if ks1>0 then ks1:=ks1-1;

           end;  {while}

        if d<>0 then

           begin

              str(d,sk3);

              rez:=sk3+rez;

              d:=0;

           end;

        for j:=1 to length(b4)-ks2 do

           rez:=rez+'0';

        bfr:=sum(bfr,rez);

        if ks2>0 then ks2:=ks2-1;

     end;   {while}

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

     ((pos('-',a4)=0)and(pos('-',b4)<>0))

     then bfr:='-'+bfr;

  deln(bfr);

  umn:=bfr;

end;

function TMainForm.Divis(a6,b6:string):string; {целочисленное деление a6 div b6}

var

  bfr,bfr1,bfr2,rez:string;

  kp1:string;

  kp2:string[1];

  kp,ig,cd:integer;

begin

  if bol(b6,'0')<>0 then

     begin

        bfr:='0';

        rez:='0';

        for kp:=1 to length(a6) do

           begin

              bfr:=bfr+copy(a6,kp,1);

              kp1:='0';

              while bol(bfr,b6)<>2 do

                 begin

                    bfr:=mins(bfr,b6);

                    kp1:=sum(kp1,'1');

                 end;

              val(kp1,ig,cd);

              str(ig,kp2);

              if (bol(rez,'0')<>0)and(bol(bfr,b6)=2)

                 and(bol(kp1,'0')=0)

                 then rez:=rez+'0'

                 else if bol(kp1,'0')<>0

                         then rez:=rez+kp2;

           end;    {for}

        deln(rez);

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

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

           then rez:='-'+rez;

        divis:=rez;

     end;   {if then}

end;

function TMainForm.Modulo(a7,b7:string):string;      {взятие от a7 остатка

                                                             по модулю b7}

var

  modulo1:string;

begin

  modulo1:='';

  modulo1:=mins(a7,umn(divis(a7,b7),b7));

  deln(modulo1);

  modulo:=modulo1;

end;

procedure TMainForm.Hamcode;          {вычисление кода Хэмминга}

var

  ih,jh:integer;

  c:integer;

begin

  for ih:=hc downto 0 do

     begin

        hamming[ih]:=false;

        for jh:=ic downto 0 do

           hamming[ih]:=hamming[ih] xor(prmx[jh,ih]and coderc[jh]);

     end;

end;

procedure TMainForm.Dhamm;        {восстановление ошибок по коду Хэмминга}

var

  i1,j1,c,kn,a,b,d:integer;

  ve:array[0..wl] of boolean;    {вектор ошибок}

  se:array[0..hc] of boolean;    {синдром}

  gh:boolean;

begin

  for i1:=hc downto 0 do

     begin

        se[i1]:=false;

        for j1:=wl downto 0 do

           se[i1]:=se[i1] xor(incode[j1]and prmx1[i1,j1]);

     end;

  for i1:=wl downto 0 do

     begin

        c:=0;

        for j1:=hc downto 0 do

           if se[j1]=prmx1[j1,i1] then c:=c+1;

        if c=hc+1

           then ve[i1]:=true

           else ve[i1]:=false;

     end;

  kn:=0;

  for i1:=wl downto 0 do

     if ve[i1] then wer:=wer+1;

  km:=km+1;

  for i1:=wl downto 0 do

     if ve[i1] then

        if wer=1 then

           incode[i1]:=incode[i1]xor ve[i1];

end;

function TMainForm.Recod:string;   {перевод двоичного кода в десятичное число}

var

  l1:integer;

  recod1:string;

begin

  recod1:='0';

  for l1:=wl downto hc+1 do

     if incode[l1] then

        recod1:=sum(recod1,b[l1-ic]);

  recod:=recod1;

end;

function TMainForm.Der1(a11,b11,c11:string):string; {вычисление a11 в степени

                                                          b11 по модулю c11}

var

  bfs,buf,buf1:string;

  b17,b13,b12,b14,kt:string;

  s12:string;

  sd,bd:integer;

begin

  bfs:=b11;

  bd:=76;

  while bol(bfs,b[bd])=2 do

     bd:=bd-1;

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

  buf:=a11;

  bd:=bd-1;

  while bd>=0 do

     begin

        if bol(bfs,b[bd])=2

           then buf:=modulo(umn(buf,buf),c11)

           else begin

                   buf:=modulo(umn(buf,buf),c11);

                   buf:=modulo(umn(a11,buf),c11);

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

                end;

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

        bd:=bd-1;

     end;

  der1:=buf;

end;

procedure TMainForm.GenKeys;   {генерация ключей}

var

  ci,cj:integer;          {счетчики циклов}

  bc:longint;             {переменная для генерации большого случайного числа}

  randt1:longint;         {число генераций}

  p,ksy:integer;          {счетчики циклов}

  prov:string;            {основание теста Ферма}

  flag:boolean;           {вспомогательные переменные}

  P1,Q1,E1,D1:string;           {ключевые числа}

  qs,qm,an,bn,buf:string;       {вспомогательные переменные}

  am:array[0..1]of string;      {вспомогат. переменные для алгоритма Евклида}

begin

  WaitForm.Timer1.Enabled:=true;

  try

  AssignFile(Sekret,'SekrKey');

  AssignFile(UnSekret,'UnSKey');

  skbin[0]:=true;

  {генерация P1}

  bc:=0;

  for ci:=1 to skd do

     begin

        randt1:=random(5000);

        WaitForm.SetFocus;

        for cj:=0 to randt1 do

           begin

              Application.ProcessMessages;

              bc:=random(65535);

           end;

        if (bc mod 2)=0 then bc:=0

                        else bc:=1;

        if bc=1 then skbin[ci]:=true

                else skbin[ci]:=false;

     end;    {for ci}

  P1:='0';

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

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

  if P1[length(P1)]='5'

     then P1:=sum(P1,'2');

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

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

  prov:=mins(prov,'1');

  repeat

     flag:=true;

     while bol(modulo(prov,P1),'0')<>0 do

        begin

           if P1[length(P1)]='3'

              then P1:=sum(P1,'4')

              else P1:=sum(P1,'2');

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

           prov:=mins(prov,'1');

        end;    {while}

     if not ftest then

        begin

           qs:='3';

           while (bol(modulo(P1,qs),'0')<>0)and

                 (bol(umn(qs,qs),P1)=2) do

           if qs[length(qs)]='3'

                 then qs:=sum(qs,'4')

                 else qs:=sum(qs,'2');

           if (bol(umn(qs,qs),P1)=0)or

              (bol(modulo(P1,qs),'0')=0)

              then begin

                      if P1[length(P1)]='3'

                         then P1:=sum(P1,'4')

                         else P1:=sum(P1,'2');

                      flag:=false;

                   end;

        end;    {if}

  until flag;

  {генерация Q1}

  bc:=0;

  for ci:=1 to skd do

     begin

        randt1:=random(5000);

        WaitForm.SetFocus;

        for cj:=0 to randt1 do

           begin

              Application.ProcessMessages;

              bc:=random(65535);

           end;

        if (bc mod 2)=0 then bc:=0

                        else bc:=1;

        if bc=1 then skbin[ci]:=true

                else skbin[ci]:=false;

     end;    {for ci}

  Q1:='0';

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

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

  if Q1[length(Q1)]='5'

     then Q1:=sum(Q1,'2');

  prov:='';

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

  prov:=mins(prov,'1');

  repeat

     flag:=true;

     while bol(modulo(prov,Q1),'0')<>0 do

        begin

           if P1[length(Q1)]='3'

              then Q1:=sum(Q1,'4')

              else Q1:=sum(Q1,'2');

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

           prov:=mins(prov,'1');

        end;    {while}

     if not ftest then

        begin

           qs:='3';

           while (bol(modulo(Q1,qs),'0')<>0)and

                 (bol(umn(qs,qs),Q1)=2) do

           if qs[length(qs)]='3'

                 then qs:=sum(qs,'4')

                 else qs:=sum(qs,'2');

           if (bol(umn(qs,qs),Q1)=0)or

              (bol(modulo(Q1,qs),'0')=0)

              then begin

                      if Q1[length(Q1)]='3'

                         then Q1:=sum(Q1,'4')

                         else Q1:=sum(Q1,'2');

                      flag:=false;

                   end;

        end;    {if}

  until flag;

  {генерация E1}

  skbin[0]:=true;

  bc:=0;

  for ci:=1 to skd do

     begin

        randt1:=random(5000);

        for cj:=0 to randt1 do

           bc:=random(65535);

        if (bc mod 2)=0 then bc:=0

                        else bc:=1;

        if bc=1 then skbin[ci]:=true

                else skbin[ci]:=false;

     end;

  E1:='0';

  for cj:=0 to skd do

     if skbin[cj]

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

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

  qs:='0';

  am[0]:='0';

  am[1]:='1';

  repeat

     am[0]:=E1;

     am[1]:=eyl;

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

        begin

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

           buf:=am[0];

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

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

           am[0]:=am[1];

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

        end;

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

        then begin

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

                am[0]:=E1;

             end;

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

  {генерация D1}

  an:='1';

  bn:='1';

  qm:=eyl;

  qs:='2';

  while bol(qm,'1')<>0 do

     begin

        if bol(modulo(qm,qs),'0')=0 then

           begin

              while bol(modulo(qm,qs),'0')=0 do

                 qm:=divis(qm,qs);

              an:=umn(mins(qs,'1'),an);

              bn:=umn(qs,bn);

           end;

        if bol(modulo(qs[length(qs)],'2'),'0')=0

           then qs:=sum(qs,'1')

           else qs:=sum(qs,'2');

        if bol(umn(qs,qs),qm)<>2

           then qs:=qm;

     end;     {while}

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

  security.P:=P1;

  security.Q:=Q1;

  security.D:=D1;

  dkeys.N:=umn(P1,Q1);

  dkeys.E:=E1;

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

  Reset(UnSekret);

  seek(UnSekret,Filesize(UnSekret));

  BlockWrite(UnSekret,dkeys,SizeOf(dkeys));

  CloseFile(UnSekret);

  Reset(Sekret);

  seek(Sekret,Filesize(Sekret));

  BlockWrite(Sekret,security,SizeOf(security));

  CloseFile(Sekret);

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

  KeyFlag:=true;

  if KeyFlag then

     MainForm.Cipher1.Enabled:=true;

     MainForm.Decipher1.Enabled:=true;

     MainForm.Open1.Enabled:=true;

  except

     on EFOpenError do ShowMessage('файл ключей не найден');

     on EInOutError do ShowMessage('нельзя записывать в этот файл');

  end;

  WaitForm.Timer1.Enabled:=false;

end;

{$R *.DFM}

procedure TMainForm.Open1Click(Sender: TObject);

begin

  if OpenDialog1.Execute then

     begin

        Caption:='RSA--'+OpenDialog1.FileName;

        MainForm.Open1.Enabled:=false;

        MainForm.Close1.Enabled:=true;

        Memo1.Clear;

        Memo1.Lines.LoadFromFile(OpenDialog1.FileName);

     end;

  if KeyFlag then

     begin

        CipherForm.Enabled:=true;

        DecipherForm.Enabled:=true;

     end;

  Open1.Enabled:=false;

end;

procedure TMainForm.Close1Click(Sender: TObject);

begin

  Close;

end;

procedure TMainForm.Save1Click(Sender: TObject);

begin

  if OpenDialog1.FileName<>''

     then Memo1.Lines.SaveToFile(SaveDialog1.FileName)

     else Saveas1Click(Sender);

  if KeyFlag and (not CipFlag) then CipherForm.Enabled:=true;

  Open1.Enabled:=false;

  Close1.Enabled:=true;

end;

procedure TMainForm.Saveas1Click(Sender: TObject);

begin

  if Memo1.Lines.Count<>0

     then with SaveDialog1 do

        if Execute then begin

           Memo1.Lines.SaveToFile(FileName);

           Caption:='RSA--'+ExtractFileName(FileName);

        end;

  Save1.Enabled:=true;

  if KeyFlag and (not CipFlag) then CipherForm.Enabled:=true;

  Open1.Enabled:=false;

  Close1.Enabled:=true;

end;

procedure TMainForm.About1Click(Sender: TObject);

var about:TAboutBox;

begin

  about:=TAboutBox.Create(Self);

  try about.ShowModal;

  finally about.Free;

  end;

end;

procedure TMainForm.AntiRSA1Click(Sender: TObject);

begin

  AntiR.ShowModal;

end;

procedure TMainForm.KeysGeneration1Click(Sender: TObject);

var

  i:integer;

begin          {заполнение массива двоичных кодов}

  b[0]:='1';

  for i:=1 to IC do

     b[i]:=umn(b[i-1],'2');

  ChooseForm.ShowModal;

end;

procedure TMainForm.FromFile1Click(Sender: TObject);

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

  try

     AssignFile(Sekret,'SekrKey');

     Reset(Sekret);

     AssignFile(UnSekret,'dkeys');

     Reset(UnSekret);

     while not eof(Sekret) do

        BlockRead(Sekret,security,SizeOf(sekret));

     while not eof(UnSekret) do

        BlockRead(UnSekret,dkeys,SizeOf(dkeys));

     CloseFile(Sekret);

     CloseFile(UnSekret);

     CipherForm.Enabled:=true;

     DecipherForm.Enabled:=true;

     KeyFlag:=true;

  except

     on EFOpenError do ShowMessage('файл ключей не найден');

  end;

end;

procedure TMainForm.Cipher1Click(Sender: TObject);

var

  i,j:integer;

  kodblock:string;    {шифрблок}

  key:string;         {несекретный ключ N}

  e:string;           {несекретный ключ Е}

begin

  AssignFile(UnSekret,'dkeys');

  Reset(UnSekret);

  while not eof(UnSekret) do

     BlockRead(UnSekret,dkeys,SizeOf(dkeys));

  key:=dkeys.N;

  e:=dkeys.E;

  CloseFile(UnSekret);

  try

     AssignFile(f1,OpenDialog1.FileName);

     Rewrite(f1);

     AssignFile(f2,'cipher');

     Rewrite(f2);

     CipherForm.Show;

     Enabled:=false;

     HelpForm.Enabled:=false;

     for i:=0 to Memo1.Lines.Count-1 do

        begin

           for j:=1 to Length(Memo1.Lines[i]) do

              write(f1,Memo1.Lines[i][j]);

           ch:=chr(13);

           write(f1,ch);

        end;

     CloseFile(f1);

     Reset(f1);

     CipherForm.Gauge1.MaxValue:=FileSize(f1)+1;

     CipherForm.Gauge1.Progress:=0;

     {------------------Шифрация----------------}

     CipherForm.Gauge1.Progress:=CipherForm.Gauge1.Progress+1;

     while not eof(f1) do

        begin

           read(f1,ch);

           temp:=ord(ch);

           str(temp,tc1);

           kodblock:=der1(tc1,e,key);

           write(f2,kodblock);

           Hamcode;                {добавление кодов Хэмминга}

           for i:=HC downto 0 do

              write(f2,Hamming[i]);

           CipherForm.Gauge1.Progress:=CipherForm.Gauge1.Progress+1;

           Application.ProcessMessages;

        end;

     CloseFile(f1);

     CloseFile(f2);

     Reset(f2);

     tc1:='0';

     Memo1.Clear;

     Memo1.Lines.LoadFromFile('cipher');

     CloseFile(f2);

     CipherForm.Close;

     Enabled:=true;

     CipherForm.Enabled:=false;

     DecipherForm.Enabled:=true;

  except

     on EFOpenError do ShowMessage('файл ключей не найден');

     on EInOutError do ShowMessage ('нельзя записывать в этот файл');

  end;

  cipflag:=true;

end;

procedure TMainForm.Decipher1Click(Sender: TObject);

var

  set1:set of '0'..'9';

  i,j:integer;

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

  key,key1,key2,dm,kodblock:string;    {ключи}

  asc,cd:integer;                      {переменные для ASCII-кодов}

  fileflag:boolean;

begin

  AssignFile(Sekret,'SekrKey');

  Reset(Sekret);

  while not eof(Sekret) do

     BlockRead(Sekret,security,SizeOf(sekret));

  key1:=security.P;

  key2:=security.Q;

  dm:=security.D;

  eyl:=umn(mins(key1,'1'),mins(key2,'1'));

  CloseFile(Sekret);

  fileflag:=true;

  set1:=['0','1','2','3','4','5','6','7','8','9'];

  try

     AssignFile(f2,'cipher');

     Rewrite(f2);

     for i:=0 to Memo1.Lines.Count-1 do

        begin

           writeln(f2,Memo1.Lines[i]);

        end;

     CloseFile(f2);

     Reset(f2);

     if Memo1.Lines[0][1] in set1         {проверка шифра}

        then fileflag:=true

        else fileflag:=false;

     if fileflag then

        begin

           AssignFile(f3,'decipher');

           Rewrite(f3);

           DecipherForm.Show;

           Enabled:=False;

           HelpForm.Enabled:=false;

           DecipherForm.Gauge1.MaxValue:=CipherForm.Gauge1.MaxValue;

           DecipherForm.Gauge1.Progress:=0;

           {---------------------Дешифрация-------------------}

           Application.ProcessMessages;

           DecipherForm.Gauge1.Progress:=DecipherForm.Gauge1.Progress+1;

           j:=0;

           i:=WL;

           while not eof(f2) do

              begin

                 seek(f2,j);

                 BlockRead(f2,incode[i]);

                 if j>0 then

                    if i=0 then

                       begin

                          cp:=cp+1;

                          i:=WL+1;

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

                          sim:='';

                          sim:=der1(cdb,dm,umn(key1,key2));

                          Reset(f3);

                          while length(sim)>0 do

                             begin

                                if (length(sim) mod 3)<>0

                                   then begin

                                           sim1:=copy(sim,1,length(sim) mod 3);

                                           val(sim1,asc,cd);

                                           delete(sim,1,length(sim) mod 3);

                                        end

                                   else begin

                                           sim1:=copy(sim,1,3);

                                           val(sim1,asc,cd);

                                           delete(sim,1,3);

                                        end;

                                if asc>0 then

                                   begin

                                      seek(f3,filesize(f3));

                                      ch:=chr(asc-1);

                                      write(f3,ch);

                                   end;

                             end;    {while}

                       end;     {if}

                 i:=i-1;

                 j:=j+1;

                 Application.ProcessMessages;

                 DecipherForm.Gauge1.Progress:=DecipherForm.Gauge1.Progress+1;

              end;     {while not eof(f2)}

           CloseFile(f2);

           CloseFile(f3);

           DecipherForm.Close;

           Enabled:=true;

           MainForm.Decipher1.Enabled:=false;

           MainForm.Cipher1.Enabled:=true;

           Memo1.Clear;

           Memo1.Lines.LoadFromFile('decipher');

           Erase(f3);

        end     {then}

     else begin

             ShowMessage('этот файл не является шифром');

             DecipherForm.Enabled:=false;

             CloseFile(f2);

          end;

  except

     on EFOpenError do ShowMessage('файл ключей не найден');

     on EInOutError do ShowMessage('нельзя записывать в этот файл');

  end;

  cipflag:=true;   

end;

procedure TMainForm.Help2Click(Sender: TObject);

begin

  HelpForm.Enabled:=true;

  HelpForm.ShowModal;

end;

procedure TMainForm.Close2Click(Sender: TObject);

begin

  if CipFlag then

     begin

        Saveas1Click(Sender);

        CipFlag:=false;

     end;

  Caption:='RSA';

  MainForm.Open1.Enabled:=true;

  Memo1.Clear;

end;

procedure TMainForm.FormActivate(Sender: TObject);

begin

  KeyFlag:=false;

  CipFlag:=false;

end;

end.

Приложение 2.   Текст модуля выбора теста простоты

unit Choose;

interface

uses

 Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

 StdCtrls, ExtCtrls;

type

 TChooseForm = class(TForm)

   RadioGroup1: TRadioGroup;

   Button1: TButton;

   procedure Button1Click(Sender: TObject);

 private

   { Private declarations }

 public

   { Public declarations }

 end;

var

 ChooseForm: TChooseForm;

implementation

uses MainProg, Wait;

{$R *.DFM}

procedure TChooseForm.Button1Click(Sender: TObject);

begin

  ftest:=ChooseForm.RadioGroup1.ItemIndex=0;

  WaitForm.ShowModal;

  MainForm.GenKeys;

  WaitForm.Close;

  ChooseForm.Close;

end;

end.

Приложение 3.   Текст модуля взлома шифра RSA

unit AntiRSA;

interface

uses

 Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

 StdCtrls;

type

 TAntiR = class(TForm)

   Label1: TLabel;

   Edit1: TEdit;

   Button1: TButton;

   Label2: TLabel;

   Edit2: TEdit;

   Button2: TButton;

   Label3: TLabel;

   Edit3: TEdit;

   Button3: TButton;

   Label4: TLabel;

   Label5: TLabel;

   procedure Button1Click(Sender: TObject);

   procedure Button2Click(Sender: TObject);

   procedure Edit1Change(Sender: TObject);

   procedure Button3Click(Sender: TObject);

 private

   { Private declarations }

 public

   { Public declarations }

 end;

var

 AntiR: TAntiR;

 d,e,n,m:string;

 s,ss,sss:string;

 j:integer;

implementation

uses MainProg;

{$R *.DFM}

procedure TAntiR.Button1Click(Sender: TObject);

{процедура шифрации сообщения}

var

  code:integer;

begin

  e:='16813';   {открытый ключ}

  n:='47053';   {произведение p, q}

  d:='19837';   {секретный ключ}

  m:='46620';   {функция Эйлера}

  if Edit1.Text=''

     then begin

             ShowMessage('Где сообщение?');

             Edit1.SetFocus;

          end

     else if MainForm.Bol(Edit1.Text,n)=1

             then begin

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

                     Edit1.SetFocus;

                  end

             else begin

                     s:=MainForm.Der1(Edit1.Text,e,n);

                     code:=StrToInt(s);

                     MainForm.Deln(s);

                     Edit2.Text:=IntToStr(code);

                     Edit2.Refresh;

                  end;

end;

procedure TAntiR.Button2Click(Sender: TObject);

{процедура взлома шифра}

var

  flag:boolean;

  code:integer;

begin

  flag:=false;

  j:=1;

  sss:=s;

  repeat        {зашифровываем шифр открытым ключом}

     ss:=MainForm.Der1(s,e,n);

     code:=StrToInt(ss);

     ss:=IntToStr(code);

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

                                                          совпадение с шифром}

        then begin

                code:=StrToInt(s);

                Edit3.Text:=IntToStr(code);

                flag:=True;

             end

        else begin

                s:='';

                s:=ss;

                code:=StrToInt(ss);

                Edit3.Text:=IntToStr(code);

                Edit3.Refresh;

             end;

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

     Label5.Caption:=IntToStr(j);

     Label5.Refresh;

  until flag;

end;

procedure TAntiR.Edit1Change(Sender: TObject);

begin

  Edit2.Text:='';

  Edit3.text:='';

  Label5.Caption:='';

end;

procedure TAntiR.Button3Click(Sender: TObject);

begin

  Close;

end;

end.

 



 

Другие похожие работы, которые могут вас заинтересовать.
21263. Разработка математической модели и автоматизация технологии построения карты изолиний (на примере «Лесного» месторождения, объект зеленая свита) 159.98 KB
  Точечная аппроксимация поверхности степенными полиномами. Разложение функции поверхности в ряд Фурье по ортонормированной системе полиномов Лежандра. линии соединяющие на земной поверхности точки одинаковой высоты - основной способ-изображения рельефа на топографических картах. Такие системы изолиний отображают поверхности реальные например рельеф местности или абстрактные например поверхность годового слоя осадков.
10172. Основные понятия и уравнения интегральной математической модели пожара в помещении 53.24 KB
  Основные понятия и уравнения интегральной математической модели пожара в помещении. Основные понятия математической модели пожара в помещении. Допущения интегрального метода термодинамического анализа пожара.
11720. РАЗРАБОТКА И РЕАЛИЗАЦИЯ КОРПОРАТИВНОГО ИЗДАНИЯ СПОРТИВНОЙ ОРГАНИЗАЦИИ 4.51 MB
  Корпоративные издания на протяжении многих лет широко практиковались на отечественных предприятиях самого разного типа: крупные советские предприятия имели свои производственные газеты, многие учреждения выпускали стенгазеты. В то же время в 90-е годы прошлого столетия в связи с осложнившейся экономической, финансовой ситуацией многие крупные заводы прекратили издание своих газет и журналов, а вновь создаваемые фирмы и кооперативы не рассматривали их в качестве необходимой сферы приложения денежных средств.
751. Разработка, принятие и реализация управленческих решений по совершенствованию структуры системы управления организацией 38.92 KB
  Организация контроля реализации решения. Принятие решения в процессе производства. Практическое использование технологии принятия решения. В обобщенном виде эта деятельность связана с решениями.
19494. Разработка и реализация программного модуля для трехмерной и двухмерной визуализации геометрических сборок для ПК BRAND 3.22 MB
  Изначально комплекс предназначался для моделирования методом Монте-Карло исключительно нейтронно-физических экспериментов но удачно выбранная структура разбиения на модули позволила очень быстро распространить BRND на задачи расчета защиты от излучений реакторные задачи задачи радиационной медицины и другие охватив моделирование совместного переноса нейтронов фотонов и заряженных частиц. Для программного комплекса был разработан собственный язык построения сложных геометрических объектов с помощью которого с высокой степенью детализации...
1303. Разработка модели антикризисного управления 272.29 KB
  Разработка модели антикризисного управления При разработке предлагаемой модели антикризисного управления торговой организацией использован экономический механизм антикризисного управления который может быть наглядно представлен в виде...
1545. Разработка модели женская блуза 8.11 MB
  Выбор модели Блуза женская легкая одежда из тонкой ткани в виде короткой приталенной рубашки. Свойства основных материалов Свойства ткани. Ткань по волокнистому составу однородная. Вид ткацкого переплетения
20084. Разработка модели сервисной организации 29.23 KB
  Рост потребления услуг в странах с высокоразвитой промышленностью является одним из наиболее значимых явлений экономической жизни второй половины ХХ века. Успешная деятельность предприятий и отраслей сферы услуг невозможна без прогнозирования спроса: функционирование этих экономических объектов самым непосредственным образом ориентировано на удовлетворение спроса физических и юридических лиц на оказываемые услуги подтверждая известный тезис о том что спрос рождает предложение. Все это указывает на актуальность...
13245. Разработка жизнеспособной модели сельских поселений XXI века 31.97 MB
  Выполнить анализ научных исследований в сфере изучения сельских поселений России и зарубежных стран; разработать социокультурную типологию сельских поселений, исходя из исторических аспектов их развития; подготовить предложения по междисциплинарным исследованиям сельских поселений с разработанным вопросником, учитывающим региональные...
15230. Выбор модели и разработка конструкции изделия на конкретную фигуру 108.88 KB
  Именно поэтому то что мы носим и то как мы носим одежду аксессуары обувь для других людей представляет собой своеобразную стенограмму по которой можно прочитать истинное положение вещей. При проектировании изделий должны быть максимально использованы последние достижения науки техники и прикладного искусства выбраны оптимальные конструктивные и композиционные решения соответствующие созданию изделия имеющего высокие эстетические и утилитарные свойства отвечающие потребностям и вкусам различных этносоциальных групп потребителей и...
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.