Алгоритм RSA. Жданов О.Н - 9 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

9
В нашем примере N = 23393, e = 5. Применив алгоритм Эвклида к числам
( ) 23088N
ϕ = и e = 5, найдем
1
mod 23088 13853.de
−
== Значит для расшиф-
ровки блоков шифртекста мы должны возвести этот блок в степень 13583 по
модулю 23393. В примере первый блок шифртекста – число 22752, тогда полу-
чим 22752
13853
mod 23393 = 2524.
Разбиение числа на блоки можно произвести различными способами. При
этом промежуточные результаты зависят от способа разбиения, однако конеч-
ный результат – не зависит.
1.2. АТАКИ НА АЛГОРИТМ RSA
Для дешифрации необходимо по известным N, e и шифртексту y найти та-
кое (( / ))*
x
ZN∈ , что mod
e
yx N= .
Попытаемся решить сравнение при конкретных y, затем использовать го-
моморфность отображения D(x).
Один из возможных способов следующий: пусть имеется набор пар
11
{( , )...( , )}
kk
x
yxy
с условием, что mod
e
ii
x
yN
=
, 1 < y < N, (y, N) = 1. Если ка-
ким-либо образом удалось представить y в виде
1
1
mod...
k
s
s
k
yy y N=⋅⋅ с целыми
s
k
, то
1
1
...
k
s
s
k
x
xx=⋅⋅ будет решением сравнения mod .
e
yx N
=
Пример 3. В наличии имеется открытый ключ N = 31459, e = 5 и набор пар
соответствующих друг другу исходных и зашифрованных сообщений: (23,
18707), (755, 26871), (631, 6384). Требуется расшифровать шифртекст
y = 11 638. Для этого представим y в виде
132
18 707 26 871 6 384 11 638.y
−
−
=⋅⋅=
Отсюда легко вычислить исходное сообщение:
13 2
23 755 631 28 260x
−
−
=⋅⋅ = .
Заметим, что этот подход не менее труден, чем поиск алгоритма решения
сравнения
mod .
e
yx N=
Взлом RSA при неудачном выборе параметров криптосистемы
Само по себе использование RSA не обеспечивает безопасности. Дело еще
в деталях реализации. Приведем ряд примеров. Для простоты вычислений бу-
дем работать с небольшими числами. Цель – показать особенности, не завися-
щие от размера.
Пример 4. Пусть пользователь выбрал N = 2047, e = 179, d = 411. Так как
2047 = 2389, а (23) 22, (89) 88
ϕϕ== имеют наименьшее общее кратное 88, то
любой обратный к 179 по модулю 88, например 59, будет действовать как d.
Пример 5. Число N = 536813567 является произведением простого числа
Мерсенна 8191 и простого числа Ферма 65537. Это очень плохой выбор.
Пример 6. Число 23360947609 является очень плохим выбором для N из-за
того, что два его простых делителя слишком близки
к друг другу. Пусть p > q,

Страницы