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

Пусть абоненты А и В решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо друг от друга выбирает два различных больших простых числа, а именно,

A:

В:

Пусть

Абонент А выбирает случайное число такое, что НОД Абонент В выбирает случайное число такое, что НОД

Абонент А вычисляет такое, что Абонент B вычисляет такое, что

Затем А и В делают общедоступными следующие книги паролей:

A:

В:

Теперь можно отправлять конфиденциальные сообщения абонентам А или В.

Например, если пользователь книги паролей хочет отправить сообщение х для А, то он поступает следующим образом:

использует открытый ключ из книги паролей,

вычисляет

отправляет сообщение абоненту А.

Абонент А для дешифровки сообщения использует секретный ключ и вычисляет Используя теорему Эйлера, несложно проверить, что это и будет переданное сообщение х.

Корректность работы такой криптосистемы основана на том, что фактически требуется, чтобы НОД Но вероятность того, что случайно взятое число х не является таковым, ничтожна мала при больших значениях