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

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

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

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

Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии – проблему распределения ключей.

Предисловие

Проблема передачи ключа по открытым каналам была большой проблемой криптографии прошлого века. Но эту проблему удалось решить после появления алгоритма Диффи-Хеллмана. Данный алгоритм позволил дать ответ на главный вопрос: "Как при обмене зашифрованными посланиями уйти от необходимости передачи секретного кода расшифровки, который, как правило, не меньше самого послания?" Открытое распространение ключей Диффи-Хеллмана позволяет паре пользователей системы выработать общий секретный ключ, не обмениваясь секретными данными.

История

Основы криптографии с открытыми ключами были выдвинуты Уитфилдом Диффи(Whitfield Diffie) и Мартином Хеллманом(Martin Hellman), и независимо Ральфом Мерклом(Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования - и что может быть невозможно, получить один ключ из другого. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции 1976г., через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptography" ("Новые направления в криптографии").

Годом позже был изобретен первый алгоритм асимметричного шифрования RSA, который позволил решить проблему общения через незащищённый канал.

В 2002 году Мартин Хеллман писал:

«Эта система … с тех пор известна под названием алгоритма Диффи — Хеллмана. Однако, когда система была впервые описана на бумаге Диффи и мной, это была система распространения публичных ключей, концепция которой была выработана Мерклем, и поэтому она должна называться „алгоритмом Диффи — Хеллмана — Меркля“, если её связывают с именами. Я надеюсь что это небольшое изменение поможет признанию равного вклада Меркля в изобретение криптографии с открытыми ключами.»

Следуя данной трактовке, журнале U.S. Patent 4 200 770, некогда описывающем данный алгоритм, отметил его создателями уже три автора - Хеллман, Диффи и Меркль.

Только в декабре 1997 года появилась обновленная информация о том что в Малькольм Вильямсон уже в 1974 году изобрел математический алгоритм, основанный на коммутативности показателей при последовательном возведении в степень ( (bx)y = (by)x = bxy). Данный метод можно назвать аналогом алгоритма Диффи-Хеллмана.

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

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

$A=g^a \bmod p$ (1)

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

$B=g^b \bmod p$ (2)

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

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

$B^a\bmod p=g^{ab}\bmod p$ (3)

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

$A^b\bmod p=g^{ab}\bmod p$ (4)

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

$K=g^{ab}\bmod p$ (5)

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

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

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

1. генерирует случайное натуральное число a — закрытый ключ
2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

   p является случайным простым числом

   (p-1)/2 также должно быть случайным простым числом (для повышения безопасности)

   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 не обязано быть большим и обычно имеет значение в пределах первого десятка.

Пример

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

• s = секретный ключ. s = 2
• g = открытое простое число. g = 5
• p = открытое простое число. p = 23
• a = секретный ключ Алисы. a = 6
• A = открытый ключ Алисы. A = g^a mod p = 8
• b = секретный ключ Боба. b = 15
• B = открытый ключ Боба. B = g^b 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. Стороны договариваются о параметрах алгоритма p и g
2. Стороны генерируют свои ключи — a, b и c
3. Алиса вычисляет $A=g^a$ и посылает его Бобу
4. Боб вычисляет $A=(g^a)^b$ = $g^{ab}$ и посылает его Кэрол
5. Боб вычисляет $A=g^b$ и посылает его Кэрол
6. Кэрол вычисляет $A=(g^{b})^c = g^{bc}$ и посылает его Алисе.
7. Алиса вычисляет $A=(g^{bc})^a = g^{bca} = g^{abc}$ и использует его как свою тайну.
8. Кэрол вычисляет $A=g^c$ и посылает его Алисе
9. Алиса вычисляет $A=(g^c)^a = g^{ca}$ и посылает его Бобу
10. Боб вычисляет $A=(g^{ca})^b = g^{cab} = g^{abc}$ и использует его как свою тайну

В данной ситуации любой участник может видеть $A=g^a$, $A=g^b$ , $A=g^c$ , $A=g^{ab}$ , $A=g^{ac}$, $A=g^{bc}$, но при этом не может видеть любую комбинацию $A=g^{abc}$.

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

• Передача ключа должна начинаться с «пустого» ключа g. Весь секрет состоит в повышении текущего значения показателя каждого участника один раз;
• Любое промежуточное значение может быть раскрыто публично, но окончательное значение представляет из себя секретный ключ, который никогда не должен быть публично раскрыт. Таким образом, каждый пользователь получает свою копию тайного ключа и передает его последующему.

Шифрование с открытым ключом

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

На практике, алгоритм Диффи-Хеллмана не используется таким образом. В данной области доминирующим алгоритм с открытым ключом является RSA. Это больше обусловлено в силу коммерческих выгод, так как именно компанией RSA Data Security был создан центр сертификации. К тому же алгоритм Диффи-Хеллмана не может быть использован при подписании сертификатов.

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

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

Криптографическая стойкость

Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления $K = g^{ab} \bmod p$ по известным p, g, $A = g^a \bmod p$ и $B = g^b \bmod p$), основана на предполагаемой сложности проблемы дискретного логарифмирования.

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

