 |
|
Криптосистема с открытым ключом
Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir A.) и Л. Адлеман (Adleman L.). По их именам эта система получила название RSA.
Пусть абоненты 
и 
решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа ( 
, 
и 
, 
), находит их произведение ( 
и 
), функцию Эйлера от этого произведения ( 
и 
) и случайное число ( 
и 
), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, из уравнения 
находит 
( 
), а из уравнения 
находит 
( 
). Затем и печатают доступную всем книгу паролей вида:
Теперь кто-угодно может отправлять конфиденциальные сообщения или . Например, если пользователь книги паролей хочет отправить сообщение 
для ( должно быть меньшим , или делиться на куски, меньшие ), то он использует ключ из книги паролей для получения шифрованного сообщения 
по формуле 
, которое и отправляется . для дешифровки использует ключ в формуле 
, т.к. , следовательно, 
для некоторого целого 
и 
, т.к. 
по теореме Эйлера-Ферма. Доказано1) , что задача нахождения секретного ключа по данным из книги паролей имеет ту же сложность, что и задача разложения числа на простые множители.
Пример. Пусть для 
и 
, тогда 
, 
, 
, 
(из уравнения 
). Следовательно, запись в книге паролей для будет иметь вид 
. Если кто-то захочет отправить секретное сообщение 
, то он должен сначала превратить его в шифровку по формуле 
. Когда получит 
он дешифрует его по формуле 
.
Упражнение 49 Нужно послать секретные сообщения 25 и 2 для JB и 14 для CIA, используя следующие записи открытой книги паролей криптосистемы RSA:
JB: 77,7;CIA: 667,15.Упражнение 50 Пользователь системы RSA выбрал 
и 
. Какие из чисел 12, 33, 125, 513 он может выбрать для открытого ключа? Вычислить для них закрытый ключ.
Упражнение 51 Пользователь системы RSA, выбравший 
, 
и 
, получил шифрованное сообщение 
. Дешифровать .