mvladlin Jun 16 at 09:40

Особенность дискретного логарифма —> математический бэкдор в протоколе Диффи — Хеллмана

Easy

6 min

5.9K

Opinion

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

Пробежимся по теории

Вспомним дискретный логарифм (далее DLOG) https://ru.wikipedia.org/wiki/Дискретное_логарифмирование

Нам нужен вариант DLOG в конечном поле GF(p) , где p - простое число https://ru.wikipedia.org/wiki/Конечное_поле

$g^x \equiv a \pmod p$

Общеизвестно что задача DLOG является односторонней функцией https://ru.wikipedia.org/wiki/Односторонняя_функция т.е. поиск является трудной задачей.

Кроме полного перебора, существует много алгоритмов решения данной задачи https://ru.wikipedia.org/wiki/Дискретное_логарифмирование#Алгоритмы_решения (не будем их рассматривать).

Иногда поиск является тривиальной задачей, например:

если a = 1 , то x = 0

если a = g , то x = 1

Следует сказать что является первообразным корнем или примитивом https://ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел)

Для GF(7) примитив g = 3 , проверим:

$3^0 \equiv 1 \pmod 7$
$3^1 \equiv 3 \pmod 7$
$3^2 \equiv 2 \pmod 7$
$3^3 \equiv 6 \pmod 7$
$3^4 \equiv 4 \pmod 7$
$3^5 \equiv 5 \pmod 7$
$3^6 \equiv 1 \pmod 7$

Обращаем внимание на последнюю строку, т.е. если a = 1 , то x = 0 или x = p-1

Итак, у нас есть уже три случая, когда поиск тривиален:

$x \in \{ 0, 1, p-1\}$

Как правило для анализа DLOG строят таблицу логарифмов:

Таблица логарифмов для (нулевое значение обычно опускают) — Таблица логарифмов для $GF(7), \ g = 3$ (нулевое значение обычно опускают)

Таблица логарифмов для $GF(7), \ g = 3$ (нулевое значение обычно опускают)

По таблице логарифмов нарисуем график:

График таблицы логарифмов для $GF(7), \ g = 3$

На графике ничего интересного, только хаотичное изменение показателя

Криптографический протокол DH построен на задаче DLOG https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана

Посмотрим пример прямо из вики:

Скрин из викистатьи Протокол Диффи — Хеллмана

Ничего сложного.

Далее пойдет новая или непубличная информация.

Основная часть

Будем анализировать DLOG как таблицу степеней. Таблица степеней это перевернутая таблица логарифмов (см. рис. ниже), слева — таблица степеней, справа — таблица логарифмов. Об этом я писал в статье "Как сгенерировать порождающие полиномы для конечных полей." https://habr.com/ru/articles/844300

Таблица степеней и таблица логарифмов для

GF(7) — Таблица степеней и таблица логарифмов для

Таблица степеней удобнее, так как можно наблюдать сразу несколько примитивов (), синим подчеркнута строка для примитива g = 3 , колонка для x = 0 не обозначена.

Далее посмотрим несколько таблиц степеней и обратим внимание на среднюю колонку x = (p-1)/2

Имея ввиду экстраполяцию, можно предположить, что данная особенность распространяется на все множество таблиц степеней GF(p) .

В средней колонке число p-1 показывает строки с уникальными значениями, значит в начале строки - примитив, наблюдаем также:

не касается последней строки, там $\{1, (p-1), 1, (p-1), \cdots \}$ ;
- простое число, иначе, например для $GF(13) \ \Longrightarrow \ (p-1)/2 = 6$ - непростое, поэтому будут "лишние" строки: $\{5, 8\}$ .

Математически это выглядит так:

$g^{(p-1)/2} \equiv p-1\ |\ 1 \pmod p \quad (1)$

Математики знакомые с критериями Эйлера https://ru.wikipedia.org/wiki/Критерий_Эйлера и квадратичным вычетом https://ru.wikipedia.org/wiki/Квадратичный_вычет увидят знакомое:

$a^{(p-1)/2}\equiv 1 \pmod p$
$a^{(p-1)/2}\equiv -1 \pmod p$

но здесь вместо (p-1) установлено (-1) !

