Книга шифров

Во Второй мировой войне британские дешифровальщики одержали верх над немецкими шифровальщиками главным образом потому, что в Блечли-Парке, по примеру поляков, был разработан ряд технических средств для дешифрования сообщений противника. Помимо «бомб» Тьюринга, которые использовались для взлома шифра «Энигмы», англичане придумали и создали еще одно устройство, «Колосс», предназначенное для борьбы со значительно более стойким видом шифрования, а именно, с немецким шифром Лоренца. Из двух видов дешифровальных машин именно «Колосс» определил развитие криптографии во второй половине двадцатого столетия.

Шифр Лоренца использовался для связи между Гитлером и его генералами. Шифрование выполнялось с помощью машины Lorenz SZ40, которая действовала подобно «Энигме», но была намного сложнее, и из-за этого у дешифровальщиков в Блечли возникали огромные проблемы. Но все же двум дешифровальщикам, Джону Тилтману и Биллу Тьютте, удалось отыскать изъян в способе использования шифра Лоренца — то слабое место, которым сумели воспользоваться в Блечли и, благодаря этому, прочитать сообщения Гитлера.

Для дешифрования сообщений, зашифрованных шифром Лоренца, требовалось осуществлять перебор вариантов, сопоставлять их, проводить статистический анализ и на основании полученных результатов давать осторожную оценку, — ничего этого «бомбы» делать не могли. Они могли с огромной скоростью решать определенную задачу, но не обладали достаточной гибкостью, чтобы справиться с тонкостями шифра Лоренца. Зашифрованные этим шифром сообщения приходилось дешифровать вручную, что занимало недели кропотливых усилий, а за это время они по большей части уже устаревали. Со временем Макс Ньюмен, математик из Блечли, предложил способ, как механизировать криптоанализ шифра Лоренца.

В значительной степени позаимствовав концепцию универсальной машины Алана Тьюринга, Ньюмен спроектировал машину, которая была способна сама настраиваться на решение различных задач — то, что сегодня мы назвали бы программируемым компьютером.

Реализация конструкции Ньюмена считалась технически невозможной, так что руководство Блечли даже не стало рассматривать проект. По счастью, Томми Флауэрс, инженер, принимавший участие в обсуждении проекта Ньюмена, решил проигнорировать скептицизм Блечли и приступил к созданию такой машины. В исследовательском центре Управления почт и телеграфа в Доллис Хилл, в Северном Лондоне, Флауэрс взял чертежи Ньюмена и потратил десять месяцев, чтобы создать на его основе машину «Колосс», которую 8 декабря 1943 года передал в Блечли-Парк. Машина состояла из 1500 электронных ламп, которые действовали значительно быстрее медлительных электромеханических релейных переключателей, используемых в «бомбах». Но гораздо важнее скорости «Колосса» являлось то, что эту машину можно было программировать. Благодаря этому-то «Колосс» и стал предшественником современных цифровых ЭВМ.

После войны «Колосс», как и все остальное в Блечли-Парке, был демонтирован, а всем, кто так или иначе был связан с работой над «Колоссом», было запрещено даже упоминать о нем. Когда Томми Флауэрсу приказали уничтожить чертежи «Колосса», он послушно отнес их в котельную и сжег. Так были навсегда утрачены чертежи первого в мире компьютера. Такая секретность означала, что признание за изобретение компьютера получили другие ученые. В 1945 году Джон Преспер Эккерт и Джон Уильям Мочли в Пенсильванском университете завершили создание ЭНИАКа (электронного числового интегратора и компьютера), состоящего из 18 000 электронных ламп и способного выполнять 5000 вычислений в секунду. И в течение десятилетий именно вычислительная машина ЭНИАК, а не «Колосс», считалась прародительницей всех компьютеров.

Внеся вклад в рождение современного компьютера, криптоаналитики продолжали и после войны развивать компьютерные технологии и применять вычислительную технику для раскрытия любых видов шифров. Теперь они могли использовать быстродействие и гибкость программируемых компьютеров для перебора всех возможных ключей, пока не будет найден правильный ключ. Но время шло, и уже криптографы начали пользоваться всей мощью компьютеров для создания все более и более сложных шифров. Короче говоря, компьютер сыграл решающую роль в послевоенном поединке между шифровальщиками и дешифровальщиками.

Применение компьютера для зашифровывания сообщения во многом напоминает обычные способы шифрования. И в самом деле, между шифрованием с использованием компьютеров и шифрованием с использованием механических устройств, как, например, «Энигмы», существует всего лишь три основных отличия. Первое отличие состоит в том, что на деле можно построить механическую шифровальную машину только ограниченных размеров, в то время как компьютер может имитировать гипотетическую шифровальную машину огромной сложности. К примеру, компьютер мог бы быть запрограммирован так, чтобы воспроизвести действие сотен шифраторов, часть из которых вращается по часовой стрелке, а часть — против, некоторые шифраторы исчезают после каждой десятой буквы, а другие по ходу шифрования вращаются все быстрее и быстрее. Такую механическую машину в реальности изготовить невозможно, но ее виртуальный компьютеризованный аналог давал бы исключительно стойкий шифр.

Второе отличие заключается просто в быстродействии. Электроника может работать гораздо быстрее механических шифраторов; компьютер, запрограммированный для имитирования шифра «Энигмы», может вмиг зашифровать длинное сообщение. С другой стороны, компьютер, запрограммированный на использование существенно более сложного способа шифрования, по-прежнему способен выполнить свою задачу за приемлемое время.

Третье, и, пожалуй, наиболее существенное отличие — это то, что компьютер выполняет зашифровывание чисел, а не букв алфавита. Компьютеры работают только с двоичными числами — последовательностями единиц и нулей, которые называются двоичными знаками, или, для краткости, битами. Поэтому любое сообщение перед зашифровыванием должно быть преобразовано в двоичные знаки. Такое преобразование может выполняться в соответствии с различными протоколами, например, американским стандартным кодом для обмена информацией, широко известным как ASCII. В ASCII каждой букве алфавита сопоставляется число длиной 7 бит. Будем пока рассматривать двоичное число просто как последовательность единиц и нулей, которая однозначно определяет каждую букву (таблица 24), подобно тому, как в коде Морзе каждая буква обозначается своей последовательностью точек и тире. Существует 128 (2⁷) способов расположения 7 двоичных знаков, поэтому в ASCII можно определить до 128 различных символов. Этого вполне достаточно, чтобы задать все строчные буквы (например, а = 1100001), все необходимые знаки пунктуации (например, ! = 0100001), а также другие символы (например, & = 0100110). После того как сообщение будет переведено в двоичный вид, можно приступать к его зашифровыванию.

Хотя мы имеем дело с компьютерами и числами, а не с машинами и буквами, зашифровывание по-прежнему выполняется с помощью традиционных способов замены и перестановки, при которых элементы сообщения заменяются другими элементами, либо элементы сообщения меняются местами, либо оба эти способа применяются совместно. Любой процесс зашифровывания — неважно, насколько он сложен — можно представить как сочетание этих двух простых операций. В следующих двух примерах наглядно показывается, насколько просто можно осуществить компьютерное шифрование с помощью элементарного шифра замены и элементарного шифра перестановки.

Допустим, что мы хотим зашифровать сообщение HELLO с использованием простой компьютерной версии шифра перестановки. Перед тем как начать зашифровывание, мы должны вначале преобразовать сообщение в ASCII-код в соответствии с таблицей 24:

Открытый текст = HELLO = 1001000 1000101 1001100 1001100 1001111

Здесь можно было бы воспользоваться одним из простейших видов шифра перестановки и поменять местами первую и вторую цифры, третью и четвертую цифры, и так далее. В этом случае последняя цифра останется на своем месте, поскольку их количество нечетно. Чтобы было более понятно, я убрал пробелы между группами чисел, представляющих собой ASCII-код исходного открытого текста, записал их сплошной строкой, а затем, для наглядности, выровнял относительно получившегося шифртекста:

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

Так, например, если переставить седьмую и восьмую цифры, то поменяются местами последний 0 буквы H и первая 1 буквы E. Зашифрованное сообщение представляет собой сплошную строку из 35 двоичных цифр, которую можно передать получателю и из которой затем, путем обратной перестановки, можно воссоздать исходную строку двоичных цифр. После чего получатель преобразует двоичные цифры ASCII-кода и восстановит сообщение HELLO.

_{Таблица 24. ASCII-код двоичного представления заглавных букв}

Допустим, что теперь мы хотим зашифровать это же сообщение, HELLO, только на этот раз с помощью простой компьютерной версии шифра замены. Перед тем как приступить к зашифровыванию, мы вначале опять-таки преобразуем сообщение в ASCII-код. Как обычно, при замене используется ключ, который был согласован между отправителем и получателем. В нашем случае ключом будет слово DAVID, преобразованное в ASCII-код, которое используется следующим образом. Каждый элемент открытого текста «добавляется» к соответствующему элементу ключа. «Добавление» двоичных цифр может выполняться, исходя из двух простых правил. Если элементы в открытом тексте и в ключе одинаковы, то элемент в открытом тексте заменяется на 0 в шифртексте. Если же элементы в сообщении и в ключе различны, то элемент в открытом тексте заменяется на 1 в шифртексте:

Получающееся зашифрованное сообщение представляет собой сплошную строку из 35 двоичных цифр, которую можно передать получателю, а тот уже с помощью этого же ключа проведет обратную замену, вновь воссоздав исходную строку двоичных цифр. После чего получатель преобразует двоичные цифры ASCII-кода и восстановит сообщение HELLO.

Компьютерное шифрование ограничивалось только тем кругом лиц, у кого имелись компьютеры; первоначально это означало правительство и военных. Однако ряд научных открытий, и технологических и инженерных достижений сделали компьютеры и компьютерное шифрование гораздо более широко доступными. В 1947 году в компании AT&T Bell Laboratories был создан транзистор — дешевая альтернатива электронной лампе. Использование компьютеров для решения промышленных и коммерческих задач стало реальностью в 1951 году, когда такие компании, как Ферранти, начали изготавливать компьютеры на заказ. В 1953 году IBM выпустила свой первый компьютер, четыре года спустя она же представила Фортран — язык программирования, который позволил «обычным» людям писать компьютерные программы. А создание в 1959 году интегральных схем провозгласило новую эру компьютеризации.

В 60-х годах двадцатого века компьютеры стали более мощными и в то же время более дешевыми. Все больше и больше коммерческих компаний и промышленных предприятий могли позволить себе приобрести компьютеры и использовать их для зашифровывания важной информации, например, переводов денег или проведения щекотливых торговых переговоров. Однако по мере роста количества таких компаний и предприятий и в связи с тем, что шифрование между ними распространялось во все большей степени криптографы столкнулись с новыми сложностями, которых не существовало, когда криптография являлась прерогативой правительств и военных. Одним из первоочередных вопросов был вопрос стандартизации. В компании, для обеспечения безопасности внутренней связи, могла использоваться специфическая система шифрования, но с ее помощью нельзя было отправить секретное сообщение ни в какую другую организацию, если только получатель не пользовался той же самой системой шифрования. В итоге 15 мая 1973 года Американское Национальное бюро стандартов США наметило разрешить эту проблему и официально запросило предложения по стандартной системе шифрования, которая бы позволила обеспечить секретность связи между различными компаниями.

Одним из наиболее известных и признанных алгоритмов шифрования и кандидатом в качестве стандарта был продукт компании IBM, известный как Люцифер. Он был создан Хорстом Файстелем, немецким эмигрантом, приехавшим в Америку в 1934 году. Файстель уже вот-вот должен был получить гражданство США, когда Америка вступила в войну, что означало, что он находился под домашним арестом вплоть до 1944 года. После этого он еще несколько лет умалчивал о своем интересе к криптографии, чтобы не возбудить подозрений у американских властей. Когда же он в конце концов начал заниматься изучением шифров в Кембриджском научно-исследовательском центре ВВС США, то вскоре оказался под пристальным вниманием Агентства национальной безопасности (АНБ) — организации, отвечающей за обеспечение безопасности военной и правительственной связи, которая занималась также перехватом и дешифровкой иностранных сообщений. В АНБ работало больше математиков, она приобретала больше компьютерной техники и перехватывала больше сообщений, чем любая другая организация в мире. В общем, что касается совать нос в чужие дела, то тут оно является мировым лидером.

