Рассмотрим работу асимметричного 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). Получаем (x e · d) mod n = x . Для того чтобы прочесть сообщение c i = ((m i) e)mod n достаточно возвести его в степень d по модулю m :
((c i) d)mod n = ((m i) e · d) mod n = m i .
Приведем простой пример использования метода 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) = (1 7) mod 33 = 1 mod 33 = 1,
С(З) = (2 7) mod 33 = 128 mod 33 = 29.
6. Попытаемся расшифровать сообщение {9, 1, 29}, полученное в результате зашифровывания по известному ключу, на основе секретного ключа {3, 33}:
M(1) = (9 3) mod 33 = 729 mod 33 = 3,
М(2) = (1 3) mod 33 = 1 mod 33 = 1,
М(З) = (29 3) mod 33 = 24389 mod 33 = 2.
Таким образом, в результате расшифровывания сообщения получено исходное сообщение «CAB».
Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключ по известному открытому, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Данная задача не допускает в настоящее время эффективного (полиномиального) решения. В связи с этим для ключей, состоящих из 200 двоичных цифр (а именно такие числа рекомендуется использовать), традиционные методы поиска делителей требуют выполнения огромного числа операций (около 10 23).
Криптосистема RSA используется в самых различных платформах и во многих отраслях. Она встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении алгоритм RSA применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании фирмы Zaxus (Rasal). Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах.
Технологию шифрования RSA BSAFE используют более 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире, и это количество имеет явную тенденцию к увеличению по мере роста пользователей Internet.
Под катом описаны примеры выбора «плохих» параметров шифра RSA.
«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n ) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p , q или φ(n) , можно легко найти секретный ключ RSA…».
Дополним этот текст. При неудачном выборе модуля шифра RSA, как это сделано в примере пособия, приводимом ниже, можно дешифровать текст и без наличия секретного ключа, т.е. не зная ни одной из трех названных величин.
Для этого достаточно располагать зашифрованным текстом, заданным модулем шифра n , открытым ключом е шифра и выполнить всего три шага атаки «бесключевого чтения». После четвертого атакующего шага устанавливается, что на предыдущем шаге был получен исходный текст, он может быть прочитан. Покажем, насколько просто это делается.
Вначале приведем сам пример со стр. 313-315 из названного пособия.
Пример
Шифрование короткого исходного текстового сообщения: RSA .Получатель устанавливает шифр с характеристиками n=pq=527 , где р=17 , q=31 и φ(n)=(р –1)(q – 1)=480 . В качестве открытого ключа е выбрано число, взаимно простое с φ(n) , е=7 . Для этого числа с помощью расширенного алгоритма Евклида найдены целые числа u и v , удовлетворяющие соотношению е∙u+φ(n)∙v=1 :
480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137
.
Поскольку –137≡343(mod480) , то d=343 .
Проверка: 7∙343=2401≡1(mod480) .
Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале . Для этого буквы R , S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:
R=18 10 =(10010) 2
, S=19 10 =(10011) 2
,
A=1 10 =(00001) 2
.
Тогда RSA=(100101001100001) 2 . Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М 1 =297, М 2 =33) .
Последовательно шифруются блоки исходного текста М 1 =297
, М 2 =33
:
y 1 =Е k (М 1)=М 1 e ≡297 7 (mod527)=474
.
Здесь воспользовались тем, что:
297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474
,
y 2 =Е k (М 2)=M 2 e ≡33 7 (mod527)=407
.
Шифрованный текст, как и исходный, получаем в виде двух блоков: у 1 =474 ; у 2 =407 .
Расшифрование представляется последовательностью действий D k (y i)=(y i) d =(y i) 343 (mod 527) , i=1,2 .
Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2 , а именно: 343=256+64+16+4+2+1 .
Используя это представление показателя степени d=343 , получаем:
474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
и окончательно 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297
.
Аналогично вычисляется значение 407 343 (mod527)=33 .
Переход к буквенному представлению расшифрованного сообщения дает: RSA .
После рассмотрения примера в пособии приводятся рассуждения о стойкости системы RSA. Подчеркивается необходимость соблюдения осторожности в выборе модуля шифра RSA (числа n ) для каждого из корреспондентов сети. Указывается на недопустимость игнорирования требований к выбираемым характеристикам системы шифрования. Среди таких требований, к сожалению, не указано то, нарушение которого иллюстрирует приведенный пример.
Атака на шифр RSA
Рассмотрим пример атаки на шифр RSA. Воспользуемся данными примера, приведенного на странице 313-315 в учебном пособии «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001.Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7
, n=527
) и шифрованный текст. В примере шифрованный текст представлен двумя блоками
у=(у 1 =474, у 2 =407)
.
Каждый шифрованный блок атакуется индивидуально, вначале атакуем у 1 =474 , после его дешифрования, атакуем другой блок у 2 =407 .
Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений у i , у 1 =у имеющийся шифрованный текст.
В алгоритме атаки на шифрованный текст определяется такой номер шага j , для которого y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i , i>1 . Из последнего соотношения видим, что при возведении в степень е значения (y i e j–1 (mod n)) получается начальный шифoртекст y i = у 1 .
Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j , при котором цикл шифрования завершается значением y 1 , с которого цикл и был начат.
Атака на первый блок у 1 =474
шифртекста.
Шаг 1
:   474 7 (mod527)=382
;
Шаг 2
:   382 7 (mod527)=423
;
Шаг 3
:   423 7 (mod527)=297
;
Шаг 4
:   на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474
) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.
297 7 (mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у 1 =474 . Предшествующий результат шага 3 равен открытому тексту М 1 =297 .
n=527
r=297
по модулю n=527
. Это записывается так y i =у 1 =297
. Формируем степенные вычеты
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297
.
Атака на второй блок у 2 =407
шифртекста.
Шаг 1
:   407 7 (mod527)=16
;
Шаг 2
:   16 7 (mod527)=101
;
Шаг 3
:   101 7 (mod527)=33
;
Шаг 4
:   33 7 (mod527)=407
.
Вновь на третьем шаге получен блок исходного текста (М 2 =33 ), но атакующему это неизвестно, и он выполняет следующий (четвертый шаг), результат которого (407 ) совпадает с начальным шифртекстом у 2 =407 .
По существу в кольце вычетов по модулю n=527
реализовался короткий цикл обработки вычета r=33
по модулю n=527
. Это записывается так y i =у 2 =33
.
Формируем степенные вычеты ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33
.
Результат атаки (исходный текст М 1 =297 , М 2 =33 ) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.
Продолжая обсуждение вопроса о выборе модуля и других параметров шифра, можно добавить, что модуль шифра (n=527 ) некоторые исходные тексты вообще не позволяет шифровать. При этом выбор значения открытого ключа е большой роли не играет. Существуют значения исходных текстов, которые вообще невозможно зашифровать выбранным шифром с модулем n=527 .
Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами
187
, 341
, 154
и 373
.
Пример (невозможность шифрования значений некоторых исходных текстов)
Пусть исходные тексты представлены четырьмя блоками y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373) . Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)=φ(527)=480 . Впрочем, для рассматриваемого случая открытый ключ е может быть задан произвольно. Действительно, пусть е=2, 4, 7, 9, 17, 111 тогда:154 2 (mod527)=1
;
154 4 (mod527)=1
;
154 7 (mod527)=154
;
154 9 (mod527)=154
;
154 17 (mod527)=154
;
154 111 (mod527)=154
;
187 2 (mod527)=187
;
187 4 (mod527)=187
;
187 7 (mod527)=187
;
187 9 (mod527)=187
;
187 17 (mod527)=187
;
187 111 (mod527)=187
;
341 2 (mod527)=341
;
341 4 (mod527)=1
;
341 7 (mod527)=341
;
341 9 (mod527)=341
;
341 17 (mod527)=341
;
341 111 (mod527)=341
;
373 2 (mod527)=1
;
373 4 (mod527)=373
;
373 7 (mod527)=373
;
373 9 (mod527)=373
;
373 17 (mod527)=373
;
373 111 (mod527)=373
.
Из рассмотренного примера следует простой вывод. Действительно, к выбору параметров процесса шифрования надо подходить очень внимательно и проводить тщательный предварительный анализ таких параметров. Как это делать - отдельный вопрос, и в рамках этой работы он не рассматривается.
Схема Райвеста - Шамира - Адлемана (RSA) в настоящее время является единственной, получившей широкое признание и практически применяемой схемой шифрования с открытым ключом.
Схема RSA представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до п - 1 для некоторого п.
Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа п. Это значит, что длина блока должна быть не больше log2(«). На практике длина блока выбирается равной 2 к битам, где 2 к Схема, разработанная Райвестом, Шамиром и Адлеманом, основана на выражениях со степенями. Шифрование и дешифрование для блока открытого текста М и блока шифрованного текста С можно представить в виде следующих формул:
Как отправитель, так и получатель должны знать значение п. Отправитель знает значение е, и только получателю известно значение d. Таким образом, данная схема является алгоритмом шифрования с открытым ключом KU= {е, п), и личным ключом KR = {d, п}.
Чтобы этот алгоритм мог использоваться для шифрования с открытым ключом, должны быть выполнены следующие требования:
Должны существовать такие значения е, d и п, что M ed = M(mod п) для всех М п.
Должны относительно легко вычисляться IVT и С с1 для всех значений М п.
Должно быть практически невозможно определить d по имеющимся ей п.
Проанализируем сначала первое требование, а остальные рассмотрим позже. Необходимо найти соотношение вида
Здесь как нельзя лучше подойдет следствие из теоремы Эйлера: для таких любых двух простых чисел р и q и таких любых двух целых чисел пит, что n=pqn0 и произвольного целого числа к выполняются следующие соотношения:
где ф(я) является функцией Эйлера, значение которой равно числу положительных целых чисел, меньших п и взаимно простых с п.
В случае простых р и q имеем ф(pq) - (р - 1 )(q - 1). Поэтому требуемое соотношение получается при условии
Это эквивалентно следующим соотношениям:
т.е. ей d являются взаимно обратными по модулю ф(я). Обратите внимание, что в соответствии с правилами арифметики в классах вычетов это может иметь место только тогда, когда d (а следовательно и е) является взаимно простым с ф(и). В эквивалентной записи (ф(/7), d)=.
Теперь у нас есть все, чтобы представить схему RSA. Компонентами схемы являются:
р и q - два простых числа (секретные, выбираются);
п - pq (открытое, вычисляется);
такое е , что (ф(я), е) = 1,1 е
d = е л (mod ф(/?)) (секретное, вычисляется).
Личный ключ складывается из {d,n}, а открытый- из {е, п}. Предположим, что пользователь А опубликовал свой открытый ключ, и теперь пользователь В собирается переслать ему сообщение М.
Тогда пользователь В вычисляет шифрованное сообщение
Получив этот шифрованный текст, пользователь А дешифрует его, вычисляя
Имеет смысл привести здесь обоснование этого алгоритма. Были выбраны ей d такие, что
Значит, еЛшеет вид кц>(п)+. Но по следствию теоремы Эйлера, для таких любых двух простых чисел р и qu целых чисел п = pqn М, чтоО выполняются соотношения
Поэтому
Теперь имеем
Таблица 10.1 резюмирует алгоритм RSA, а на рис. 10.1 показан пример его применения. В этом примере ключи вычисляются следующим образом:
- 1. Выбираются два простых числа: р- 7 wq- 17.
- 2. Вычисляется п =pq = 7 х 17=119.
- 3. Вычисляется ф(п) - (р -){q - 1) = 96.
- 4. Выбирается е , взаимно простое с ф(п) = 96 и меньшее, чем ф(я); в данном случаев = 5.
- 5. Определяется такое d, что de = 1 (mod 96) и d 96. Соответствующим значением будет d= 77, так как 77 х 5 = 385 = 4 х 96 + 1.
- 6. В результате получаются открытый ключ KU= (5, 119} и личный ключ KR = {77, 119}.
В данном примере показано использование этих ключей с вводимым открытым текстом М = 19. При шифровании 19 возводится в пятую степень, что в результате дает 2 476 099. В результате деления на 119 определяется остаток, равный 66. Следовательно, 19 5 = 66(mod 119), и поэтому шифрованным текстом будет 66. После дешифрования выясняется, что
Рис. 10.1.
Таблица 10.1
Допустим, что объект А хочет передать сообщение объекту В в зашифрованном виде. Для этого используем алгоритм RSA. При передаче могут возникнут проблемы из-за или плохую . Для этого нужно использовать методы обнаружения ошибок . Но для разных сетей разные методы.
- объект В придумывает два любых больших простых числа Р и Q;
- объект В решает значение модуля N = P × Q;
- объект В решает функцию Эйлера:φ(N) = (P-1) × (Q-1)
;
и выбирает любым образом значение открытого ключа K в с учетом условия:1 < K в ≤ φ(N), НОД (K в, φ(N)) = 1 - объект В решает значение секретного ключа κ в решая алгоритм Евклида когда достигается условие: κ в ≡ K в -1 (mod φ(N)).
- объект В передает объекту А пару числе (N, K в) по незащищенному пути.
- Если объект А хочет передать объекту В сообщение М , он должен разбить исходный открытый текст M на блоки, каждый из которых может быть показан в виде: M i = 0, 1, 2, …, N — 1 .
- Объект А шифрует данные, показаны в виде последовательности чисел M i по формуле: C i = M i K в (mod N) , и отправляет криптограмму C 1 , C 2 , …, C i … объекту В.
- Пользователь В расшифровывает криптограмму C 1 , C 2 , …, C i … используя секретный ключ κ в по формуле: M i = C i K в (mod N)
При реализации алгоритма на практике, нужно иметь возможность без сильных затрат генерировать большие простые числа, к тому же быстро решать значение ключей.
Пример: шифрование сообщения
Для наглядности вычисления, будем использовать небольшие числа. Но на практике используют очень большие числа (длиной 200-300 десятичных разрядов).
Действия объекта В:
- Берет Р = 3, Q = 11.
- Берет модуль N = P × Q = 3 × 11 = 33.
- Берет значение функции Эйлера для N = 33: φ(N) = (P-1) × (Q-1) = 2 × 10 = 20.
- Берет в качестве открытого ключа K в произвольное число с учетом условия: 1 < K в ≤ φ(N), НОД (K в, φ(N)) = 1 , допустим K в = 7.
- Решаем значение секретного ключа κ в используя алгоритм Евклида: κ в ≡ = 3.
- объект В передает объекту А пару чисел (N = 33, K в = 7).
Действия объекта A:
- Показывает шифруемое сообщение как последовательность целых чисел в диапазоне 0…32. Допустим буква А представляется как число 1, буква В это 2 и С = 3. Припустим что сообщение С А В можно показать как последовательность числе 321, то есть M 1 = 3, M 2 = 1, M 3 = 2.
- Шифрует сообщение, М используя ключ K в = 7 и N = 33 по формуле: C i = M i K в (mod N) = M i 7 (mod 3).
- Получаем:
- C i = 3 7 (mod 33) = 2187 (mod 33) = 9
- C i = 1 7 (mod 33) = 1 (mod 33) = 1
- C i = 2 7 (mod 33) = 128 (mod 33) = 29
- Передает объекту В криптограмму: C 1 , C 2 , C 3 = 9, 1, 29.
Действия объекта B:
- Расшифровывает принятую криптограмму C 1 , C 2 , C 3 используя секретный ключ ≡ = 3 по формуле:M i = C i K в (mod N)
= C i 3 (mod 3)
- M 1 = 9 3 (mod 33) = 729 (mod 33) =3.
- M 2 = 1 3 (mod 33) = 1 (mod 33) =1.
- M 2 = 29 3 (mod 33) = 24389 (mod 33) =2.
Объект получил исходное сообщение, которое послал объект A.
Шифрование с помощью RSA есть одним из при передачи данных через сеть Интернет. Схема Рабина очень похожа на схему RSA. Криптоалгоритм RSA признан стойким при дине ключа больше 1024 бит. Нужно отметить что алгоритм применяют как для шифрования так и для электронно-цифровой подписи. Нетрудно заметить что в асимметричной криптосистеме RSA количество ключей связано с количеством пользователей линейной зависимостью (N пользователей используют 2 × N ключей), а не квадратичной как это используется в симметричных системах.
Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = m e (mod n).
При этом n = pq, где p и q - случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e выбирается как достаточно большое число из диапазона 1 < e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Далее, решая в целых числах x, y уравнение xe + yφ(n) = 1, полагается d = х, т.е. ed = 1(j(n)). При этом для всех m выполняется соотношение m ed = m(n), поэтому знание d позволяет расшифровывать криптограммы.
Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два следующих требования.
1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.
Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах.
Рассмотрим построение криптосистемы RSA на простом примере.
1. Выберем p = 3 и q = 11.
2. Определим n = 3 ∙ 11 = 33.
3. Найдем j(n) = (p – 1)(q – 1) = 20.
5. Выберем число d, удовлетворяющее 7d = 1(mоd 20).
Легко увидеть, что d = 3(mоd 20).
Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия: А = 1, B = 2, С = 3, ..., Z = 26. Поскольку size(n) = 6, то наша криптосистема в состоянии зашифровывать буквы латинского алфавита, рассматриваемые как блоки, Опубликуем открытый ключ (e, n) = (7, 33) и предложим прочим участникам системы секретной связи зашифровывать с его помощью сообщения, направляемые в наш адрес.Пусть такимсообщением будет CAB, которое в выбранном нами кодировке принимает вид (3, 1, 2).Отправитель должензашифроватькаждый блок и отправитьзашифрованное сообщение в наш адрес:
RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33).
Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:
9 3 = 729 = 3(mоd 33);
1 3 = 1(mоd 33);
29 3 = 24389 = 2(mоd 33).
Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):
· 512–768 бит - для частных лиц;
· 1024 бит - для коммерческой информации;
· 2048 бит- для секретной информации.
Пример реализации алгоритма RSA представлен в листингах 18.1 и 18.2 (компиляторы - Delphi, FreePascal).
Листинг 18.1. Пример реализации алгоритма RSA на языке Pascal
program Rsa;
{$APPTYPE CONSOLE}
{$IFDEF FPC}
{$MODE DELPHI}
{$ENDIF}
uses SysUtils, uBigNumber;
//Генератор случайных чисел
var t: array of Byte;
var pos: Integer;
var cbox: array of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);
procedure InicMyRandom;
var i: Integer;
var s: string;
begin
WriteLn("Введите какой-либо текст для инициализации генератора
случайных чисел (до 256 символов):");
ReadLn(s);
i:= 1;
while (i<=255) and (i<=Length(s)) do