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

Немного элементарных математических подробностей о “коротких ключах” УЦ eMudhra. Секретный ключ в ECDSA – это натуральное число в некотором заранее известном интервале, от 2 до N. Арифметика там довольно простая. Обозначим ключ d. Этот ключ d на техническом языке называют “секретным скаляром”, но, вообще говоря, от этого он не перестаёт быть натуральным числом (натуральные числа, если кто вдруг забыл, это “обычный” счёт: 1, 2, 3, 4, 5 и так “до самого большого числа”).

Открытый ключ в ECDSA получается из секретного умножением точки-генератора G на секретный скаляр; на техническом языке: [d]G. Точка-генератор – это точка, принадлежащая эллиптической кривой, используемой в данном наборе параметров криптосистемы. Умножение здесь вводится как повторное сложение: [2]G = G + G. Задача вычисления d по известной точке [d]G в произвольной группе точек кривой считается вычислительно сложной.

Минимальное значение 2 – оно очевидно из соображений умножения; понятно, 2 – это угадывамое число (см. важные детали ниже). Максимальное значение N – про него обычно пишут, что это “порядок группы точек”. Это, опять же, технический термин, который обозначает количество точек, потенциально доступных при операциях данной криптосистемы. Математически, эта самая группа точек так устроена, что всё её элементы образуются сложением генератора G с самим собой (сложение здесь – обозначение групповой операции; на техническом языке такая группа называется “циклической”). Это всё может показаться сложным, из-за терминов, но на практике это просто закольцованная цепочка значений (точек): складываете один элемент с самим собой – идёте последовательно по другим элементам, которые получаются в результате; на определённом шаге – процесс зацикливается, попадаете “в начало”, в нейтральный элемент (следом за которым будет опять генератор G, потому что G = G + 0). На практике нельзя брать именно порядок группы M в качестве максимального значения, берут, например, M-2, но это технические детали.

Точек кривой в практических криптосистемах ECDSA очень много. Их количество близко к разрядности записи, то есть, например, около 2^256. Очень много. Это определяющий момент: если бы точек было мало, то их можно было бы перебрать за обозримое время все, определив секретный скаляр. Да, практически так же, как в рассматриваемом случае нестойких ключей, но только универсальным образом.

Опять же, в упомянутом случае – набор точек называется P-384 (обычно говорят, что это “кривая P-384”), базовая разрядность – 384 бита. Точка кривой – это тоже два натуральных числа, из определённого интервала, связанных определённой формулой в пару координат. Точка-генератор G – всем известна, это открытый параметр криптосистемы. Обычно, хотя бы одна из координат G – это “большое” натуральное число. Но данные аспекты не относятся к обсуждаемой теме прямо. (Кстати, “большое” тут в кавычках, потому что с порядком в группе точек кривой всё не так просто, как хотелось бы.)

Соответственно, умножаем известную точку G на подбираемое значение d (это быстрая операция), получаем точку Q, представленную парой координат (натуральных чисел), сравниваем получившиеся координаты с атакуемым открытым ключом, если совпало – мы нашли секретный ключ, он равен d.

Итак, значение секретного ключа d, натуральное число, которое на практике должно лежать в некотором большом интервале. Казалось бы, идеально – равновероятное распределение по всем возможным значениям. Но тогда и угадывамое число 254 (например) оказывается столь же вероятным, как и все прочие, не так ли? Почему же подобные малые числа должны отбрасываться? Потому, что есть внешние допущения, связанные с битовым представлением. “Слишком много нулей” – это одна из сигнатур, связанных с дефектами в реализации алгоритмов. Такие сигнатуры накладываются на доступный интервал и оказывается, что атакующий может угадать 254 именно потому, что он будет перебирать варианты, в которых “слишком много нулей”. Если бы запись скаляра 254 не обладала отличительными чертами (все старшие биты – нуль), то и угадать его было бы не так легко. Представьте, что скаляры d “перетасовали” секретным идеальным способом и 254 перешло в какое-то произвольное значение – как теперь его найти? Только полным перебором.

Но если при выборе секретного ключа d заведомо берутся значения больше 255 (например), то что это означает? Ничего нового: теперь нужно перебирать 257, 258 и т.д. То есть, тут важен не сам аспект, что “все старшие байты нулевые”, а наличие дополнительной информации о структуре распределения секретных ключей. Естественно, есть хорошо известные варианты, к которым и относится этот случай с последовательными нулевыми байтами. Это тривиальные ключи, подпадающие под универсальные ошибочные схемы. И эти случаи можно проверять без какой-то дополнительной информации. Но если, предположим, известно, что секретные ключи на сервере – это значение SHA-256 от текущего таймстемпа и IPv4-адреса сервера, то пространство перебора тоже не очень велико.

Адрес записки: https://dxdt.blog/2026/10/22/19482/