Интернет магазин китайских планшетных компьютеров

Компьютеры - ECDSA - Выбор параметров

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

Параметры алгоритма

1. Выбор хэш-функции H. Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в последователность битов, которые можно потом преобразовать в число.
2. Выбор большого простого числа q — порядок одной из циклических подгрупп группы точек эллиптической кривой.

   Замечание: Если размерность этого числа в битах меньше размерности в битах значений хэш-функции H то используются только левые биты значения хэш-функции.

3. Простым числом p обозначается характеристика поля координат F_p.

Генерирование ключей ECDSA

Для простоты будем рассматривать эллиптические кривые над полем F_p, где F_p — конечное простое поле. Причем, если необходимо, конструкцию можно легко адаптировать для эллиптических кривых над другим полем.

Пусть E — эллиптическая кривая, определенная над F_p, и P — точка простого порядка q кривой E. Кривая E и точка P являются системными параметрами. Число p — простое. Каждая пользовательница Алиса конструирует свой ключ посредством следующих действий:

1. Выбирает случайное или псевдослучайное целое число x из интервала .
2. Вычисляет произведение Q = x·P.

Открытым ключом пользовательницы Алисы A является точка Q, а закрытым — x.

Вместо использования E и P в качестве глобальных системных параметров, можно фиксировать только поле F_p для всех пользователей и позволить каждому пользователю выбирать свою собственную эллиптическую кривую E и точку P\in E. В этом случае определенное уравнение кривой E, координаты точки P, а также порядок q этой точки P должны быть включены в открытый ключ пользователя. Если поле F_p фиксировано, то аппаратная и программная составляющие могут быть построены так, чтобы оптимизировать вычисления в том поле. В то же время имеется огромное количество вариантов выбора эллиптической кривой над полем F_p.

Вычисление цифровой подписи

Для того, чтобы подписать какое-либо сообщение, для которого подсчитано значение h хэш-функции H, пользователь A должен сделать следующее:

1. Выбрать случайное целое число k в интервале .
2. Вычислить k·P = и положить в r = x₁, где r получается из целого числа x₁ между 0 и приведением по модулю q.

   Замечание: если r = 0, то уравнение подписи s = k не зависит от секретного ключа x, и следовательно, не подходит в качестве цифровой подписи. Значит, в случае r = 0 необходимо вернуться к шагу 1.

3. Вычислить k и положить s = k.

   Замечание: если s = 0, то значение s, нужное для проверки, не существует.

Значит, в случае s = 0 необходимо вернуться к шагу 1.

Подписью для сообщения является пара целых чисел .

Проверка цифровой подписи

Для того, чтобы проверить подпись пользовательницы Алисы на сообщение, пользователь Борис B должен сделать следующее:

1. Получить подтвержденную копию открытого ключа Q пользовательницы А;
2. Проверить, что числа r и s являются целыми числами из интервала , и вычислить значение хеш-функции h от сообщения;
3. Вычислить u₁ = s h и u₂ = s r;
4. Вычислить u₁P + u₂Q =, и относительно x₀, как целого числа между 0 и , положить v = x₀;
5. Принять подпись, если и только если v = r.

Заметим, что, если пользовательница Алиса вычислила свою подпись правильно, то u₁P + u₂Q =P = kP, так как k = s, и поэтому v = r.

Для подтверждения публичного ключа Q нужно проделать следующее:

1. Проверить, что Q не равно O и координаты верны;
2. Проверить, что Q лежит на кривой;
3. Проверить, что qQ = O;