АНБ выдвигало обвинения не против прошлого Файстеля, оно просто хотело обладать монополией в области криптографических исследований, и, по-видимому, именно оно устроило так, что исследовательский проект Файстеля был закрыт. В 60-х годах Файстель перешел в компанию Mitre Corporation, но АНБ продолжало оказывать на него давление и вторично вынудило его бросить работу.

В конце концов Файстель оказался в исследовательской лаборатории Томаса Дж. Уотсона компании IBM неподалеку от Нью-Йорка, где в течение нескольких лет он мог без помех продолжать свои исследования. Там-то в начале 70-х он и создал систему Люцифер.

Люцифер зашифровывает сообщения следующим образом. Вначале сообщение преобразуется в длинную строку двоичных цифр. Далее эта строка разбивается на блоки из 64 цифр, и зашифровывание производится отдельно для каждого блока. Затем берется только один блок, 64 цифры этого блока перетасовываются, после чего его делят на два полублока, состоящих из 32 цифр и обозначаемых как Left⁰ и Right⁰. Потом к цифрам в полублоке Right⁰ применяется «функция обжима», которая сложным образом заменяет цифры. Затем «обжатый» полублок Right⁰ добавляется к полублоку Left⁰, образуя новый полу-блок из 32 цифр, который обозначается как Right¹. Производится переобозначение исходного полублока Right⁰ на Left¹. Данная последовательность операций называется раундом. Процесс повторяется во втором раунде, но начинается с новых полублоков, Left¹ и Right¹, и заканчивается полублоками Left² и Right², и так продолжается до тех пор, пока не будет выполнено 16 раундов. Процесс зашифровывания немного напоминает замешивание теста. Представьте себе длинный кусок теста в виде бруска с написанным на нем сообщением. Вначале этот длинный кусок делится на блоки длиной 64 см. Затем половинка одного из блоков подцепляется, обжимается, складывается пополам, добавляется к другой половине и растягивается, образуя новый блок. После чего процесс повторяется снова и снова, пока сообщение не станет основательно перемешанным. По завершении 16 циклов «замешивания» шифртекст отсылается; его расшифровка получателем производится точно так же, как и зашифровывание, но в обратном порядке.

Параметры «функции обжима» могут меняться; они определяются ключом, согласованным отправителем и получателем. Другими словами, одно и то же сообщение может быть зашифровано бесчисленным количеством различных способов в зависимости от того, какой был выбран ключ. Ключи, используемые в компьютерной криптографии, являются просто числами. Поэтому, чтобы выбрать ключ, и отправитель, и получатель должны просто договориться о числе. После этого для зашифровывания необходимо, чтобы отправитель ввел число-ключ и сообщение в Люцифер, который выдаст шифртекст. Получателю для расшифровывания требуется ввести в Люцифер это же самое число-ключ и шифртекст, после чего будет выдано исходное сообщение.

По всеобщему мнению Люцифер являлся одним из наиболее стойких, коммерчески доступных программных продуктов шифрования, вследствие чего он использовался рядом организаций. Казалось само собой разумеющимся, что эта система шифрования будет принята в качестве американского стандарта, но в работу Файстеля опять вмешалось АНБ. Люцифер оказался настолько стойким, что, будучи принятым в качестве стандарта шифрования, мог оказаться за пределами криптоаналитических возможностей АНБ; поэтому не удивительно, что АНБ не хотело видеть стандартом шифрования такой продукт, который они не смогут взломать. Ходили слухи, что АНБ, перед тем как разрешить принять Люцифер в качестве стандарта, пыталось ослабить один из его аспектов — сократить число возможных ключей.

Число возможных ключей является одним из решающих факторов, определяющих стойкость любого шифра. Криптоаналитик, стремящийся дешифровать зашифрованное сообщение, мог бы попытаться проверить все возможные ключи, и чем больше существует возможных ключей, тем больше времени придется затратить, чтобы найти правильный. Если существует всего 1 000 000 возможных ключей, то криптоаналитик мог бы воспользоваться мощным компьютером, чтобы найти верный, что заняло бы у него минуты, и тем самым дешифровать перехваченное сообщение. Однако, если число возможных ключей достаточно велико, отыскание правильного ключа становится практически невозможным. Если бы Люцифер стал стандартом шифрования, то АНБ хотело бы гарантировать, что в нем будет использоваться только ограниченное число ключей.

АНБ настаивало на том, чтобы число ключей составляло примерно 100 000 000 000 000 000 (или, иначе, 56 бит[26], поскольку это число состоит из 56 цифр, если записать его в двоичном представлении). Видимо, АНБ полагало, что такой ключ обеспечит безопасность для гражданских организаций и лиц, так как ни в одной гражданской организации нет достаточно мощного компьютера, способного проверить все возможные ключи за приемлемое время. Однако само АНБ, имеющее доступ к самым мощным в мире вычислительным ресурсам, сможет раскрыть такие сообщения. 56-битовый вариант шифра Люцифер Файстеля, получивший название DES (стандарт шифрования данных), был официально принят 23 ноября 1976 года. Четверть века спустя DES по-прежнему остается официальным американским стандартом шифрования.

Принятие DES решило проблему стандартизации, содействуя использованию коммерческими компаниями и промышленными предприятиями криптографии для обеспечения безопасности. К тому же DES обладал достаточной стойкостью, чтобы гарантировать защиту от атак со стороны торговых конкурентов. Для компании, имеющей обычный компьютер, практически невозможно было взломать зашифрованное с помощью DES сообщение, поскольку число возможных ключей было достаточно велико. Но несмотря на стандартизацию и стойкость DES, коммерческие компании и промышленные предприятия по-прежнему сталкивались с еще одной значительной проблемой, известной как проблема распределения ключей.

Представьте, что банк хочет передать определенную конфиденциальную информацию клиенту по телефонной линии, но обеспокоен тем, что кто-нибудь может подключиться к линии и перехватить сообщение. Банк выбирает ключ и использует DES, чтобы зашифровать информационное сообщение. Чтобы расшифровать сообщение, клиенту нужно не только иметь копию DES на своем компьютере, но также знать, какой ключ использовался для зашифровывания сообщения. Каким же образом банк может сообщить о ключе своему клиенту? Он не может выслать ключ по телефонной линии, поскольку подозревает, что на линии имеется подслушивающее устройство. Единственный, действительно безопасный способ передать ключ, — это вручить его лично, что, несомненно, требует времени. Менее безопасное, но более практичное решение — это передать ключ через курьера. В 70-х годах банки пытались передавать ключи, используя для этого специальных связных из числа наиболее доверенных служащих. Эти связные мчались через весь мир с запертыми на замок портфелями, лично доставляя ключи тем, кто должен будет получить сообщения от банка в течение следующей недели. По мере роста масштабов коммерческих сетей, передачи все большего числа сообщений и необходимости доставки все большего количества ключей, банки пришли к заключению, что процесс распределения превратился в ужасающий кошмар, а накладные расходы стали непомерно высоки.

Проблема распределения ключей беспокоила криптографов на протяжении всей истории. Так, во время Второй мировой войны немецкое Верховное командование должно было каждый месяц передавать книги с ключами текущего дня всем своим операторам «Энигмы», что представляло собой огромную проблему, связанную с осуществлением их доставки. Это же касалось и подводных лодок, которые длительное время находились вне своих баз, но должны были каким-то образом бесперебойно получать ключи. А прежде пользователи шифра Виженера должны были найти способ передать ключевое слово от отправителя к получателю. Неважно, насколько теоретически надежен шифр, на поверку его ценность может оказаться нулевой как раз из-за проблемы распределения ключей.

Правительство и вооруженные силы способны до известной степени справиться с проблемой распределения ключей, вкладывая в ее решение средства и ресурсы. Их сообщения настолько важны, что они не остановятся ни перед чем, чтобы обеспечить безопасность распределение ключей. Контролем и распределением ключей правительства США ведает COMSEC — сокращенное название подразделения, обеспечивающего безопасность передачи данных. В 70-х годах COMSEC отвечала за перевозку огромного количества ключей текущего дня. Когда корабли, перевозящие материалы COMSEC, швартовались у причала, сотрудники, ответственные за хранение криптоключей, поднимались на борт и забирали кипы перфокарт, бумажные перфоленты, дискеты и любые другие носители, на которых могли храниться ключи, доставляя их затем адресатам.

Распределение ключей может показаться рутинной задачей, но она стала важнейшей для послевоенных криптографов. Если две стороны хотят обеспечить безопасный обмен информацией, они вынуждены полагаться на третьего участника, который осуществляет доставку ключа, и это становится самым слабым звеном в цепи. Дилемма для коммерческих компаний и промышленных предприятий была проста: если правительства со всеми их деньгами изо всех сил пытаются обеспечить безопасность распределения ключей, то как могли гражданские компании даже хотя бы надеяться достичь надежного распределения ключей и при этом не разориться?

Несмотря на заявления, что проблема распределения ключей неразрешима, команда ярких личностей справилась с ней несмотря ни на что и в середине 70-х предложила блестящее решение. Они придумали систему шифрования, которая, казалось, попирала всякую логику. Хотя компьютеры неузнаваемо изменили применение шифров, разработка способов преодоления проблемы распределения ключей явилась поистине переворотом в криптографии двадцатого столетия. И это безусловно расценивается как величайшее криптографическое достижение с момента изобретения свыше двух тысячелетий назад одноалфавитного шифра.

Бог вознаграждает дураков

Уитфилд Диффи — один из криптографов-энтузиастов своего поколения. Внешний вид его поражает и создает отчасти противоречивый образ. Его безупречный костюм отражает тот факт, что большую часть 90-х годов он трудился в одной из американских компьютерных корпораций — ныне официально его должность звучит как «Заслуженный инженер компании Сан Микросистеме». В то же время его длинные, до плеч, волосы и белая бородка говорят о том, что сердце его принадлежит 60-м. Он проводит массу времени за компьютером, но выглядит так, словно столь же комфортно он чувствовал бы себя и в ашраме Бомбея. Диффи понимает, что его одежда и внешность вполне могут оказать влияние на других, и так комментирует это: «Люди всегда думают, что я выше, чем я есть на самом деле, но я говорю, что это — «эффект тигра»: неважно, сколько он весит фунтов и унций; из-за своих прыжков он всегда кажется крупнее».

Диффи родился в 1944 году и большую часть детства жил в Куинсе, одном из районов Нью-Йорка. Еще ребенком он увлекся математикой, читая все подряд от «Сборника математических таблиц для компаний по производству синтетического каучука» до «Курса чистой математики» Г. Х. Харди. Он продолжил ее изучение в Массачусетском технологическом институте, который окончил в 1965 году. И к началу 70-х годов, поработав в нескольких местах, стал одним из нескольких полностью независимых экспертов по безопасности, свободным криптографом, не состоящим на службе у правительства или каких-либо крупных корпораций. Оглядываясь назад, можно сказать, что он был первым шифрпанком[27].

_{Рис. 62. Уитфилд Диффи}

Диффи особенно интересовался проблемой распределения ключей, и он понял, что тот, кому удастся найти решение, войдет в историю как один из самых величайших криптографов. Диффи настолько захватила проблема распределения ключей, что в его специальной записной книжке появилась даже запись «Задачи для величественной теории криптографии». Отчасти Диффи занялся этой проблемой еще и потому, что в воображении ему виделся мир, весь опутанный проводами. Еще в 60-е годы министерство обороны США стало финансировать организацию, занимающуюся самыми современными и перспективными исследованиями — Управление перспективных исследований[28] (ARPA), и одна из задач, стоящих перед Управлением, заключалась в том, чтобы найти способ объединить компьютеры военного назначения, находящиеся на значительных расстояниях друг от друга. Это позволило бы в случае повреждения или выхода из строя какого-либо компьютера передать решаемые им задачи другому компьютеру в сети. Основной целью являлось создание более надежной и стойкой к ядерному удару инфраструктуры имеющихся в Пентагоне компьютеров, но эта сеть также позволила бы ученым пересылать друг другу сообщения и выполнять вычисления, используя резервные мощности удаленных компьютеров. Сеть ARPANet была создана в 1969 году, а к концу этого же года четыре рабочих места уже стали объединены. ARPANet постоянно расширялся, и в 1982 году на ее основе появился Интернет. В конце 80-х доступ к Интернету получили пользователи, не являющиеся сотрудниками учебных заведений и правительственными служащими; с этого момента число пользователей стало быстро возрастать. Сегодня более сотни миллионов людей используют Интернет для обмена информацией и отправки сообщений по электронной почте.

