ВУЗ:
Составители:
25
e и d, удовлетворяющих заданным условиям. Если сделать открытыми числа e и
n, а ключ d (и обязательно p и g) держать в секрете - то предложенная система
является RSA-криптосистемой открытого шифрования. Очевидно, ее стойкость
определяется сложностью операции извлечения из С корня степени е по моду-
лю n.
Рассмотрим основные этапы реализации алгоритма RSA.
1. Отправитель вычисляет n = p х q и M=(p-1)(q-1).
2.
Затем он выбирает случайное целое число e, взаимно простое с М и
вычисляет d, удовлетворяющее условию
ed = 1 (mod M).
Напомним, что два числа являются взаимно простыми, если их HOD
=1. Числа а и b имеют HOD d, если d делит и а и b и максимальный среди таких
чисел.
3. После этого он публикует е и n как свой открытый ключ шифрова-
ния, сохраняя
d, как закрытый (секретный) ключ.
4. Рассмотрим теперь числа e и d. Предположим, что мы знаем одно из
них и знаем соотношение, которым они связаны. Мы могли бы легко вычислить
второе число, однако мы не знаем чисел p и q. Следовательно можно одно из
чисел подарить кому-нибудь вместе с n и попросить его посылать нам сообще
-
ния следующим образом.
5. Сообщение представить как векторы (блоки) длины l
X= (x
1
,x
2
...,x
l
)
0<x
i
< M;
6. Каждое x
i
возвести в степень e по mod n.
7. Прислать нам Y=(x
1
e
(mod n), x
2
e
(mod n),...,x
l
e
(mod n)).
Обозначим t=y
i
=х
i
e
(mod n) и рассмотрим расшифрование полученной
информации.
Для этого возведем полученное число t в степень второго числа пары -
d:
R=t
d
(mod n) = x
e
(mod n)
d
(mod n) = x
ed
(mod n).
В соответствие с п.2 соотношение ed=1(mod M). а это означает, что ed-
1 делится нацело на (p-1)(q-1), т.е. ed=1+a(p-1)(q-1),
где а - целое число.
Утверждается, что
х
ed
(mod n) =x.
Действительно,
x
ed
(mod n) = x
1+a(p-1)(q-1)
(mod n)
Учитывая,что
x
p-1
= 1 mod p, x
q-1
= 1 mod q (эти соотношения доказываются как малая
теорема Ферма, например в /10/) получим
x
(p-1)(q-1)
= 1(mod pq)
x
1+a(p-1) (g-1)
(mod n) = x, т.к.
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
