Алгоритм Диффи-Хеллмана начал свое революционное шествие в мире шифрования. И на первом же шаге споткнулся. Хотя протокол и снимал основную проблему классической криптографии – проблему распределения ключей, выяснилась одна его неприятная особенность. Он оказался уязвим к модификации данных в канале связи. То есть, без дополнительных средств аутентификации пользователи не могли быть уверены, кем именно сгенерирован их общий секретный ключ. Классическая проблема атаки «человек посередине».

Однако пытливый человеческий мозг, получив верное направление для размышлений, начал пытаться построить такую математическую функцию, которая сочетала бы в себе инновационность предложенного Диффи и Хеллманом решения с одной стороны, и была нечувствительна к атакам в канале связи – с другой. Как в истории с зайчиком, который пытался и морковку съесть, и об елку не уколоться. В этот раз зайчик родился в Массачусетском технологическом институте. Рональд Ривест, Ади Шамир и Леонард Адлеман из этого института перебрали более 40 различных вариантов алгоритмов. В итоге был сформулирован алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел. По давно сложившейся традиции, алгоритм был назван по первым буквам фамилий авторов – RSA (Rivest, Shamir, Adleman). И в августе 1977 года в журнале «Scientific American» было опубликовано первое описание криптосистемы RSA39. Описание опубликовал ведущий колонки «Математические игры» журнала Мартин Гарднер с любезного разрешения одного из соавторов, Рональда Риверста. Так как колонка в журнале была игровая, о чем недвусмысленно намекало и её название, то не обошлось без игры. Читателям было предложено расшифровать зашифрованную описываемым алгоритмом фразу:

В комплекте с исходными данными для расшифровки шли открытые параметры системы: n=1143816…6879541 (129 десятичных знаков, 425 бит) и e=9007. Бонусом победителю предлагалось 100 американских долларов, что для 1977 года было вполне серьезной суммой. Зашифрованная фраза была, разумеется, на родном для авторов английском языке. Рональд Ривест оценивал время, необходимое на расшифровку этой фразы, в 40 квадриллионов лет.

С наскока решить предложенную головоломку и заработать приятную банкноту с портретом президента Франклина ни у кого не получилось. Интернет еще не изобрели, а круг вооруженных калькуляторами читателей печатной версии журнала «Scientific American» был не очень широк. Калькуляторы семидесятых годов особой мощностью тоже не отличались. Однако пытливые любители математики о стодолларовом призе не забыли. Через 16 лет после старта гонки за банкнотой, в сентябре 1993 года, был анонсирован международный проект распределенных вычислений, ставящий целью решить все-таки предложенную головоломку. Интернет уже появился, и, координируя свои действия с помощью сверхсовременной на тот момент электронной почты, 600 энтузиастов из 20 стран мира с воодушевлением взялись за работу. Были задействованы мощности 1600 компьютеров и других аппаратов, которые могли проводить хоть какое-то количество вычислений в единицу времени. Включая два факса. Через полгода шифр пал40. Зашифрованной фразой оказалась «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE» («Волшебные слова – это брезгливый ягнятник»). По причине девальвации к тому времени доллара, на купюру с изображением Франклина купить пива для всех 600 участников проекта не представлялось возможным. Банкнота была пожертвована в Фонд свободного программного обеспечения (Free Software Foundation). Видимо, штат фонда в то время был существенно меньше 600 человек, и банкнота была с благодарностью принята.