Исследование алгоритма защиты информации RSA. Криптосистемы с открытым ключом. Алгоритм Евклида, страница 3

24 26³ +4-26 + 18=16346.

После шифрования алгоритмом RSA получаем

8

16346³'⁴"mcu* 4(5927, что дает число 21166.

Пользователю В известен открытый ключ (n_A, d_A) - (46927, 26767), и для расшифровки полученного сообщения В использует преобразование

21166²⁶⁷⁶⁷mod 46927= 16346 = "YES".

Наиболее сложным шагом с вычислительной точки зрения ■ проделанных выше действиях является операция вычисления модулярной экспоненты 16346^зм" mod 46927. Если использовать метод последовательного возведения числа в квадрат, то алгоритмическая сложность может быть оценена величиной O(t'), где t - количество бит в числе.

Шифр ЭльГамаля. Схема шифрования основана ва возведении в степень по модулю большого простого числа р. Сообщения представляются целыми числами m из интервала (1,р).

Протокол сообщения m выглядит следующим образом.

•  Отправитель А и получатель В знают лишь число р. А генерирует случайное число х е(1,р), В тоже генерирует случайное число у из того же интервала

•  А шифрует сообщение С, = m*mod р и посылает его В.

9

•  В шифрует его своим ключом С₂= CVmodp и досылает С₂ к А

•  А снимает свой ключ, выполняя преобразование с₃ = CJmod р, и возвращав! С₃ пользователю В

•  Получатель В расшифровывает сообщение с/    = т modp-

•  Обратные числах"' и /' могут быть найдены с помощью алгоритма

"

Евклида.

2.3.    Открытое распределение ключей

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

АлгоритмW. Diffie, M. E. Hellman. Подразумевает независимое генерирование каждым из пары связывающихся пользователей своего случайного числа, преобразование его посредством некоторой процедуры, обмен преобразованными числами по открытому каналу связи и вычисление общего секретного ключа на основе информации, полученной в процессе связи от партнера.

Процедура открытого распределения ключей между абонентами А и В выглядит следующим образом:

•  Абонеиты А,В знают два открытых числа р и а. Число р является большим простым числом, (р-1) - имеет по крайней мере один большой множитель. В качестве числа а может использоваться примитивный элемент поля GF(p).

•  Пользователь А имеет свой секретный ключ d_A, а пользователь В -секретный ключ d_B, d_A, d_Be(l,N).

•  Абонент А посылает В шифровку своею ключа z* = а^л* mod р, a абонент В посылает А шифровку своего ключа г" = а^л> mod р

•  Общий секретный ключ вычисляется, как

K = Z-"' =Z""* =a"'^d'mod p.

2.4.    Алгоритм вероятное!ной атаки на криптосистему RSA

Из алгоритма RSA следует, что число п определяется как произведение двух чисел ( pq ) и знание функции Эйлера <р(п) эквивалентно знанию сомножителей факторизации п. Предположим, что ставится задача «взломать» систему RSA, т.е. определить положительное число d, удовлетворяющее условию

а"* я a mod л для всех а простых к п. Это эквивалентно тому, что (ed - 1) становится кратным НОК чисел (р-1), (q-1).

Предположим, что известно п (являющееся произведением двух простых чисел) и также некое целое число т, удовлетворяющее сравнению а" я lmod л для всех а взаимно простых с п. Заметим, что в этом случае m должно быть четным числом, поэтому, не меняя существа задачи, можно вместо m в дальнейшем использовать число т/2. Отсюда следует, что выражение а^т/г * lmod n справедливо, по крайней мере, для 50% _а из (Z/nZ). Таким образом, если осуществляется тестирование множества случайно   выбранных    {_0j}    и   определяется,   что    во   всех    случаях выполняется сравнение а^я/2 = lmod ч, тогда с большой степенью вероятности можно утверждать, что все а и п взаимно просты . При этом возможны следующие варианты: