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

В алгоритме ECDSA есть число, обычно обозначаемое k, которое используется при вычислении значения подписи, а именно – k определяет параметр r из пары (r,s) подписи. Значение r из этой пары необходимо для того, чтобы сошлась формула проверки. В исходном алгоритме k предлагается выбирать случайным образом (но без повторов, и держать в секрете). Дело в том, что если третья сторона знает k, то она может элементарным способом вычислить секретный ключ по сообщению с подписью; повторное использование k для разных сообщений, при прочих равных, так же приводит к раскрытию секретного ключа.

Можно встретить мнение, что такая особенность заложена в ECDSA специально (оставлено за скобками то, что такой подход использовался и в других, предшествующих ECDSA, криптосистемах). Действительно, если, например, k вычисляется по некоторому алгоритму генерирования псевдослучайных чисел “с секретом”, то если третьей стороне известны скрытые особенности данного алгоритма, эта сторона может раскрыть секретный ключ ECDSA, быстро подобрав k под открытое значение r, которое можно взять из подписи. (Это хрестоматийный теоретический подход к созданию бэкдоров методом “алгебраического разбиения”.)

Вообще, на этом направлении весьма легко ошибиться в программном коде, без всякого бэкдора. Либо подведёт аппаратура, обеспечивающая выдачу случайных значений. Либо вмешается тот или иной гипервизор – сейчас повсеместно используется виртуализация для размещения программного кода, вычисляющего ECDSA-подписи, с этим сложно что-то поделать, как и с тем, что инженеры DevOps обожают делать “снапшоты” виртуальных машин, а потом их восстанавливать (так себе решение) или множить (ещё хуже). Заметьте, кстати, что всё это полностью применимо и к современной ГОСТ-подписи – там математически эквивалентная схема.

Так что проблем с псевдослучайным параметром в ECDSA много. На практике, в алгоритм вычисления k так или иначе подмешивают дополнительные значения, не ограничиваясь лишь выдачей генератора псевдослучайных чисел. Это полумера. Однако есть и полностью детерминированный вариант (“deterministic ECDSA“), в котором значение k вычисляется для конкретного сочетания сообщения и секретного ключа (например, такой алгоритм поддерживается свежим OpenSSL 3.2).

Практика использования детерминированного варианта сопряжена с ещё одним занятным моментом. Если сообщение подписывается обычной ECDSA (или ГОСТ-подписью), то значение подписи будет каждый раз разным, даже для одного сообщения и одного подписывающего ключа. То есть, значение подписи псевдослучайное, и этот факт вполне может использоваться приложениями (хотя, вообще говоря, не должен бы). Соответственно, “фиксирование” значения подписи в таком приложении может что-то сломать. Но детерминированный вариант, конечно, всё равно лучше.

Адрес записки: https://dxdt.ru/2023/11/25/11674/