Система Диффи — Хеллмана

Первой открытой публикацией в области криптографии с открытым ключом принято считать статью У. Диффи (Whitfield Diffie) и М. Хеллмана (Martin Heilman) «Новые направления в криптографии», опубликованную в 1976 г. Диффи и Хеллман предложили алгоритм, позволяющий двум абонентам, обмениваясь сообщениями по небезопасному каналу связи, распределить между собой секретный ключ шифрования.

В алгоритме Диффи — Хеллмана в качестве односторонней функции используется возведение в степень по модулю простого числа:

у = a^xmodp.

Здесь р — большое простое число (в настоящее время считается безопасным использовать модуль порядка 2¹⁰²⁴ или более).

Для организации системы обмена ключами между абонентами, А и В сначала выбираются два больших целых числа р и g, причем р — простое число, a g таково, что 1 < g

1, и все числа из множества {1,2,…, р — 1} могут быть представлены как различные степени g по модулю р.

Пусть такие числа png найдены, хранить их в секрете не обязательно и абоненты могут договориться об их использовании по открытому каналу. Таким образом, числа р и g известны обоим абонентам. Затем каждый из абонентов выбирает случайное большое целое число в качестве своего секретного ключа:

• 1) абонент, А выбирает случайное число х и посылает абоненту В значение X = g^xmodp;
• 2) абонент В выбирает случайное число у и посылает абоненту, А значение Y = g^ymodp.

Значения X и Y могут передаваться по открытому каналу, поскольку получение на их основе значений секретных ключей х и у практически невозможно (утверждение базируется на вычислительной сложности задачи дискретного логарифмирования при больших значениях р)

• 3) абонент, А вычисляет значение к = Y^xmod/?;
• 4) абонент В вычисляет значение k' = X^ymodp.

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

Система Диффи — Хеллмана легко обобщается на произвольное число абонентов.

Выбор g и р может существенно влиять на безопасность системы. При произвольном р нахождение g может оказаться трудной задачей, связанной с разложением на множители числа р — 1.

Для обеспечения стойкости системы число р — 1 должно содержать большой простой множитель, в противном случае дискретный логарифм может быть быстро найден с помощью алгоритма Полига — Хеллмана. Поэтому рекомендуется следующий подход к выбору чисел р и g.

Простое число р выбирается таким образом, чтобы р = 2q + 1, где q — также большое простое число. Тогда g — любое число, для которого справедливы неравенства: 1 < g < р — 1, gxmodp * 1.

Пример 3.1.

Пусть р = 23 = 11 -2+1 (q = 11). Выберем g. Допустим, g = 3, проверим выполнение условия g^qmodp * 1: 3ⁿ mod 23 = 1, следовательно, значение g = 3 не подходит. Пусть теперь g = 5: 5¹¹ mod 23 = 22 * 1, следовательно, значение g = 5 подходит.

Выбрали р = 23, g = 5. Теперь каждый абонент выбирает свой секретный ключ — случайное целое число. Пусть, А выбрал х = 7, В выбрал г/ = 13. Вычислим Х= 5⁷'mod 23 = 17, F= 5¹³ mod 23 = 21.

Пусть, А и В решили сформировать общий секретный ключ. После обмена числами Хи Yабоненты вычисляют: А — k = 21⁷mod 23 = 10, В — к = 17¹³mod 23 = = 10. Теперь абоненты имеют общий ключ 10, значение которого нс передавалось по каналу связи.