Алгоритм цифровой подписи на основе эллиптических кривых ECDSA

Аналог алгоритма Диффи-Хеллмана обмена ключами

Обмен ключами с использованием эллиптических кривых может быть выполнен следующим образом. Сначала выбирается простое число р ≈ 2¹⁸⁰ и параметры a и b для уравнения эллиптической кривой. Это задает множество точек E_p (a,b). Затем в E_p (a,b) выбирается генерирующая точка G = (x₁,y₁). При выборе G важно, чтобы наименьшее значение n, при котором n × G = 0, оказалось очень большим простым числом. Параметры E_p (a,b) и G криптосистемы являются параметрами, известными всем участникам.

Обмен ключами между пользователями А и В производится по следующей схеме.

1. Участник А выбирает целое число n_A, меньшее n. Это число является закрытым ключом участника А. Затем участник А вычисляет открытый ключ P_A = n_A × G, который представляет собой некоторую точку на E_p (a,b).
2. Точно так же участник В выбирает закрытый ключ n_B и вычисляет открытый ключ P_B.
3. Участники обмениваются открытыми ключами, после чего вычисляют общий секретный ключ K

Участник А:

K = n_A × P_B

Участник В:

K = n_В × P_А

Следует заметить, что общий секретный ключ представляет собой пару чисел. Если данный ключ предполагается использовать в качестве сеансового ключа для алгоритма симметричного шифрования, то из этой пары необходимо создать одно значение.

Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) принят в качестве стандартов ANSI X9F1 и IEEE P1363.

Создание ключей:

1. Выбирается эллиптическая кривая E_p (a,b). Число точек на ней должно делиться на большое целое n.
2. Выбирается точка Р E_p (a,b).
3. Выбирается случайное число d [1, n-1].
4. Вычисляется Q = d × P.
5. Закрытым ключом является d, открытым ключом - (E, P, n, Q).

Создание подписи:

1. Выбирается случайное число k [1, n-1].
2. Вычисляется

3. k × P = (x₁, y₁) 4. и 5. r = x₁ (mod n).

Проверяется, чтобы r не было равно нулю, так как в этом случае подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k.

1. Вычисляется

7. k^-1 mod n

1. Вычисляется

9. s = k^-1 (Н(M) + dr) (mod n)

Проверяется, чтобы s не было равно нулю, так как в этом случае необходимого для проверки подписи числа s^-1 mod n не существует. Если s = 0, то выбирается другое случайное число k.

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

Проверка подписи:

1. Проверить, что целые числа r и s принадлежат диапазону чисел [0, n-1]. В противном случае результат проверки отрицательный, и подпись отвергается.
2. Вычислить w = s^-1 (mod n) и H(M)
3. Вычислить

4. u₁ = H(M) w (mod n)5. u₂ = rw (mod n)

1. Вычислить

7. u₁P + u₂Q = (x₀, y₀)8. v = x₀ (mod n)

1. Подпись верна в том и только том случае, когда v = r

Дата добавления: 2014-12-23