Детерминированная ЭЦП

Предварительный стандарт СТБ П 34.101.45 определяет алгоритмы электронной цифровой подписи на основе эллиптических кривых. Алгоритм выработки подписи Sign берет на вход долговременные параметры params, которые описывают группу точек эллиптической кривой, личный ключ d подписывающей стороны, сообщение X и возвращает его подпись. Корректность подписи может быть проверена любой другой стороной на открытом ключе Q, соответствующем личному ключу. 

Алгоритм Sign является вероятностным, в нем используется случайный одноразовый ключ k. В СТБ П 34.101.45 сказано, что «для создания… одноразовых ключей может быть использован физический генератор случайных чисел… или алгоритм генерации псевдослучайных чисел с секретным параметром».

Физический генератор – это устройство Dev, которое «оцифровывает» стохастические физические процессы, как правило, шум в полупроводниковых приборах. Разработчику средства ЭЦП требуется, по крайней мере, приобрести Dev, встроить Dev, контролировать работу Dev. Все это вызывает удорожание и усложнение средства ЭЦП. Имеются трудности с размещением Dev на микроустройствах.

Алгоритм генерации псевдослучайных чисел берет на вход секретный ключ K, уникальную синхропосылку S и возвращает k. Как правило, алгоритмы генерации строятся на основе функций хэширования. Примеры таких алгоритмов можно найти в новом стандарте СТБ 34.101.47.

При организации псевдослучайной генерации разработчик опять сталкивается с трудностями – требуется обеспечить секретность K и уникальность S. Иногда поддержать уникальность даже труднее, чем секретность. Синхропосылки S снова можно строить с помощью Dev (но тогда зачем вообще переходить к псевдослучайной генерации), либо определять по значениям монотонного счетчика. В последнем случае средство ЭЦП должно иметь перезаписываемую память, обновляемую при каждом подписывании или, в лучшем случае, запуске средства.

Повтор S приводит к повтору k, а повтор k при подписи двух разных сообщений позволяет без труда определить личный ключ d. Это давно известный факт, тем не менее, не учтенный разработчиками игровой консоли PlayStation 3 – повтор одноразовых ключей при подписи (с помощью алгоритмов ECDSA) загружаемых в консоль программ привел к раскрытию личного ключа компании Sony. Интересно, что на простоте определения d при повторе k строится обоснование стойкости алгоритмов ЭЦП типа Шнорра, в том числе алгоритмов СТБ П 34.101.45.

Проблему входных данных для алгоритма псевдослучайной генерации k легко решить следующим образом: 

K = d, S = X.

Данное решение было предложено еще, по крайней мере, в 1997 году, в настоящее время оно баллотируется на стандарт Интернет. 

При генерации одноразового ключа k по личному ключу d и подписываемому сообщению X алгоритм выработки ЭЦП перестает быть вероятностным. Подпись становится детерминированной, всегда одной и той же для конкретного сообщения. Это облегчает управление документами, позволяет использовать подпись в качестве контрольной суммы. У владельца личного ключа остается меньше возможностей отказаться от своей подписи из-за ошибок в Dev или повтора k.

Детерминированный алгоритм Sign планируется включить в окончательный стандарт СТБ 34.101.45.