Алгоритм цифровой подписи ECDSA

 

В алгоритме ЭЦП ECDSA (Elliptic Curve Digital Signature Algorithm) определение параметров системы и генерация ключей аналогичны алгоритму асимметричного шифрования ECES.

 

Генерация ЭЦП (пользователь А подписывает сообщение М):

¨ вычисляется хэш сообщения h (М);

¨ выбирается случайное целое число k, взаимно простое с п (то есть не имеющее других общих с п делителей, кроме 1; поскольку п является простым числом по определению, данное условие выполняется автоматически), ;

¨ вычисляется точка и . В случае если r = 0, повторяется выбор k;

¨ вычисляется ;

¨ цифровой подписью сообщения М является пара чисел (r, s).

 

Проверка ЭЦП (пользователь В проверяет ЭЦП пользователя А под сообщением М):

¨ если r = 0, то полученная ЭЦП неверна;

¨ вычисляется хэш сообщения ;

¨ вычисляются и ;

¨ вычисляется точка ;

¨ вычисляется ;

¨ ЭЦП считается верной, если .

 

Алгоритм цифровой подписи ГОСТ Р 34.10-94

 

Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. В нем используются следующие параметры:

¨ p – большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит;

¨ q – простой сомножитель числа (р - 1), имеющий длину 254÷256 бит;

¨ а – любое число, меньшее (р - 1), причем такое, что a^q mod p = 1;

¨ х – некоторое число, меньшее q;

¨ у = а^х mod p.

Кроме того, этот алгоритм использует однонаправленную хэш-функцию Н (х). Стандарт ГОСТ Р 34.11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.

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

Чтобы подписать некоторое сообщение т, а затем проверить подпись, необходимо выполнить следующие действия:

1. Пользователь А генерирует случайное число k, причем k < q.

2. Пользователь А вычисляет значения

 

, (4.27)

 

. (4.28)

 

 

Если H (m)mod q = 0, то значение Н (т) mod q принимают равным единице.

Если r = 0, то выбирают другое значение k и начинают снова.

Цифровая подпись представляет собой два числа: r mod 2²⁵⁶ и s mod 2²⁵⁶. Пользователь А отправляет эти числа пользователю В.

3. Пользователь В проверяет полученную подпись, вычисляя

 

, (4.29)

 

, (4.30)

 

, (4.31)

 

. (4.32)

 

Если и = r, то подпись считается верной.

Различие между этим алгоритмом и алгоритмом DSA заключается в том, что в DSA

 

,

 

что приводит к другому уравнению верификации.

Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи. Этот стандарт вступил в действие с начала 1995 года.