Еще когда ARPANet пребывал во младенческом возрасте, Диффи оказался достаточно прозорлив, чтобы предсказать появление информационной «супермагистрали» и того, что произойдет цифровая революция. В один прекрасный день у обычных людей появятся собственные компьютеры, и эти компьютеры будут соединены между собой по телефонным линиям. Диффи был убежден, что если люди будут пользоваться своими компьютерами для обмена сообщениями по электронной почте, то они должны обладать правом зашифровывать их для обеспечения секретности переписки. Однако для зашифровывания требуется безопасный обмен ключами. Если даже правительства и крупные корпорации испытывали трудности с распределением ключей, то население сочло бы это попросту невозможным и фактически оказалось бы лишено права на приватность.

Диффи представил себе, что двое незнакомых людей встретились в Интернете, и задался вопросом, как они могли бы послать друг другу зашифрованное сообщение? А если человек захочет приобрести товары через Интернет? Каким образом он мог бы передать по электронной почте письмо с зашифрованными данными своей кредитной карточки так, чтобы только продавец интернет-магазина смог расшифровать их? По всему выходило, что обоим участникам и в первом, и во втором случае следует пользоваться ключом, но как можно было бы обменяться ключами безопасным образом?

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

В 1974 году Диффи, тогда еще странствующий криптограф, посетил исследовательскую лабораторию Томаса Дж. Уотсона компании 1ВМ, где его попросили сделать доклад. Его выступление касалось различных стратегий решения задачи распределения ключей, но все его идеи были чисто умозрительными, и настроение аудитории было скептическим. Единственный положительный отзыв на доклад Диффи был дан Аланом Конхеймом, одним из старших экспертов по криптографии компании IВМ, упомянувшим, что кто-то не так давно приезжал в лабораторию и прочел лекцию, посвященную проблеме распределения ключей. Тем докладчиком был Мартин Хеллман, профессор Стэнфордского университета в Калифорнии. В тот же вечер Диффи сел в свой автомобиль и отправился на западное побережье, за 5000 км, чтобы встретиться с единственным человеком, который, похоже, как и он, разделял его увлеченность. Союз Диффи и Хеллмана станет одним из самых плодотворных в криптографии.

Мартин Хеллман родился в 1945 году в еврейском квартале Бронкса, но, когда ему исполнилось четыре года, его семья переехала в другой район, где жили преимущественно ирландцы-католики. Как говорил Хеллман, это навсегда изменило его отношение к жизни: «Другие дети ходили в церковь, и там они узнали, что евреи убили Христа; из-за этого меня звали «Христоубийцей» и нередко били. Сначала мне хотелось быть таким же, как и другие дети: хотелось, чтобы у меня была рождественская елка и рождественские подарки. Но потом я понял, что таким же я быть не смогу, и тогда, в целях самозащиты, я занял позицию «а кому хочется быть похожим на других?» Свой интерес к шифрам Хеллман относит на счет стремления быть не похожим на других. Его коллеги говорили ему, что он сошел с ума, решив заняться исследованиями по криптографии, потому что его конкурентом будет АНБ с его многомиллиардным бюджетом. Как мог он надеяться найти что-то, чего им еще не было известно? А если даже он что-нибудь и обнаружит, АНБ тут же это засекретит.

Когда Хеллман приступил к исследованиям, он наткнулся на книгу «Взломщики кодов» историка Дэвида Кана. В этой книге впервые подробно рассказывается о развитии шифров, и в этом качестве она являлась прекрасным учебником для начинающих криптографов. «Взломщики кодов» была единственным помощником Хеллмана вплоть до сентября 1974 года, когда ему неожиданно позвонил Уитфилд Диффи, только что пересекший весь континент, чтобы встретиться с ним. Хеллман никогда прежде не слышал о Диффи и с неохотой согласился уделить ему полчаса попозже днем. Но к концу встречи Хеллман понял, что Диффи был самым знающим человеком, которого он когда-либо встречал. И это чувство было обоюдным. Как вспоминает Хеллман: «Я пообещал своей жене, что буду дома, чтобы присмотреть за детьми, поэтому он пошел со мной, и мы вместе пообедали. Он уехал где-то за полночь. Мы совершенно разные, он гораздо больше нигилист, чем я, но в конечном счете наше несходство пошло нам обоим только на пользу. Для меня это оказалось словно глоток свежего воздуха. Работать «в вакууме» было поистине тяжело».

Поскольку Хеллману не выделяли значительных средств, у него не было возможности нанять на работу своего нового единомышленника в качестве исследователя. Вместо этого Диффи был зачислен как аспирант. Теперь уже они вместе, Хеллман и Диффи, приступили к изучению проблемы распределения ключей, отчаянно пытаясь найти альтернативу неинтересной задаче физической перевозки ключей на большие расстояния. Через некоторое время к ним присоединился Ральф Меркль, сбежавший из другой исследовательской группы, руководитель которой не выражал никакой симпатии к неосуществимой мечте решить проблему распределения ключей. Говорит Хеллман:

В целом, проблема распределения ключей является классическим парадоксом. Если два человека хотят обменяться секретным сообщением по телефону, отправитель должен его зашифровать. Чтобы зашифровать секретное сообщение, отправитель должен воспользоваться ключом, который сам является секретом, поэтому возникает проблема передачи секретного ключа получателю, чтобы передать секретное сообщение. Короче говоря, до того, как два человека смогут передать друг другу секрет (зашифрованное сообщение), оба они уже должны обладать этим секретом (ключом).

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

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

_{Рис. 63 Мартин Хеллман}

Представьте себе, что Алиса и Боб живут в стране, в которой почтовая система совершенно аморальна и почтовые служащие читают всю незащищенную корреспонденцию. В один прекрасный день Алиса хочет отправить очень личное сообщение Бобу. Она кладет его в железную коробку, закрывает ее и запирает ключом замок. Затем она кладет запертую на замок коробку в почтовый ящик, а ключ оставляет себе. Но когда коробку доставляют Бобу, он не может открыть ее, так как у него нет ключа. Алиса может положить ключ в другую коробку, замкнуть ее на замок и отправить Бобу, но без ключа ко второму замку он не сможет открыть вторую коробку и достать оттуда ключ, которым откроет первую коробку. Для Алисы, по-видимому, единственный путь обойти эту проблему — это сделать дубликат своего ключа и заранее передать его Бобу, когда они встретятся за чашечкой кофе. До этого момента я просто переформулировал ту же старую задачу в новых условиях. Избежать распределения ключей кажется логически невозможным; если Алиса хочет запереть что-то в коробке так, чтобы только Боб мог открыть ее, она, безусловно, должна дать ему дубликат ключа. Или, на примере криптографии, если Алиса хочет зашифровать сообщение таким образом, чтобы только Боб мог расшифровать его, она должна передать ему копию ключа. Обмен ключами является неизбежной частью шифрования — или все-таки нет?

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

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

Кажется, что проблема распределения ключей может быть решена, поскольку в схеме с двойным зашифровыванием не требуется обмена ключами. Существует, однако, фундаментальное препятствие реализации системы, при которой Алиса зашифровывает, Боб зашифровывает, Алиса расшифровывает и Боб расшифровывает. Проблема состоит в том, в каком порядке выполняются зашифровывания и расшифровывания. Вообще говоря, порядок зашифровывания и расшифровывания является принципиальным и должен подчиняться принципу «последним пришел, первым ушел». Другими словами, последний этап при зашифровывании должен быть первым этапом при расшифровывании. В вышеприведенной же последовательности действий последним выполнял зашифровывание Боб, и поэтому при расшифровывании этот этап должен выполняться первым, но первой убирала свое шифрование Алиса — до того, как это сделал Боб. Важность порядка выполнения действий проще всего понять путем проверки чего-то такого, что мы выполняем каждый день. Утром мы надеваем носки, а затем ботинки, а вечером сначала снимаем ботинки, и только потом носки — не удастся снять носки раньше ботинок. Мы обязаны подчиняться принципу «последним пришел, первым ушел».

Некоторые самые элементарные шифры, такие как шифр Цезаря, являются настолько простыми, что порядок неважен. Однако в 70-х годах казалось, что любая форма стойкого шифрования должна подчиняться правилу «последним пришел, первым ушел». Если сообщение зашифровано ключом Алисы, а затем ключом Боба, то его необходимо вначале расшифровывать ключом Боба, а только потом — ключом Алисы. Порядок является критичным даже с одноалфавитным шифром замены. Представьте, что у Алисы и Боба имеются свои собственные ключи, как показано на следующей странице, и давайте взглянем, что случится, если порядок неправильный. Алиса использует свой ключ, чтобы зашифровать сообщение Бобу, затем Боб повторно зашифровывает то, что получилось, используя свой ключ; Алиса пользуется своим ключом, чтобы провести частичную расшифровку, и наконец, Боб своим ключом старается полностью расшифровать сообщение.

В результате получается бессмыслица. Вы можете, однако, сами проверить, что если расшифровывание будет производиться в обратном порядке — вначале Бобом, а затем Алисой, — то есть соблюдаться правило «последним пришел, первым ушел», то в результате будет получено исходное сообщение. Но если порядок настолько важен, то почему же, казалось бы, работала система с замками в шуточной истории о запертых коробках? Ответ заключается в том, что при использовании замков порядок неважен. Я могу навесить на коробку двадцать замков и отпирать их в любом порядке — в конце коробка будет открыта. К сожалению, системы шифрования в том, что касается порядка, оказываются гораздо более чувствительными, чем замки.

Несмотря на то что на практике принцип запертой на два замка коробки работать не будет, он вдохновил Диффи и Хеллмана на поиск способа, позволяющего избежать проблемы распределения ключей. Месяц за месяцем они старались найти решение. Хотя все предположения оканчивались ничем, они вели себя словно форменные дураки и настойчиво продолжали поиски. В своих исследованиях они занялись проверкой различных математических функций. Функция — это любая математическая операция, которая преобразует одно число в другое число. Например, «удвоение» представляет собой один из видов функции, поскольку с ее помощью число 3 превращается в число 6, а число 9 — в 18. Более того, мы можем рассматривать все виды компьютерного шифрования как функции, так как с их помощью одно число (открытый текст) преобразуется в другое число (шифртекст).

Большинство математических функций относится к двусторонним функциям, поскольку их легко применять при вычислениях в прямом и обратном направлении. К примеру, «удваивание» является двусторонней функцией, поскольку с ее помощью можно без труда образовать новое число, вдвое увеличив исходное число, и так же просто применить функцию в обратном направлении и вернуться от удвоенного к исходному числу. Так, если мы знаем, что результатом удваивания является число 26, то совершенно очевидно, что, чтобы найти исходное число — 13, следует применить данную функцию в обратном направлении. Самый простой способ понять, что такое двусторонняя функция, — это рассмотреть ее на примере повседневной деятельности. Включение освещения является функцией, так как при этом загорается лампочка. Эта функция — двусторонняя, поскольку если выключатель включен, то его легко и выключить, погасив тем самым горящую лампочку.

Но Диффи и Хеллман не интересовались двусторонними функциями. Они обратили свое внимание на односторонние функции. Как следует из названия, одностороннюю функцию легко вычислить в прямом направлении, но очень сложно в обратном. Другими словами, двусторонние функции обратимы, а односторонние функции необратимы. И опять-таки самый простой способ показать, что такое односторонняя функция, — это рассмотреть ее на примере повседневной деятельности. Смешивание желтой и синей красок для получения зеленой краски является односторонней функцией, поскольку краски смешать несложно, но вот разделить их после этого снова на исходные невозможно. Односторонней функцией также будет разбивание яйца: разбить яйцо легко, но вернуть его в исходное состояние уже невозможно. Из-за этого односторонние функции иногда называются функциями Шалтай-Болтая.

