dxdt.blog: занимательный интернет-журнал

Определяющий фактор для практических криптосистем – это сокрытие структур, существующих в исходных данных. Исходная структура маскируется, но обратимым способом. Эффект проявляется повсеместно. Очевидные примеры – шифры простой замены (здесь нет сокрытия статистики), полиалфавитные шифры замены и другие, в том числе, современные блочные шифры. Прицип работает и в типичной схеме с умножением точек эллиптической кривой (над конечным полем): Q = [d]P; то есть, точка Q это сумма d экземпляров точки P. Формула используется повсеместно, – в ECDSA, в ECDH и т.д., – а обратная задача, – отыскание d по Q и P, – называется дискретным логарифмированием. Какую структуру скрывает эта задача? Она скрывает отношение порядка. То есть, стойкость той же ECDSA нивелируется, если будет найден способ поднять отношение порядка из группы скаляров (d) в группу точек кривой.

Рассмотрим ситуацию на примере ECDSA. Речь тут вот о чём. Скаляр d – это секретный ключ. Но, вообще-то, d – это натуральное число, лежащее в заданном интервале. То есть, привычное число, подсчитывающее количество точек. Самый тривиальный индекс: две точки P – это [2]P = P + P, и так далее. А раз d – натуральное число, то тут применимо отношение порядка, существующее в натуральных числах: 101 > 80; 79 < 179; и т.д.

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

Будем записывать вместо d натуральные значения: 1, 2, 3, 4, 5… Тогда, перенос отношения порядка означает, что мы могли бы быстро определить, что если Q = [5]P, а R = [3]P, то Q > R. “Быстро” – означает, что вычислительно быстро, по самим точкам Q, R, без вычисления секретного скаляра (это 5 для Q, 3 для R).

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

Представим, что есть некий “оракул порядка”, то есть, простой способ сказать, что точка Q “больше” (“меньше”) точки R, без знания секретного скаляра, но “по модулю” точки-генератора P и с сохранением данного отношения порядка “на точках”, относительно арифметики “на скалярах”: то есть, если Q > R, и Q = [n]P, а R = [m]P, то n > m (арифметика тут означает именно поднятие отношения порядка из “обычной арифметики”). Это тут же уничтожает стойкость базовой задачи, и ECDSA в частности, потому что теперь можно найти секретный скаляр бинарным поиском, который очень быстрый.

Как это сделать? В нашей группе точек эллиптической кривой мы можем быстро вычислять умножение на скаляр, потому что в нашем индексе (в натуральных числах) есть удвоение, которое переносится на сложение точек: [5]P = P + P + P + P + P = [2]P + [2]P + P. Пусть нам нужно найти d из Q = [d]P, Q != P, Q != O (O – это нейтральный элемент). Поскольку группа точек, сгенерированная P, конечная циклическая, то d лежит в известном интервале [2..N-1], где N – количество точек в группе (порядок). Вычислим точку [m]P, значение скаляра m которой делит этот интервал на две “половины”. Сравним Q и [m]P и определим, лежит скаляр точки Q слева или справа от m, в нашем отношении порядка. Дальше, думаю, понятно – привычный бинарный поиск: делим новый подинтервал на две “половины”, определяем, куда попала точка, и так далее. У бинарного поиска логарифмическая сложность, это означает, что мы найдём секретный скаляр для 256-битной кривой не более, чем за 256 проверок. Каждая проверка – это одно умножение точки и одно сравнение “в точках”: с вычислительной точки зрения – почти что ничего.

Вывод: быстро вычислимый порядок есть в исходном индексе, в скалярах, которые натуральные числа, но операция сложения точек, для ряда кривых, этот порядок эффективно скрывает; если удалось восстановить в точках порядок, существующий на скалярах, криптосистема полностью теряет стойкость. (Тут необходима техническая оговорка: некоторые кривые как раз можно быстрым способом вложить в большее кольцо, где дискретный логарифм решается за разумное время; это часть кривых особенного подвида, которые называют “суперсингулярными”, а сам процесс вычисления данного вложения, вообще говоря, полностью эквивалентен восстановлению отношения порядка.) Но универсального метода, который позволяет быстро поднять порядок, пока что не найдено (можно просто “посчитать” каждую точку, как упоминалось выше, но это лишено смысла, поскольку эквивалентно дискретному логарифму, взятому перебором “в лоб”). Если же такой быстрый метод появится даже для частных случаев, например, для кривой P-256, то и ECDSA на P-256, и ECDH на P-256 – мгновенно потеряют стойкость. К этому же фундаментальному классу принадлежат и алгоритмы, упрощающие вычисление других отношений между точками.

Адрес записки: https://dxdt.blog/2026/11/14/19629/