Математики, шпионы и хакеры. Кодирование и криптография

Предположим, что отправитель по имени Джеймс шифрует сообщение с помощью своего ключа и посылает результат получателю по имени Питер, который повторно шифрует зашифрованное послание своим ключом и возвращает его отправителю. Джеймс расшифровывает сообщение своим ключом и посылает назад результат, т. е. текст, в данный момент зашифрованный только ключом Питера, который его расшифровывает. Казалось бы, вековая проблема безопасного обмена ключами решена! Неужели это правда? К сожалению, нет. В любом сложном алгоритме шифрования порядок применения ключей имеет решающее значение, а в нашем примере мы видим, что Джеймс расшифровывает сообщение, которое уже зашифровано другим ключом. Когда порядок ключей меняется, результат будет абракадаброй. Вышеизложенный пример не объясняет теории подробно, но он дает подсказку к решению проблемы. В 1976 г. два молодых американских ученых, Уитфилд Диффи и Мартин Хеллман, нашли способ, при котором два человека могут обмениваться зашифрованными сообщениями без всякого обмена секретными ключами. Этот метод использует модульную арифметику, а также свойства простых чисел. Идея заключается в следующем.

* * *

АВТОРЫ АЛГОРИТМА

Уитфилд Диффи родился в 1944 г. в Соединенных Штатах. Получив степень бакалавра математики в Массачусетском технологическом институте (МП), он с 2002 по 2009 гг. работал главой службы безопасности и вице-президентом компании Sun Microsystems (в Калифорнии).

Инженер Мартин Хеллман родился в 1945 г. и работал в IBM и Массачусетском технологическом институте, где сотрудничал с Диффи.

Уитфилд Диффи

* * *

1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это число N_j1

2. Питер выбирает другое случайное число, которое он тоже держит в секрете. Мы обозначим это число N_p1

3. Затем и Джеймс, и Питер применяют к своим числам функцию вида f(x) = а^х (mod р) где р — простое число, известное им обоим.

• После этой операции Джеймс получает новое число, N_j2, которое он посылает Питеру.

• А Питер посылает Джеймсу свое новое число N_p2

4. Джеймс вычисляет N^Nj1_p2 (mod р) и получает новое число С_j.

5. Питер вычисляет N^Np1_j2 (mod р) и получает новое число С_р.

Хотя это кажется невозможным, но числа С_j и С_р являются одинаковыми. И теперь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией только тогда, когда они выбрали функцию f(x) = а^х (mod р) и послали друг другу числа N_j2 и N_p2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:

a^Nj1•Np1  (mod p).

Важно также учесть, что данная функция имеет одну особенность: она необратима, то есть зная саму функцию и результат ее применения к переменной х, невозможно (или, по крайней мере, очень сложно) найти исходное значение х.

Далее, чтобы пояснить идею, мы повторим процесс с конкретными значениями.

Возьмем следующую функцию:

f(x) = 7^х (mod 11).

1. Джеймс выбирает число, N_J1 например, 3, и подставляет в функцию f(3) = 7³   2 (mod 11).

2. Питер выбирает число, N_p1 например, 6, и подставляет в функцию f(6) = 7⁶  4 (mod 11).

3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу — свой, 4.

4. Джеймс считает 4³  9 (mod 11).

5. Питер считает 2⁶  9 (mod 11).

Это число, 9, и будет ключом системы.

Джеймс и Питер обменялись функцией f(х) и числами 2 и 4. Будет ли эта информация полезна злоумышленнику? Допустим, злоумышленник знает и функцию, и числа. Тогда он должен найти N_j1 и N_p1 по модулю 11, где N_j1и N_p1 — такие числа, которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удастся узнать эти числа, он получит ключ, лишь вычислив a^Nj1•Np1  по модулю р. Решение уравнения вида у = а^х, кстати, в математике называется дискретным логарифмом.

Например, в случае:

f(х) = 3^х (mod 17),

зная, что 3^х = 15 (mod 17), и пробуя различные значения х, мы получим, что х = 6.

Алгоритмы этого типа и задачи с дискретным логарифмом не получали должного внимания вплоть до начала 1990 гг., и лишь в последнее время эти методы начали разрабатываться. В приведенном выше примере число 6 является дискретным логарифмом числа 15 с основанием 3 по модулю 17.

Особенностью этого типа уравнений, как мы уже говорили, является сложность обратного процесса — они асимметричны. Если р больше 300, а число а больше 100, решение — и, следовательно, взлом ключа — становится крайне сложной задачей.

* * *