Главная | Обратная связь

Новое направление в криптографии , постулаты У. Диффи и М. Хеллмана

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

отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 г. под названием "Новые направления в современной криптографии". В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом.

Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электроннойцифровой подписи (ЭЦП) и электронных денег.

В 1980–90-е гг. появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В этот же период были разработаны нефейстелевские шифры (SAFER, RC6 и др.), а в 2000 г.после открытого международного конкурса был принят новый национальный стандарт шифрования США – AES.

Постулаты У. Диффи и М. Хеллмана:

1. Ключ K_A для шифрования сообщений входящих к абоненту А должен изготовить сам абонент А. Он же изготавливает ключ K_A^-1 - для расшифрования данных сообщений.

2. Ключ K_A рассылается всем желающим, отправлять сообщения абоненту A, ключ K_A^-1 держится в секрете.

3. Ключ K_A^-1 не восстанавливается по ключу K_A.

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

Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана.

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

Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа Q как числа, чьи степени создают все целые от 1 до Q – 1. Это означает, что если А является примитивным корнем простого числа Q, тогда числа

A mod Q, A² mod ……A^Q-1 mod Q

являются различными и состоят из целых от 1 до Q – 1 с некоторыми перестановками. В этом случае для любого целого B < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что

Y =A^X mod Q ,где 0≤ X ≤ (Q-1).

Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как

ind_A,Q(Y)

Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.

Общеизвестные элементы
Q	Простое число
A	A < Q и A является примитивным корнем Q

Создание пары ключей пользователем I
Выбор случайного числа X i (закрытый ключ)	Xi<Q
Вычисление числа Y i (открытый ключ)	Yi=AXimod Q
Создание открытого ключа пользователем J
Выбор случайного числа X j (закрытый ключ)	X j< Q
Вычисление случайного числа Y j (открытый ключ)	Yj=A Ximod Q

 

Создание общего секретного ключа пользователем I

K= (Yi)Ximod Q

 

Создание общего секретного ключа пользователем J

K=(Yj)Xjmod Q

 

Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число X_i< Q и вычисляет Y _i=A^X_i mod Q. Аналогично пользователь J независимо выбирает случайное целое число X_j<Q и вычисляет Y _i=A^X_j mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как K=(Y_i)^X_i mod Q, и пользователь J вычисляет ключ как K= (Y_j)^X_j mod Q. В результате по правилам модульной арифметики оба получат одно и то же значение:

K= (Y_j)^X_i mod Q= (A^X_j mod Q)^X_i mod Q = (A ^X_j)^X_i mod Q = A ^X_j^X_i mod Q =

(A ^X_i)^X_j mod Q= ( A ^X_i mod Q)^X_j mod Q = ( Y_i)^X_j mod Q.

 

Таким образом, две стороны обменялись секретным ключом. Так как X_i и X_j являются закрытыми, противник может получить только следующие значения: Q, A, Y_i и Y_j. Для вычисления ключа атакующий должен взломать дискретный логарифм, т. е. вычислить

X_j = ind _a,q(Y_j)

39)