Diffie-Hellman с тремя и более участниками *

Протокол обмена ключами Diffie-Hellman легко можно расширить на случай с тремя и более участниками. В приводимом примере Алиса, Боб и Кэрол вместе генерируют секретный ключ.

10. Алиса выбирает случайное большое целое число x и вычисляет

X = g^x mod n

11. Боб выбирает случайное большое целое число y и посылает Кэрол

Y = g^y mod n

12. Кэрол выбирает случайное большое целое число z и посылает Алисе

Z = g^z mod n

13. Алиса посылает Бобу

Z'=Z^x mod n

14. Боб посылает Кэрол *

X'=X^y mod n

15. Кэрол посылает Алисе

Y'=Y^zmod n

16. Алиса вычисляет

k = Y'^x mod n

17. Боб вычисляет

k = Z'^y mod n

18. Кэрол вычисляет

k = X'^z mod n

Секретный ключ k равен g^xyz mod n, и никто из подслушивающих каналы связи не сможет вычислить это значение. Протокол можно легко расширить для четверых и более участников, просто добавляются участники и этапы вычислений.

Расширенный Diffie-Hellman

Diffie-Hellman также работает в коммутативных кольцах [1253]. З. Шмули (Z. Shmuley) и Кевин МакКерли (Kevin McCurley) изучили вариант алгоритма, в котором модуль является составным числом [1441, 1038]. В.С. Миллер (V. S. Miller) и Нил Коблиц (Neal Koblitz) расширили этот алгоритм, используя эллиптические кривые [1095, 867]. Тахер ЭльДжамаль (Taher ElGamal) использовал основополагающую идею для разработки алгоритма шифрования и цифровой подписи (см. раздел 19.6).

Этот алгоритм также работает в поле Галуа GF(2^k) [1442, 1038]. В ряде реализаций используется именно этот подход [884, 1631, 1632], так как вычисления выполняются намного быстрее. Но и криптоаналитические вычисления выполняются намного быстрее, поэтому важно тщательно выбирать поле, достаточно большое, чтобы обеспечить нужную безопасность.

Hughes

Этот вариант алгоритма Diffie-Hellman позволяет Алисе генерировать ключ и послать его Бобу [745].

5. Алиса выбирает случайное большое целое число x и генерирует

k = g^x mod n

6. Боб выбирает случайное большое целое число y и посылает Алисе

Y = g^y mod n

7. Алиса посылает Бобу

X = Y^x mod n

8. Боб вычисляет

z = y^-1

k' = X^z mod n

Если все выполнено правильно, k = k'.

Преимуществом этого протокола над Diffie-Hellman состоит в том, что k можно вычислить заранее, до взаимодействия, и Алиса может шифровать сообщения с помощью k задолго до установления соединения с Бобом. Она может послать сообщение сразу множеству людей, а передать ключ позднее каждому по отдельности.

Обмен ключом без обмена ключом

Если у вас сообщество пользователей, каждый может опубликовать открытый ключ, X = g^x mod n, в общей базе данных. Если Алиса захочет установить связь с Бобом, ей понадобится только получить открытый ключ Боба и генерировать их общий секретный ключ. Она может зашифровать сообщение этим ключом и послать его Бобу. Боб извлечет открытый ключ Алисы и вычислит общий секретный ключ.

Каждая пара пользователей может использовать уникальный секретный ключ, не требуется никаких предварительных обменов данными между пользователями. Открытые ключи должны пройти сертификацию, чтобы предотвратить мошеннические вскрытия, и должны регулярно меняться, но в любом случае это очень умная идея