Книга шифров

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

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

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