Чтение онлайн

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

Рис. 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, а это уже не тот результат, который мы получили бы в обычной арифметике. Эти результаты могут быть выражены в следующем виде: