Алгоритм обмена ключа Диффи-Хеллмана

Обсуждение криптоанализа

Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:

1. Лобовая атака: перебрать все возможные закрытые ключи.
2. Разложить n на два простых сомножителя. Это даст возможность вычислить Φ(n) = (p-1) · (q-1) и d = e^-1 (mod (n)).
3. Определить Φ(n) непосредственно, без начального определения р и q. Это также даст возможность определить d = e^-1 (mod Φ(n)).
4. Определить d непосредственно, без начального определения Φ(n).

Защита от лобовой атаки для RSA и ему подобных алгоритмов состоит в использовании большой длины ключа. Таким образом, чем больше битов в е и d, тем лучше. Однако, так как вычисления необходимы как при создании ключей, так и при шифровании/дешифровании, чем больше размер ключа, тем медленнее работает система.

Большинство дискуссий о криптоанализе RSA фокусируется на задаче разложения n на два простых сомножителя. В настоящее время неизвестны алгоритмы, с помощью которых можно было бы разложить число на два простых множителя для очень больших чисел (т.е. несколько сотен десятичных цифр). Лучший из известных алгоритмов дает результат, пропорциональный:

L (n) = e^{sqrt (ln n * ln (ln n))}

Пока не разработаны лучшие алгоритмы разложения числа на простые множители, можно считать, что величина n от 100 до 200 цифр в настоящее время является достаточно безопасной. На современном этапе считается, что число из 100 цифр может быть разложено на множители за время порядка двух недель. Для дорогих конфигураций (т.е. порядка $10 млн) число из 150 цифр может быть разложено приблизительно за год. Разложение числа из 200 цифр находится за пределами вычислительных возможностей. Например, даже если вычислительный уровень в 10¹² операций в секунду достижим, что выше возможностей современных технологий, то потребуется свыше 10 лет для разложения на множители числа из 200 цифр с использованием существующих алгоритмов.

Для известных в настоящее время алгоритмов задача определения (n) по данным е и n, по крайней мере, сопоставима по времени с задачей разложения числа на множители.

Для того чтобы избежать выбора значения n, которое могло бы легко раскладываться на сомножители, на р и q должно быть наложено много дополнительных ограничений: р и q должны друг от друга отличаться по длине только несколькими цифрами. Таким образом, оба значения р и q должны быть от 10⁷⁵ до 10¹⁰⁰.

Оба числа (р - 1) и (q - 1) должны содержать большой простой сомножитель.

gcd (p -1, q - 1) должен быть маленьким.

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

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

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

A mod Q, A² mod Q,..., A^{Q - 1} mod Q

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

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

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

ind_{A, Q} (Y).

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

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

Создание пары ключей пользователем I
Выбор случайного числа Хi (закрытый ключ)	Xi < Q
Вычисление числа Yi (открытый ключ)	Yi = A^Xi mod Q

Создание открытого ключа пользователем J
Выбор случайного числа Хj (закрытый ключ)	Xj < Q
Вычисление случайного числа Yj (открытый ключ)	Yj = A^Xj mod Q

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

K = (Y_j)^Xi mod Q

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

K = (Y_i)^Xj mod Q

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

K = (Y_j)^Xi mod Q = (A^Xj mod Q)^Xi mod Q = (A^Xj)^Xi mod Q по правилам модульной арифметики = A^{Xj Xi} mod Q = (A^Xj)Xj mod Q = (A^Xi mod Q)^Xj mod Q = (Y_i)^Xj mod Q

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

X_j = ind_{a, q} (Y_j)

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

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

8. Лекция: Хэш-функции и аутентификация сообщений. Часть 1:
Рассматриваются основные понятия, относящиеся к обеспечению целостности сообщений с помощью МАС и хэш-функций; представлены простые хэш-функции и сильная хэш-функция MD5.

Дата добавления: 2014-12-23