Книга шифров

В апреле 1977 года Ривест, Шамир и Адлеман отмечали еврейскую Пасху в студенческом общежитии колледжа и выпили значительное количество вина Манишевич, а где-то около полуночи отправились по домам. Ривест не мог уснуть и, лежа на кровати, читал учебник по математике. Непроизвольно он начал размышлять над вопросом, который занимал его уже много недель: можно ли создать асимметричный шифр? Существует ли односторонняя функция, которую можно было бы обратить, только если у получателя есть некая специальная информация? Внезапно туман в голове стал рассеиваться, и на него снизошло откровение. Остаток ночи он провел, формализуя свою идею, и, еще до того, как наступил рассвет, практически написал законченную научную статью. Ривест сделал открытие, но состоялось оно только благодаря длившемуся целый год сотрудничеству с Шамиром и Адлеманом, а без них оказалось бы невозможным. Закончил статью Ривест перечислением авторов в алфавитном порядке: Адлеман, Ривест, Шамир.

На следующее утро Ривест передал статью Адлеману, который, как обычно, постарался ее растерзать, но на сей раз он не смог найти ни одной ошибки. Единственно, он раскритиковал список авторов.

« Я попросил Рона, чтобы он убрал мое имя из статьи, — вспоминает Адлеман. — Я сказал ему, что это его открытие, а не мое. Но Рон отказался, и в результате завязался спор. Мы порешили, что я отправлюсь домой, поразмышляю над этим ночь и скажу, чего бы мне хотелось. На следующий день я вернулся и предложил Рону, чтобы он поставил меня третьим автором. Как мне сейчас вспоминается, тогда я думал, что эта статья будет самой неинтересной из всех, которые я когда-либо писал». Вряд ли Адлеман мог ошибиться сильнее. Алгоритм, получивший название RSA (Ривест, Шамир, Адлеман), а не ARS, стал важнейшим шифром в современной криптографии.

Перед тем как познакомиться с идеей Ривеста, напомним, что же искали ученые для создания асимметричного шифра:

(1) Алиса должна создать открытый ключ, который затем обнародует, так что Боб (и любой другой) смогут воспользоваться им, чтобы зашифровывать для нее сообщения. Поскольку открытый ключ является односторонней функцией, он должен быть таким, чтобы обратить эту функцию и расшифровать сообщения для Алисы не смог практически никто.

(2) Алисе, однако, необходимо расшифровывать присланные ей сообщения. Поэтому у нее должен иметься секретный ключ — некоторое количество специальной информации, которая позволит ей обратить действие открытого ключа. Тем самым Алиса (и лишь она одна) сумеет расшифровать все присланные ей сообщения.