Шаг	Алиса	Меллори	Боб
1	ga→	ga
2	gn←	gn
	gam	gan
3		gm→	gm
4		gb	gb
		gmb←	gmb

То есть, Меллори получает один ключ общий с Алисой (которая считает, что это Боб), и один ключ общий с Бобом (который считает, что это Алиса). А, следовательно, он может получать от Алисы любое сообщение для Боба расшифровать его ключом, прочитать, зашифровать ключом и передать Бобу. Таким образом, подлог может оставаться незамеченным очень долгое время.

Задача Диффи-Хеллмана и задача дискретного логарифмирования

Стойкость разделенного ключа в протоколе Диффи-Хеллмана обеспечивается вычислением значенияе $g^{ab}mod p$ по заданным числам $g^a$ и $g^b$. Эта задача называется вычислительной проблемой Диффи-Хеллмана (CDH problem —Diffie-Hellman problem).

Вычислительная проблема Диффи-Хеллмана(в конечном поле)

ИСХОДНЫЕ ДАННЫЕ:
desq$F_q$ : описание конечного поля $F_q$ ;
g∈ $F_q^*$— порождающий элемент группы $F_q^*$ ;
$g_a$,$g_b$∈$F_q^*$, где 0 < a, b < q.
РЕЗУЛЬТАТ:
$g^{ab}$

Такая формулировка представляет собой общую постановку задачи в конечном поле $F_q$ представляет общий случай, для Диффи-Хеллмана используется специальный случай. Если бы проблему Диффи-Хеллмана было легко решить, то значение $g^{ab} mod p$ можно было бы найти, зная числа $p$, $g$, $g^a$ и $g^b$, которые являются частью протокола. Предполагая, что противник обладает возможностями перехвата информации, следует предположить, что эти числа не являются для него секретом. Проблема Диффи-Хеллмана опирается на сложность вычисления дискретного логарифма (discrete logarithm problem).

Задача дискретного логарифмирования (в конечном поле)

ИСХОДНЫЕ ДАННЫЕ:
desq$F_q$ : описание конечного поля $F_q$ ;
g∈ $F_q^*$— порождающий элемент группы $F_q^*$ ;
h ∈${}_U$$F_q^*$
РЕЗУЛЬТАТ:
Уникальное число a < q, удовлетворяющее условию h = $g^a$.
Целое число a обозначается как $log_g$h.

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

Интуитивно ясно, что сложность решения этих задач зависит как от размера поля Fq, так и от выбора параметров (открытого параметра g и секретных чисел a и b). Очевидно, что небольшие варианты этих задач являются разрешимыми. Полученные сведения позволяют сформулировать точные предположения о неразрешимости проблемы Диффи–Хеллмана и задачи дискретного логарифмирования.

Предположение 1 - Условия неразрешимости проблемы Диффи-Хеллмана

Алгоритмом решения проблемы Диффи-Хеллмана называется вероятностный полиномиальный алгоритм A с преимуществом ε > 0:

ε = Prob[$g^{ab}$$\longleftarrow$A(desc($F_q$), g,$g^a$,$g^b$)].

