Аддитивный генератор случайных чисел
Генератор, формирующий очередное случайное число в соответствии с отношением (3), называется аддитивным:
Xn+1=(Xn+Xn-k) mod m. (3)
В трехтомнике Кнута [5] обсуждаются подобные генераторы и рекомендован следующий вариант формулы (3):
Xn+1=(Xn-24+Xn-55) mod m.(4)
Здесь n > 55, m=21, Хо, ..., Х54 — произвольные числа, среди которых есть и нечетные. При этих условиях длина периода последовательности равна 21-1 (255-1).
Алгоритм RSA.
Рассмотрим работу асимметричного RSA. Он был предложен тремя математиками Рональдом Ривестом (R. Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L. Adleman) в 1978 году.
Под простым числом будем понимать такое число, которое делится только на 1 и на само себя. Эвклид в своих «Началах» показал, что для любого простого числа есть большее простое число, то есть количество простых чисел бесконечно.
Доказательство. Допустим, что существует наибольшее простое число p, определим произведение всех простых чисел P=2・3・5・7・…・p.
Рассмотрим число P+1. Оно или само является простым числом большим p или произведением простых чисел, которые больше P. Мы пришли к противоречию, значит количество простых чисел бесконечно.
Примеры:
2・3+1=7; 2・3・5+1=31; 2・3・5・7+1=211;
2・3・5・7・11+1=2311; 2・3・5・7・11・13+1=30031=59・509.
Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме 1.
Наконец, под результатом операции i mod j будем считать остаток от целочисленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги.
1. Выберем два очень больших простых числа р и q.
2. Определим n как результат умножения р на q (n=p·q).
3. Выберем большое случайное число, которое назовем d. Это число должно быть взаимно простым с результатом умножения (р – 1) · (q – 1).
4. Определим такое число е, для которого является истинным следующее соотношение (е·d) mod ((p – 1) · (q – 1)) = 1.
5. Назовем открытым ключом числа е и n, а секретным ключом – числа d и n.
Теперь, чтобы зашифровать данные по известному ключу {е, n}, необходимо сделать следующее:
– разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числаM(i);
– зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле С(i) = (M(i)e) mod n. Чтобы расшифровать эти данные, используя секретный ключ {d, n}, необходимо выполнить следующие вычисления: M(i)=(C(i)d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.
Алгоритм RSA основан на одной из доказанных теорем Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство x(p-1)(q-1) mod n = 1.
Для дешифрования RSA- сообщений воспользуемся этой формулой. Для этого возведем обе ее части в степень (-y):
(x(-y)(p-1)(q-1)) mod n = 1(-y) = 1.
Теперь умножим обе ее части на x:
(x(-y)(p-1)(q-1)+1) mod n = 1·x = x.
Вспомним теперь, как создавались открытый и закрытый ключи. Мы подбирали d такое, что
e·d+(p-1)(q-1) ·y = 1, то есть e·d = (-y)(p-1)(q-1)+1.
Следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e·d). Получаем (xe·d) mod n = x.
Для того чтобы прочесть сообщение ci = ((mi)e)mod n достаточно возвести его в степень d по модулю m:
((ci)d)mod n = ((mi)e·d) mod n = mi.
Приведем простой пример использования метода RSA для шифрования сообщения «CAB». Для простоты будем использовать очень маленькие числа (на практике используются большие числа).
1. Выберем р=3 и q=11.
2. Определим n=3·11=33.
3. Найдем (р–1) (q–1)=20. В качестве d выберем любое число, которое является взаимно простым с 20, например d=3.
4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е·3) mod 20 = 1, например 7.
5. Представим шифруемое сообщение как последовательность целых чисел в диапазоне 0...32. Пусть буква А изображается числом 1, буква В – числом 2, а буква С – числом 3. Тогда сообщение можно представить в виде последовательности чисел 312. Зашифруем сообщение, используя ключ {7, 33}:
С(1)=(З7) mod 33 = 2187 mod 33 = 9,
С(2) = (17) mod 33 = 1 mod 33 = 1,
С(З) = (27) mod 33 = 128 mod 33 = 29.
6. Попытаемся расшифровать сообщение {9, 1, 29}, полученное в результате зашифровывания по известному ключу, на основе секретного ключа {3, 33}:
M(1) = (93) mod 33 = 729 mod 33 = 3,
М(2) = (13) mod 33 = 1 mod 33 = 1,
М(З) = (293) mod 33 = 24389 mod 33 = 2.
Таким образом, в результате расшифровывания сообщения получено исходное сообщение «CAB».
Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключ по известному открытому, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Данная задача не допускает в настоящее время эффективного (полиномиального) решения. В связи с этим для ключей, состоящих из 200 двоичных цифр (а именно такие числа рекомендуется использовать), традиционные методы поиска делителей требуют выполнения огромного числа операций (около 1023).
Криптосистема RSA используется в самых различных платформах и во многих отраслях. Она встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении
алгоритм RSA применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании фирмы Zaxus (Rasal). Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах.
Технологию шифрования RSA BSAFE используют более 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире, и это количество имеет явную тенденцию к увеличению по мере роста пользователей Internet.