Надо вспомнить модулярную арифметику https://en.wikipedia.org/wiki/Modular_arithmetic (статья в en-вики более понятна), фактически в данном случае (-1) = (p-1) , вернее так:

$(-1) \pmod p = (p-1) \pmod p$

Используя вышесказанное, можно находить все примитивы конечного поля:

Общее количество примитивов конечного поля равно $\varphi(p-1)$ , где $\varphi$ — функция Эйлера totient https://ru.wikipedia.org/wiki/Функция_Эйлера

Посмотрим на таблицу степеней GF(11) в виде графика, добавил нулевое значение для симметричности, похож на "паука":

Вернемся в протоколу DH, изменим наименования переменных:

для Алисы: $A=g^a \bmod {p}$ , - открытый ключ, - закрытый ключ.

для Боба: $B=g^b \bmod {p}$ , - открытый ключ, - закрытый ключ.

- общий секретный ключ, используется для шифровки - расшифровки сообщений.

Алиса вычисляет $S_{alice} = B^a \bmod {p}$

Боб вычисляет $S_{bob} = A^b \bmod {p}$

Рассмотрим канонический пример:

Алиса выбирает закрытый ключ
Боб выбирает закрытый ключ
Алиса вычисляет открытый ключ $A = 2^3 \bmod 11 = 8$
Боб вычисляет открытый ключ $B = 2^9 \bmod 11 = 6$
Алиса и Боб обмениваются открытыми ключами
Алиса вычисляет общий секретный ключ $S_{alice} = 6^3 \bmod 11 = 7$
Боб вычисляет общий секретный ключ $S_{bob} = 8^9 \bmod 11 = 7$
Алиса и Боб получили один и тот-же секретный ключ , не передавая его по сети.

Теперь пример, когда закрытый ключ равен (p-1)/2 :

Алиса выбирает закрытый ключ
Боб выбирает закрытый ключ
Алиса вычисляет открытый ключ $A = 2^5 \bmod 11 = 10$
Боб вычисляет открытый ключ $B = 2^9 \bmod 11 = 6$
Алиса и Боб обмениваются открытыми ключами
Алиса вычисляет общий секретный ключ $S_{alice} = 6^5 \bmod 11 = 10$
Боб вычисляет общий секретный ключ $S_{bob} = 10^9 \bmod 11 = 10$

Злоумышленник перехватил открытый ключ A = (p-1) = 10 и вычисляет закрытый ключ той-же Алисы по формуле (1): $(p-1) = 10 \Longrightarrow a = (p-1)/2 = (11-1)/2 = 5$

Далее, для получения секретного ключа есть два способа:

1 способ. С помощью открытого ключа Боба B = 6

$S_{alice} = 6^5 \bmod 11 = 10$

2 способ. Сразу, если хотя бы один из открытых ключей равен (p-1) , то S = (p-1) или , по формуле:

$S = (p-1)^n \bmod p = (p-1)\ |\ 1, \mbox{ где } n - \mbox{ любой элемент конечного поля } GF(p)$

Внимательно посмотрите на последнюю строку любого , например см. рис. выше "Несколько таблиц степеней".

Я не нашел в открытых источниках запрета на использование в качестве закрытого ключа (p-1)/2 .

Данное выражение упоминается в статье: S. C. Pohlig and M. E. Hellman, "An improved algorithm for computing logarithms in GF(p) and its cryptographic significance." https://ee.stanford.edu/~hellman/publications/28.pdf, IEEE Trans. Info. Theory 24 (1978), 106–111.

В статье указано что (p-1)/2 должно быть простым числом для повышения безопасности.

Еще в статье можно встретить упоминание тривиального случая : "Also, restrictions might be imposed on K (e.g., $K \ne 1$ ) to avoid simple but improbable transformations." В переводе: "Кроме того, на K могут быть наложены ограничения (например, $K \ne 1$ ), чтобы избежать простых, но маловероятных преобразований." ( - ключ).

Решение: запретить использовать в качестве закрытого ключа (p-1)/2 , дополняем список тривиальных случаев:

$x \in \{0, 1, (p-1)/2, p-1\}$

Можно найти еще? Попробуем.

