Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году [496]. Его безопасность опирается на трудность вычисления дискретных логарифмов в конечном поле (в сравнении с легк о-стью возведения в степень в том же самом поле. Diffie-Hellman может быть использован для распределения ключей - Алиса и Боб могут воспользоваться этим алгоритмом для генерации секретного ключа - но его нельзя использовать для шифрования и дешифрирования сообщений .
Математика несложна. Сначала Алиса и Боб вместе выбирают большие простые числа п и g так, чтобы g было примитивом mod п. Эти два целых числа хранить в секрете необязательно, Алиса и Боб могут договориться об из использовании по несекретному каналу. Эти числа даже могут совместно использоваться группой пол ь-зователей. Без разницы. Затем выполняется следующий протокол:
(1) Алиса выбирает случайное большое целое число х и посылает Бобу X = gx mo&n
(2) Боб выбирает случайное большое целое число у и посылает Алисе F=/mod и
(3) Алиса вычисляет к = Г mod n
(4) Боб вычисляет
к' =Гто&п
Я к, и к' равны g^ mod п. Никто из подслушивающих этот канал не сможет вычислить это значение, им и з-вестно только n, g, Xn Y. Пока они не смогут вычислить дискретный логарифм и раскрыть х или у, они не смогут решить проблему. Поэтому, к - это секретный ключ, который Алиса и Боб вычисляют независимо .
Выбор g и п может заметно влиять на безопасность системы. Число (и-1)/2 также должно быть простым [1253]. И, самое главное, п должно быть большим: безопасность системы основана на сложности разложения на множители чисел того же размера, что и п. Можно выбирать любое g, которое является примитивом mod и; нет причин, по которым нельзя было бы выбрать наименьшее возможное g - обычно одноразрядное число. (К тому же, на самом деле, g не должно даже быть примитивом, оно только должно генерировать достаточно большую подгруппу мультипликативной группы mod и.)
Diffie-Hellman с тремяиболее участниками*
Протокол обмена ключами Diffie-Hellman легко можно расширить на случай с тремя и более участниками . В приводимом примере Алиса, Боб и Кэрол вместе генерируют секретный ключ.
(1) Алиса выбирает случайное большое целое число х и вычисляет X = gx mod n
(2) Боб выбирает случайное большое целое число у и посылает Кэрол 7=/mod и
(3) Кэрол выбирает случайное большое целое число z и посылает Алисе Z = /mod/i
(4) Алиса посылает Бобу Z'=ZX mod n
(5) Боб посылает Кэрол * Х=Г mod n
(6) Кэрол посылает Алисе r=Fmod n
(7) Алиса вычисляет к = Г mod n
(8) Боб вычисляет к = Zv mod n
(9) Кэрол вычисляет
к=Х*то&п
Секретный ключ к равен g^ mod n, и никто из подслушивающих каналы связи не сможет вычислить это значение. Протокол можно легко расширить для четверых и более участников, просто добавляются участники и этапы вычислений.