Модулярная арифметика, иногда в школе называемая арифметикой, оперирующей с абсолютными значениями чисел, является разделом математики, который богат односторонними функциями. В модулярной арифметике математики имею дело с циклически замкнутыми конечными группами чисел, подобно числам на циферблате часов. Например, на рис. 64 показан циферблат часов с модулем 7, на котором имеется только 7 цифр от 0 до 6. Чтобы вычислить 2 + 3 по модулю 7 (или mod 7), мы возьмем в качестве отправной точки 2 и передвинемся на 3 позиции, получив в результате 5, то есть получим тот же самый ответ, что и в обычной арифметике. Чтобы вычислить 2 + 6 по модулю 7, мы возьмем в качестве начальной точки 2 и передвинемся на 6 позиций, но на сей раз мы обойдем весь циферблат и окажемся на 1, а это уже не тот результат, который мы получили бы в обычной арифметике. Эти результаты могут быть выражены в следующем виде:

2 + 3 = 5 (mod 7) и 2 + 6 = 1 (mod 7)

Модулярная арифметика сравнительно проста, и на самом деле мы пользуемся ею ежедневно, когда говорим о времени. Если сейчас 9 часов, а у нас назначена встреча, которая состоится через 8 часов, мы скажем, что встреча произойдет в 5, а не в 17 часов.

Мы в уме сосчитали 9 + 8 по (mod 12). Представьте себе, циферблат часов, посмотрите на 9, а затем отсчитайте 8 делений, и вы остановитесь на 5:

9 + 8 = 5 (mod 12)

Математики, вместо того чтобы представлять себе циферблаты на часах, часто выбирают кратчайший путь, выполняя модулярные вычисления следующим образом. Вначале вычисление проводится по правилам обычной арифметики. Затем, если мы хотим узнать ответ по (mod x), мы делим результат, полученный на предыдущем этапе, на x и записываем остаток. Этот остаток и является ответом по (mod x). Чтобы найти ответ в примере 11 x 9 (mod 13), мы поступим следующим образом:

11 x 9 = 99

99 + 13 = 7, остаток 8

11 x 9 = 8 (mod 13)

Функции, с которыми работают в модулярной арифметике, ведут себя хаотичным образом, что, в свою очередь, иногда делает их односторонними функциями. Это становится очевидным, если сравнить простую функцию в обычной арифметике с этой же простой функцией, но в модулярной арифметике. В первой арифметике данная функция будет двусторонней и легко вычисляемой в обратном направлении; во второй арифметике она станет односторонней, и обратные вычисления провести будет сложно. В качестве примера возьмем функцию 3^x. Это означает следующее: взять число x, а затем умножить 3 само на себя x раз, в результате получится новое число. Например, если x = 2, и мы выполняем функцию, тогда:

3^x = З² = 3 x 3 = 9.

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

Например, если результат равен 81, мы можем установить, что x равно 4, потому что 3⁴ =_81. Если мы ошибемся и предположим, что x равно 5, путем вычисления мы можем определить, что 3⁵ = 243, а это подскажет нам, что мы выбрали слишком большое значение x. После этого мы уменьшим x до 4 и получим правильный ответ. Короче говоря, даже когда наше предположение неверно, мы можем исправить свою ошибку и получить точное значение x, выполнив тем самым обратное преобразование функции.

Однако в модулярной арифметике эта же самая функция ведет себя не так благоразумно. Представьте, что нам сообщают, что 3^x по модулю 7 (mod 7) дает 1, и просят найти значение x. В голову ничего не приходит, поскольку мы, как правило, не знакомы с модулярной арифметикой. Мы можем предположить, что x = 5, и мы можем вычислить З⁵ (mod 7). В ответе получится 5, что слишком много, так как нам нужно, чтобы в ответе было 1. Напрашивается желание уменьшать значения x. Но так мы будем двигаться неверным путем, поскольку в действительности ответ будет x = 6.

_{Рис. 64 Модулярная арифметика выполняется на конечном множестве чисел, которые можно рассматривать как числа на циферблате часов. В этом случае мы можем вычислить 6 + 5 по модулю 7, если взять в качестве исходной точки 6 и отсчитать 5 делений, в результате чего мы окажемся на цифре 4.}

В обычной арифметике мы можем проводить проверку чисел и в состоянии понять, движемся ли мы в нужном направлении или выбранное направление неверно. Модулярная арифметика не дает нам

таких путеводных нитей, и выполнять обратное преобразование функции гораздо труднее. Зачастую, единственный способ выполнить обратное преобразование функции в модулярной арифметике — это составить таблицу, вычисляя значение функции для множества значений x, пока не будет найден нужный ответ. В таблице 25 показан результат вычисления нескольких значений функции для обычной и для модулярной арифметики. Здесь ясно видно хаотическое поведение функции, когда расчеты проводятся в модулярной арифметике. До тех пор пока мы имеем дело со сравнительно небольшими числами, составление такой таблицы лишь слегка утомительно, но как же мучительно тягостно создавать таблицу, если имеешь дело с такой, к примеру, функцией, как 453^x (mod 21 997). Это классический пример односторонней функции, так как я могу выбрать значение для x и вычислить результирующее значение функции, но если я сообщу вам значение функции, скажем, 5787, у вас возникнут огромные трудности при обратном преобразовании функции и вычислении выбранного мною значения x. Чтобы провести вычисления и получить число 5787, мне понадобится лишь несколько секунд, вам же потребуются многие часы, чтобы составить таблицу и найти мое x.

_{Таблица 25 Вычисленные значения функции 3^x в обычной арифметике (ряд 2) и модулярной арифметике (ряд 3). В обычной арифметике функция растет непрерывным образом, в модулярной арифметике ее поведение крайне хаотично.}

Спустя два года исследований в области модулярной арифметики и односторонних функций, «глупость» Хеллмана начала приносить плоды. Весной 1976 года он натолкнулся на алгоритм решения проблемы обмена ключами. За полчаса исступленной работы он доказал, что Алиса и Боб могут договориться о ключе, не встречаясь друг с другом, покончив, тем самым, с аксиомой, считавшейся непререкаемой в течение столетий. Идея Хеллмана основывалась на использовании односторонней функции вида Y^x (mod P). Вначале Алиса и Боб договариваются о значениях чисел Y и P. Подходят почти любые значения за исключением некоторых ограничений; так, например, Y должно быть меньше, чем P. Эти значения несекретны, так что Алиса может позвонить Бобу и предложить, скажем, Y = 7 и P = 11. Даже если телефонная линия ненадежна и подлая Ева слышит этот разговор, это, как мы увидим позже, не имеет значения. Алиса и Боб договорились об односторонней функции T^x (mod 11). Сейчас они уже могут начать процесс создания секретного ключа. Поскольку их работа идет параллельно, я объясню их действия в двух колонках таблицы 26.

_{Таблица 26 Общей односторонней функцией является Yx (mod P). Алиса и Боб выбрали значения для Y и P и тем самым договорились об односторонней функции 7^x (mod 11).}

Внимательно изучив этапы в таблице 26, вы увидите, что и не встречаясь Алиса и Боб договорились об одном и том же ключе, который они могут использовать для зашифровывания сообщения. Например, они могут использовать свое число 9 в качестве ключа для DES-шифрования. (В действительности, в DES применяются в качестве ключа гораздо большие числа, и процесс обмена, описанный в таблице 26, будет выполняться с гораздо большими числами, соответственно давая в результате большой ключ DES.) Воспользовавшись схемой Хеллмана, Алиса и Боб смогли договориться о ключе; им не пришлось встречаться, чтобы шепотом сообщить этот ключ друг другу. Исключительность достижения состоит в том, что секретный ключ был создан путем обмена информацией по обычной телефонной линии. Но если Ева подключилась к этой линии, то будет ли также и она знать ключ?

Проверим схему Хеллмана с позиции Евы. Если она подключилась к линии, ей станут известны только следующие факты: что функцией является Т^x(mod 11), что Алиса отправила α = 2 и что Боб отправил β = 4. Чтобы определить ключ, она должна сделать либо то, что делает Боб, который, зная В, преобразует в ключ α, либо то, что делает Алиса, которая, зная А, преобразует в ключ β.

Однако Ева не знает, чему равны А и В, потому что Алиса и Боб не обменивались значениями этих чисел, держа их в секрете. Ева находится в безвыходном положении. У нее есть только одна надежда: теоретически, так как функция ей известна, она могла бы вычислить А из α, поскольку а представляет собой результат подстановки в нее А, или же она могла бы вычислить В из β, поскольку β представляет собой результат подстановки в нее В. К сожалению для Евы, эта функция является односторонней, так что хотя для Алисы преобразовать А в α, а для Боба — В в β не представляет сложности, Ева сможет выполнить обратное преобразование с огромным трудом, особенно в случае очень больших чисел.

Боб и Алиса передали друг другу ровно столько информации, сколько нужно, чтобы дать им возможность создать ключ, но Еве для вычисления ключа ее оказывается недостаточно. Чтобы показать, как работает схема Хеллмана, представьте шифр, в котором в качестве ключа каким-то образом используется цвет. Допустим вначале, что у всех, включая Алису, Боба и Еву, имеется трехлитровая банка, в которую налит один литр желтой краски. Если Алиса и Боб хотят договориться о секретном ключе, они добавляют в свои банки по одному литру своей собственной секретной краски. Алиса может добавить краску фиолетового оттенка, а Боб — малинового. После этого каждый из них посылает свою банку с перемешанным содержимым другому. И наконец, Алиса берет смесь Боба и подливает в нее один литр своей секретной краски, а Боб берет смесь Алисы и добавляет в нее один литр своей секретной краски. Краска в обеих банках теперь станет одного цвета, поскольку в каждой находится по одному литру желтой, фиолетовой и малиновой краски. Именно этот цвет, полученный при добавлении дважды в банки красок, и будет использоваться как ключ. Алиса понятия не имеет, какую краску добавил Боб, а Боб также не представляет, какую краску налила Алиса, но оба они достигли одного и того же результата. Между тем Ева в ярости. Даже если она и сумеет перехватить банки с промежуточным продуктом, ей не удастся определить конечный цвет, который и будет согласованным ключом. Ева может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Алисы в банке, отправленной Бобу, и она может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Боба в банке, отправленной Алисе, но чтобы найти ключ, ей, на самом деле, необходимо знать цвета исходных секретных красок Алисы и Боба. Однако, рассматривая банки с перемешанными красками, Ева не сможет определить секретные краски Алисы и Боба. Даже если она возьмет образец одной из смешанных красок, ей не удастся разделить ее на исходные краски, чтобы найти секретную, поскольку смешивание краски является односторонней функцией.

Озарение снизошло на Хеллмана глубокой ночью, так что, когда он закончил расчеты, было уже слишком поздно, чтобы звонить Диффи и Мерклю. Ему пришлось ждать утра, когда он смог продемонстрировать свое открытие двум единственным в мире людям, кто верил в возможность решения проблемы распределения ключей. «Осенило меня, — говорит Хеллман, — но в разработке принципов участвовали мы все вместе». Диффи сразу же осознал всю мощь открытия Хеллмана: «Марти объяснил свою систему обмена ключами во всей ее простоте. Когда я слушал его, то понял, что ка-кое-то время эта идея крутилась и у меня в голове, но так и не выкристаллизовалась».

Как известно, схема обмена ключами Диффи-Хеллмана-Меркля дает возможность Алисе и Бобу установить секретную переписку посредством открытых переговоров. Это было одно из самых алогичных открытий в истории науки, вынудившее криптографический истэблишмент переработать правила шифрования. Диффи, Хеллман и Меркль во всеуслышание сообщили о своем открытии на национальной компьютерной конференции в июне 1976 года, чем поразили аудиторию, состоящую из экспертов по криптографии и криптоанализу. На следующий год они подали заявку на патент. Впредь Алисе и Бобу больше не было нужды встречаться, чтобы обменяться ключом. Вместо этого Алиса могла просто позвонить Бобу по телефону, обменяться с ним парой чисел, сообща создать секретный ключ, а затем приступить к зашифровыванию.

