ВУЗ:
Составители:
157
их соединяют вместе и получают число. После этого числа заменяют
буквами в соответствии с таблицей.
Обратите внимание на то, что в этом примере мы каждую букву кодируем
двузначным числом. Это сделано для предотвращения неоднозначности.
Если бы мы пронумеровали буквы не по порядку, начиная с 1, т.е. А
соответствует 1, Б — 2 и.т
.д., то мы не смогли бы сказать, блок 12 обозначает
пару букв АБ или букву Л, двенадцатую букву алфавита. Конечно, для
кодирования можно использовать любые однозначные соответствия между
буквами и числами, например, ASCII–кодировку, что чаще всего и делается.
Продолжим наш пример. Мы выбираем p = 149, q = 157, вычисляем
23088)( =N
ϕ
. Теперь нужно выбрать число e, взаимно простое с
)(N
ϕ
.
Наименьшее простое, не делящее
)(N
ϕ
, равно 5. Положим e = 5. Зашифруем
первый блок сообщения. Вычисляем 2524
5
mod 23393 = 22752. Далее, 1723
5
mod 23393 = 6198
10199
5
mod 23393 = 14204,
9271
5
mod 23393 = 23191,
511
5
mod 23393 = 10723,
41
5
mod 23393 = 14065.
Теперь шифрованный текст имеет вид:
22752619814204231911072314065
В нашем примере N = 23393, e = 5. Применив алгоритм Эвклида к числам
23088)( =N
ϕ
и e = 5, найдем 1385323088mod
1
==
−
ed . Значит, для расшифровки
блоков шифртекста мы должны возвести этот блок в степень 13583 по
модулю 23393. В примере первый блок шифртекста — число 22752.
Вычисляем: 22752
13853
mod 23393 = 2524.
Разбиение числа на блоки можно произвести различными способами. При
этом промежуточные
результаты зависят от способа разбиения, однако
конечный
результат — не зависит.
Атаки на RSA
Для дешифрации необходимо по известным N, e и шифртексту y найти
такое
*))/(( NZx ∈ , что Nxy
e
mod= .
Можно попытаться решить сравнение при конкретных y, затем
использовать гомоморфность отображения D(x).
Один из возможных способов следующий. Пусть имеется набор пар
)},)...(,{(
11 kk
yxyx с условием Nyx
i
e
i
mod= . Пусть 1<y<N, (y,N) = 1. Если каким-
либо образом удалось представить y в виде:
Nyyy
k
s
k
s
mod...
1
1
⋅⋅= с целыми s
k
,
то
k
s
k
s
xxx ⋅⋅= ...
1
1
будет решением сравнения Nxy
e
mod= .
Пример 3. У нас есть в наличии открытый ключ N = 31459, e = 5 и набор
пар соответствующих друг другу исходных и зашифрованных сообщений:
(23,18707), (755,26871), (631,6384). Требуется расшифровать шифртекст y =
11638. Для этого представим y в виде
1163863842687118707
231
=⋅⋅=
−−
y . Отсюда
легко вычислить исходное сообщение:
2826063175523
231
=⋅⋅=
−−
x .
Страницы
- « первая
- ‹ предыдущая
- …
- 155
- 156
- 157
- 158
- 159
- …
- следующая ›
- последняя »
