ФЭНДОМ


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

Алгоритм был впервые опубликован Витфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом в 1976 году.

В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом.

История Править

Схема обмена ключами Диффи — Хеллмана, изобретённая в 1976 году при сотрудничестве Витфилда Диффи и Мартина Хеллмана, под сильным влиянием работы Ральфа Меркле (Ralph Merkle) о системе распространения публичных ключей, стала первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи. Для обеспечения устойчивости, по совету Джона Гилла (John Gill), была использована проблема дискретного логарифмирования. За несколько лет до этого эта же схема была изобретена Малькольмом Вильямсоном из английского штаба правительственной связи, но оставалась в секрете до 1997 года.

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

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

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

В патенте U.S. Patent 4,200,770 (англ.) (в настоящее время истёкшем), описывающем данный алгоритм, изобретателями значатся Хеллман, Диффи и Меркле.

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

Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A=g^a \bmod p и пересылает его второму, а второй вычисляет B=g^b \bmod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (т.е. у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение B^a\bmod p=g^{ab}\bmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение A^b\bmod p=g^{ab}\bmod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K=g^{ab}\bmod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления g^{ab} \bmod p по перехваченным g^a \bmod p и g^b \bmod p, если числа p, a, b выбраны достаточно большими.

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

  1. генерирует случайное натуральное число aзакрытый ключ
  2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где
    p является случайным простым числом
    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 или 5.

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

Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления K=gab mod p по известным p, g, A=ga mod p и B=gb mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования. Однако, хотя умение решать проблему дискретного логарифмирования позволит взломать алгоритм Диффи — Хеллмана, обратное утверждение до сих является открытым вопросом (другими словами, эквивалентность этих проблем не доказана).

Необходимо еще раз отметить, что алгоритм Диффи — Хеллмана работает только на линиях связи, надёжно защищённых от модификации. Если бы он был применим на любых открытых каналах, то давно снял бы проблему распространения ключей и, возможно, заменил собой всю асимметричную криптографию. Однако, в тех случаях, когда в канале возможна модификация данных, появляется очевидная возможность вклинивания в процесс генерации ключей «злоумышленника-посредника» по той же самой схеме, что и для асимметричной криптографии.

См. также Править


ar:تبادل مفتاح ديفي-هيلمان

cs:Diffie-Hellman de:Diffie-Hellman-Schlüsselaustausch en:Diffie-Hellman key exchange es:Diffie-Hellman fa:پروتکل تبادل کلید دیفی-هلمن fi:Diffie-Hellman fr:Échange de clés Diffie-Hellman he:פרוטוקול דיפי-הלמן it:Scambio di chiavi Diffie-Hellman ja:Diffie-Hellman鍵共有 nl:Diffie-Hellman-sleuteluitwisselingsprotocol pl:Protokół Diffiego-Hellmana pt:Diffie-Hellman simple:Diffie-Hellman key exchange tr:Diffie-Hellman

Обнаружено использование расширения AdBlock.


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

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики