Книга шифров. Тайная история шифров и их расшифровки - Сингх Саймон - Страница 67

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

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

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

Некоторые самые элементарные шифры, такие как шифр Цезаря, являются настолько простыми, что порядок неважен. Однако в 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 часов.