Шифр Марии Стюарт, королевы Шотландии 19 страница
Когда Хеллман приступил к исследованиям, он наткнулся на книгу «Взломщики кодов» историка Дэвида Кана. В этой книге впервые подробно рассказывается о развитии шифров, и в этом качестве она являлась прекрасным учебником для начинающих криптографов. «Взломщики кодов» была единственным помощником Хеллмана вплоть до сентября 1974 года, когда ему неожиданно позвонил Уитфилд Диффи, только что пересекший весь контитент, чтобы встретиться с ним. Хеллман никогда прежде не слышал о Диффи и с неохотой согласился уделить ему полчаса попозже днем. Но к концу встречи Хеллман понял, что Диффи был самым знающим человеком, которого он когда-либо встречал. И это чувство было обоюдным. Как вспоминает Хеллман: «Я пообещал своей жене, что буду дома, чтобы присмотреть за детьми, поэтому он пошел со мной, и мы вместе пообедали. Он уехал где-то за полночь. Мы совершенно разные, он гораздо больше нигилист, чем я, но в конечном счете наше несходство пошло нам обоим только на пользу. Для меня это оказалось словно глоток свежего воздуха. Работать «в вакууме» было поистине тяжело».
Поскольку Хеллману не выделяли значительных средств, у него не было возможности нанять на работу своего нового единомышленника в качестве исследователя. Вместо этого Диффи был зачислен как аспирант. Теперь уже они вместе, Хеллман и Диффи, приступили к изучению проблемы распределения ключей, отчаянно пытаясь найти альтернативу неинтересной задаче физической перевозки ключей на большие расстояния. Через некоторое время к ним присоединился Ральф Меркль, сбежавший из другой исследовательской группы, руководитель которой не выражал никакой симпатии к неосуществимой мечте решить проблему распределения ключей. Говорит Хеллман:
Ральф, как и мы, хотел быть дураком. А единственным способом выбраться при начальном поиске — это быть дураком, поскольку только дураки не прекращают своих попыток. У вас появилась идея под номером 1, вы возбуждены, а она не оправдала надежд. Потом у вас появилась идея под номером 2, вы снова возбуждены, а она опять не оправдала надежд. Затем у вас появилась идея под номером 99, вы вновь чувствуете себя возбужденным, но и она не сработала. Только глупец ощутит возбуждение от сотой идеи, но может потребоваться проверить 100 предположений, прежде чем одно принесет свои плоды. Если только вы не глупы в достаточной мере, чтобы ощущать возбуждение, у вас не будет ни стимула, ни энергии, чтобы довести дело до конца. Бог вознаграждает дураков.
В целом, проблема распределения ключей является классическим парадоксом. Если два человека хотят обменяться секретным сообщением по телефону, отправитель должен его зашифровать. Чтобы зашифровать секретное сообщение, отправитель должен воспользоваться ключом, который сам является секретом, поэтому возникает проблема передачи секретного ключа получателю, чтобы передать секретное сообщение. Короче говоря, до того, как два человека смогут передать друг другу секрет (зашифрованное сообщение), оба они уже должны обладать этим секретом (ключом).
Рассматривая проблему распределения ключей, полезно представить себе Алису, Боба и Еву, трех вымышленных лиц, ставших нарицательными персонажами при обсуждении вопросов криптографии. В типичной ситуации Алиса хочет послать сообщение Бобу, или наоборот, а Ева старается перехватить его. Если Алиса отправляет конфиденциальные сообщения Бобу, она должна будет перед отправкой зашифровать каждое из сообщений, всякий раз используя иной ключ. Поскольку Алисе необходимо безопасным образом передавать ключи Бобу, иначе он не сможет расшифровать сообщения, она то и дело сталкивается с проблемой распределения ключей.
Один из способов решения этой проблемы заключается в том, что Алиса и Боб встречаются раз в неделю и обмениваются ключами, число которых должно быть достаточным для отправки сообщений в течение следующих семи дней. Обмен ключами при личной встрече является, несомненно, безопасным, но неудобным способом, ведь если Алиса или Боб заболеют, вся эта система перестанет работать. Или же Алиса и Боб могли бы нанять курьеров, что оказалось бы менее надежно и более затратно, но им хотя бы перепоручили часть работы. Так ли, иначе ли, но, похоже, распределения ключей не избежать. В течение двух тысяч лет это считалось аксиомой криптографии — непререкаемой истиной. Можно, однако, поставить мысленный эксперимент, который, кажется, опровергает эту аксиому.
Рис. 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 х ), мы делим результат, полученный на предыдущем этапе, на х и записываем остаток. Этот остаток и является ответом по (mod x ). Чтобы найти ответ в примере 11 x 9 (mod 13), мы поступим следующим образом:
11 х 9 = 99
99 + 13 = 7, остаток 8
11 x 9 = 8 (mod 13)
Функции, с которыми работают в модулярной арифметике, ведут себя хаотичным образом, что, в свою очередь, иногда делает их односторонними функциями. Это становится очевидным, если сравнить простую функцию в обычной арифметике с этой же простой функцией, но в модулярной арифметике. В первой арифметике данная функция будет двусторонней и легко вычисляемой в обратном направлении; во второй арифметике она станет односторонней, и обратные вычисления провести будет сложно. В качестве примера возьмем функцию 3х. Это означает следующее: взять число х , а затем умножить 3 само на себя х раз, в результате получится новое число. Например, если х = 2, и мы выполняем функцию, тогда:
3x = З2 = 3 х 3 = 9.
Другими словами, функция преобразует 2 в 9. В обычной арифметике по мере увеличения х возрастает также и значение функции. Поэтому если нам дано значение функции, то сравнительно несложно выполнить обратное преобразование и найти исходное значение.
Например, если результат равен 81, мы можем установить, что х равно 4, потому что 34 =_81. Если мы ошибемся и предположим, что х равно 5, путем вычисления мы можем определить, что 35 = 243, а это подскажет нам, что мы выбрали слишком большое значение х . После этого мы уменьшим х до 4 и получим правильный ответ. Короче говоря, даже когда наше предположение неверно, мы можем исправить свою ошибку и получить точное значение х, выполнив тем самым обратное преобразование функции.
Однако в модулярной арифметике эта же самая функция ведет себя не так благоразумно. Представьте, что нам сообщают, что 3х по модулю 7 (mod 7) дает 1, и просят найти значение х. В голову ничего не приходит, поскольку мы, как правило, не знакомы с модулярной арифметикой. Мы можем предположить, что x = 5, и мы можем вычислить З5 (mod 7). В ответе получится 5, что слишком много, так как нам нужно, чтобы в ответе было 1. Напрашивается желание уменьшать значения х. Но так мы будем двигаться неверным путем, поскольку в действительности ответ будет x = 6.
Рис. 64 Модулярная арифметика выполняется на конечном множестве чисел, которые можно рассматривать как числа на циферблате часов. В этом случае мы можем вычислить 6 + 5 по модулю 7, если взять в качестве исходной точки 6 и отсчитать 5 делений, в результате чего мы окажемся на цифре 4.
В обычной арифметике мы можем проводить проверку чисел и в состоянии понять, движемся ли мы в нужном направлении или выбранное направление неверно. Модулярная арифметика не дает нам
таких путеводных нитей, и выполнять обратное преобразование функции гораздо труднее. Зачастую, единственный способ выполнить обратное преобразование функции в модулярной арифметике — это составить таблицу, вычисляя значение функции для множества значений х , пока не будет найден нужный ответ. В таблице 25 показан результат вычисления нескольких значений функции для обычной и для модулярной арифметики. Здесь ясно видно хаотическое поведение функции, когда расчеты проводятся в модулярной арифметике. До тех пор пока мы имеем дело со сравнительно небольшими числами, составление такой таблицы лишь слегка утомительно, но как же мучительно тягостно создавать таблицу, если имеешь дело с такой, к примеру, функцией, как 453х (mod 21 997). Это классический пример односторонней функции, так как я могу выбрать значение для х и вычислить результирующее значение функции, но если я сообщу вам значение функции, скажем, 5787, у вас возникнут огромные трудности при обратном преобразовании функции и вычислении выбранного мною значения х. Чтобы провести вычисления и получить число 5787, мне понадобится лишь несколько секунд, вам же потребуются многие часы, чтобы составить таблицу и найти мое х.
Таблица 25 Вычисленные значения функции 3x в обычной арифметике (ряд 2) и модулярной арифметике (ряд 3). В обычной арифметике функция растет непрерывным образом, в модулярной арифметике ее поведение крайне хаотично.
Спустя два года исследований в области модулярной арифметики и односторонних функций, «глупость» Хеллмана начала приносить плоды. Весной 1976 года он натолкнулся на алгоритм решения проблемы обмена ключами. За полчаса исступленной работы он доказал, что Алиса и Боб могут договориться о ключе, не встречаясь друг с другом, покончив, тем самым, с аксиомой, считавшейся непререкаемой в течение столетий. Идея Хеллмана основывалась на использовании односторонней функции вида Yx (mod Р). Вначале Алиса и Боб договариваются о значениях чисел Y и Р. Подходят почти любые значения за исключением некоторых ограничений; так, например, Y должно быть меньше, чем Р. Эти значения несекретны, так что Алиса может позвонить Бобу и предложить, скажем, Y = 7 и Р = 11. Даже если телефонная линия ненадежна и подлая Ева слышит этот разговор, это, как мы увидим позже, не имеет значения. Алиса и Боб договорились об односторонней функции ТX (mod 11). Сейчас они уже могут начать процесс создания секретного ключа. Поскольку их работа идет параллельно, я объясню их действия в двух колонках таблицы 26.
Таблица 26 Общей односторонней функцией является Yx (mod Р). Алиса и Боб выбрали значения для Y и Р и тем самым договорились об односторонней функции 7х (mod 11).
Внимательно изучив этапы в таблице 26, вы увидите, что и не встречаясь Алиса и Боб договорились об одном и том же ключе, который они могут использовать для зашифровывания сообщения. Например, они могут использовать свое число 9 в качестве ключа для DES-шифрования. (В действительности, в DES применяются в качестве ключа гораздо большие числа, и процесс обмена, описанный в таблице 26, будет выполняться с гораздо большими числами, соответственно давая в результате большой ключ DES.) Воспользовавшись схемой Хеллмана, Алиса и Боб смогли договориться о ключе; им не пришлось встречаться, чтобы шепотом сообщить этот ключ друг другу. Исключительность достижения состоит в том, что секретный ключ был создан путем обмена информацией по обычной телефонной линии. Но если Ева подключилась к этой линии, то будет ли также и она знать ключ?
Проверим схему Хеллмана с позиции Евы. Если она подключилась к линии, ей станут известны только следующие факты: что функцией является ТX (mod 11), что Алиса отправила α = 2 и что Боб отправил β = 4. Чтобы определить ключ, она должна сделать либо то, что делает Боб, который, зная В , преобразует в ключ α, либо то, что делает Алиса, которая, зная А, преобразует в ключ β.
Однако Ева не знает, чему равны А и В, потому что Алиса и Боб не обменивались значениями этих чисел, держа их в секрете. Ева находится в безвыходном положении. У нее есть только одна надежда: теоретически, так как функция ей известна, она могла бы вычислить А из α, поскольку а представляет собой результат подстановки в нее А , или же она могла бы вычислить В из β, поскольку β представляет собой результат подстановки в нее В. К сожалению для Евы, эта функция является односторонней, так что хотя для Алисы преобразовать А в α, а для Боба — В в β не представляет сложности, Ева сможет выполнить обратное преобразование с огромным трудом, особенно в случае очень больших чисел.
Боб и Алиса передали друг другу ровно столько информаци, сколько нужно, чтобы дать им возможность создать ключ, но Еве для вычисления ключа ее оказывается недостаточно. Чтобы показать, как работает схема Хеллмана, представьте шифр, в котором в качестве ключа каким-то образом используется цвет. Допустим вначале, что у всех, включая Алису, Боба и Еву, имеется трехлитровая банка, в которую налит один литр желтой краски. Если Алиса и Боб хотят договориться о секретном ключе, они добавляют в свои банки по одному литру своей собственной секретной краски. Алиса может добавить краску фиолетового оттенка, а Боб — малинового. После этого каждый из них посылает свою банку с перемешанным содержимым другому. И наконец, Алиса берет смесь Боба и подливает в нее один литр своей секретной краски, а Боб берет смесь Алисы и добавляет в нее один литр своей секретной краски. Краска в обеих банках теперь станет одного цвета, поскольку в каждой находится по одному литру желтой, фиолетовой и малиновой краски. Именно этот цвет, полученный при добавлении дважды в банки красок, и будет использоваться как ключ. Алиса понятия не имеет, какую краску добавил Боб, а Боб также не представляет, какую краску налила Алиса, но оба они достигли одного и того же результата. Между тем Ева в ярости. Даже если она и сумеет перехватить банки с промежуточным продуктом, ей не удастся определить конечный цвет, который и будет согласованным ключом. Ева может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Алисы в банке, отправленной Бобу, и она может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Боба в банке, отправленной Алисе, но чтобы найти ключ, ей, на самом деле, необходимо знать цвета исходных секретных красок Алисы и Боба. Однако, рассматривая банки с перемешанными красками, Ева не сможет определить секретные краски Алисы и Боба. Даже если она возьмет образец одной из смешанных красок, ей не удастся разделить ее на исходные краски, чтобы найти секретную, поскольку смешивание краски является односторонней функцией.
Озарение снизошло на Хеллмана глубокой ночью, так что, когда он закончил расчеты, было уже слишком поздно, чтобы звонить Диффи и Мерклю. Ему пришлось ждать утра, когда он смог продемонстрировать свое открытие двум единственным в мире людям, кто верил в возможность решения проблемы распределения ключей. «Осенило меня, — говорит Хеллман, — но в разработке принципов участвовали мы все вместе». Диффи сразу же осознал всю мощь открытия Хеллмана: «Марти объяснил свою систему обмена ключами во всей ее простоте. Когда я слушал его, то понял, что ка-кое-то время эта идея крутилась и у меня в голове, но так и не выкристаллизовалась».
Как известно, схема обмена ключами Диффи-Хеллмана-Меркля дает возможность Алисе и Бобу установить секретную переписку посредством открытых переговоров. Это было одно из самых алогичных открытий в истории науки, вынудившее криптографический истэблишмент переработать правила шифрования. Диффи, Хеллман и Меркль во всеуслышание сообщили о своем открытии на национальной компьютерной конференции в июне 1976 года, чем поразили аудиторию, состоящую из экспертов по криптокрафии и криптоанализу. На следующий год они подали заявку на патент. Впредь Алисе и Бобу больше не было нужды встречаться, чтобы обменяться ключом. Вместо этого Алиса могла просто позвонить Бобу по телефону, обменяться с ним парой чисел, сообща создать секретный ключ, а затем приступить к зашифровыванию.
Хотя обмен ключами Диффи-Хеллмана-Меркля оказался гигантским шагом вперед, сама система была несовершенной, поскольку по своей сути оказалась неудобной. Представим, что Алиса живет на Гавайях и хочет послать сообщение по электронной почте Бобу, живущему в Стамбуле. Боб в этот момент, возможно, спит, но электронная почта удобна тем, что Алиса может послать сообщение в любой момент и оно будет находиться в компьютере Боба, ожидая, пока он не проснется. Однако, если Алиса желает зашифровать свое сообщение, то ей нужно согласовать ключ с Бобом, а чтобы осуществить обмен ключами, для Алисы и Боба лучше одновременно находиться в режиме онлайн, так как для создания ключа требуется обоюдный обмен информацией. Так что Алисе придется ждать, пока проснется Боб. Как вариант, Алиса могла бы отправить свою часть и ожидать 12 часов ответа Боба; при получении ответа Боба ключ будет создан, и Алиса сможет, если сама не будет спать в это время, зашифровать и отправить сообщение. Так или иначе, но система обмена ключами Хеллмана затрудняет непринужденное общение по электронной почте.
Хеллман разрушил один из догматов криптографии и доказал, что Бобу и Алисе не нужно встречаться, чтобы условиться о секретном ключе. Теперь уже кто-нибудь просто обязан был предложить более эффективную схему, позволяющую справиться с проблемой распределения ключей.
Мэри Фишер никогда не забудет тот день, когда Уитфилд Диффи впервые пригласил ее на свидание: «Он знал, что я была фанатично предана космосу, и поэтому предложил пойти посмотреть на запуск ракеты. Уит объяснил, что сегодня вечером он ушел, чтобы увидеть старт Скайлэба, и мы ехали всю ночь и прибыли туда примерно в 3 утра. Как в те дни говорили, «птичка уже летела к нам». У Уита было удостоверение представителя прессы, но у меня его не было. Поэтому, когда потребовали мое удостоверение личности и спросили, кто я такая, Уит ответил: «Моя жена». Это было 16 ноября 1973 года». В конце концов, они действительно поженились, и в первые годы Мэри поддерживала мужа во время его криптографических раздумий. Диффи все еще работал в качестве аспиранта, получая скудное жалованье. И чтобы свести концы с концами, Мэри, археолог по образованию, нанялась на работу в Бритиш Пертолеум.
Когда Мартин Хеллман открыл свой метод обмена ключами, Уитфилд Диффи разрабатывал совершенно иной подход к решению проблемы распределения ключей. У него часто случались долгие периоды бесплодных раздумий во время одного из которых, в 1975 году, он был настолько расстроен, что уверял Мэри, что он неудачник, который никогда ничего не добьется, и даже предложил ей найти кого-нибудь другого. Но в ответ Мэри возразила, что она беспредельно верит в него, а спустя всего лишь две недели Диффи предложил поистине блестящую идею.
Он до сих пор вспоминает, как идея мелькнула у него в голове, а затем чуть было не исчезла: «Я спускался вниз по лестнице, чтобы купить кока-колу, и почти забыл об идее. Я помнил, что думал о чем-то интересном, но совершенно не мог припомнить, что же это было. Затем она всплыла в памяти, и я почувствовал прилив возбуждения с настоящим адреналиновым шоком. Впервые с тех пор, как я начал заниматься криптографией, я понимал, что обнаружил что-то действительно стоящее. Все, что мне удавалось до сегодняшнего дня найти в этой области, представлялось просто техническими деталями». Это случилось в полдень, и Диффи пришлось томиться ожиданием еще пару часов, пока не вернулась Мэри. «Уит ждал у двери», — вспоминает она. «Он сказал, что должен что-то сообщить мне, и у него было забавное выражение лица. Я вошла, и он произнес: «Сядь, пожалуйста, я хочу поговорить с тобой. Я думаю, что сделал великое открытие; я знаю, что я — первый человек, который сделал это». В этот момент весь мир для меня замер. Я почувствовала себя так, словно я — героиня голливудского фильма».
Диффи придумал новый вид шифра — шифра, который включал в себя так называемый асимметричный ключ. Все те алгоритмы шифрования, о которых до сих пор рассказывалось в этой книге, были симметричными , то есть расшифровывание представляло собой просто процесс, обратный зашифровыванию. К примеру, чтобы зашифровать сообщение, в шифровальной машине «Энигма» используется определенный ключ, а получатель, чтобы его расшифровать, использует идентичную шифровальную машину с тем же самым ключом. Точно так же при зашифровывай и и с помощью алгоритма DES применяется ключ для выполнения 16 раундов шифрования, а затем при расшифровывании с помощью алгоритма DES используется этот же ключ для выполнения 16 раундов, только в обратном порядке. Оба, и отправитель, и получатель, фактически обладают равным знанием, и оба они используют один и тот же ключ для зашифровывания и расшифровывания, то есть их взаимоотношение является симметричным. С другой стороны, в системе с асимметричным ключом, как это следует из названия, ключ для зашифровывания и ключ для расшифровывания не идентичны. При использовании асимметричного шифра, если Алиса знает ключ для зашифровывания, она сможет зашифровать сообщение, но вот расшифровать его не сумеет. Чтобы расшифровать сообщение, Алиса должна иметь доступ к ключу для расшифровывания. Вот в этом-то различии между ключом для зашифровывания и ключом для расшифровывания и заключается особенность асимметричного шифра.