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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
тогда имеем
22
()()
22
p
qpq
N
+
−
=+. Обозначим:
,
22
p
qpq
tS
+
−
==. Так как S
мало, то t – целое число, лишь немного большее
,N причем t
2
– N является
полным квадратом. Проверяем подряд целые числа
.tN> В нашем примере
t
1
= 152843, t
2
= 152844, t
3
= 152845 и
32
,
804tN−= тогда 152 845 804,
p
=+
р = 152845 – 804. Таким образом, мы с третьей попытки нашли p и q. Количест-
во попыток, необходимых для факторизации N, можно при известных p и q вы-
числить по следующей формуле:
2
()
2
pq
kpq pq
⎡
⎤
⎣
⎦
−
=
⋅+ − ⋅ , где [x] – опера-
ция округления x до ближайшего целого числа.
Атака повторным шифрованием
Строим последовательность:
1
mod,(),1
1
e
i
i
yyyy Ni
=>
−
. Итак,
mod()
m
e
m
yy N=
, а так как
(
)
(
)
,1eNϕ
=
, то существует такое натуральное число
m, что
mod1( ( ))
m
eNϕ≡ . Но тогда
1
mod1( )
m
e
yN
−
≡ , отсюда следует, что
mod()
m
e
yyN≡ , значит, y
m-1
– решение сравнения
(
)
mod
e
yx N
=
.
Пример 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
является решением сравнения
(
)
mod
e
yx N=
, а, следовательно, искомым сообщением x.
Замечание. Анализ метода повторного шифрования хорошо показывает
необходимость соблюдения требований на выбор p и q для обеспечения стой-
кости. В данном примере d = 82 225. Неудачный выбор криптосистемы привел
к тому, что атака методом повторного шифрования дала результат почти сразу,
тогда как нахождение d потребовало бы на
порядок больших вычислений.
Атака на основе Китайской теоремы об остатках.
Как отмечалось ранее, системы шифрования с открытыми ключами рабо-
тают сравнительно медленно. Для повышения скорости шифрования RSA на
практике используют малую экспоненту зашифрования.
Если выбрать число е небольшим или таким, чтобы в его двоичной записи
было мало единиц, то процедуру шифрования можно значительно ускорить.
Например, выбрав е = 3 (при этом ни р – 1, ни
q – 1 не должны делиться на 3),
мы сможем реализовать шифрование с помощью одного возведения в квадрат
по модулю N и одного перемножения. Выбрав
16
21e
=
−= 65 537 – число, дво-
ичная запись которого содержит только две единицы, мы сможем реализовать
шифрование с помощью 16 возведений в квадрат по модулю N и одного пе-
ремножения. Если экспонента е выбирается случайно, то реализация шифрова-

Страницы