Реферат Список основных специальных терминов с определениями

3.5. Алгоритм шифрования Деффи-Хеллмана

Схема обмена ключами Диффи — Хеллмана, изобретённая в 1976 году Уитфилдом Диффи и Мартином Хеллманом под влиянием работ Ральфа Меркле (Ralph Merkle), стала первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи. Годом позже был изобретен первый алгоритм асимметричного шифрования RSA, который решил проблему общения через незащищённый канал кардинально, уже не требуя, чтобы каждая сторона имела копию одного и того же секретного ключа.

Предположим, что обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = g^amod p и пересылает его второму, а второй вычисляет B = g^bmod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение B^amod p = g^abmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение A^bmod p = g^abmod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = g^abmod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления g^abmod p по перехваченным g^amod p и g^bmod p, если числа p,a,b выбраны достаточно большими.

Рисунок 3.3

Алгоритм Диффи — Хеллмана

где K — итоговый общий секретный ключ.

При работе алгоритма каждая сторона:

1. Пользователь 1 генерирует случайное число a, которое является закрытым ключом
2. Совместно с удалённой стороной устанавливает открытые параметры p и g такие, что:
p является случайным простым числом.
(p-1)/2 также должно быть случайным простым
g является обратным числом по модулю p
3. Вычисляет открытый ключ A по формуле (3.3)

𝐴 = 𝑔∗𝑎 𝑚𝑜𝑑 𝑝 (3.3)

4. Пользователи обмениваются ключами

5. Вычисляет общий секретный ключ K по формуле (3.4)

𝐾 = 𝐵∗𝑎 𝑚𝑜𝑑 𝑝 (3.4)

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

𝐵∗𝑎 𝑚𝑜𝑑 𝑝 = (𝑔𝑏 𝑚𝑜𝑑 𝑝)𝑎 𝑚𝑜𝑑 𝑝 = 𝑔𝑎𝑏 𝑚𝑜𝑑 𝑝 = (𝑔𝑎 𝑚𝑜𝑑 𝑝)𝑏 𝑚𝑜𝑑 𝑝 = 𝐴∗𝑏 𝑚𝑜𝑑 𝑝 (3.5)

Формула (3.5) доказывает, что с помощью секретных ключей разных пользователей можно вычислить общий секретный ключ.

В практических реализациях, для a и b используются числа порядка 10¹⁰⁰ и p порядка 10³⁰⁰. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.