Обмен ключами по алгоритму Диффи-Хеллмана

Данный алгоритм помогает обмениваться секретным ключом для симметричных криптосистем, но использует метод, очень похожий на асимметричный алгоритм RSA. Алгоритм назван по фамилиям его создателей Диффи (Whitfield Diffie) и Хеллмана (Martin Hellman).

Предположим, что двум абонентам необходимо провести конфиденциальную переписку, а в их распоряжении нет первоначально оговоренного секретного ключа. Однако, между ними существует канал, защищенный от модификации. Пусть абонентам известны некоторые два числа v и n. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют случайные или псевдослучайные простые числа: абонент A – число Xa, абонент B – число Xb. Затем абонент A вычисляет и пересылает абоненту B значение:

A ® B: (v^Xa) mod n,

а абонент B вычисляет и пересылает абоненту A:

B ® A: (v^Xb) mod n,

A: k₁₂ = (((v^Xb) mod n) ^Xa ) mod n,

B: k₂₁ = (((v^Xa) mod n) ^Xb ) mod n.

На самом деле операция возведения в степень переносима через операцию взятия модуля по простому числу (то есть коммутативна в конечном поле), то есть у обоих абонентов получилось одно и то же число: (v^Xa·Xb) mod n. Его они и могут использовать в качестве секретного ключа.

Пример.

v = 17; n = 23;

Xa = 3;

v^Xa = 17³ mod 23 = 4 913 mod 23 = 14;

Xb = 5;

v^Xb = 17⁵ mod 23 = 1 419 857 mod 23 = 21;

k_ab = (v^Xb)^Xa = 21³ = 9 261 mod 23 = 15;

k_ba = (v^Xa)^Xb = 14⁵ = 537 824 mod 23 = 15.

Аналог алгоритма Диффи-Хеллмана с использованием эллиптических кривых

Сначала выбираются параметры эллиптической кривой Ep(a,b) (p ≈ 2¹⁸⁰) и генерирующая точка G, принадлежащая этой кривой. При выборе G важно, чтобы наименьшее значение q, при котором [ q ] G = O, оказалось очень большим простым числом. Эти параметры известны всем абонентам системы.

1. A: выбирает целое число n_A < q; вычисляет точку P_A = [ n_A ] G;

2. B: выбирает целое число n_B < q; вычисляет точку P_B = [ n_B ] G;

3. A ® B: P_A;

4. A ® B: P_B;

5. A: K = [ n_A ] P_B;

6. B: K = [ n_B ] P_A.

Приложение 1. Генерация простых чисел

Проверка на простоту

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

1) проверяем, делится ли n на какое-нибудь простое число не превосходящее 5 000;

2) если n не делится ни на одно из них, то применяем к нему тест Миллера, используя в качестве оснований первые 20 простых чисел;

3) если тест Миллера по всем этим основаниям дает неопределенный ответ, то подвергаем n тесту на простоту.