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
|
= 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 для
сравнения
* x = 9 (mod 23).
Получаем y = 5-1
14 (mod 23), затем находим
x = 14 * 9 (mod
23) = 126 (mod 23) = 11,
x =
11.
2.7 Конечные поля [5]
Определение. Поле F=
< F, +, x, 0, 1 > называют конечным, если F- множество его элементов - конечно.
Обозначение. F, - символ для обозначения конечного поля из q элементов, F* - мультипликативная
группа не равных нулю элементов поля F. Если а - элемент некоторого кольца, а n - неотрицательное целое число, то n*а
- n-кратное элемента a.
Примеры:
1. Если. p - простое число, то Z/(p) - кольцо классов вычетов по модулю p - конечное поле из p элементов:
{0}P, {1}P, {2}P, ..., {p -1}P. (*)
Если a, b Z, то {a}p = {b}p a b (mod p).
Для краткости при указанном p элементы ряда (*) обозначаем знаками
0, 1, 2, …, p-1.
. Пусть p = 5, тогда таблицы сложения и умножения
элементов поля Fs
Определение. Число элементов конечной группы называют ее порядком.
Порядком элемента g G=<=G, *, e>
называют наименьшее натуральное число n с условием
gn = e.
Теорема Лагранжа.
(1) Если m - порядок группы G=<G,*,e>, g -
элемент группы G, то
gm = e .
(2) Если 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 ;
отсюда легко выводится первое утверждение.
(2) Если m = n * q + r, то
gm = gn * q + r = gr .
Это и доказывает второе утверждение.
2.7.1 Характеристика поля
Теорема 2.7.1.1. Если Fq = < F, +,
х, 0, 1 > - конечное поле из q
элементов,1 - единица поля, то для любого элемента а из F
* а = 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, то по теореме
Лагранжа
(m - n) * 1 = 0 p | (m - n).
(2) По свойству
кратных имеем
(m * 1) + (n + 1) = (m + n) * 1.
Отсюда и из (1) следует (2). Аналогично доказывается утверждение (3).
Теорема 2.7.1.5. Всякое конечное простое поле F = < F, +, х, 0, 1 >
характеристики p изоморфно кольцу классов вычетов кольца Z целых чисел по простому модулю р.
= 0 * 1, 1 = 1 * 1, 2 * 1, ..., (p - 1) * 1 (2.7.1.5)
В силу теоремы 2.7.1.4 сумма, разность, произведение любых элементов ряда
(2.7.1.5) и обратный элемент к любому ненулевому элементу этого множества
принадлежат тому же множеству. Поэтому множество элементов (2.7.1.5) относительно
операций "+" и "х" образует подполе поля F, а так как F
простое поле (т. е. поле, не содержащее других подполей, кроме самого поля F), то
это подполе совпадает с полем F.
Определим отображение , множества (2.7.1.5) на множество классов вычетов кольца
целых чисел Z по простому модулю p
условием:
: m * 1 {m}p.
Легко проверить, что - взаимно однозначное отображение, которое сумму и
произведение элементов поля F переводит в сумму и произведение образов этого
отображения.
Теорема 2.7.1.6. Всякое конечное поле F характеристики p содержит простое
подполе из p элементов и является его конечным расширением.
Доказательство. По теореме 2.7.1.2 характеристика простого подполя поля F
равна р. Но конечное поле заведомо является конечным расширением любого своего
подполя.
Теорема 2.7.1.7. Число элементов конечного поля Н = Fq характеристики p
есть степень его характеристики.
Доказательство. Пусть Fp - простое подполе поля H. По теореме 2.7.1.6 поле Н содержит элементы h1, h2, …, hn (базис), такие, что любой элемент 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 Н. Тогда
(a + b) p = a p + b p ,
(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 тривиален.
Так как (a - b)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 = xq - x. Если 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, то
q-1 = 1 .
Доказательство. Равенство следует из теоремы Лагранжа, так как q-1 - число элементов
мультипликативной группы поля Fq.
Определение. Пусть Fq = < Fq
, +, x, 0, 1 > -
конечное поле; a Fq, a 0.
Наименьшее натуральное число с условием
= 1 (2.7.3.1)
называют порядком элемента а поля Fp .
Обозначение. ord а - порядок
элемента а.
Теорема 2.7.3.2. Если а - элемент мультипликативной группы поля Fq, то:
ord а q - l и, более того, ord a | q - 1,
другими словами, порядок ненулевого элемента поля Fq - делитель числа q - 1;
б) в тех же предположениях, если n - натуральное число, то
q - 1 = 1; (2.7.3.2)
в) если n
- натуральное число и а
- любой элемент поля Fq, то
а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. Тогда элементы
, 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.
Тогда
km = 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.
.8 Шифрование потока данных [6]
Все практически применяемые криптографические методы связаны с разбиением
сообщения на большое число частей фиксированного размера, каждая из которых
шифруется отдельно [7]. Это существенно упрощает задачу шифрования, т. к.
сообщения обычно имеют различную длину. Можно выделить следующие основные
методы шифрования: побитовое шифрование потока данных (рис. 1), побитовое
шифрование потока данных с обратной связью по зашифрованному (рис. 2) и по
исходному сообщению (рис. 3), поблочное шифрование потока данных с прямой (рис.
4) и обратной связью (рис. 5).
При пассивных вторжениях, пользователи, не имеющие полномочий, просто
наблюдают за сообщениями, передаваемым по линиям связи, не изменяя самих
сообщений. При активных вторжениях, регулярные сообщения могут быть удалены,
модифицированы, отсрочены, перенаправлены, защищены повторно, или сформированы
ложные сообщения. В результате активных вторжений восстановление исходного
текста проблематично. Поэтому криптографическая система RSA предусматривает поблочное
(нелинейное) шифрование потока данных и шифрование блоками (рис. 6).
Один из основных принципов хорошего криптографического алгоритма состоит
в том, чтобы малое изменение исходного текста или ключа приводило к
значительному изменению шифрованного текста.
Рис. 1. Схема побитового шифрования потока данных
Рис. 2 Схема побитового шифрования потока данных с обратной связью по
зашифрованному сообщению
Рис. 3 Схема побитового шифрования потока данных с обратной связью по
исходному сообщению
Рис. 4 Схема поблочного шифрования потока данных
Рис. 5 Схема поблочного шифрования потока данных с обратной связью
Рис. 6 Схема шифрования блоками
Рис. 7 Схема шифрования блоками с обратной связью
При блочном шифровании исходный текст сначала разбивается на равные по
длине блоки бит. К блокам применяется зависящая от ключа функция шифрования для
преобразования их в блоки шифровки такой же длины [7].
Главное свойство блочного шифрования состоит в том, что каждый бит блока
текста шифровки является функцией почти всех бит соответствующего блока
открытого текста, и никакие два блока открытого текста не могут быть
представлены одним и тем же блоком текста шифровки. Основное преимущество
простого блочного шифрования состоит в том, что в хорошо сконструированной
системе небольшие изменения открытого текста или ключа вызывают большие и
непредсказуемые изменения в тексте шифра.
Достоинство блочных шифров состоит в том, что желающим их расколоть
криптоаналитикам при достаточной длине блока ничего не остается, как вести
атаку прямым подбором ключа, т. к. надежда отгадать кусок исходного текста
большой длины весьма химерична.
Недостаток этого шифра связан с размножением ошибок внутри блока.
Результатом изменения одного бита в принятом блоке шифровки будет неправильное
расшифровывание всего блока.
3. Системы с открытым ключом
Любая передаваемая нами информация может быть представлена в виде
последовательности двоичных цифр; это - сообщение [1]. Любая последовательность
из n цифр, которая может быть передана,
называется кодовым словом.
Ключ - информация, необходимая для беспрепятственного шифрования и
дешифрования текстов.
Как бы ни были сложны и надёжны криптографические системы - их слабое место при практической
реализации - проблема
распределения ключей. Для того, чтобы был возможен обмен конфиденциальной
информацией между двумя субъектами ИС, ключ должен быть сгенерирован одним из
них, а затем каким-то образом, опять же в конфиденциальном порядке, передан другому.
То есть в общем случае для передачи ключа опять же требуется использование
какой - то криптосистемы [4].
Для решения этой проблемы на основе результатов, полученных классической
и современной алгеброй, были предложены системы с открытым ключом (СОК).
Понятие криптосистем открытого ключа было впервые введено Диффи и Хелманом в
1976 г.
В системах с открытым ключом используются два ключа - открытый и
закрытый, которые математически связаны друг с другом. Информация шифруется с
помощью открытого ключа, который доступен всем желающим, а расшифровывается с
помощью закрытого ключа, известного только получателю сообщения.
Для того, чтобы гарантировать надежную защиту информации, к системам с
открытым ключом (СОК) предъявляются два важных и очевидных требования [6]:
1 преобразование исходного текста
должно быть необратимым и исключать его восстановление на основе открытого
ключа
2 определение закрытого ключа на основе
открытого также должно быть невозможным на современном технологическом уровне.
При этом желательна точная нижняя оценка сложности (количества операций)
раскрытия шифра.
Согласно этим схемам, каждый пользователь помещает в открытый каталог
процедуру шифрования Е (чтобы другие подписчики использовали ее для кодирования
сообщений, адресованных этому пользователю), но держит в секрете детали
соответствующей процедуры D
дешифровки.
Очевидно, что эти методы основаны на наблюдении, что процедура шифрования
и соответствующий ключ не должны быть такими же, как процедура дешифровки и
соответствующий ей ключ. Чтобы такая система имела право на существование,
должен найтись простой метод, позволяющий получать процедуры Е и D друг от друга. Желательно, чтобы
процедуры Е и D
обладали следующими свойствами [1]:
1. Если М - открытый текст сообщения, то
Е и D должны быть такими, что D[E(M)] = M, т. е. дешифровка зашифрованного
текста М дает М.
2. Как Е, так и D могут быть легко вычислены.
3. Знание Е не приводит к легкому
способу вычисления D.
4. Для каждого сообщения М должно быть E[D(M)] = M. Это полезно для реализации
подписей.
Например, если пользователь В хочет послать частное сообщение М
пользователю А, то пользователь В находит процедуру ЕА в открытом
каталоге пользователя А (как в телефонном справочнике) и передает С = ЕА(М)
в открытую, зная, что только А может декодировать это, пользуясь секретной
процедурой DA.
Все известные на сегодняшний день криптосистемы с открытым ключом
опираются на один из следующих типов необратимости преобразований [6]:
·
разложение
больших чисел на простые множители;
·
вычисление
логарифма в конечном поле;
·
вычисление корней
алгебраических уравнений в конечном поле.
Алгоритмы шифрования с открытым ключом получили широкое распространение в
современных информационных системах. Так, алгоритм RSA стал мировым стандартом для открытых систем.
.1 Принцип работы RSA -
криптосистемы [1]
Покажем, как работает RSA -
криптосистема. Получатель вычисляет следующие величины:
p, q : выбраны два больших простых числа,
которые держатся в секрете;
n :
произведение p, q, которое помещается в открытый каталог;
Е : случайное целое число, также размещаемое в открытом каталоге.
Используется для кодирования сообщений, посылаемых получателю, который должен
убедиться, что Е взаимно просто с числом j(n) = (p-1)(q-1); D : целое число, используемое получателем для декодирования,
также держится в секрете.
Подведём итоги: получатель знает p, q, D, образующие секретный ключ,
отправитель знает сообщение М, каждый знает открытый ключ n и Е.
Сообщение М, передаваемое получателю, прежде всего преобразуется в
цифровую форму некоторой стандартной несекретной процедурой. В частности, можно
использовать присвоения а=00, в=01, с=02, d=03, e=04,
..., z=25, .=26, ,=27, ?=28, ;=29, т.е.
каждая буква заменяется двузначным числом. Например, сообщение «computer algebra» должно быть переписано в виде «0214121520 1904170011
0604011700». Конечно, если сообщение длинное, то оно разбивается на блоки.
Длина каждого блока такова, что его численное значение не превосходит n. Важно, чтобы каждый блок Mi сообщения находился в области 0<=Mi<=n-1 поскольку в противном случае невозможно отличить его от
любого большего целого числа, сравнимого с ним по модулю n. Практически модуль n выбирается большим, порядка 200
десятичных цифр, так что могут использоваться блоки размером до 10200.
Отправитель берёт каждый блок сообщения Mi , смотрит на открытые ключи Е и n и передаёт ci (mod n), где 0<=Mi<=n-1. Получатель получает ci и вычисляет (ci)D(mod n). Заметим,
однако, что по определению мы имеем EDº1 [mod j(n)], откуда следует, что ED=1+k*j(n) для некоторого целого k. Таким образом,
(ci)D º (Mi)ED
= (Mi)[1+k*j(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
и j(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], которым перехватчик может пытаться решить проблему,
состоит в нахождении j(n), поскольку в
этом случае D может быть легко вычислено из
соотношения
ED º 1 [mod j(n)]
Однако следующие соображения показывают, что этот подход не проще чем
попытки разложить n. Если известно j(n), то p и q могут быть найдены следующим
образом. Из соотношений
j(n) = (p-1)(q-1) = pq - (p+q) +1 = n - (p+q) +1
видно, что по j(n) легко находится p + q. Более того, соотношения
(p-q)*2 = (p+q)*2 - 4pq = (p+q)*2 - 4n
показывают, что, зная n и p+q, легко получить p-q. Тогда p и q
даются формулами:
p = [ (p+q) + (p-q)] ,= [ (p+q) - (p-q) ] .
Таким образом, любая попытка найти j(n) эквивалентна решению сложной проблемы разложения n на множители.
.2 Управление ключами
Кроме выбора подходящей для конкретной ИС криптографической системы,
важная проблема -
управление ключами. Как бы ни была сложна и надёжна сама криптосистема, она основана
на использовании ключей [4]. Если для обеспечения конфиденциального обмена
информацией между двумя пользователями процесс обмена ключами тривиален, то в
ИС, где количество пользователей составляет десятки и сотни, управление ключами
- серьёзная проблема.
Под ключевой информацией понимается совокупность всех действующих в ИС
ключей [4]. Если не обеспечено достаточно надёжное управление ключевой
информацией, то завладев ею, злоумышленник получает неограниченный доступ ко
всей информации.
Управление ключами -
информационный процесс, включающий в себя три элемента: генерацию ключей,
накопление ключей, распределение ключей.
3.2.1 Генерация ключей
Не стоит использовать неслучайные ключи с целью лёгкости их запоминания.
В серьёзных ИС используются специальные аппаратные и программные методы
генерации случайных ключей [4]. Степень случайности их генерации должна быть
достаточно высокой. Идеальным генератором являются устройства на основе
натуральных» случайных процессов. Например, появились серийные образцы генерации
ключей на основе белого радиошума.
3.2.2 Накопление ключей
Под накоплением ключей понимается организация их хранения, учёта и
удаления [4]. Секретные ключи никогда не должны записываться в явном виде на
носителе, который может быть считан или скопирован.
В достаточно сложной ИС один пользователь может работать с большим
объёмом ключевой информации, и иногда даже возникает необходимость организации
мини-баз данных по ключевой информации. Такие базы данных отвечают за принятие,
хранение, учёт и удаление используемых ключей.
Очень важным условием безопасности информации является периодическое
обновление ключевой информации в ИС [4]. В особо ответственных ИС обновление
ключевой информации желательно делать ежедневно.
3.2.3 Распределение ключей
Это самый ответственный процесс в управлении ключами. К нему
предъявляются два требования: оперативность и точность распределения и
скрытность распределяемых ключей.
Распределение ключей между пользователями реализуется двумя разными
подходами [4]:
1 путём создания одного или нескольких
центров распределения ключей.
Недостаток такого подхода состоит в том, что в центре распределения
известно, кому и какие ключи назначены и это позволяет читать все сообщения,
циркулирующие в ИС. Возможные злоупотребления существенно влияют на защиту.
2 прямой обмен ключами между
пользователями информационной системы.
В этом случае проблема состоит в том, чтобы надёжно удостоверить
подлинность субъектов.
В обоих случаях должна быть гарантирована подлинность сеанса связи.
В качестве обобщения сказанного о распределении ключей следует сказать
следующее. Задача управления ключами сводится к поиску такого протокола
распределения ключей, который обеспечивал бы [4]:
3 возможность отказа от центра
распределения ключей
4 взаимное подтверждение подлинности
участников сеанса
5 подтверждение достоверности сеанса
механизмом запроса - ответа, использование для этого программных или аппаратных
средств использование при обмене ключами минимального числа сообщений.
4.
Криптографический
анализ асимметричных систем шифрования
Криптографические системы с открытыми ключами шифрования позволяют
пользователям осуществлять безопасную передачу данных по незащищенному каналу
без какой-либо предварительной подготовки. Такие криптосистемы должны быть асимметричными
в том смысле, что отправитель и получатель имеют различные ключи, причем ни
один из них не может быть выведен из другого с помощью вычислений. В этих
системах фазы шифрования и дешифрования отделены и защита сообщения
обеспечивается без засекречивания ключа шифрования, поскольку он не
используется при дешифровании.
С помощью открытого ключа шифрования пользователь i шифрует сообщение М и посылает
пользователю j по незащищенному каналу передачи
данных. Только пользователь j
может выполнить дешифрование, чтобы восстановить M, поскольку только он знает секретный ключ дешифрования.
Среди асимметричных (открытых) криптосистем наиболее широкое
распространение получила криптографическая система RSA. В этой системе получатель сообщения выбирает два
больших простых числа p и q
так, чтобы произведение n = pq находилось за пределами
вычислительных возможностей. Исходное сообщение М может иметь произвольную
длину в диапазоне 1<M<n. Шифрованный текст C, соответствующий сообщению М, может
быть получен в виде
C 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 = (p - q)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 делит (U - V)(U + V), но
не делит ни (U - V), ни (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} -
множество небольших простых чисел, которые могут делить выражение вида x2 - b
(т.е. 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.
5.
Работа с программой RSA
5.1 Описание программы
Программа, разработанная в среде Delphi 4, представляет собой проект с названием RSA.dpr и содержит 8 программных модулей (*.pas) и 8 соответствующих им форм (*.dfm). Опишем их более подробно:
Таблица 3
Модули (*.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=S’E mod N. Полученное S
представляет собой код ASCII.
По нему несложно получить символ исходного текста.
Процедура дешифрования итерациями состоит в следующем: зашифрованный
текст M последовательно шифруется с помощью
открытого ключа, пока снова не будет получено M. Если это произошло на i+1 итерации, то результат, полученный на i итерации, и будет исходным
сообщением [7], т. е. M1 = M, …, Mi+1 = (Mi)Е mod N, где Е - открытый ключ, N - модуль (произведение двух простых чисел). Если Mi+1 = M, то Mi - исходный текст.
.2 Требования к техническим средствам и шифруемым файлам
Для нормальной работы программы необходим компьютер Pentium с объемом диска 1Гб , 16 Мб ОП и
тактовой частотой 100 МГц. Требования к операционной системе: Windows-98 или Windows NT.
Программа вместе с необходимыми ей файлами ключей устанавливается в
каталог New_RSA в любое место диска. Возможна работа программы как из
среды Delphi 4(5), так и при отсутствии среды
программирования при наличии файла RSA.exe.
Программа RSA зашифровывает
файлы с расширением *.txt
или без расширения, содержащие текстовую информацию. Любой символ файла будет
интерпретирован как текст по таблице ASCII-кодов. Поэтому файлы, использующие другую кодировку, будут обработаны
неправильно.
5.3 Вычислительный эксперимент
В программе RSA реализована
возможность шифрации как существующих на диске, так и созданных во время работы
с программой файлов. Запуск программы можно осуществить двумя способами:
запустить файл RSA.exe из командной строки или, находясь в
среде программирования Delphi,
открыть файл проекта RSA.dpr и выполнить команду Run (F9). На экране появляется главная форма (рис. 1).
Рис. 1. Главная форма программы RSA
Пункт меню File содержит
подпункты Open, Save, Save_as, Close для работы с файлами. Выберем пункт File\Open. На экране появляется диалоговое окно выбора файла
(рис. 2).
Рис. 2. Диалоговое окно выбора файла
Выбираем из списка предложенных файлов Test2 и нажимаем Open. В окне главной формы появляется текст файла (рис. 3).
Рис. 3. Главная форма, содержащая текст выбранного файла
Заметим, что пункты главного меню Work/Cipher,
Work/Decipher недоступны для выбора. Теперь можно
выбрать Work/FromFile. Опция Work/Cipher
стала доступна: выберем ее. Шифрация началась и на экране появилось окно,
отображающее количество зашифрованных данных (рис. 4).
Рис. 4. Окно-индикатор процесса шифрации
При завершении шифрации текст в окне редактора главной формы приобрел
следующий вид (рис. 5).
Рис. 5. Зашифрованный текст в окне главной формы
Заметим, что опция Work/Decipher стала доступной для выбора (возможна
также запись зашифрованного файла на диск с помощью пункта меню File/Save_as).
Выберем ее, чтобы расшифровать сообщение. На экране появится окно, отображающее
количество дешифрованных данных (рис. 6).
Расшифровать можно также любой файл, ранее зашифрованный этой программой.
Для этого следует открыть его (File/Open) и выбрать пункт меню Work/Decipher. В результате дешифрации в окне
появляется дешифрованное сообщение (рис. 7).
Рис. 7. Результат дешифрации в окне главной формы
Следует заметить, что если открытый файл не является шифром (т. е. не
состоит полностью из цифр), то появится сообщение об ошибке (рис. 8).
Рис. 8. Сообщение об ошибке при попытке некорректной дешифрации
Рассмотрим другие возможности программы.
При выборе пункта меню Work/Keys_Generation появляется окно выбора теста
простоты (рис. 9).
Рис. 9. Выбор способа проверки числа на простоту
Выбираем вероятностный способ. Начинается генерация ключей. Все время
генерации на экране находится предупреждение “процесс генерации может занять
несколько минут”. При завершении генерации предупреждение исчезает. Опция Work/Cipher стала доступной для выбора.
Пункт меню AntiRSA
демонстрирует возможность раскрытия шифра системы RSA. В данном случае используются следующие ключи:
N =
47053
M =
46620
D =
16813 - открытый ключ
E =
19837 - секретный ключ [7]
При выборе пункта меню AntiRSA
на экране появляется окно (рис. 11).
Рис. 11. Форма для взлома шифра RSA
Если выбрать кнопку Взломать или Зашифровать, предварительно не вводя
сообщения, на экране появится окно (рис. 12).
Рис. 12. Сообщение об ошибке при отсутствии исходного текста для шифрации
При вводе исходного сообщения (число), следует учитывать, что оно должно
быть меньше N, иначе появится следующее сообщение
(рис. 13).
Рис. 13. Сообщение об ошибке при величине исходного текста, превышающей
длину ключа
Введем сообщение 3456 и выберем кнопку Зашифровать. Зашифрованное
сообщение появится в окне (рис. 14).
Рис. 14. Результат шифрации
Теперь можно выбрать кнопку Взломать и наблюдать за результатами взлома.
Число итераций, необходимых для взлома, и результаты итераций отображаются на
экране (рис. 15).
Для получения краткой информации о программе можно выбрать пункт меню Help/About. На экране появится форма (рис. 16).
Для получения справки о работе с программой следует выбрать пункт меню Help/Help. На экране появится форма (рис. 17).
Рис. 15. Результат взлома шифра RSA
Рис. 16. Форма, содержащая краткую информацию о программе
Рис. 17. Форма, содержащая справочную информацию о возможностях программы
и особенностях работы с ней
Здесь можно найти справочную информацию о программе.
Исходный текст занимает места больше, чем это необходимо - обладает
большой избыточностью, как всякий текст на родном языке. При хорошей шифрации
избыточность уменьшается. Сжатие текста архиваторами также устраняет избыточность.
Если текст шифровки сжимается одним из архиваторов больше, чем на 10 %, то
шифровальная система не состоятельна. Алгоритмам архивирования удается сжимать
даже случайные последовательности символов, хотя сжатие в этом случае не
превышает единиц процентов [7].
Вычислительный эксперимент показал следующие соотношения:
·
При использовании
архиватора ARJ исходный текст сжимается на 48,6 %;
зашифрованный файл сжимается на 1 %.
·
При использовании
архиватора RAR исходный текст сжимается на 51,09 %;
зашифрованный файл сжимается на 1,04 %.
·
При использовании
архиватора ZIP исходный текст сжимается на 51,31 %;
зашифрованный файл сжимается на 0,93 %.
Заключение
Таким образом, в данной работе были рассмотрены математические основы,
включающие в себя теоремы Эйлера, Ферма, сравнимость простых чисел по модулю,
вычисление обратной мультипликативной функции.
В данной дипломной работе рассмотрена криптосистема с открытым ключом RSA и произведена оценка криптостойкости
этой системы в виде числа операций, необходимых для вычисления секретного ключа
при наличии открытого ключа, а также в виде времени, необходимого для
вычисления этих операций при заданных технических характеристиках компьютера.
Также произведена оценка числа операций, необходимых для шифрации и
дешифрации исходного сообщения с учетом длины исходного текста, а также указано
время, необходимое для шифрации и дешифрации информации, с учетом технических
характеристик компьютера и длины исходного текста.
В зависимости от степени секретности информации и с учетом
криптостойкости дана рекомендация на длину ключа.
Разработана программа, реализующая схему шифрования RSA, с возможностью шифрации и
дешифрации файлов, использующих кодировку ASCII. Программа разработана в среде программирования Delphi 4 на языке Object Pascal.
Проведен вычислительный эксперимент, оценивающий возможности программы. В
программе реализована возможность раскрытия шифра RSA при наличии зашифрованного сообщения и открытого
ключа (дешифрование итерациями). При длине ключа, реализованной в данной
дипломной работе ( бит), возможно использование программы в личных целях,
например, при использовании электронной почты.
Главным достоинством криптосистем с открытым ключом является их
потенциально высокая безопасность: нет необходимости ни передавать, ни сообщать
кому-либо значение секретных ключей, ни убеждаться в их подлинности [6].
Алгоритм криптосистемы с открытым ключом можно использовать в трёх
направлениях.
1 Как самостоятельные средства защиты
передаваемых и хранимых данных
2 Как средства для распределения
ключей. Алгоритмы СОК более трудоёмки, чем традиционные криптосистемы. Поэтому
часто на практике рационально с помощью СОК распределять ключи, объём которых
как информации незначителен. А потом с помощью обычных алгоритмов осуществлять обмен
большими информационными потоками.
3 Средства аутентификации пользователей
(электронная подпись), так как с широким распространением электронных форм
документов (в том числе и конфиденциальных) и средств их обработки особо
актуальной стала проблема установления подлинности и авторства безбумажной
документации.
Однако алгоритмы, лежащие в основе криптосистем с открытым ключом, имеют
следующие недостатки:
·
генерация новых
секретных и открытых ключей основана на генерации новых больших простых чисел,
а проверка простоты чисел занимает много машинного времени;
·
процедуры
шифрования и дешифрования, связанные с возведением в степень многозначного
числа, достаточно громоздки.
Для практической реализации алгоритмов RSA полезно знать оценки трудоёмкости разложения простых
чисел различной длины, сделанные Шроппелем [2].
Таблица 4
lg n
|
Число операций
|
Примечания
|
50
|
1.4* 1010
|
Раскрываем на
суперкомпьютерах
|
100
|
2,3* 1015
|
На пределе современных
технологий
|
200
|
1.2 * 1023
|
За пределами современных
технологий
|
400
|
2.7 * 1034
|
Требует существенных
изменений в технологии
|
800
|
1.3 * 1051
|
Не раскрываем
|
Сами авторы RSA рекомендуют
использовать следующие размеры модуля n:
1 768 бит - для частных лиц
2 1024 бит - для коммерческой
информации
3 2048 бит - для особо секретной
информации
Данные оценки сделаны с учётом развития вычислительной техники вплоть до
2004 года.
В настоящее время алгоритм RSA
активно реализуется как в виде самостоятельных криптографических продуктов, так
и в качестве встроенных средств в популярных приложениях (в браузерах Интернет
от Microsoft и Netscape) .
В любом случае выбранный комплекс криптографических методов должен
сочетать как удобство, гибкость и оперативность использования, так и надёжную
защиту от злоумышленников циркулирующей в ИС информации.
мультипликативный криптосистема шифрование
Список использованных источников
1
А.Г. Акритас
Основы компьютерной алгебры с приложениями: пер. с венгерского. - М.: Мир,
1994. - 456 с.
2
Компьютерная
алгебра. Символьные и алгебраические вычисления / Под ред. Б. Бухбергер, Дж.
Коллинз, Р. Лоос , М.: Мир, 1986. - 557 с.
3
Виноградов И. М.
Основы теории чисел - М.: Наука, 1981. - 176 с.
4
Баричев С.
Криптография без секретов., 1998. - 43 c.
5
Нечаев В.И.
Элементы криптографии: Основы теории защиты информации: Учебное пособие. - М.:
Высшая школа, 1999. - 108 с.
6
Воронков Б.Н.,
Тупота В.И. Методическое пособие по разработке средств защиты информации в
вычислительный сетях. - Воронеж: Типография ВГУ, 2000. - 112 с.
7
Жельников В.
Криптография от папируса до компьютера. - М.:ABF, 1996. - 336 с.
8
Романец Ю.В.,
Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях /
Под ред. В.Ф. Шаньгина. - М.: Радио и связь, 1999. - 328 с.
9
Кузьминский М.
Повседневные средства безопасной работы// Открытые системы, 2000, №12. - 12 -
19 с.
10Введение в криптографию / Под общ. ред. Ященко В.В. -
М.:МЦНМО, “ЧеРо”, 1998. - 272 с.
Приложение 1
Текст основной программы RSA
unit MainProg;
interface, Messages, SysUtils, Classes, Graphics, Controls,
Forms, Dialogs,, Menus;=76; {76 бит в шифр-коде}
HC=75; {75 бит в коде Хэмминга}=152; {152 бит в общем слове}=64; {64 бит
в секретном ключе}=record {тип-несекретные ключи}:string; {N-произведение двух
простых чисел}:string; {E-взаимно простое с функцией Эйлера от N};=record
{тип-секретные ключи}:string; {P-простое число}:string; {Q-простое
число}:string; {D-мультипликатив. обратное к Е по модулю
ф.Эйлера от N};
TMainForm = class(TForm): TMainMenu;: TMenuItem;: TMenuItem;:
TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;:
TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;:
TMenuItem;
Memo1: TMemo;: TOpenDialog;: TSaveDialog;
procedure Open1Click(Sender: TObject);Close1Click(Sender:
TObject);Save1Click(Sender: TObject);Saveas1Click(Sender:
TObject);About1Click(Sender: TObject);AntiRSA1Click(Sender:
TObject);KeysGeneration1Click(Sender: TObject);FromFile1Click(Sender:
TObject);Bol(a1,b1:string):integer;Deln(a3:string);Sum(a2,b2:string):string;Mins(a5,b5:string):string;Umn(a4,b4:string):string;Divis(a6,b6:string):string;Modulo(a7,b7:string):string;Hamcode;Dhamm;Recod:string;Der1(a11,b11,c11:string):string;GenKeys;Cipher1Click(Sender:
TObject);Decipher1Click(Sender: TObject);Help2Click(Sender:
TObject);Close2Click(Sender: TObject);FormActivate(Sender: TObject);
{ Private declarations }
{ Public declarations };: TMainForm;, Cipflag:
boolean;:array[0..IC]of string; {массив
двоичных кодов}:array[0..IC]of boolean; {информационный код}:array[0..HC]of boolean;
{код Хэмминга}:array[0..IC,0..HC]of boolean; {порождающая матрица
кода Хэмминга}:array[0..HC,0..WL]of boolean; {проверочная матрица
кода Хэмминга}:array[0..WL]of boolean; {входной код на приемном блоке}:packed array[0..skd]of boolean; {бинарный код секретного ключа}:packed array[0..skd*2]of boolean; {бинарный код несекретного ключа}
security:Skey; {запись-секретные ключи}:Dkey; {запись-несекретные
ключи}:File; {файл секретных ключей}:File; {файл несекретных
ключей},wer:longint; {число ошибок в принятом слове}:string; {функция
Эйлера},f3:file of char; {исходный файл, дешифрованный файл}:TextFile;
{шифрованный файл},jd:integer; {счетчик},cp:integer; {переменная для
ASCII-кодов}:string; {переменная для ASCII-кодов}:boolean; {флаг метода теста
числа на простоту
- вероятностный, 0 - детерминированный}:char; {считываемый символ}
implementationDecipher, Cipher, Choose, AntiRSA, Wait, About,
Help;TMainForm.Bol(a1,b1:string):integer;{Сравнение абсолютных величини b1 <0-'=', 1-'>', 2-'<'>}:integer; {переменная сравнения},sd2:integer; {сравниваемые цифры - тип <целое>}
sr1,sr2:string[1]; {сравниваемые цифры - тип
<строчное>},ks2:integer; {длины сравниваемых чисел}:integer; {переменная
ошибки}:=0;:=length(a1); {запоминаем длину a1}:=length(b1); {запоминаем длину
b1}(ks1<>0) or (ks2<>0) do {пока не пройдем самое большое число}
begin:=0;:=0;ks1>0 then begin
sr1:=copy(a1,ks1,1); {копируем цифру 1-го числа для
преобр.}sr1<>'-' then val(sr1,sd1,cd); {преобр. цифру 1-го числа в тип}
end; {<целое>}ks2>0
then begin:=copy(b1,ks2,1);sr2<>'-' then val (sr2,sd2,cd);{преобр. цифру 2-го числа в тип}; {<целое>}abs(sd1)>abs(sd2)f:=1if
abs(sd1)<abs(sd2) then f:=2;ks1>0 then ks1:=ks1-1;ks2>0 then
ks2:=ks2-1;
end;:=f; {значению ф-ции присваиваем значение результир. переменной f}
end;TMainForm.Deln(a3:string); {удаляем нули спереди}:boolean; {флаг наличия минуса}
kn,ac:integer; {kn-кол-во нулей спереди, ac-анализируемая цифра
числа}:integer; {переменная ошибки процедуры val}:string; {переменная для
работы с числом}
begin:=''; {инициализируем a31}:=a3; pos('-',a31)<>0 {если <-> в числе есть,}
then m:=true {то m-истина}m:=false; {иначе m-ложно}(copy(a31,1,1),ac,cd); {копир. в перем. ac анализир. цифру и переприсв.}
{тип-integer}(length(a31)>0)
do {пока длина строки числа
a31 не пустая}
begin
{копир. в перем. ac анализир. цифру и переприсв.}
val(copy(a31,1,1),ac,cd); {тип-integer}not((ac>=49)and(ac<=57)) {если ac-ноль, то} delete(a31,1,1);
{из строки a31 удалить 1-й символ}
end;m
then a31:='-'+a31; {если в числе есть минус, то добавить его}:=''; {спереди в
результат}:=a31; {инициализируем a3 и возвращаем a3 без нулей спереди}
end;TMainForm.Sum(a2,b2:string):string; {суммирование a2+b2}
var:integer; {переменная
переполнения},s2:integer; {складываемые цифры чисел a2 и b2
тип-<целое>}:integer; {сумма цифр s1 и s2 тип-<целое>}:integer;
{переменная ошибки процедуры val},ks2:integer; {длины складываемых чисел a2 и
b2},sk2:string[1]; {складываемые цифры чисел a2 и b2
тип-<строчное>}:string[1]; {сумма цифр s1 и s2
тип-<строчное>}:boolean; {флаг смены знака на
противоположный},bb2,rez,bfr:string; {переменная для выполнения операции
<сложение>}:=length(a2); {загружаем в ks1 длину числа a2}:=length(b2);
{загружаем в ks2 длину числа b2}:=''; {инициализируем результирующую
переменную}
if
((pos('-',a2)<>0)and(pos('-',b2)<>0)) or {если
a2 и b2 одинаковы по}
((pos('-',a2)=0)and(pos('-',b2)=0))
then {знаку, то}
begin:=false; {флаг смены
знака-ложный}:=0; {обнуляем переменную переполнения}not((ks1=0)and(ks2=0)) do
{пока не пройдены все цифры склад.чисел}
begin:=0;:=0;:=0;:=copy(a2,ks1,1);
{вычисляем младшую цифру из a2}
if ks1>0 then {если цифры
a2 не пройд., то}sk1<>'-' then {если выбранная цифра не минус,
то}(sk1,s1,cd); {переводим ее в тип <целое>}:=copy(b2,ks2,1); {вычисляем
младшую цифру из a2}ks2>0 then {если цифры a2 не пройд., то}sk2<>'-'
then val(sk2,s2,cd); {переводим ее в тип <целое>}:=abs(s2)+d; {прибавляем
ко 2-му слаг. перемен. переполнения}
if (abs(s1)+abs(s2))>=10 then {если сумма абс. значений
цифр двух чисел >=10, то}
begin:=abs(s1)+abs(s2)-10;
{от
нее
отнимем 10 и}
d:=1; {переменная
переполнения равна 1}if (abs(s1)+abs(s2))<10 then {если сумма абс. значений
цифр 2-х чисел <10,
то}:=abs(s1)+abs(s2); {суммируем 2 выбр. цифры}:=0; {и перем. переполн.
обнулим};(s3,sk3); {результирующую цифру переведем в тип
<строчное>}:=sk3+rez; {и добавим ее спереди строки результата}ks1>0
then {если число a2 не пройдено до конца, то}:=ks1-1; {перейдем к более старшей
цифре}ks2>0 then {если число b2 не пройдено до конца, то}:=ks2-1; {перейдем
к более старшей цифре}; {цикл while}d<>0 then begin {если переменная
переполнения <>0, то}:= '1'+rez; {добавим спереди строки результата
'1'}:=0; {обнулим переменную переполнения};{if then}begin {иначе, если a2 и b2
неравнозначны}Bol(b2,a2)=1 {сравним выч. числа}begin fl:=true; {знак меняем на
противоположный от a2}:=b2; {переприсваиваем}:=a2; {переприсваиваем}
endbegin
fl:=false;:=a2;:=b2;;:=length(bb1);:=length(bb2);:=0;not((ks1=0)and(ks2=0))
do:=0;:=0;:=0;:=copy(bb1,ks1,1);ks1>0if sk1<>'-' then
val(sk1,s1,cd);:=copy(bb2,ks2,1);ks2>0if sk2<>'-' then
val(sk2,s2,cd);:=abs(s2)+d;(abs(s1)-abs(s2))<0begin
s3:=abs(s1)+10-abs(s2);:=1;begin
s3:=abs(s1)-abs(s2);:=0;;(s3,sk3);:=sk3+rez;ks1>0 then ks1:=ks1-1;ks2>0
then ks2:=ks2-1;; {while}; {if else}(pos('-',a2)=0)and(fl) then rez:='-'+rez;
Deln(rez);:=rez;;
function
TMainForm.Mins(a5,b5:string):string; {разность a5-b5}:boolean; {наличие минуса}pos('-',b5)<>0
then begin(b5,pos('-',b5),1);:=true;begin:='-'+b5;:=false;;:=sum(a5,b5);m then
b5:='-'+b5delete(b5,pos('-',b5),1);;TMainForm.Umn(a4,b4:string):string; {целочисленное умножение},s2,s3,i,j:integer;,ks1,ks2:integer;,sk2,sk3:string[1];:boolean;,bfr:string;:integer;:=length(a4);:=length(b4);:='0';not(ks2=0)
do:=0;:=0;:=0;:='';:=length(a4);:=copy(b4,ks2,1);ks2>0 thensk2<>'-'
then val(sk2,s2,cd);:=abs(s2);not(ks1=0) do:=0;:=copy(a4,ks1,1);ks1>0
thensk1<>'-' then val(sk1,s1,cd);(abs(s1)*abs(s2)+d)>=10
then:=(abs(s1)*abs(s2)+d)-((abs(s1)*abs(s2)+d)div
10)*10;:=(abs(s1)*abs(s2)+d)div 10;(abs(s1)*abs(s2)+d)<10
then:=abs(s1)*abs(s2)+d;:=0;;(s3,sk3);:=sk3+rez;ks1>0 then ks1:=ks1-1;; {while}d<>0
then
str(d,sk3);:=sk3+rez;
d:=0;;j:=1 to
length(b4)-ks2 do
rez:=rez+'0';:=sum(bfr,rez);
if ks2>0 then
ks2:=ks2-1;; {while}((pos('-',a4)<>0)and(pos('-',b4)=0))or {выставим знаки}
((pos('-',a4)=0)and(pos('-',b4)<>0))bfr:='-'+bfr;(bfr);:=bfr;;TMainForm.Divis(a6,b6:string):string;
{целочисленное деление a6 div b6}
var,bfr1,bfr2,rez:string;:string;:string[1];,ig,cd:integer;
beginbol(b6,'0')<>0
then:='0';:='0';kp:=1 to length(a6)
do:=bfr+copy(a6,kp,1);:='0';bol(bfr,b6)<>2
do:=mins(bfr,b6);:=sum(kp1,'1');;
val(kp1,ig,cd);(ig,kp2);
if
(bol(rez,'0')<>0)and(bol(bfr,b6)=2)(bol(kp1,'0')=0) rez:=rez+'0'if
bol(kp1,'0')<>0rez:=rez+kp2;;
{for}(rez);((pos('-',a6)<>0)and(pos('+',b6)=0))or
((pos('+',a6)=0)and(pos('-',b6)<>0))
then rez:='-'+rez;
divis:=rez;; {if
then};TMainForm.Modulo(a7,b7:string):string; {взятие от a7
остатка
по модулю
b7}:string;:='';:=mins(a7,umn(divis(a7,b7),b7));(modulo1);:=modulo1;;TMainForm.Hamcode;
{вычисление кода Хэмминга}
var,jh:integer;:integer;
beginih:=hc downto
0 do[ih]:=false;jh:=ic downto 0 do[ih]:=hamming[ih] xor(prmx[jh,ih]and
coderc[jh]);;;TMainForm.Dhamm; {восстановление ошибок по коду Хэмминга},j1,c,kn,a,b,d:integer;:array[0..wl] of
boolean; {вектор ошибок}:array[0..hc] of boolean; {синдром}:boolean;i1:=hc
downto 0 do[i1]:=false;j1:=wl downto 0 do[i1]:=se[i1] xor(incode[j1]and
prmx1[i1,j1]);;i1:=wl downto 0 do:=0;j1:=hc downto 0 dose[j1]=prmx1[j1,i1] then
c:=c+1;c=hc+1ve[i1]:=trueve[i1]:=false;;:=0;i1:=wl downto 0 dove[i1] then
wer:=wer+1;:=km+1;i1:=wl downto 0 dove[i1] thenwer=1 then[i1]:=incode[i1]xor
ve[i1];;TMainForm.Recod:string; {перевод двоичного кода в десятичное число}:integer;:string;:='0';l1:=wl downto hc+1
doincode[l1]
then:=sum(recod1,b[l1-ic]);:=recod1;;TMainForm.Der1(a11,b11,c11:string):string;
{вычисление a11 в степенипо модулю
c11},buf,buf1:string;,b13,b12,b14,kt:string;:string;,bd:integer;:=b11;:=76;bol(bfs,b[bd])=2
do:=bd-1;:=mins(bfs,b[bd]);:=a11;:=bd-1;bd>=0
dobol(bfs,b[bd])=2buf:=modulo(umn(buf,buf),c11)begin:=modulo(umn(buf,buf),c11);:=modulo(umn(a11,buf),c11);
bfs:=mins(bfs,b[bd]);
end;(buf,1,length(buf)-length(c11));
bd:=bd-1;;:=buf;
end;TMainForm.GenKeys;
{генерация ключей},cj:integer; {счетчики циклов}
bc:longint; {переменная для
генерации большого случайного числа}:longint; {число генераций},ksy:integer;
{счетчики циклов}:string; {основание теста Ферма}:boolean; {вспомогательные
переменные},Q1,E1,D1:string; {ключевые числа},qm,an,bn,buf:string;
{вспомогательные переменные}:array[0..1]of string; {вспомогат. переменные для
алгоритма Евклида}
begin.Timer1.Enabled:=true;(Sekret,'SekrKey');(UnSekret,'UnSKey');[0]:=true;
{генерация P1}:=0;ci:=1 to skd do:=random(5000);.SetFocus;cj:=0 to randt1
do.ProcessMessages;:=random(65535);;(bc mod 2)=0 then bc:=0bc:=1;bc=1 then
skbin[ci]:=trueskbin[ci]:=false;; {for ci}
P1:='0';cj:=0 to skd do
{преобразуем в десятичный вид}
if skbin[cj] then
P1:=sum(P1,b[cj]);P1[length(P1)]='5'P1:=sum(P1,'2');
prov:=''; {проверка на
простоту}
prov:=der1('8',mins(P1,'1'),P1);
prov:=mins(prov,'1');:=true;bol(modulo(prov,P1),'0')<>0
doP1[length(P1)]='3'P1:=sum(P1,'4')P1:=sum(P1,'2');
prov:=der1('8',mins(P1,'1'),P1);
prov:=mins(prov,'1');;
{while}not ftest then:='3';(bol(modulo(P1,qs),'0')<>0)and
(bol(umn(qs,qs),P1)=2)
doqs[length(qs)]='3'qs:=sum(qs,'4')qs:=sum(qs,'2');(bol(umn(qs,qs),P1)=0)or
(bol(modulo(P1,qs),'0')=0)beginP1[length(P1)]='3'P1:=sum(P1,'4')P1:=sum(P1,'2');:=false;;;
{if}flag;
{генерация Q1}:=0;ci:=1 to skd do:=random(5000);.SetFocus;cj:=0 to randt1
do.ProcessMessages;:=random(65535);;(bc mod 2)=0 then bc:=0bc:=1;bc=1 then
skbin[ci]:=trueskbin[ci]:=false;; {for ci}
Q1:='0';cj:=0 to skd do
{преобразуем в десятичный вид}
if skbin[cj] then
Q1:=sum(Q1,b[cj]);Q1[length(Q1)]='5'Q1:=sum(Q1,'2');
prov:='';:=der1('8',mins(Q1,'1'),Q1);
prov:=mins(prov,'1');:=true;bol(modulo(prov,Q1),'0')<>0
doP1[length(Q1)]='3'Q1:=sum(Q1,'4')Q1:=sum(Q1,'2');
prov:=der1('8',mins(Q1,'1'),Q1);
prov:=mins(prov,'1');;
{while}not ftest then:='3';(bol(modulo(Q1,qs),'0')<>0)and
(bol(umn(qs,qs),Q1)=2)
doqs[length(qs)]='3'qs:=sum(qs,'4')qs:=sum(qs,'2');(bol(umn(qs,qs),Q1)=0)or
(bol(modulo(Q1,qs),'0')=0)beginQ1[length(Q1)]='3'Q1:=sum(Q1,'4')Q1:=sum(Q1,'2');:=false;;;
{if}flag;
{генерация E1}[0]:=true;:=0;ci:=1 to skd do:=random(5000);cj:=0 to randt1
do:=random(65535);(bc mod 2)=0 then bc:=0bc:=1;bc=1 then
skbin[ci]:=trueskbin[ci]:=false;;:='0';cj:=0 to skd do
if
skbin[cj]E1:=sum(E1,b[cj]);
eyl:=umn(mins(P1,'1'),mins(Q1,'1'));
qs:='0';[0]:='0';[1]:='1';[0]:=E1;[1]:=eyl;
while
bol(am[1],'0')<>0 do
qs:=divis(am[0],am[1]);:=am[0];
delete(am[0],1,length(am[0])-length(eyl)-1);(am[1],1,length(am[1])-length(eyl)-1);
am[0]:=am[1];[1]:=mins(buf,umn(am[1],qs));
end;bol(am[0],'1')<>0
then
begin:=sum(E1,'2');
am[0]:=E1;;bol(am[0],'1')=0;
{генерация D1}:='1';:='1';:=eyl;:='2';bol(qm,'1')<>0
dobol(modulo(qm,qs),'0')=0 thenbol(modulo(qm,qs),'0')=0
do:=divis(qm,qs);:=umn(mins(qs,'1'),an);:=umn(qs,bn);;bol(modulo(qs[length(qs)],'2'),'0')=0qs:=sum(qs,'1')qs:=sum(qs,'2');bol(umn(qs,qs),qm)<>2qs:=qm;;
{while}
D1:=der1(E1,mins(divis(umn(eyl,an),bn),'1'),eyl);
security.P:=P1;.Q:=Q1;.D:=D1;.N:=umn(P1,Q1);
dkeys.E:=E1;
{Запись ключей в файл}
Reset(UnSekret);(UnSekret,Filesize(UnSekret));(UnSekret,dkeys,SizeOf(dkeys));(UnSekret);(Sekret);(Sekret,Filesize(Sekret));(Sekret,security,SizeOf(security));
CloseFile(Sekret);
{переменная сигнализирует о
том, что генерация состоялась}
KeyFlag:=true;KeyFlag
then.Cipher1.Enabled:=true;.Decipher1.Enabled:=true;.Open1.Enabled:=true;EFOpenError
do ShowMessage('файл ключей не найден'); EInOutError do ShowMessage('нельзя записывать в этот файл');
end;.Timer1.Enabled:=false;;
{$R
*.DFM}TMainForm.Open1Click(Sender: TObject);OpenDialog1.Execute
then:='RSA--'+OpenDialog1.FileName;.Open1.Enabled:=false;.Close1.Enabled:=true;.Clear;.Lines.LoadFromFile(OpenDialog1.FileName);;KeyFlag
then.Enabled:=true;.Enabled:=true;;.Enabled:=false;;TMainForm.Close1Click(Sender:
TObject);;;TMainForm.Save1Click(Sender:
TObject);OpenDialog1.FileName<>''Memo1.Lines.SaveToFile(SaveDialog1.FileName)Saveas1Click(Sender);KeyFlag
and (not CipFlag) then CipherForm.Enabled:=true;.Enabled:=false;.Enabled:=true;;TMainForm.Saveas1Click(Sender:
TObject);Memo1.Lines.Count<>0with SaveDialog1 doExecute then
begin.Lines.SaveToFile(FileName);:='RSA--'+ExtractFileName(FileName);;.Enabled:=true;KeyFlag
and (not CipFlag) then CipherForm.Enabled:=true;.Enabled:=false;.Enabled:=true;;TMainForm.About1Click(Sender:
TObject);about:TAboutBox;:=TAboutBox.Create(Self);about.ShowModal;about.Free;;;TMainForm.AntiRSA1Click(Sender:
TObject);.ShowModal;;TMainForm.KeysGeneration1Click(Sender: TObject);
var:integer;{заполнение
массива двоичных кодов}
b[0]:='1';i:=1 to
IC do[i]:=umn(b[i-1],'2');.ShowModal;;TMainForm.FromFile1Click(Sender:
TObject);
begin {ключи для генерации
извлекаются из файла}
try(Sekret,'SekrKey');(Sekret);(UnSekret,'dkeys');(UnSekret);not
eof(Sekret) do(Sekret,security,SizeOf(sekret));not eof(UnSekret)
do(UnSekret,dkeys,SizeOf(dkeys));(Sekret);(UnSekret);.Enabled:=true;.Enabled:=true;:=true;EFOpenError
do ShowMessage('файл ключей не найден');;;TMainForm.Cipher1Click(Sender:
TObject);,j:integer;:string; {шифрблок}:string; {несекретный ключ
N}:string; {несекретный ключ Е}(UnSekret,'dkeys');(UnSekret);not
eof(UnSekret)
do(UnSekret,dkeys,SizeOf(dkeys));:=dkeys.N;:=dkeys.E;(UnSekret);(f1,OpenDialog1.FileName);(f1);(f2,'cipher');(f2);.Show;:=false;.Enabled:=false;i:=0
to Memo1.Lines.Count-1 doj:=1 to Length(Memo1.Lines[i])
do(f1,Memo1.Lines[i][j]);:=chr(13);(f1,ch);;(f1);(f1);.Gauge1.MaxValue:=FileSize(f1)+1;.Gauge1.Progress:=0;
{------------------Шифрация----------------}.Gauge1.Progress:=CipherForm.Gauge1.Progress+1;not
eof(f1) do(f1,ch);:=ord(ch);(temp,tc1);:=der1(tc1,e,key);(f2,kodblock);; {добавление кодов Хэмминга}i:=HC
downto 0 do(f2,Hamming[i]);
.Gauge1.Progress:=CipherForm.Gauge1.Progress+1;.ProcessMessages;;(f1);(f2);(f2);:='0';.Clear;.Lines.LoadFromFile('cipher');(f2);.Close;:=true;.Enabled:=false;.Enabled:=true;EFOpenError
do ShowMessage('файл ключей не найден');EInOutError do ShowMessage ('нельзя записывать в этот файл');;:=true;;TMainForm.Decipher1Click(Sender:
TObject);:set of '0'..'9';
i,j:integer;,sim1,cdb:string;
{переменная для преобразования символов}
key,key1,key2,dm,kodblock:string;
{ключи},cd:integer; {переменные для ASCII-кодов}:boolean;(Sekret,'SekrKey');(Sekret);not
eof(Sekret) do(Sekret,security,SizeOf(sekret));:=security.P;:=security.Q;:=security.D;:=umn(mins(key1,'1'),mins(key2,'1'));(Sekret);:=true;:=['0','1','2','3','4','5','6','7','8','9'];(f2,'cipher');(f2);i:=0
to Memo1.Lines.Count-1 do(f2,Memo1.Lines[i]);;(f2);(f2);Memo1.Lines[0][1] in
set1 {проверка шифра}fileflag:=truefileflag:=false;fileflag
then(f3,'decipher');(f3);.Show;:=False;.Enabled:=false;.Gauge1.MaxValue:=CipherForm.Gauge1.MaxValue;.Gauge1.Progress:=0;
{---------------------Дешифрация-------------------}.ProcessMessages;.Gauge1.Progress:=DecipherForm.Gauge1.Progress+1;:=0;:=WL;not
eof(f2) do(f2,j);(f2,incode[i]);j>0 theni=0 then:=cp+1;:=WL+1;
Dhamm; {корректировка блоков
по кодам Хэмминга}
sim:='';:=der1(cdb,dm,umn(key1,key2));(f3);length(sim)>0
do(length(sim) mod 3)<>0begin:=copy(sim,1,length(sim) mod 3);(sim1,asc,cd);(sim,1,length(sim)
mod 3);begin:=copy(sim,1,3);(sim1,asc,cd);(sim,1,3);;asc>0
then(f3,filesize(f3));:=chr(asc-1);(f3,ch);;; {while};
{if}:=i-1;:=j+1;.ProcessMessages;.Gauge1.Progress:=DecipherForm.Gauge1.Progress+1;;
{while not eof(f2)}(f2);(f3);.Close;:=true;.Decipher1.Enabled:=false;.Cipher1.Enabled:=true;.Clear;.Lines.LoadFromFile('decipher');(f3);{then}begin('этот файл не является шифром');.Enabled:=false;(f2);;EFOpenError
do ShowMessage('файл ключей не найден');EInOutError do ShowMessage('нельзя записывать в этот файл');;:=true;
;TMainForm.Help2Click(Sender:
TObject);.Enabled:=true;.ShowModal;;TMainForm.Close2Click(Sender:
TObject);CipFlag
thenClick(Sender);:=false;;:='RSA';.Open1.Enabled:=true;.Clear;;TMainForm.FormActivate(Sender:
TObject);:=false;:=false;
end;.
Приложение 2
Текст модуля выбора теста
простоты
unit Choose;,
Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,, ExtCtrls;=
class(TForm): TRadioGroup;: TButton;Button1Click(Sender: TObject);
{ Private
declarations }
{ Public
declarations };: TChooseForm;MainProg, Wait;
{$R
*.DFM}TChooseForm.Button1Click(Sender:
TObject);:=ChooseForm.RadioGroup1.ItemIndex=0;.ShowModal;.GenKeys;.Close;.Close;;.
Приложение 3
Текст модуля взлома шифра RSA
unit AntiRSA;
interface, Messages,
SysUtils, Classes, Graphics, Controls, Forms, Dialogs,;= class(TForm): TLabel;:
TEdit;: TButton;: TLabel;: TEdit;: TButton;: TLabel;: TEdit;: TButton;:
TLabel;: TLabel;Button1Click(Sender: TObject);Button2Click(Sender:
TObject);Edit1Change(Sender: TObject);Button3Click(Sender: TObject);
{ Private
declarations }
{ Public
declarations };: TAntiR;,e,n,m:string;,ss,sss:string;:integer;MainProg;
{$R
*.DFM}TAntiR.Button1Click(Sender: TObject);
{процедура шифрации
сообщения}:integer;:='16813'; {открытый ключ}:='47053'; {произведение p,
q}:='19837'; {секретный ключ}:='46620'; {функция Эйлера}
if
Edit1.Text=''begin('Где сообщение?');.SetFocus;if
MainForm.Bol(Edit1.Text,n)=1
then begin('Сообщение должно
быть меньше 47053');
Edit1.SetFocus;begin:=MainForm.Der1(Edit1.Text,e,n);:=StrToInt(s);.Deln(s);.Text:=IntToStr(code);.Refresh;;;TAntiR.Button2Click(Sender:
TObject);
{процедура взлома шифра}:boolean;:integer;:=false;:=1;:=s;{зашифровываем шифр открытым ключом}:=MainForm.Der1(s,e,n);:=StrToInt(ss);:=IntToStr(code);
if Edit2.Text=ss {проверка
зашифрованного результата i-той итерации на совпадение с шифром}
then
begin:=StrToInt(s);.Text:=IntToStr(code);:=True;begin:='';:=ss;:=StrToInt(ss);.Text:=IntToStr(code);.Refresh;
end;:=j+1; {подсчет
совершенных итераций}
Label5.Caption:=IntToStr(j);.Refresh;flag;;TAntiR.Edit1Change(Sender:
TObject);.Text:='';.text:='';.Caption:='';;TAntiR.Button3Click(Sender:
TObject);;;.