Кому нужна математика? Понятная книга о том, как устроен цифровой мир - Андрей Райгородский

1. Схема Диффи – Хеллмана

Для начала введем обозначения. Пусть р – заданное простое число, g – заданное натуральное число, g < p. На самом деле g это так называемый первообразный корень числа р. Об этом мы расскажем ниже, в приложении 2 и приложении 3 к главе 6. Цель данного раздела – доказать, что в схеме Диффи – Хеллмана Алиса и Боб действительно получают один и тот же ключ.

Для любых натуральных чисел n и р мы воспользуемся стандартным обозначением для остатка от деления n на р:

n(mod p) = [остаток от деления n на p].

(Читается «n по модулю p».)

Итак, Алиса задумала число х, а Боб число у. Схема Диффи – Хеллмана состоит из двух шагов.

Шаг 1. Алиса передает Бобу

a = (g^x) (mod p).

Боб передает Алисе

b = (g^y) (mod p).

Шаг 2. Алиса вычисляет ключ

K_A = (b^x) (mod p).

Боб вычисляет ключ

K_B = (a^y) (mod p).

Утверждение. Боб и Алиса получили один и тот же ключ K = K_A = K_B.

Доказательство. Нам нужно доказать, что K_A = K_B. Поскольку а и b – это остатки от деления на р, то существуют такие целые числа k и l, при которых

a = g^x − kp, b = g^y − lp.

Подставив эти выражения в формулы для ключей, получаем:

K_A = (g^y − lp)^x (mod p),

K_B = (g^x − kp)^y (mod p).

Заметим, что в выражении для K_A можно расписать (g^y − lp)^x следующим образом:

где А – это целое число, то есть рА делится на р. Таким образом получаем

K_A = ((g^y − lp)^x) (mod p) = ((g^y)^x + pA) (mod p) = (g^y)^x (mod p).

Совершенно аналогично для какого-то целого числа B получаем

K_B = ((g^x − kp)^y) (mod p) = ((g^x)^y + pB) (mod p) = (g^x)^y (mod p).

Результат теперь очевиден, поскольку

(g^y)^x = g^yx = g^xy = (g^x)^y.

2. Дискретное логарифмирование

Вспомним, что логарифм числа у по основанию g – это такое число х, для которого выполняется

g^x = y.

Легко заметить, что очень похожая операция лежит в основе схемы Диффи – Хеллмана.

После возведения в степень мы берем остаток от деления на р. Как мы уже упоминали выше, в математике такая операция обозначается g^x (mod p) (читается «g в степени х по модулю р»). При этом, естественно, g и х натуральные числа и у g нет общих делителей с р.