- no title specified

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

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

Алгоритм основан на трудности вычислений дискретных логарифмов. В этом алгоритме, как и во многих других алгоритмах с открытым ключом, вычисления производятся по модулю некоторого большого простого числа Р. Вначале специальным образом подбирается некоторое натуральное число А, меньшее Р. Если мы хотим зашифровать значение X, то вычисляем

Y = A^{X} \mod P

Причем, имея Х, вычислить Y легко. Обратная задача вычисления X из Y является достаточно сложной. Экспонента X как раз и называется дискретным логарифмом Y. Таким образом, зная о сложности вычисления дискретного логарифма, число Y можно открыто передавать по любому каналу связи, так как при большом модуле P исходное значение Х подобрать будет практически невозможно. На этом математическом факте основан алгоритм Диффи-Хеллмана для формирования ключа.

Пусть два пользователя, которых условно назовем пользователь 1 и пользователь 2, желают сформировать общий ключ для алгоритма симметричного шифрования. Вначале они должны выбрать большое простое число Р и некоторое специальное число А, 1 < A < P-1, такое, что все числа из интервала [1, 2, ..., Р-1] могут быть представлены как различные степени А mod Р. Эти числа должны быть известны всем абонентам системы и могут выбираться открыто. Это будут так называемые общие параметры.

Затем первый пользователь выбирает число Х1 (X1<P), которое желательно формировать с помощью датчика случайных чисел. Это будет закрытый ключ первого пользователя, и он должен держаться в секрете. На основе закрытого ключа пользователь 1 вычисляет число

Y_{1} = A^{X_{1}} \mod P

, которое он посылает второму абоненту.

Аналогично поступает и второй пользователь, генерируя Х2 и вычисляя

Y_{2} = A^{X_{2}} \mod P

отправляет его первому пользователю.

После этого у пользователей должна быть информация, указанная в следующей таблице:

	Общие параметры	Открытый ключ	Закрытый ключ
Пользователь 1	Р, А	Y1	Х1
Пользователь 2	Р, А	Y2	Х2

Из чисел Y1 и Y2, а также своих закрытых ключей каждый из абонентов может сформировать общий секретный ключ Z для сеанса симметричного шифрования. Вот как это должен сделать первый пользователь:

Z = {(Y_{2})}^{X_{1}} \mod P

Никто другой кроме пользователя 1 этого сделать не может, так как число Х1 секретно. Второй пользователь может получить то же самое число Z, используя свой закрытый ключ и открытый ключ своего абонента следующим образом:

Z = {(Y_{1})}^{X_{2}} \mod P

Если весь протокол формирования общего секретного ключа выполнен верно, значения Z у одного и второго абонента должны получиться одинаковыми. Причем, что самое важное, противник, не зная секретных чисел Х1 и Х2, не сможет вычислить число Z. Не зная Х1 и Х2, злоумышленник может попытаться вычислить Z, используя только передаваемые открыто Р, А, Y1 и Y2. Безопасность формирования общего ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел размером сотни и тысячи бит задача считается неразрешимой, так как требует колоссальных затрат вычислительных ресурсов.

Пользователи 1 и 2 могут использовать значение Z в качестве секретного ключа для шифрования и расшифрования данных. Таким же образом любая пара абонентов может вычислить секретный ключ, известный только им.

Пример:

Пользователи 1 и 2 принимают для использования числа P=23 и A=5.

1.Пользователь 1 выбирает секретное число X=6, и затем высылает пользователю 2 число $Y = A^{X} \mod P$
- • $Y = 5^{6} \mod 23$
- •Y = 15625 mod 23
- •Y = 8
2.Пользователь 2 выбирает секретное число X=15, и высылает пользователю 1 число $Z = A^{X} \mod P$
- • $Z = 5^{15} \mod 23$
- •Z = 30517578125 mod 23
- •Z = 19
3.Пользователь 1 вычисляет $s = Z^{X} \mod P$
- • $s = 19^{6} \mod 23$
- •s = 47045881 mod 23
- •s = 2
4.Пользователь 2 вычисляет $s = Y^{X} \mod P$
- • $s = 8^{15} \mod 23$
- • s = 35184372088832 mod 23
- • s = 2
5.Оба пользователя имеют один общий ключ: s = 2 так как:
- • $s = 5^{6 * 15} \mod 23$
- • $s = 5^{15 * 6} \mod 23$
- • $s = 5^{90} \mod 23$
- •s = 807793566946316088741610050849573099185363389551639556884765625 mod 23
- •s = 2

Для того, чтобы алгоритм Диффи-Хеллмана работал правильно, то есть оба пользователя, участвующих в протоколе, получали одно и то же число Z, необходимо правильным образом выбрать число А, используемое в вычислениях. Число А должно обладать следующим свойством: все числа вида:

A \mod P

A^{2} \mod P

A^{3} \mod P

\dots

A^{P - 1} \mod P

должны быть различными и состоять из целых положительных значений в диапазоне от 1 до Р-1 с некоторыми перестановками. Только в этом случае для любого целого Y < Р и значения A можно найти единственную экспоненту Х, такую, что

Y = A^{X} \mod P

, где 0 <= X <= (P – 1).

При произвольно заданном Р задача выбора параметра А может оказаться трудной задачей, связанной с разложением на простые множители числа Р-1. На практике можно использовать следующий подход, рекомендуемый специалистами. Простое число Р выбирается таким, чтобы выполнялось равенство Р = 2q + l, где q — также простое число. Тогда в качестве А можно взять любое число, для которого справедливы неравенства

1 < A < (P - 1)

A^{q} \mod P \neq 1

На подбор подходящих параметров А и Р необходимо некоторое время, однако это обычно не критично для системы связи и не замедляет ее работу. Эти параметры являются общими для целой группы пользователей. Они обычно выбираются один раз при создании сообщества пользователей, желающих использовать протокол Диффи-Хеллмана, и не меняются в процессе работы. А вот значения закрытых ключей рекомендуется каждый раз менять и выбирать их с помощью генераторов псевдослучайных чисел.

Следует заметить, что данный алгоритм, как и все алгоритмы асимметричного шифрования, уязвим для атак типа "man-in-the-middle" ("человек в середине"). Если противник имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников, создать свою пару открытого и закрытого ключа и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником.