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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
ния по алгоритму RSA потребует s возведений в квадрат по модулю N и в сред-
нем s/2 умножений по тому же модулю, где 5 – длина двоичной записи числа N.
Вместе с тем выбор небольшой экспоненты е может привести к негативным по-
следствиям. Дело в том, что у нескольких корреспондентов могут оказаться
одинаковые экспоненты
е.
Пусть, например, три корреспондента имеют попарно взаимно простые
модули N
1
, N
2
, N
3
и общую экспоненту е = 3. Если еще один пользователь посы-
лает им некое циркулярное сообщение x, то криптоаналитик противника может
получить в свое распоряжение три шифрованных текста
3
mod(),
ii
yx N=
i = 1, 2, 3. Далее он может найти решение системы сравнений, лежащее в ин-
тервале 0 < y < N
1
·N
2
·N
3
11
22
33
mod
mod
mod
(),
(),
(),
yy N
yy N
yy N
⎧
⎪
⎪
⎨
⎪
⎪
⎩
≡
≡
≡
По китайской теореме об остатках такое решение единственно, а так как
3
123
, ,
x
NN N< , то y = x
3
. Значение х можно найти, вычислив кубический ко-
рень
3
x
y= .
Отметим, что выбор малой экспоненты расшифрования d также нежелате-
лен в связи с возможностью определения d простым перебором. Известно также
что если
4
dN<
, то экспоненту d легко найти, используя непрерывные дроби.
Пример 8. Три пользователя имеют модули N
1
= 26549, N
2
= 45901,
N
3
= 25351. Все пользователи используют экспоненту e = 3. Всем пользовате-
лям было послано некое сообщение x, причем пользователи получили сообще-
ния y
1
= 5366, y
2
= 814, y
3
= 4454. Найдем M
0
= N
1
·N
2
·N
3
= 30893378827799. Да-
лее находим
m
1
= N
2
·N
3
= 1163636251
m
2
= N
1
·N
3
= 673043699
m
3
= N
1
·N
2
= 1218625649
n
1
= m
1
-1
mod N
1
= 13533
n
2
= m
2
-1
mod N
2
= 27930
n
3
= m
3
-1
mod N
3
= 22354
S = y
1
·n
1
·m
1
+ y
2
·n
2
·m
2
+ y
3
·n
3
·m
3
= 84501028038745578 + 15301661957638980 +
+ 121332116653000684 = 221134806649385242
S
mod M
0
= 1000000000
x = (S
mod M
0
)
1/3
= 1000 – исходное сообщение, отправленное пользовате-
лям.
Бесключевое чтение
Пусть два пользователя выбрали одинаковый модуль N и разные экспо-
ненты e
1
и e
2
. Если один пользователь посылает им некое циркулярное сообще-

Страницы