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

Материал из Википедии — свободной энциклопедии

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

Алгорим был впервые опубликован Витфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом в 1976 году, однако, позднее выяснилось, что этот же метод был придуман несколькими годами раньше Малькольмом Вильямсоном (Malcolm J. Williamson) для английского штаба правительственной связи, и был засекречен. В 2002 году Хеллман предложил называть алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом.

[править] История

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

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

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

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

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

[править] Описание

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

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

   p может быть любым натуральным числом

   g должно быть первообразным корнем p

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

   A = g^a mod p, где mod — опрерация деления по модулю (остаток от деления)

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 или K из известных p, g, A и B), основана на предполагаемой сложности задачи дискретного логарифмирования. В практических реализациях, для a и b используются числа порядка 10¹⁰⁰ и p порядка 10³⁰⁰. Число g не должно быть большим и обычно имеет значения 2 или 5.