только теорией, и чуть позже разработали алгоритм, позволяющий двум сторонам получить защищенный секретный ключ, используя незащищенный канал связи. Алгоритм заслужил положительные отзывы от криптографического коммьюнити, звучное и скромное название «алгоритм Диффи-Хеллмана» от своих авторов и непременную ложку дегтя от дотошных исследователей. В 1997 году выяснилось, что еще в 1974 году, то есть за два года до публикации Диффи и Хеллмана, британский математик Малькольм Вильямсон уже изобрел этот алгоритм38. Ничто не ново в этом мире. Все та же самая коммутативность показателей при возведении в степень. Но кто не успел – тот опоздал.
Алгоритм Диффи-Хеллмана начал свое революционное шествие в мире шифрования. И на первом же шаге споткнулся. Хотя протокол и снимал основную проблему классической криптографии – проблему распределения ключей, выяснилась одна его неприятная особенность. Он оказался уязвим к модификации данных в канале связи. То есть, без дополнительных средств аутентификации пользователи не могли быть уверены, кем именно сгенерирован их общий секретный ключ. Классическая проблема атаки «человек посередине».
Однако пытливый человеческий мозг, получив верное направление для размышлений, начал пытаться построить такую математическую функцию, которая сочетала бы в себе инновационность предложенного Диффи и Хеллманом решения с одной стороны, и была нечувствительна к атакам в канале связи – с другой. Как в истории с зайчиком, который пытался и морковку съесть, и об елку не уколоться. В этот раз зайчик родился в Массачусетском технологическом институте. Рональд Ривест, Ади Шамир и Леонард Адлеман из этого института перебрали более 40 различных вариантов алгоритмов. В итоге был сформулирован алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел. По давно сложившейся традиции, алгоритм был назван по первым буквам фамилий авторов – RSA (Rivest, Shamir, Adleman). И в августе 1977 года в журнале «Scientific American» было опубликовано первое описание криптосистемы RSA39. Описание опубликовал ведущий колонки «Математические игры» журнала Мартин Гарднер с любезного разрешения одного из соавторов, Рональда Риверста. Так как колонка в журнале была игровая, о чем недвусмысленно намекало и её название, то не обошлось без игры. Читателям было предложено расшифровать зашифрованную описываемым алгоритмом фразу:
9686 9613 7546 2206
1477 1409 2225 4355
8829 0575 9991 1245
7431 9874 6951 2093
0816 2982 2514 5708
3569 3147 6622 8839
8962 8013 3919 9055
1829 9451 5781 5154
В комплекте с исходными данными для расшифровки шли открытые параметры системы: n=1143816…6879541 (129 десятичных знаков, 425 бит) и e=9007. Бонусом победителю предлагалось 100 американских долларов, что для 1977 года было вполне серьезной суммой. Зашифрованная фраза была, разумеется, на родном для авторов
Singh Simon. The Code Book. Doubleday. – 1999. – pp. 279—292.
Gardner M. A New Kind of Cipher that Would Take Millions of Years to Break. // Sci. Amer. – New York City: Nature Publishing Group. – 1977. – Iss. 237. – P. 120—124. – ISSN 0036—8733.