где входные данные А указанны в определение (Вычислительная проблема Диффи-Хеллмана) (в конечном поле).

Пусть IG — генератор вариантов, получающий на вход число $1^k$ время работы которого является полиномом от параметра k, а результатом — 1) desq($F_q$), где |q| = k, и 2) порождающий элемент g ∈$F_q^*$.

Будем говорить, что генератор IG удовлетворяет условиям неразрешимости проблемы Диффи-Хеллмана, если для вариантов IG($1^k$) не существует алгоритма решения с преимуществом ε> 0, которое не является пренебрежимо малым по сравнению со всеми достаточно большими числами k.

Предположение 2 - Условия неразрешимости задачи дискретного логарифмирования

Алгоритмом решения задачи дискретного логарифмирования называется вероятностный полиномиальный алгоритмA с преимуществом ε > 0:

ε = Prob[$logh$$\longleftarrow$A(desc($F_q$), g, h)]

где входные данные А указанны в определение (Вычислительная проблема Диффи-Хеллмана) (в конечном поле).

Пусть IG — генератор вариантов, получающий на вход число $1^k$ время работы которого является полиномом от параметра k, а результатом — 1) desq($F_q$), где |q| = k, и 2) порождающий элемент g ∈$F_q^*$ и 3) элемент h ∈$F_q^*$

Будем говорить, что генератор IG удовлетворяет условиям неразрешимости проблемы Диффи-Хеллмана, если для вариантов IG($1^k$) не существует алгоритма решения с преимуществом ε> 0, которое не является пренебрежимо малым по сравнению со всеми достаточно большими числами k.

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

Источники

• Брюс Шнаер "Прикладная Криптография"
• Шифрование-асимметричные методы Глава 8 ("Шифрование с открытым ключом", "Обмен ключом без обмена ключем", "Криптографическая стойкость", "Задача Диффи-Хеллмана и задача дискретного логарифмирования")
• Dieter Gollmann (2006). Computer Security Second Edition West Sussex, England: John Wiley & Sons, Ltd.
• The possibility of Non-Secret digital encryption J. H. Ellis, January 1970.
• Non-Secret Encryption Using a Finite Field MJ Williamson, January 21, 1974.
• Thoughts on Cheaper Non-Secret Encryption MJ Williamson, August 10, 1976.
• New Directions in Cryptography W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644–654.
• Cryptographic apparatus and method Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, 29 April 1980
• The History of Non-Secret Encryption[dead link] JH Ellis 1987 (28K PDF file) (HTML version[dead link])
• The First Ten Years of Public-Key Cryptography Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp: 560–577 (1.9MB PDF file)
• Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Handbook of Applied Cryptography Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. (Available online)
• Singh, Simon (1999) The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography New York: Doubleday ISBN 0-385-49531-5
• An Overview of Public Key Cryptography Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42–49. (123kB PDF file)
• Diffie-Hellman key exchange explained in 5 minutes
• Oral history interview with Martin Hellman, Charles Babbage Institute, University of Minnesota. Leading cryptography scholar *Martin Hellman discusses the circumstances and fundamental insights of his invention of public key cryptography with collaborators Whitfield Diffie and Ralph Merkle at Stanford University in the mid-1970s.
• RFC 2631 – Diffie–Hellman Key Agreement Method E. Rescorla June 1999.
• Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography[dead link] (64K PDF file) (Description of ANSI 9 Standards)
• Diffie–Hellman Key Exchange – A Non-Mathematician’s Explanation by Keith Palmgren
• Crypt::DH Perl module from CPAN
• Hands-on Diffie–Hellman demonstration
• C implementation using GNU Multiple Precision Arithmetic Library[dead link]
• Diffie Hellman in 2 lines of Perl (using dc)
• Smart Account Management (SAcct) (using DH key exchange to derive session key)
• Talk by Martin Hellman in 2007, Google video

См. также

• Zebedee
• Обмен ключами
• Эллиптическая кривая Диффи-Хеллмана
• Пароль проверки подлинности ключевого соглашения
• CDH problem —Diffie-Hellman problem