Хотя обмен ключами Диффи-Хеллмана-Меркля оказался гигантским шагом вперед, сама система была несовершенной, поскольку по своей сути оказалась неудобной. Представим, что Алиса живет на Гавайях и хочет послать сообщение по электронной почте Бобу, живущему в Стамбуле. Боб в этот момент, возможно, спит, но электронная почта удобна тем, что Алиса может послать сообщение в любой момент и оно будет находиться в компьютере Боба, ожидая, пока он не проснется. Однако, если Алиса желает зашифровать свое сообщение, то ей нужно согласовать ключ с Бобом, а чтобы осуществить обмен ключами, для Алисы и Боба лучше одновременно находиться в режиме онлайн, так как для создания ключа требуется обоюдный обмен информацией. Так что Алисе придется ждать, пока проснется Боб. Как вариант, Алиса могла бы отправить свою часть и ожидать 12 часов ответа Боба; при получении ответа Боба ключ будет создан, и Алиса сможет, если сама не будет спать в это время, зашифровать и отправить сообщение. Так или иначе, но система обмена ключами Хеллмана затрудняет непринужденное общение по электронной почте.

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

Мэри Фишер никогда не забудет тот день, когда Уитфилд Диффи впервые пригласил ее на свидание: «Он знал, что я была фанатично предана космосу, и поэтому предложил пойти посмотреть на запуск ракеты. Уит объяснил, что сегодня вечером он ушел, чтобы увидеть старт Скайлэба, и мы ехали всю ночь и прибыли туда примерно в 3 утра. Как в те дни говорили, «птичка уже летела к нам». У Уита было удостоверение представителя прессы, но у меня его не было. Поэтому, когда потребовали мое удостоверение личности и спросили, кто я такая, Уит ответил: «Моя жена». Это было 16 ноября 1973 года». В конце концов, они действительно поженились, и в первые годы Мэри поддерживала мужа во время его криптографических раздумий. Диффи все еще работал в качестве аспиранта, получая скудное жалованье. И чтобы свести концы с концами, Мэри, археолог по образованию, нанялась на работу в Бритиш Пертолеум.

Когда Мартин Хеллман открыл свой метод обмена ключами, Уитфилд Диффи разрабатывал совершенно иной подход к решению проблемы распределения ключей. У него часто случались долгие периоды бесплодных раздумий во время одного из которых, в 1975 году, он был настолько расстроен, что уверял Мэри, что он неудачник, который никогда ничего не добьется, и даже предложил ей найти кого-нибудь другого. Но в ответ Мэри возразила, что она беспредельно верит в него, а спустя всего лишь две недели Диффи предложил поистине блестящую идею.

Он до сих пор вспоминает, как идея мелькнула у него в голове, а затем чуть было не исчезла: «Я спускался вниз по лестнице, чтобы купить кока-колу, и почти забыл об идее. Я помнил, что думал о чем-то интересном, но совершенно не мог припомнить, что же это было. Затем она всплыла в памяти, и я почувствовал прилив возбуждения с настоящим адреналиновым шоком. Впервые с тех пор, как я начал заниматься криптографией, я понимал, что обнаружил что-то действительно стоящее. Все, что мне удавалось до сегодняшнего дня найти в этой области, представлялось просто техническими деталями». Это случилось в полдень, и Диффи пришлось томиться ожиданием еще пару часов, пока не вернулась Мэри. «Уит ждал у двери», — вспоминает она. «Он сказал, что должен что-то сообщить мне, и у него было забавное выражение лица. Я вошла, и он произнес: «Сядь, пожалуйста, я хочу поговорить с тобой. Я думаю, что сделал великое открытие; я знаю, что я — первый человек, который сделал это». В этот момент весь мир для меня замер. Я почувствовала себя так, словно я — героиня голливудского фильма».

Диффи придумал новый вид шифра — шифра, который включал в себя так называемый асимметричный ключ. Все те алгоритмы шифрования, о которых до сих пор рассказывалось в этой книге, были симметричными, то есть расшифровывание представляло собой просто процесс, обратный зашифровыванию. К примеру, чтобы зашифровать сообщение, в шифровальной машине «Энигма» используется определенный ключ, а получатель, чтобы его расшифровать, использует идентичную шифровальную машину с тем же самым ключом. Точно так же при зашифровывай и и с помощью алгоритма DES применяется ключ для выполнения 16 раундов шифрования, а затем при расшифровывании с помощью алгоритма DES используется этот же ключ для выполнения 16 раундов, только в обратном порядке. Оба, и отправитель, и получатель, фактически обладают равным знанием, и оба они используют один и тот же ключ для зашифровывания и расшифровывания, то есть их взаимоотношение является симметричным. С другой стороны, в системе с асимметричным ключом, как это следует из названия, ключ для зашифровывания и ключ для расшифровывания не идентичны. При использовании асимметричного шифра, если Алиса знает ключ для зашифровывания, она сможет зашифровать сообщение, но вот расшифровать его не сумеет. Чтобы расшифровать сообщение, Алиса должна иметь доступ к ключу для расшифровывания. Вот в этом-то различии между ключом для зашифровывания и ключом для расшифровывания и заключается особенность асимметричного шифра.

Здесь стоит подчеркнуть, что, хотя Диффи сформулировал общую концепцию асимметричного шифра, но на самом деле никакого конкретного примера такого шифра у него не было. Но даже просто концепция асимметричного шифра стала революционной. Если бы криптографы смогли найти действительно работающий асимметричный шифр — систему, которая отвечает требованиям Диффи, — то для Алисы и Боба это будет иметь огромное значение. Алиса могла бы создавать свою собственную пару ключей: один ключ для зашифровывания и один — для расшифровывания. Если предположить, что асимметричный шифр является видом компьютерного шифрования, тогда Алисин ключ для зашифровывания является одним числом, а ключ для расшифровывания — другим числом. Ключ для расшифровывания Алиса хранит в секрете, поэтому он обычно называется секретным ключом Алисы. В то же время свой ключ для зашифровывания она предает гласности, так что все имеют к нему доступ, вот почему он обычно называется открытым ключом Алисы. Если Боб хочет послать Алисе сообщение, он просто ищет ее открытый ключ, который будет указан в чем-то сродни телефонному справочнику. Затем Боб берет этот открытый ключ Алисы и зашифровывает сообщение. Он посылает зашифрованное сообщение Алисе, и, когда оно приходит, Алиса может расшифровать его с помощью своего секретного ключа для расшифровывания. Точно так же, если зашифрованное сообщение Алисе хотят послать Чарли, Дон или Эдвард, они также могут отыскать открытый ключ Алисы для зашифровывания, и в каждом случае только Алиса имеет доступ к секретному ключу, необходимому, чтобы расшифровать сообщения.

Важным достоинством этой системы является то, что здесь нет той суматохи, как при использовании алгоритма обмена ключами Диффи-Хеллмана-Меркля. Бобу больше нет нужды ждать, пока придет информация от Алисы, прежде чем он сможет зашифровать и послать ей сообщение; ему просто надо найти ее открытый ключ для зашифровывания. К тому же асимметричный шифр еще и позволяет разрешить проблему распределения ключей. Алисе не требуется секретно доставлять открытый ключ для зашифровывания Бобу; напротив, она может теперь всем и всюду сообщать о своем открытом ключе для зашифровывания. Она хочет, чтобы весь мир знал ее открытый ключ для зашифровывания, чтобы любой мог воспользоваться им и слать ей зашифрованные сообщения. Но в то же время, даже если весь мир будет знать открытый ключ Алисы, ни один человек, включая Еву, не сможет расшифровать зашифрованные этим ключом сообщения, поскольку знание открытого ключа не поможет в расшифровывании. Кстати, после того как Боб зашифрует сообщение с помощью открытого ключа Алисы, даже он не сможет расшифровать его. Одна лишь Алиса, у которой имеется секретный ключ, сумеет расшифровать сообщение.

То есть здесь, в отличие от традиционного симметричного шифра, когда Алисе приходилось идти на все, чтобы безопасным образом передать ключ для зашифровывания Бобу, ситуация прямо противоположная. В симметричном шифре ключ для зашифровывания и ключ для расшифровывания один и тот же, так что Алиса и Боб должны были принимать изрядные меры предосторожности, чтобы ключ не попал в руки Евы. Это — основа основ в проблеме распределения ключей.

Если вернуться к аналогии с замками, то шифрование с открытым ключом можно представить себе следующим образом. Любой способен запереть замок, просто защелкнув его, чтобы он закрылся, но отпереть его может только тот, у кого есть ключ. Запереть замок (зашифровывание) легко, почти все могут это сделать, но открыть его (расшифровывание) имеет возможность только владелец ключа. Понимание того, как защелкнуть замок, чтобы он закрылся, ничего не скажет вам, как его отпереть. Можно провести и более глубокую аналогию. Представьте, что Алиса проектирует замок и ключ. Она бдительно охраняет ключ, но при этом изготавливает тысячи дубликатов замков и рассылает их по почтовым отделениям по всему миру. Если Боб хочет послать сообщение, он кладет его в коробку, идет на местный почтамт, просит «замок Алисы» и запирает им коробку. Теперь уже ему не удастся открыть коробку, но когда коробку получит Алиса, она сможет открыть ее своим единственным ключом. Замок и защелкивание его, чтобы он закрылся, эквивалентны общему ключу для зашифровывания, поскольку все имеют доступ к замкам и все могут воспользоваться замком, чтобы закрыть сообщение в коробке. Ключ от замка эквивалентен секретному ключу для расшифровывания, потому что он имеется только у Алисы, только она сможет открыть замок, и только она сможет получить доступ к находящемуся в коробке сообщению.

Эта система представляется простой, если рассматривать ее применительно к замкам, но далеко не так-то легко найти такую математическую функцию, которая выполняет то же самое действие, функцию, которую можно было бы включить в работоспособную криптографическую систему. Чтобы перейти от прекрасной идеи к практической реализации асимметричных шифров, кто-то должен найти подходящую математическую функцию. Диффи рассматривал специальный тип односторонней функции — функции, которая могла бы быть обратимой при особых обстоятельствах. В асимметричной системе Диффи Боб зашифровывает сообщение с помощью открытого ключа, но он не может расшифровать его — это, по сути, односторонняя функция. Однако Алиса сможет расшифровать сообщение, поскольку у нее есть секретный ключ — специальная порция информации, которая дает ей возможность провести обратное вычисление функции. Еще раз — замки являются хорошей аналогией — запирание замка представляет собой одностороннюю функцию, поскольку обычно сложно открыть замок, если только у вас нет специального инструмента (ключа) — в этом случае функция становится легко обратимой.

Диффи опубликовал основные принципы своей идеи летом 1975 года, после чего другие ученые присоединились к поискам подходящей односторонней функции, функции, которая отвечала бы критериям, требующимся для асимметричного шифра. Вначале все были настроены крайне оптимистично, но к концу года никто так и не смог найти подходящую кандидатуру. Шли месяцы, и все больше и больше создавалось впечатление, что специальных односторонних функций не существует. Казалось, что идея Диффи работала только в теории, но не на практике. Тем не менее к концу 1976 года команда Диффи, Хеллмана и Меркля произвела переворот в мире криптографии. Они убедили всех, что решение проблемы распределения ключей существует, и создали алгоритм обмена ключами Диффи-Хеллмана-Меркля — работоспособную, хотя и несовершенную систему, а также предложили концепцию асимметричного шифра — совершенную, но пока что неработоспособную систему. Свои исследования они продолжили в Стэнфордском университете, стараясь отыскать специальную одностороннюю функцию, которая позволила бы сделать асимметричные шифры реальностью. Однако найти ее им не удалось. Состязания по поиску асимметричного шифра выиграла другая троица исследователей, которая находилась за 5000 км от них, на восточном побережье Америки.

Главные подозреваемые

«Я вошел в кабинет Рона Ривеста, — вспоминает Леонард Адлеман, — и Рон держал в руках эту статью. Он начал было говорить: «Эти парни из Стэнфорда действительно сделали эту ерунду». А я в этот момент, помнится, подумал: «Это прекрасно, Рон, но мне бы хотелось поговорить о другом». Я совсем не знал истории криптографии, и меня совершенно не интересовало, о чем он говорит». Статью, которая привела Рона Ривеста в такое возбуждение, написали Диффи и Хеллман, и в ней была дана концепция асимметричных шифров. В конце концов, Ривес убедил Адлемана, что в этой проблеме может заключаться интересная математика, и они решили вместе попытаться найти одностороннюю функцию, которая удовлетворяла бы требованиям асимметричного шифра. К ним присоединился также Ади Шамир. Все трое были исследователями и работали в лаборатории вычислительной техники на восьмом этаже Массачусетского технологического института.

