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

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

Данный алгоритм не применяется для шифрования сообщений или формирования электронной подписи. Его назначение – в распределении ключей.

Это была первая криптосистема, которая позволяла защищать информацию без использования секретных ключей, передаваемых по защищенным каналам.

Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб— число b. Затем Алиса вычисляет значение^[5] (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 является случайным простым числом

g является первообразным корнем по модулю p

3. вычисляет открытый ключ A, используя преобразование над закрытым ключом

A = g^a mod p

4. обменивается открытыми ключами с удалённой стороной

5. вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a

K = B^a mod p

К получается равным с обеих сторон, потому что:

B^a mod p = (g^b mod p)^a mod p = g^ab mod p = (g^a mod p)^b mod p = A^b mod p

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

Использование алгоритма Диффи-Хеллмана не ограничивается двумя участниками. Он может быть применен на неограниченное количество пользователей. Рассмотрим ситуацию, когда Алиса, Боб и Кэрол вмести генерируют исходный ключ. В данном случае последовательность действий будет следующая^[8]:

1. Стороны договариваются о параметрах алгоритма p и g

2. Стороны генерируют свои ключи — a, b и c

3. Алиса вычисляет и посылает его Бобу

4. Боб вычисляет = и посылает его Кэрол

5. Боб вычисляет и посылает его Кэрол

6. Кэрол вычисляет и посылает его Алисе.

7. Алиса вычисляет и использует его как свою тайну.

8. Кэрол вычисляет и посылает его Алисе

9. Алиса вычисляет и посылает его Бобу

10. Боб вычисляет и использует его как свою тайну

В данной ситуации любой участник мог видеть , , , , , , но при этом не может видеть любую комбинацию .

Для того чтобы данный алгоритм был эффективно применен для большой группы людей необходимо соблюдение двух основных принципов:

· Передача ключа должна начинаться с «пустого» ключа g. Весь секрет состоит в повышении текущего значения показателя каждого участника один раз;

· Любое промежуточное значение может быть раскрыто публично, но окончательное значение представляет из себя секретный ключ, которое никогда не должно быть публично раскрыто. Таким образом, каждый пользователь получает свою копию тайного ключа и передает его последующему.

Алгоритм Диффи-Хеллмана так же может быть использован при шифровании с открытым ключом. В этом случае общая схема остаётся аналогичной приведённой выше, но с небольшими отличиями. Алиса не передаёт значения p, g и A Бобу напрямую, а публикует их заранее в качестве своего открытого ключа. Боб выполняет свою часть вычислений, после чего шифрует сообщение симметричным алгоритмом, используя K в качестве ключа, и передает шифротекст Алисе вместе со значением B.Если имеется сообщество пользователей, каждый из пользователей может опубливать открытый ключ X= mod n, в общей базе данных. Если Алиса хочет установить связь с Бобом, ей надо получить открытый ключ Боба и сгенерировать их общий секретный ключ. Алиса может зашифровать сообщение открытым ключом и послать его Бобу. Боб извлечет открытый ключ Алисы и найдет общий секретный ключ. Каждая пара пользователей может использовать свой уникальный секретный ключ, не требуя обмена данными между пользователями. При этом все открытые ключи должны пройти проверку подлинности для того чтобы исключить "человека в середине"Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления по известным p, g, и , основана на предполагаемой сложности проблемы дискретного логарифмирования.

Протокол Диффи-Хеллмана отлично противостоит пассивному нападению, но в случае реализации атаки «человек посередине» он не устоит. В самом деле, в протоколе ни Алиса, ни Боб не могут достоверно определить, кем является их собеседник, поэтому вполне возможно представить следующую ситуацию, при которой Боб и Алиса установили связь с Меллори, который Алисе выдает себя за Боба, а Бобу представляется Алисой