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

Мы в уме сосчитали 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, и мы выполняем функцию, тогда:

3^x = З² = 3 х 3 = 9.

Другими словами, функция преобразует 2 в 9. В обычной арифметике по мере увеличения х возрастает также и значение функции. Поэтому если нам дано значение функции, то сравнительно несложно выполнить обратное преобразование и найти исходное значение.

Например, если результат равен 81, мы можем установить, что х равно 4, потому что 3⁴ =_81. Если мы ошибемся и предположим, что х равно 5, путем вычисления мы можем определить, что 3⁵ = 243, а это подскажет нам, что мы выбрали слишком большое значение х. После этого мы уменьшим х до 4 и получим правильный ответ. Короче говоря, даже когда наше предположение неверно, мы можем исправить свою ошибку и получить точное значение х, выполнив тем самым обратное преобразование функции.

Однако в модулярной арифметике эта же самая функция ведет себя не так благоразумно. Представьте, что нам сообщают, что 3^х по модулю 7 (mod 7) дает 1, и просят найти значение х. В голову ничего не приходит, поскольку мы, как правило, не знакомы с модулярной арифметикой. Мы можем предположить, что x = 5, и мы можем вычислить З⁵ (mod 7). В ответе получится 5, что слишком много, так как нам нужно, чтобы в ответе было 1. Напрашивается желание уменьшать значения х. Но так мы будем двигаться неверным путем, поскольку в действительности ответ будет x = 6.

_{Рис. 64 Модулярная арифметика выполняется на конечном множестве чисел, которые можно рассматривать как числа на циферблате часов. В этом случае мы можем вычислить 6 + 5 по модулю 7, если взять в качестве исходной точки 6 и отсчитать 5 делений, в результате чего мы окажемся на цифре 4.}

В обычной арифметике мы можем проводить проверку чисел и в состоянии понять, движемся ли мы в нужном направлении или выбранное направление неверно. Модулярная арифметика не дает нам

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

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

Спустя два года исследований в области модулярной арифметики и односторонних функций, «глупость» Хеллмана начала приносить плоды. Весной 1976 года он натолкнулся на алгоритм решения проблемы обмена ключами. За полчаса исступленной работы он доказал, что Алиса и Боб могут договориться о ключе, не встречаясь друг с другом, покончив, тем самым, с аксиомой, считавшейся непререкаемой в течение столетий. Идея Хеллмана основывалась на использовании односторонней функции вида Y^x (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. Чтобы определить ключ, она должна сделать либо то, что делает Боб, который, зная В, преобразует в ключ α, либо то, что делает Алиса, которая, зная А, преобразует в ключ β.

Однако Ева не знает, чему равны А и В, потому что Алиса и Боб не обменивались значениями этих чисел, держа их в секрете. Ева находится в безвыходном положении. У нее есть только одна надежда: теоретически, так как функция ей известна, она могла бы вычислить А из α, поскольку а представляет собой результат подстановки в нее А, или же она могла бы вычислить В из β, поскольку β представляет собой результат подстановки в нее В. К сожалению для Евы, эта функция является односторонней, так что хотя для Алисы преобразовать А в α, а для Боба — В в β не представляет сложности, Ева сможет выполнить обратное преобразование с огромным трудом, особенно в случае очень больших чисел.