Ривест, Шамир и Адлеман составили великолепную команду. Ривест был специалистом в области теории вычислительных машин и систем; он обладал исключительной способностью впитывать новые идеи и применять их в самых неожиданных областях. Он всегда был в курсе последних научных статей, служивших источником его идей, то и дело предлагая причудливые и поразительные кандидатуры на лежащие в основе асимметричного шифра односторонние функции. Но в каждой из них обнаруживались изъяны. Шамир, еще один ученый в той же области, имел быстрый ум, необычайную проницательность и способность концентрироваться на сути проблемы. Он также регулярно генерировал идеи по созданию асимметричного шифра, но и они также неизменно оказывались ошибочными. Адлеман, математик, отличающийся огромным упорством и терпением, был занят преимущественно тем, что выискивал в идеях Ривеста и Шамира недостатки и слабые места, гарантируя тем самым, что они не станут впустую тратить время. Ривест и Шамир потратили год, предлагая новые идеи, а Адлеман — разбивая их вдребезги. Троица начала терять надежду, но они и не предполагали, что череда непрерывных неудач послужила необходимой частью их исследований, мягко направляя их из области чистой математики на более благодатную почву. В должное время их усилия были вознаграждены.

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

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

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

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

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

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

_{Рис. 65 Рональд Ривест, Ади Шамир и Леонард Адлеман.}

Душой асимметричного шифра Ривеста является односторонняя функция, основанная на модулярной функции, описанной ранее в этой главе. Односторонняя функция Ривеста может применяться для зашифровывания сообщения; к сообщению, которое в нашем случает является числом, применяется функция, и в результате получается шифртекст — другое число. Я не буду подробно описывать одностороннюю функцию Ривеста (для этого см. Приложение J) один особый аспект, известный просто как N, поскольку именно N делает при определенных обстоятельствах одностороннюю функцию обратимой и, тем самым, идеальной для применения в качестве асимметричного шифра.

N важно, поскольку оно представляет собой изменяющийся элемент односторонней функции, благодаря чему каждый человек может выбирать различные значения N, образуя всякий раз различные односторонние функции. Чтобы выбрать свое собственное значение N, Алиса берет два простых числа, р и q перемножает их. Простое число — это число, у которого нет других делителей, кроме самого себя и 1. Например, 7 — это простое число, т. к. оно не делится без остатка ни на какое другое число, кроме 1 и 7. Точно так же и 13 — простое число, т. к. оно тоже не делится без остатка ни на какое другое число, кроме 1 и 13. А вот 8 уже является не простым, а составным числом, поскольку может делиться на 2 и на 4.

Итак, Алиса может выбрать свои простые числа, например, р = 17 159 и q = 10 247. Перемножая эти два числа, она получает 17 159 x 10 247 = 175 828 273. Полученное Алисой N фактически будет ее открытым ключом для зашифровывания, и она может напечатать его на своей визитной карточке, разместить в Интернете или опубликовать в справочнике открытых ключей вместе со значениями N других людей. Если Боб захочет зашифровать сообщение для Алисы, он отыскивает ее значение N (175 828 273), а затем вставляет его в одностороннюю функцию общего вида, которая также известна всем. Теперь у Боба есть односторонняя функция, сшитая с открытым ключом Алисы, поэтому ее можно назвать односторонней функцией Алисы. Чтобы зашифровать сообщение для Алисы, он берет одностороннюю функцию Алисы, вставляет сообщение, выписывает результат и отправляет его Алисе.

В этот момент зашифрованное сообщение становится секретным, поскольку никто не сможет расшифровать его. Сообщение было зашифровано с помощью односторонней функции, поэтому обращение односторонней функции и расшифровка сообщения по определению является исключительно трудным делом. Однако остается вопрос, как же Алиса сумеет его расшифровать? Чтобы прочитать присланные ей сообщения, у Алисы должен быть способ обращения односторонней функции. Ей необходимо иметь доступ к некоторой специальной порции информации, которая и даст ей возможность расшифровать сообщение. К счастью для Алисы, Ривест задумал и создал одностороннюю функцию таким образом, что она является обратимой для каждого, кто знает значения p и q — два простых числа, которые были перемножены для получения N. Хотя Алиса сообщила всем, что у нее N равняется 175 828 273, она не раскрыла значений р и q, поэтому только у нее есть специальная информация, необходимая для расшифровки своих сообщений.

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

Подробности того, как можно использовать p и q для обращения односторонней функции приведены в Приложении J. Имеется, однако, один вопрос, который следует решить не откладывая. Если все знают открытый ключ N, то разве нельзя найти p и q — секретный ключ — и прочесть сообщения Алисы? Как-никак, N было образовано из p и q. В действительности же оказывается, что если N достаточно велико, то из него практически невозможно вычислить p и q, и это, пожалуй, самый превосходный и элегантный аспект в асимметричном шифре RSA.

Алиса образовала N, выбрав p и q затем перемножив их вместе. Основной момент здесь заключается в том, что это по своей сути односторонняя функция. Чтобы продемонстрировать односторонний характер умножения простых чисел, мы можем взять два простых числа, например, 9419 и 1933, и перемножить их. Используя калькулятор, нам понадобится всего лишь несколько секунд, чтобы получить ответ 18 206 927. Однако, если вместо этого нам дадут число 18 206 927 и попросят найти простые множители (два числа, которые перемножили, чтобы получить 18 206 927), это займет у нас гораздо больше времени. Если вы сомневаетесь в том, насколько трудно находить простые множители, то примите во внимание следующее. Мне понадобилось лишь десять секунд, чтобы образовать число 1 709 023, но у вас с калькулятором в руках, чтобы найти простые множители, это займет добрую часть дня.

Считается, что данная система асимметричной криптографии, известная как RSA, является одним из видов шифрования с открытым ключом. Чтобы понять, насколько надежна RSA, мы можем проверить ее с точки зрения Евы и попробовать прочесть сообщение, посланное Алисой Бобу. Для того чтобы зашифровать сообщение для Боба, Алиса должна отыскать его открытый ключ. Для создания своего открытого ключа Боб берет выбранные им самим простые числа, р_B и q_B, и перемножает их, получая N_B. Он хранит р_B и q_B в секрете, ибо они составляют его секретный ключ для дешифровывания, но при этом публикует N_V, которое равно 408 508 091. Так что Алиса подставляет открытый ключ Боба N_B в общую одностороннюю функцию шифрования, а затем зашифровывает свое сообщение ему. Когда приходит зашифрованное сообщение, Боб может обратить функцию и расшифровать его, используя значения p_в и q_B, которые составляют его секретный ключ. Между тем Ева сумела во время передачи сообщения перехватить его. Ее единственная надежда расшифровать сообщение — обратить одностороннюю функцию, а это возможно только в том случае, если она знает р_B и q_B. Боб держит рv и qv в секрете, но, как и всем остальным, Еве известно N_B, равное 408 508 091. Далее Ева пытается найти значения р_B и q_B путем подбора чисел, которые при перемножении дают 408 508 091 — процесс, известный как разложение на множители.

Операция разложения на множители отнимает очень много времени, но сколько же на самом деле понадобится Еве времени, чтобы найти сомножители числа 408 508 091? Существуют различные способы разложения на множители числа N_B. Хотя одни из них быстрее, а другие — медленнее, но, по сути, во всех них проверяется, делится ли N_B без остатка на каждое из простых чисел. Например, 3 — это простое число, но оно не является множителем числа 408 508 091, так как 408 508 091 нацело на 3 не делится. Поэтому Ева берет следующее простое число — 5. 5 точно так же не является множителем, поэтому Ева переходит к следующему простому числу и так далее. В конце концов, Ева добирается до числа 18 313, 2000-го простого числа, которое является множителем числа 408 508 091. Найдя один из сомножителей, легко найти и другой — 22 307. Если у Евы есть калькулятор и она способна проверять четыре простых числа в минуту, то ей, чтобы отыскать p_B и q_B, потребуется 500 минут, или свыше 8 часов. Другими словами, Ева сможет раскрыть секретный ключ Боба и, тем самым, расшифровать перехваченное сообщение менее, чем за день.

Это не слишком-то высокий уровень стойкости, но Боб мог бы выбрать гораздо большие простые числа и повысить стойкость своего секретного ключа. Например, он мог бы выбрать простые числа, состоящие из 10⁶⁵ цифр (это означает 1 с 65 нулями, или сто тысяч миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов). В результате величина N будет приблизительно составлять 10⁶⁵ x 10⁶⁵, то есть 10¹³⁰ цифр. Компьютер смог бы перемножить оба простых числа и вычислить N всего лишь за секунду, но если Ева захочет выполнить обратную операцию и определить p и q, на это потребуется не в пример больше времени. Насколько больше, зависит от быстродействия компьютера Евы. По оценке эксперта по безопасности Симеона Гарфинкеля, 100-MHz компьютеру Intel Pentium с 8 MB RAM, чтобы разложить на множители число, состоящее из 10¹³⁰ цифр потребуется около 50 лет. Криптографы проявляют тенденцию к параноидальности и учитывают при определении стойкости своих шифров наихудшие ситуации, как, например, глобальная секретность. Поэтому Гарфинкель рассматривал, что произойдет, если объединить вместе сотню миллионов персональных компьютеров (количество компьютеров, проданных в 1995 году). В результате он получил, что число, состоящее из 10¹³⁰ цифр, может быть разложено на множители примерно за 15 секунд. Так что в настоящее время общепринято, что для обеспечения подлинной стойкости необходимо использовать еще большие простые числа. Для ответственных банковских операций N стремятся сделать как минимум 10³⁰⁸, которое в десять миллионов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов раз больше, чем 10¹³⁰. Объединенными усилиями сотне миллионов персональных компьютеров потребуется затратить более тысячи лет, чтобы раскрыть такой шифр. При достаточно больших значениях p и q, RSA является неуязвимой.

Единственное предупреждение относительно надежности использования алгоритма RSA шифрования с открытым ключом — это то, что в будущем кто-нибудь сможет найти способ быстро находить множители N. Возможно, через десять лет или даже завтра, кто-то откроет способ быстрого разложения на множители, после чего RSA станет бесполезным. Однако свыше двух тысяч лет математики пытались и не смогли его отыскать, и на сегодняшний момент для разложения на множители требуется огромное количество времени.

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

Огромным преимуществом алгоритма RSA шифрования с открытым ключом является то, что он избавляет от всех проблем, связанных с традиционными шифрами и обменом ключами. Алисе больше не надо волноваться о безопасности доставки ключа Бобу или что Ева сможет перехватить ключ. Более того, Алиса даже не беспокоится, кто увидит открытый ключ — чем больше, тем лучше, — так так открытый ключ помогает только при зашифровывании, а не при расшифровывании. Единственно, что следует хранить в секрете, — это секретный ключ, применяющийся для расшифровывания, и Алиса может всегда держать его при себе.

Об RSA впервые было объявлено в августе 1977 года, когда Мартин Гарднер написал статью, озаглавленную «Новый вид шифра, для взлома которого потребуются миллионы лет», для колонки «Математические игры» в «Сайентифик Америкен». Объяснив, как происходит шифрование с открытым ключом, Гарднер задал задачу своим читателям. Он напечатал зашифрованное сообщение и дал открытый ключ, который использовал для его зашифровывания:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

Задача заключалась в том, чтобы разложить на сомножители р и q, а затем использовать эти числа, чтобы расшифровать сообщение. Призом были 100 долларов. У Гарднера не было места, чтобы объяснить все подробности алгоритма RSA; вместо этого он попросил читателей написать в лабораторию вычислительной техники Массачусетского технологического института, откуда им пришлют технический меморандум, который был как раз к тому времени подготовлен. Ривест, Шамир и Адлеман были поражены, получив три тысячи запросов. Однако ответили они не сразу, так как были обеспокоены, что открытое распространение их идеи могло бы поставить под угрозу получение патента. Когда же вопросы по выдаче патента были в конце концов разрешены, троица устроила праздничную вечеринку, на которой преподаватели и студенты уплетали пиццу, запивая ее пивом, и одновременно раскладывали по конвертам технические меморандумы для читателей «Сайентифик Америкен».

