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

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

Нередко приходится слышать и читать, что в ECDSA значение “параметра k” должно вырабатываться криптографически стойким генератором (псевдо)случайных чисел, для каждой операции подписи. Например, так написано в английской “Википедии”, и практически то же самое написано в стандарте FIPS 186 (но обратите внимание, что в современном стандарте уже есть и другой вариант). Нельзя сказать, что это уж совсем неверно, но есть занятные тонкости с трактовкой слова “должно”.

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

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

Теперь должно быть очевидно, что выбор k при помощи криптографически стойкого генератора псевдослучайных чисел – лишь один из вариантов выполнения основного требования. Ведь, с вычислительной точки зрения, последовательность непредсказуемых значений выглядит, для третьей стороны, так же, как и выдача генератора. Следовательно, атакующий не может узнать, какое значение k использовано, поскольку выдача генератора должна быть “неотличима от случайной”. Но, во-первых, это лишь результат использования генератора псевдослучайных чисел, а обратное, то есть, само требование использовать генератор, отсюда не следует; во-вторых, это работает только в том случае, если генератор – действительно стойкий и в нём нет бэкдора.

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

Кстати, всё это непосредственно применимо и к современной ГОСТ-подписи: там есть такой же “параметр k”, точно так же влияющий на выдачу криптосистемы подписи и на стойкость реализации.

Адрес записки: https://dxdt.ru/2026/01/27/17171/