Метод получения цифровых подписей и криптосистем с открытым ключом

Представлен метод шифрования, обладающий новым свойством: публичное раскрытие ключа шифрования не приводит к раскрытию соответствующего ключа расшифрования. Это имеет два важных следствия: (1) для передачи ключей не требуются курьеры или другие защищённые средства, поскольку сообщение может быть зашифровано с использованием ключа шифрования, публично раскрытого предполагаемым получателем. Расшифровать сообщение может только он, поскольку лишь ему известен соответствующий ключ расшифрования. (2) Сообщение может быть «подписано» с использованием хранящегося в тайне ключа расшифрования. Любой может проверить эту подпись с помощью соответствующего публично раскрытого ключа шифрования. Подписи невозможно подделать, а подписавший не может впоследствии отрицать действительность своей подписи. Это имеет очевидные применения в системах «электронной почты» и «электронного перевода денежных средств». Сообщение шифруется путём представления его в виде числа M, возведения M в степень e, заданную публично, и вычисления остатка от деления результата на произведение n, также заданное публично, двух больших секретных простых чисел p и q. Расшифрование выполняется аналогично; используется лишь другая, секретная степень d, для которой e * d ≡ 1 (mod (p - 1) * (q - 1)). Безопасность системы отчасти основана на трудности факторизации опубликованного делителя n.