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

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

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

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

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

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

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

a = (g^>x) (modp).

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

b = (g^>y) (modp).

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

K_>A = (b^>x) (modp).

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

K_>B = (a^>y) (modp).

Утверждение.Боб и Алиса получили один и тот же ключ 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(modp),

K_>B = (g^>x −kp)^>y(modp).

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

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

K_>A = ((g^>y −lp)^>x) (modp) = ((g^>y)^>x +pA) (modp) = (g^>y)^>x(modp).

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

K_>B = ((g^>x −kp)^>y) (modp) = ((g^>x)^>y +pB) (modp) = (g^>x)^>y(modp).

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

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

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

g^>x =y.

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

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

Одна нетривиальная теорема из теории чисел (см., например,{35}) утверждает, что для каждого простого р существует такое число g, что все числа

разные, то есть служат перестановкой множества 1, 2, …, p − 1 (среди них нет нуля, поскольку g < p и, значит, g^>х не делится на р). Например,

Из этого следует возможность корректного определения дискретного логарифма, который еще называется индексом. А именно: «логарифм» произвольного числа y ∈ {1, 2, …, p − 1} по основанию g – это тот самый, уникальный, x ∈ {1, 2, …, p − 1}, при котором выполняется g^>x (mod p) = y. Поскольку для всех x < p остатки разные, то х определяется однозначно. Операция нахождения такого х называется операцией дискретного логарифмирования. Она очень сложная, и никто не знает, можно ли придумать способ ее быстрой реализации.