Что касается задачи Гарднера, то для ее решения потребовалось 17 лет. 26 апреля 1994 года команда из шестисот добровольцев сообщила о том, какие сомножители были у N:

q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577

p = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533.

Используя эти значения в качестве секретного ключа, они смогли расшифровать сообщение. Сообщение состояло из ряда чисел, но, преобразованное в буквы, гласило: «Волшебные слова: брезгливая скопа». Задача разложения на множители была распределена между добровольцами, проживающими в Австралии, Англии, США и Венесуэле. Они использовали свободное время своих рабочих станций, больших ЭВМ и суперкомпьютеров; при этом каждый занимался только частью задачи. По сути, чтобы решить задачу Гарднера, компьютеры, разбросанные по всему миру, объединялись в сеть и работали одновременно. Даже принимая во внимание огромную работу, которая велась параллельно, некоторые читатели могут удивиться, что RSA была взломана за такое короткое время, но следует заметить, что в задаче Гарднера использовалось относительно малое значение N; оно составляло порядка 10¹²⁹. Сегодня, чтобы обеспечить безопасность жизненно важной информации, пользователи RSA могут брать гораздо большие значения. Ныне вполне обычное дело зашифровывать сообщение с использованием такого большого N, что всем компьютерам в мире, чтобы взломать шифр, потребуется время, превышающее возраст Вселенной.

Альтернативная история шифрования с открытым ключом

За последние двадцать лет Диффи, Хеллман и Меркль приобрели мировую известность как криптографы, которые придумали способ шифрования с открытым ключом, а Ривесту, Шамиру и Адлеману приписывается слава создания RSA — самой превосходной реализации криптографии с открытым ключом. Однако появившаяся недавно информация означает, что учебники истории необходимо переписать.

Как заявило правительство Великобритании, шифрование с открытым ключом было первоначально разработано в Штаб-квартире правительственной связи (ШКПС) в Челтенхеме, сверхсекретном учреждении, которое было сформировано из остатков Блечли-Парка после Второй мировой войны. Это — рассказ о поразительной изобретательности, безвестных героях и о правительственном комплексе мер по обеспечению скрытности, что длилось несколько десятилетий.

История началась в конце 60-х годов, когда перед Вооруженными силами Великобритании встала проблема распределения ключей. Заглядывая в 70-е годы, высшие армейские чины представили себе ситуацию, когда миниатюризация и снижение стоимости радио приведет к тому, что у каждого солдата будет постоянная связь со своим офицером. Преимущества такого широкого распространения средств связи были бы неоспоримы, но информация при этом должна передаваться в зашифрованном виде, и проблема распределения ключей оказалась бы непреодолимой. То была эпоха, когда существовала единственно симметричная форма криптографии, так что каждому участнику коммуникационной сети следовало надежным образом передать отдельный ключ. Любое расширение линий коммуникации вело к тому, что они стали бы просто задыхаться под бременем проблемы распределения ключей. Поэтому в начале 1969 гот да представители вооруженных сил попросили Джеймса Эллиса, одного из ведущих правительственных криптографов Великобритании, изучить, каким образом можно было бы справиться с проблемой распределения ключей.

Эллис был любознательным и слегка эксцентричным человеком. Он с гордостью похвалялся, что объехал пол мира еще до рождения: зачат он был в Британии, а родился в Австралии. Затем, еще будучи ребенком, он вернулся в Лондон и в 20-е годы рос в Ист-Энде. В школе его прежде всего интересовала наука. После школы он продолжил изучение физики в Имперском колледже, а затем поступил на службу в исследовательский центр Управления почт и телеграфа в Доллис Хилл, где Томми Флауэрс построил «Колосс», первый компьютер для взлома шифров. Криптографическое отделение в Доллис Хилл было в итоге присоединено к ШКПС, и поэтому 1 апреля 1965 года Эллис был переведен в Челтенхем для работы во вновь созданном Отделении обеспечения скрытности работы средств связи и электронного оборудования, специальное подразделение в ШКПС, предназначенное для обеспечения безопасности британских средств коммуникации. В связи с тем, что его работа была связана с вопросами национальной безопасности, Эллис обязался хранить тайну в течение всего срока службы. Хотя его жена и семья знали, что он работал на ШКПС, им ничего не было известно о его открытиях, и они и не подозревали, что он являлся одним из самых выдающихся криптографов страны.

_{Рис 66 Джеймс Эллис}

Но несмотря на его высокую квалификацию как криптографа, Эллиса никогда не назначали руководителем любой мало-мальски важной исследовательской группы ШКПС. Он был гениален, но непредсказуем, интроверт, и его никак нельзя было назвать настоящим членом команды. Его коллега Ричард Уолтон вспоминал:

Что больше всего поражало в Эллисе, так это его широта знаний. Он прочитывал все научные журналы, которые попадали ему в руки, и никогда ничего не выбрасывал. В целях безопасности сотрудники ШКПС должны были каждый вечер освобождать свои столы и все складывать в запирающиеся шкафы, и поэтому шкафы Эллиса были набиты под завязку самыми непонятными изданиями. Он приобрел репутацию «криптогуру», и если кто-то из исследователей сталкивался с исключительно сложной задачей, он стучался к нему в дверь в надежде, что его обширные знания и оригинальность мышления позволят решить ее. Возможно, что именно благодаря такой своей репутации его и попросили исследовать проблему распределения ключей.

Затраты на распределение ключей уже были огромны, становясь фактором, сдерживающим любое расширение шифрования. Даже снижение затрат на распределение ключей на 10 процентов пробило бы значительную брешь в статье расходов на безопасность бюджета вооруженных сил. Однако Эллис не стал потихоньку подбираться к проблеме, он сразу же принялся за поиск радикального и полного ее решения. «Он обычно всегда приступал к решению задачи с вопроса: «Это действительно то, что мы хотим сделать? — говорит Уолтон. — Джеймс есть Джеймс, и первое, что он делал, это выяснял необходимость совместного пользования секретными данными, я имею в виду — ключом. Теоремы, гласящей, что вам требуется иметь совместно используемые секретные данные, не было. Это было нечто, вызывающее сомнения».

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

Шумом называется любой сигнал, который накладывается на сигналы, используемые для связи. Обычно он создается естественными причинами, и больше всего в нем раздражает то, что он носит совершенно случайный характер, что означает, что убрать шум из сообщения крайне сложно. Если радиосистема хорошо спроектирована, то уровень шума низок и сообщение отчетливо слышно, но если уровень шума высок и он забивает сообщение помехами, то разобрать сообщение не удается. Эллис предложил, чтобы получатель, Алиса, намеренно создавала шум, который она может измерять перед тем, как подать его в канал связи, соединяющий ее и Боба. После этого Боб может послать сообщение Алисе; если же Ева подсоединится к каналу связи, она не сможет прочесть сообщение, потому что оно будет «утоплено» в шуме. Ева не сможет выделить сообщение из шума. Так что единственным человеком, который в состоянии устранить шум и прочесть сообщение, будет Алиса, поскольку она единственная знает точную природу шума. Эллис понял, что безопасность достигнута без обмена какими-либо ключами. Ключом здесь послужил шум, и только Алисе требовалось знать все об этом шуме.

В меморандуме Эллис подробно описал ход своих мыслей: «Следующий вопрос был очевиден. Может ли это быть выполнено при обычном зашифровывании? Можем ли создать надежным образом зашифрованное сообщение, которое сможет прочесть законный получатель без какого-то ни было предварительного секретного обмена ключом? Этот вопрос действительно как-то ночью, когда я лежал в кровати, пришел мне в голову, причем на доказательство теоретической возможности мне понадобилось всего несколько минут. Мы получили теорему существования. То, что представлялось немыслимым, на самом деле было возможно». (Теорема существования показывает, что конкретное решение возможно, но не затрагивает подробностей решения). Другими словами, вплоть до того момента поиск решения проблемы распределения ключей напоминал поиск иголки в стоге сена, причем была вероятность, что иголки там может и не быть вовсе. Однако благодаря теореме существования Эллис теперь знал, что иголка где-то там есть.

Идеи Эллиса очень напоминали идеи Диффи, Хеллмана и Мерк-ля, за исключением того, что он на несколько лет опережал их. Однако никто не знал о работе Эллиса, так как он был служащим Британского правительства и потому дал клятву хранить тайну. Похоже, что в конце 1969 года Эллис зашел в тот же тупик, что и стэнфордская троица в 1975 году. Он убедился, что криптография с открытым ключом (или, как он ее назвал, «несекретное шифрование») возможна, и развил концепцию раздельных открытых и секретных ключей. Он также знал, что ему необходимо найти специальную одностороннюю функцию — функцию, которая смогла бы стать обратимой, если получатель имел доступ к некоторому количеству специальной информации. К сожалению, Эллис не был математиком. Он поэкспериментировал с несколькими математическими функциями, но вскоре понял, что самостоятельно добиться большего не сможет.

На этом этапе Эллис представил свое открытие руководству. Какова была их реакция — до сих пор относится к засекреченным материалам, но в интервью Ричард Уолтон был готов изложить мне своими словами содержание различных меморандумов, которые были заменены. Он сидел с портфелем на коленях, так чтобы крышка его закрывала бумаги от моего взора, и бегло просматривал документы:

Следующие три года самые светлые умы ШКПС изо всех сил старались отыскать одностороннюю функцию, которая удовлетворила бы требованиям Эллиса, но ничего не вышло. В сентябре 1973 года к команде присоединился новый математик. Клиффорд Кокс недавно окончил Кембриджский университет, где он специализировался в теории чисел, разделе, который относится к чистой математике. Когда он пришел в ШКПС, он почти ничего не знал ни о шифровании, ни о призрачном мире военных и дипломатических средств связи, так что ему был выделен наставник, Ник Паттерсон, который инструктировал и направлял его первые несколько недель в ШКПС.

Примерно через шесть недель Паттерсон рассказал Коксу о «совершенно дурацкой идее». Он в общих чертах обрисовал теорию Эллиса относительно криптографии с открытым ключом и пояснил, что до сих пор никто не сумел отыскать требуемую математическую функцию. Паттерсон поделился с Коксом не потому, что ожидал от него, что тот попробует ее решить, а поскольку это была самая щекочущая нервы криптографическая идея. Однако в тот же день, чуть позже, Кокс принялся за эту работу. Как он объясняет: «Ничего особенного не происходило, так что я решил поразмыслить над этой идеей. Поскольку я работал в области теории чисел, было вполне естественно, что и думать я стал об односторонних функциях, с помощью которых вы можете что-то сделать, но вернуться обратно уже не удастся. Явными кандидатурами были простые числа и разложение на множители, и это стало моей отправной точкой».

_{Рис 67 Клиффорд Кокс}

Кокс начал разрабатывать алгоритм, который позднее стал известен как асимметричный шифр RSA. Ривест, Шамир и Адлеман нашли свой алгоритм для криптографии с открытым ключом в 1977 году, но четырьмя годами раньше юный выпускник Кембриджа шел тем же самым путем. Как вспоминает Кокс: «От начала и до конца это заняло у меня не более получаса. Я был вполне доволен собой. Я думал: «О, это здорово. Мне дали задачу, и я решил ее».

Кокс не мог в полной мере оценить всю значимость своего открытия. Он не знал, что самые светлые умы ШКПС целых три года всеми силами старались отыскать решение проблемы, и не подозревал, что совершил переворот в криптографии, сделав самое выдающееся открытие века. Отчасти причиной успеха Кокса могла быть его неискушенность, позволившая ему самонадеянно взяться за решение проблемы. Кокс рассказал своему наставнику о найденном им решении, а уже тот сообщил об этом руководству.

Кокс был очень застенчив и пока еще оставался слишком «зеленым» новичком, в то время как Паттерсон полностью разбирался в ситуации и в большей мере мог разрешить технические вопросы, которые неизбежно возникнут в дальнейшем. Вскоре к Коксу начали подходить и поздравлять его совершенно незнакомые люди. Одним из них был Джеймс Эллис, страстно желающий встретиться с тем, кто превратил его мечту в реальность. Поскольку Кокс все еще не понимал всей важности своего достижения, эта встреча не произвела на него сильного впечатления, и поэтому сегодня, спустя двадцать лет, он не помнит реакции Эллиса.

