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

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