Рассмотрим внимательно "паука", см. рис. выше, почему он симметричен?

Примитивы сгруппированы парами:

Когда-то я неправильно предположил, что эти пары взаимно простые, на самом деле они мультипликативно обратны по модулю https://ru.wikipedia.org/wiki/Обратное_по_модулю_число

$g \times g' \equiv 1 \pmod p$

Проверим:

$2 \times 6 \equiv 1 \pmod {11}$
$7 \times 8 \equiv 1 \pmod {11}$

Посмотрим график первой пары $\{2, 6\}$

Таблица степеней в виде графика для пары примитивов $\{2,6\}$

Симметрично, не правда ли? и в табличном виде:

Таблица степеней для примитивов $\{2,6\}$

Мы выяснили выше, что $\{2,6\}$ мультипликативно обратны, проверим остальные пары:

$1 \times 1 \equiv 1 \pmod {11}$
$4 \times 3 \equiv 1 \pmod {11}$
$8 \times 7 \equiv 1 \pmod {11}$
$5 \times 9 \equiv 1 \pmod {11}$
$10 \times 10 \equiv 1 \pmod {11}$

Все пары мультипликативно обратны по модулю .

Возвращаемся к DH, рассмотрим пример:

Алиса выбирает закрытый ключ
Боб выбирает закрытый ключ
Алиса вычисляет открытый ключ $A = 7^4 \bmod 11 = 3$
Боб вычисляет открытый ключ $B = 7^9 \bmod 11 = 8$
Алиса и Боб обмениваются открытыми ключами
Алиса вычисляет общий секретный ключ $S_{alice} = 8^4 \bmod 11 = 4$
Боб вычисляет общий секретный ключ $S_{bob} = 3^9 \bmod 11 = 4$

Вроде все нормально, но!

Нам известен примитив , мы можем получить мультипликативно обратный при помощи расширенного алгоритма Евклида https://ru.wikipedia.org/wiki/Расширенный_алгоритм_Евклида
Сравниваем с открытыми ключами, у Боба открытый ключ , значит закрытый ключ Боба равен , см. рис. ниже
Вычисляем секретный ключ $S_b = A^b \bmod 11 = 3^9 \bmod 11 = 4$

Бинго - вот вторая "дырка", согласно формуле:

$g^{(p-2)} \equiv g' \pmod p$

Эту формулу можно вывести из Малой теоремы Ферма https://ru.wikipedia.org/wiki/Малая_теорема_Ферма

$g^{(p-1)} \equiv 1 \pmod p$
$g * g^{(p-2)} \equiv 1 \pmod p$
$g^{(p-2)} \equiv g^{-1} \pmod p$ .
$g^{-1}$ - это и есть обратное число -

Дополняем список тривиальных случаев:

$x \in \{ 0, 1, (p-1)/2, p-2, p-1\}$

Больше уязвимостей пока не нашел.

Можно еще посмотреть график поля GF(47) (симметричность также видна) и таблицу, см. рисунки ниже:

График по двум парам примитивов: $\{5, 19\}, \{10, 33\}$

Заключение

Предупреждения о предполагаемой сложности задачи DLOG, например:

"Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления $K=g^{ab} \bmod {p}$ по известным $p, g, A=g^{a} \bmod {p} \mbox{ и } B=g^{b} \bmod {p}$ ) основана на предполагаемой сложности задачи дискретного логарифмирования." Форматирование сохранено, источник: https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана#Криптографическая_стойкость
"A cryptographic system is described which is secure if and only if computing logarithms over is infeasible." (мой перевод: "Описывается криптографическая система, которая является безопасной тогда и только тогда, когда вычисление логарифмов по невозможно.") Источник: S. C. Pohlig and M. E. Hellman, "An improved algorithm for computing logarithms in GF(p) and its cryptographic significance." https://ee.stanford.edu/~hellman/publications/28.pdf IEEE Trans. Info. Theory 24 (1978), 106–111.

Что касается описанных в данной статье уязвимостях, то проблемы не такие большие. Необходимо в программное обеспечение, генерирующее закрытые ключи, добавить исключения: $\{(p-1)/2, \ p-2\}$ , остальные были известны и ранее.