Теория информации

       

Криптосистема с открытым ключом


Первую и наиболее известную систему с открытым ключом разработали в 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, выбравший , и , получил шифрованное сообщение . Дешифровать .



Содержание раздела