Данный алгоритм помогает обмениваться секретным ключом для симметричных криптосистем, но использует метод, очень похожий на асимметричный алгоритм RSA. Алгоритм назван по фамилиям его создателей Диффи (Whitfield Diffie) и Хеллмана (Martin Hellman).
Предположим, что двум абонентам необходимо провести конфиденциальную переписку, а в их распоряжении нет первоначально оговоренного секретного ключа. Однако, между ними существует канал, защищенный от модификации. Пусть абонентам известны некоторые два числа v и n. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют случайные или псевдослучайные простые числа: абонент A – число Xa, абонент B – число Xb. Затем абонент A вычисляет и пересылает абоненту B значение:
A ® B: (vXa) mod n,
а абонент B вычисляет и пересылает абоненту A:
B ® A: (vXb) mod n,
A: k12 = (((vXb) mod n) Xa ) mod n,
B: k21 = (((vXa) mod n) Xb ) mod n.
На самом деле операция возведения в степень переносима через операцию взятия модуля по простому числу (то есть коммутативна в конечном поле), то есть у обоих абонентов получилось одно и то же число: (vXa·Xb) mod n. Его они и могут использовать в качестве секретного ключа.
|
|
Пример.
v = 17; n = 23;
Xa = 3;
vXa = 173 mod 23 = 4 913 mod 23 = 14;
Xb = 5;
vXb = 175 mod 23 = 1 419 857 mod 23 = 21;
kab = (vXb)Xa = 213 = 9 261 mod 23 = 15;
kba = (vXa)Xb = 145 = 537 824 mod 23 = 15.
Аналог алгоритма Диффи-Хеллмана с использованием эллиптических кривых
Сначала выбираются параметры эллиптической кривой Ep(a,b) (p ≈ 2180) и генерирующая точка G, принадлежащая этой кривой. При выборе G важно, чтобы наименьшее значение q, при котором [ q ] G = O, оказалось очень большим простым числом. Эти параметры известны всем абонентам системы.
1. A: выбирает целое число nA < q; вычисляет точку PA = [ nA ] G;
2. B: выбирает целое число nB < q; вычисляет точку PB = [ nB ] G;
3. A ® B: PA;
4. A ® B: PB;
5. A: K = [ nA ] PB;
6. B: K = [ nB ] PA.
Приложение 1. Генерация простых чисел
Проверка на простоту
Для доказательства простоты данного нечетного числа n можно применять следующую стратегию:
1) проверяем, делится ли n на какое-нибудь простое число не превосходящее 5 000;
2) если n не делится ни на одно из них, то применяем к нему тест Миллера, используя в качестве оснований первые 20 простых чисел;
3) если тест Миллера по всем этим основаниям дает неопределенный ответ, то подвергаем n тесту на простоту.