Протокол Диффи — Хеллмана

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:44, 1 февраля 2016.

Протокол Ди́ффи-Хе́ллмана[1] (DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричное шифрование|симметричного шифрования.

Описание алгоритма

Самый распространенный пример во всех учебных пособиях: Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны два числа g и p, желательно простых, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб — число b. Затем Алиса вычисляет значение (1):

(1)

и пересылает его Бобу, а Боб вычисляет (2):

(2)

и передаёт Алисе. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть, у него нет возможности вмешаться в процесс передачи).

На втором этапе Алиса на основе имеющегося у неё a и полученного по сети B вычисляет значение (3):

(3)

Боб на основе имеющегося у него b и полученного по сети A вычисляет значение (4):

(4)

Как нетрудно видеть, у Алисы и Боба получилось одно и то же число (5):

(5)

Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления (3) или (4) по перехваченным и , если числа p, a, b выбраны достаточно большими.

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

  1. Генерирует случайное натуральное число a — закрытый ключ
  2. Совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где
    p является случайным простым числом
    (p-1)/2 также должно быть случайным простым числом (для повышения безопасности)
    g является первообразным корнем по модулю p (также является простым числом)
  3. Вычисляет открытый ключ A, используя преобразование над закрытым ключом
    A = ga mod p
  4. Обменивается открытыми ключами с удалённой стороной
  5. Вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a
    K = Ba mod p
    К получается равным с обеих сторон, потому что:
    Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p

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

Пример

Ева — криптоаналитик. Она читает пересылку Боба и Алисы, но не изменяет содержимого их сообщений[2].

  • s = секретный ключ. s = 2
  • g = первообразный корень по модулю р. g = 5
  • p = открытое простое число. p = 23
  • a = секретный ключ Алисы. a = 6
  • A = открытый ключ Алисы. A = ga mod p = 8
  • b = секретный ключ Боба. b = 15
  • B = открытый ключ Боба. B = gb mod p = 19
Alice
Знает Не знает
p = 23 b = ?
g = 5
a = 6
A = 56 mod 23 = 8
B = 5b mod 23 = 19
s = 196 mod 23 = 2
s = 8b mod 23 = 2
s = 196 mod 23 = 8b mod 23
s = 2
Bob
Знает Не знает
p = 23 a = ?
g = 5
b = 15
B = 515 mod 23 = 19
A = 5a mod 23 = 8
s = 815 mod 23 = 2
s = 19a mod 23 = 2
s = 815 mod 23 = 19a mod 23
s = 2
Eve
Знает Не знает
p = 23 a = ?
g = 5 b = ?
s = ?
A = 5a mod 23 = 8
B = 5b mod 23 = 19
s = 19a mod 23
s = 8b mod 23
s = 19a mod 23 = 8b mod 23

Протокол Диффи — Хеллмана для конференц-связи

Разновидность протокола используемого при общении трех и более участников. Участники:

  1. ,где - простое, - первообразный корень.

Ссылки

  1. Протокол Диффи-Хэллмана — Википедия https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана
  2. Cryptographic apparatus and method Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, 29 April 1980)