Математические основы криптологии. Галуев Г.А. - 54 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

107
а ]1,1[
−
∈ nM взаимно просто с n, то
MnnM
de
=)(mod)](mod[,
что в свою очередь означает, что
MMED
nend
=
))((
),(),(
.
Действительно,
).(mod)(mod)](mod[ nMnnM
edde
=
Условие
))((mod1 nde
ϕ
≡⋅
означает, что
)(1 ntde
ϕ
+=⋅
для некоторого целого
t.
Тогда
1() ()
()
(mod ) (mod ) (mod )
[ (mod )](mod ),
ed tn tn
tn
M
nM nMM n
MM n n
ϕϕ
ϕ
+
=
=⋅ =
=
где
1)(mod1)(mod)](mod[)(mod
)()(
===
⋅
nnnMnM
ttnnt
ϕϕ
.
Значит
.)](mod1[)(mod MnMnM
de
=⋅=
⋅
При наличии )(n
ϕ
можно легко найти пару чисел е и d,
удовлетворяющих соотношению
)).((mod1 nde
ϕ
≡⋅
Для этого выбирается число
е взаимно простое с )(n
ϕ
, что
можно проверить с помощью алгоритма Евклида. Взаимная про-
стота нужна для разрешимости сравнения
))((mod1 nxe
ϕ
≡⋅
относительно неизвестного
х. Число х=d определяется с
помощью алгоритма Евклида, определяющего числа
d и t, удов-
летворяющие соотношению 1)(
=
⋅
−⋅ tnde
ϕ
, что и означает
справедливость сравнения
)).((mod1 nde
ϕ
≡⋅
При этом, сложность алгоритма Евклида не превосходит
][log0
2
n операций.
108
Все сказанное выше справедливо для произвольного цело-
го модуля
n. В алгоритме RSA модуль n есть произведение про-
стых чисел
p и q, т.е. n=p·q. Поэтому в данном случае
)1()1()(
−
⋅
−
= qpn
ϕ
и любое простое число e>max(p,q) будет
взаимно простым с
)(n
ϕ
, т.е. при выборе ключа зашифрования е
можно не применять алгоритм Евклида, а воспользоваться из-
вестными быстрыми тестами проверки числа
е на простоту.
Без знания простых сомножителей
p и q значение функции
)(n
ϕ
, а значит и ключей е и d определить очень трудно. Поэтому
если делать открытыми числа
e и n, а число d держать в секрете,
то нахождение
М из С сводится к трудной задаче извлечения
корня степени
е из числа С по модулю n. Это и означает, что ал-
горитм
RSA может быть использован для построения криптоси-
стемы с открытым ключом, т.е. системы открытого шифрования,
когда преобразование зашифрования
),( ne
E открыто, а преобра-
зование расшифрования
),( nd
D держится в секрете.
С учетом описанного выше алгоритма
RSA работу крипто-
системы с открытым ключом можно представить в виде сле-
дующей последовательности действий:
1. Пользователь выбирает два больших простых числа
p и q
и вычисляет два произведения
q
p
n
⋅
=
и
).1)(1()( −
−
=
qpn
ϕ
2. Затем пользователь выбирает случайное целое число е и
вычисляет число
d, удовлетворяющее условию
))((mod1 nde
ϕ
≡
⋅
,
т.е.
)).1)(1(mod(1
−
−
≡
⋅
qpde
3. После этого пользователь публикует другим пользовате-
лям числа
е и n как свой открытый ключ, сохраняя при этом
найденное число
d в секрете как закрытый ключ.
4. Если
М сообщение, длина которого определяется по зна-
чению выражаемого им целого числа, должна быть в интервале
от
1 до n, то оно преобразуется в шифровку с возвращением в
степень
е числа М по модулю n и отправляется получателю
(пользователю, который знает ключ
d)

Страницы