ВУЗ:
Составители:
158
Однако заметим, что этот подход не менее труден, чем поиск алгоритма
решения сравнения
Nxy
e
mod= .
Взлом RSA при неудачном выборе параметров криптосистемы
Само по себе использование RSA не обеспечивает безопасности. Дело ещё
в деталях реализации. Приведём ряд примеров. Для простоты вычислений
будем работать с небольшими числами. Наша цель — показать особенности,
не зависящие от размера.
Пример 4. Пусть пользователь выбрал N = 2047, e = 179, d = 411. Так как
2047 = 23·89, а
88)89(,22)23(
=
=
ϕ
ϕ
имеют наименьшее общее кратное 88, то
любой обратный к 179 по модулю 88, например, 59, будет действовать как d.
Пример 5. Число N = 536813567 является произведением простого числа
Мерсенна 8191 и простого числа Ферма 65537. Это очень плохой выбор.
Пример 6. Число 23360947609 является очень плохим выбором для N из-за
того, что два его простых делителя слишком близки к друг другу.
Действительно, пусть p>q, имеем:
22
)
2
()
2
(
qpqp
N
−
+
+
= . Обозначим:
2
,
2
qp
S
qp
t
−
=
+
= . Так как S мало, то t — целое число, лишь немного большее
N , причем t
2
– N является полным квадратом. Проверяем подряд целые
числа
Nt > . В нашем примере: t
1
= 152843, t
2
= 152844, t
3
= 152845, и
23
804=− Nt , тогда 804152845,804152845
−
=
+
= pp . Таким образом мы с третьей
попытки нашли p и q. Количество попыток, необходимых для факторизации
N, можно при известных p и q вычислить по следующей формуле:
[]
qp
qp
qpk ⋅−
−
+⋅=
2
)
2
( , где [x] — операция округления x до ближайшего
целого числа.
Атака повторным шифрованием
Строим последовательность:
1),(mod,
11
>==
−
iNyyyy
e
ii
. Итак,
)(mod Nyy
m
e
m
= , а так как
(
)()
1,
=
Ne
ϕ
, то существует такое натуральное число
m, что
))((mod1 Ne
m
ϕ
≡ . Но тогда )(mod1
1
Ny
m
e
≡
−
, отсюда следует:
)(mod Nyy
m
e
≡ , значит, y
m-1
— решение сравнения
(
)
Nxy
e
mod= .
Пример 7. Пусть у нас имеется открытый ключ N =84517 , e = 397 и
зашифрованное им сообщение y = 8646. Необходимо найти исходный текст
x. Возведем y в степень e и получим y
2
= 37043. Будем повторять операцию
до тех пор, пока не получим y
n
= y. y
n-1
— искомое сообщение: y
3
= 5569, y
4
=
61833, y
5
= 83891, y
6
= 16137, y
7
= 8646. y
6
является решением сравнения
()
Nxy
e
mod= , а, следовательно, искомым сообщением x.
Замечание. Анализ метода повторного шифрования хорошо показывает
необходимость соблюдения требований на выбор p и q для обеспечения
стойкости. В данном примере d = 82225. Неудачный выбор криптосистемы
привел к тому, что атака методом повторного шифрования дала результат
Страницы
- « первая
- ‹ предыдущая
- …
- 156
- 157
- 158
- 159
- 160
- …
- следующая ›
- последняя »
