Саймон Сингх - Книга шифров .Тайная история шифров и их расшифровки
Однако в модулярной арифметике эта же самая функция ведет себя не так благоразумно. Представьте, что нам сообщают, что 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 года, чем поразили аудиторию, состоящую из экспертов по криптокрафии и криптоанализу. На следующий год они подали заявку на патент. Впредь Алисе и Бобу больше не было нужды встречаться, чтобы обменяться ключом. Вместо этого Алиса могла просто позвонить Бобу по телефону, обменяться с ним парой чисел, сообща создать секретный ключ, а затем приступить к зашифровыванию.