Когда в конце концов Кокс понял, что он сделал, его осенило, что это открытие могло бы разочаровать Г. Х. Харди, одного из величайших английских математиков начала века. В своей книге «Апология математика», написанной в 1940 году, Харди с гордостью заявлял: «Истинная математика никак не влияет на войну. Никто еще не обнаружил ни одной, связанной с военной деятельностью цели, для которой понадобилась бы теория чисел». Под истинной математикой подразумевается «чистая» математика, как, например, теория чисел, которая послужила основой для работы Кокса. Кокс доказал, что Харди был неправ. Теперь сложности теории чисел могли помочь генералам планировать свои сражения в абсолютной секретности. Поскольку работа Кокса имела значение для военной связи, ему, как и Эллису, было запрещено говорить кому бы то ни было за пределами ШКПС о том, что он сделал. Работа в совершенно секретном правительственном учреждении означала, что он не мог поделиться этим ни со своими родителями, ни со своими прежними коллегами из Кембриджского университета. Единственным человеком, с кем он мог общаться, была его жена, Джил, так как она тоже работала на ШКПС.

Несмотря на то что идея Кокса была одной из важнейших в ШКПС, она страдала от того, что время для нее еще не пришло. Кокс нашел математическую функцию, которая дала жизнь криптографии с открытым ключом, но по-прежнему оставалась сложность с реализацией данной системы. Для шифрования с использованием криптографии с открытым ключом требуются гораздо большие вычислительные мощности, чем для шифрования с использованием симметричного шифра, как, например, DES. Но в начале 70-х компьютеры были все еще сравнительно примитивными и не могли выполнять процесс шифрования с открытым ключом за приемлемое время. Так что ШКПС была не в состоянии использовать криптографию с открытым ключом. Кокс и Эллис доказали, что, казалось бы, невозможное было возможным, но никто не мог найти способ сделать возможное осуществимым.

В начале следующего, 1974 года Кокс рассказал о своей работе по криптографии с открытым ключом Малькольму Уильямсону, который недавно был принят в ШКПС в качестве криптографа. Так случилось, что оба они были давними друзьями. Оба ходили в манчестерскую среднюю школу, девизом которой был Sapere aude — «Имей мужество пользоваться собственным умом». В 1968, еще учась в школе, оба мальчика представляли Великобританию на математической Олимпиаде, проводившейся в Советском Союзе. Оба поступили в Кембриджский университет, где их дороги на пару лет разошлись, но теперь они вновь воссоединились в ШКПС. Они обменивались математическими идеями уже в одиннадцать лет, но открытие Коксом криптографии с открытым ключом было самым поразительным, о чем когда-либо слышал Уильямсон. «Клиф объяснил мне свою идею, — вспоминает Уильямсон, — но я, вообще-то, не поверил в нее. Я был очень недоверчив, ведь это крайне специфическая вещь, чтобы суметь ее сделать».

Уильямсон ушел, решив попытаться доказать, что Кокс сделал ошибку и что криптографии с открытым ключом в действительности не существует. Он внимательно изучил математические выкладки в поисках изъянов и слабых мест. Криптография с открытым ключом казалась слишком хорошей, чтобы быть правдой, и Уильямсон был настолько полон решимости найти ошибку, что взял задачу домой.

Сотрудникам ШКПС запрещалось брать работу на дом, поскольку все, что они делали, было секретным, а семейная обстановка потенциально уязвима для шпионажа. Однако задача настолько засела в голове Уильямсона, что перестать думать о ней он не мог и, проигнорировав инструкции и предписания, забрал работу к себе домой. Он потратил пять часов, стараясь найти ошибку. «В конце концов я сдался, — говорит Уильямсон. — Вместо этого я предложил другое решение проблемы распределения ключей». Уильямсон нашел алгоритм обмена ключами Диффи-Хеллмана-Меркля, примерно в то же время, когда его открыл Мартин Хеллман. Начальная реакция Уильямсона отражала его циничный характер: «Выглядит это превосходно, — думал я про себя. — Интересно, смогу ли я найти здесь ошибку. Полагаю, что в тот день у меня было дурное настроение».

_{Рис 68 Малькольм Уильямсон}

К 1975 году Джеймс Эллис, Клиффорд Кокс и Малькольм Уильямсон нашли все фундаментальные аспекты криптографии с открытым ключом, но им по-прежнему приходилось молчать. Все три англичанина вынуждены были наблюдать, как в течение трех следующих лет их открытия были заново открыты Диффи, Хеллманом, Мерклем, Ривестом, Шамиром и Адлеманом. Любопытно, что в ШКПС шифр RSA был найден раньше алгоритма обмена ключами Диффи-Хеллмана-Меркля, в то время как во внешнем мире вначале появился алгоритм обмена ключами Диффи-Хеллмана-Меркля. В научной печати сообщалось о выдающихся достижениях в Стэнфорде и Массачусетском технологическом институте, а исследователи, которым было разрешено опубликовать свои работы в научных журналах, стали известны в криптографическом сообществе.

Если провести поиск в Интернете с помощью какой-нибудь из поисковых машин, то окажется, что Клиффорд Кокс упоминается на 15 веб-страницах, а Уитфилд Диффи — на 1382. Кокс относится к этому исключительно сдержанно: «Вы ввязались в это дело не для получения всеобщего признания». Так же спокоен и Уильямсон: «Моей реакцией было: «Ну что ж, так устроен мир». В сущности ведь жизнь продолжается».

_{Рис. 69 Малькольм Уильямсон (второй слева) и Клиффорд Кокс (крайний справа), прибывшие на математическую Олимпиаду 1968 года.}

Единственно, что тревожило Уильямсона, это то, что ШКПС не стала брать патент на криптографию с открытым ключом. Когда Кокс и Уильямсон совершали свои открытия, в руководстве ШКПС существовало мнение, что патентование невозможно по двум причинам. Во-первых, патентование означало бы раскрытие деталей их работы, что противоречило бы целям ШКПС. Во-вторых, в начале 70-х годов было далеко не ясно, могут ли быть запатентованы математические алгоритмы. Однако когда Диффи и Хеллман в 1976 году попробовали подать заявку на патент, оказалось, что патентовать их можно. В этот момент у Уильямсона появилось огромное желание предать гласности свое открытие и заблокировать заявку Диффи и Хеллмана, но ему было отказано руководителями высокого ранга, которые не были достаточно дальновидны, чтобы разглядеть возникновение цифровой революции и возможностей криптографии с открытым ключом. К началу 80-х руководство Уильямсона начало уже раскаиваться в своем решении, поскольку усовершенствования в компьютерах и зарождающийся Интернет убедительно показали, что RSA и алгоритм обмена ключами Диффи-Хеллмана-Меркля оказались бы продуктами, имеющими огромный коммерческий успех. В 1996 году компанией RSA Дата Секьюрити Инк. было продано продуктов RSA на сумму 200 миллионов долларов.

Несмотря на то что работа в ШКПС оставалась по-прежнему секретной, существовала еще одна организация, которой было известно об открытиях, совершенных в Великобритании. К началу 80-х годов американское Агентство национальной безопасности знало о работе Эллиса, Кокса и Уильямсона, и возможно, что именно от АНБ до Уитфилда Диффи дошел слух об открытиях в Великобритании. В сентябре 1982 года Диффи решил проверить, насколько слухи истинны, и со своей женой отправился в Челтенхем, чтобы с глазу на глаз поговорить с Джеймсом Эллисом. Они встретились в местном пабе, и очень скоро незаурядная личность Эллиса произвела впечатление на Мэри:

Диффи и Эллис обсуждали различные темы: от археологии до вопроса о том, как крысы в бочке улучшают вкус сидра, но каждый раз, как разговор начинал переходить на криптографию, Эллис мягко менял тему. В конце своего визита Диффи, поскольку он уже готовился уезжать и больше не мог выжидать, без обиняков спросил Эллиса: «Расскажите мне, как вам удалось открыть криптографию с открытым ключом?» Последовала длинная пауза. Наконец Эллис прошептал: «Ну, я не знаю, сколько я могу рассказать. Позвольте мне только заметить, что вы сделали гораздо больше, чем мы».

И хотя криптографию с открытым ключом вначале нашли в ШКПС, не следует недооценивать достижения ученых, открывших ее «заново». Именно они первыми осознали возможности шифрования с открытым ключом, и именно они воплотили ее в жизнь. Более того, вполне возможно, что ШКПС никогда бы и не обнародовала их работу, воспрепятствовав тем самым появлению шифрования, которое позволит цифровой революции раскрыть все свои возможности. И наконец, открытие было сделано учеными совершенно независимо от открытия в ШКПС, а интеллектуально — наравне с нею. Засекреченная область закрытых исследований полностью обособлена от академической среды, и ученые академических институтов не имеют доступа к программным продуктам и секретным сведениям, которые могут быть скрыты от них в засекреченном мире. С другой стороны, у исследователей, работающих в засекреченной области, всегда есть доступ к академическим изданиям. Можно представить себе этот поток информации как одностороннюю функцию: информация свободно движется в одном направлении, но в обратном направлении передавать информацию запрещено.

Когда Диффи рассказывал Хеллману об Эллисе, Коксе и Уильямсоне, по его мнению, поступить надо было следующим образом: об открытиях ученых академических институтов следует указывать в виде примечания в историческом описании закрытых исследований, а об открытиях, сделанных в ШКПС, следует указывать в виде примечания в историческом описании академических исследований. Однако на данном этапе никто, кроме ШКПС, АНБ, Диффи и Хеллмана, не знал о закрытых исследованиях, и поэтому их не удалось бы дать даже в качестве ссылки.

К середине 80-х настроение в ШКПС изменилось и ее руководство подумывало о том, чтобы открыто объявить о работе Эллиса, Кокса и Уильямсона. Математика криптографии с открытым ключом была уже в достаточной мере разработана в открытых исследованиях, и не было причин продолжать держать ее в секрете. Более того, если бы Великобритания обнародовала свою выдающуюся работу по криптографии с открытым ключом, это принесло бы очевидные выгоды. Как вспоминает Ричард Уолтон:

Питер Райт был отставным офицером британской секретной службы, и его мемуары «Ловец шпионов» привели Британское правительство в сильное замешательство. Это произошло за 13 лет до того, как о ШКПС в конце концов стало известно широкому обществу, и через 28 лет после первого важного открытия Эллиса. В 1997 году Клиффорд Кокс закончил имеющую важное значение несекретную работу по RSA, которая представляла интерес для широкой общественности, и которая, если бы ее опубликовали, не представляла угрозы системе безопасности. В результате его попросили представить статью на конференцию в Институт математики и ее приложений, которая должна была проводиться в Сиренчестере. Комната была переполнена экспертами-криптографами. Только некоторые из них знали, что Кокс, доклад которого будет посвящен только одному аспекту RSA, являлся на самом деле его невоспетым автором. Существовал риск, что кто-нибудь мог задать ему неуместный вопрос, например: «Это вы придумали RSA?» Если бы такой вопрос прозвучал, как должен был реагировать Кокс? Согласно политике ШКПС, ему следовало отрицать свое участие в разработке RSA и тем самым лгать в совершенно безобидном вопросе. Ситуация была совершенно смехотворной, и ШКПС решила, что настало время изменить свою политику. Коксу разрешили начать свой доклад с краткой предыстории о вкладе ШКПС в криптографию с открытым ключом.

18 декабря 1997 года Кокс прочитал свой доклад. После почти трех десятилетий секретности Эллис, Кокс и Уильямсон получили заслуженное признание. К сожалению, Джеймс Эллис умер месяцем раньше, 25 ноября 1997 года, в возрасте семидесяти трех лет. Эллис попал в список британских экспертов по шифрам, чей вклад не был оценен при их жизни. О том, что Чарльз Бэббидж раскрыл шифр Виженера, никогда не сообщалось, пока он был жив, так как его работа была бесценной для английских войск в Крымской войне. А вся слава досталась Фридриху Касиски. Так же не имел себе равного в повышении обороноспособности страны и вклад Алана Тьюринга, и тем не менее, в целях обеспечения государственной секретности, потребовалось, чтобы его работа по Энигме не была обнародована.

В 1987 году Эллис написал секретный документ, который свидетельствует о его вкладе в криптографию с открытым ключом и в котором содержатся его размышления о секретности, которой столь часто окружен труд шифровальщика: