Алгоритмы обмена ключами и электронной цифровой подписи на основе эллиптических кривых.
Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) принят в качестве стандартов ANSI X9F1 и IEEE P1363.
Создание ключей:
- Выбирается эллиптическая кривая Ep(a,b). Число точек на ней должно делиться на большое целое n.
- Выбирается точка Р на кривой Ep(a,b).
- Выбирается случайное число d из отрезка [1, n-1].
- Вычисляется Q = d × P.
- Закрытым ключом является d, открытым ключом - (E, P, n, Q).
Создание подписи:
- Выбирается случайное число k из отрезка [1,n-1].
- Вычисляются k × P = (x1, y1) и r = x1 (mod n). Проверяется, чтобы r не было равно нулю, так как в этом случае подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k.
- Вычисляется k-1 mod n .
- Вычисляется s = k-1(Н(M)+dr) (mod n) Проверяется, чтобы s не было равно нулю, так как в этом случае необходимого для проверки подписи числа s-1 mod n не существует. Если s = 0, то выбирается другое случайное число k.
- Подписью для сообщения М является пара чисел (r,s).
Проверка подписи:
- Проверить, что целые числа r и s принадлежат диапазону чисел [0, n-1]. В противном случае результат проверки отрицательный, и подпись отвергается.
- Вычислить w = s-1 (mod n) и H(M)
- Вычислить u1=H(M)w(modn)
u2 = r w (mod n) - Вычислить
u1P + u2Q = (x0, y0) v = x0 (mod n) - Подпись верна в том и только том случае, когда v = r