ECDSA(楕円曲線デジタル署名アルゴリズム)の概要

ECDSA(Elliptic Curve Digital Signature Algorithm)の概要です。
要点だけをまとめ、異例のチェックや楕円曲線上の点であるかどうかなどの細かな点は省きます。

正確な仕様は以下です。

AMERICAN NATIONAL STANDARD
X9.62-1998
Public Key Cryptography For The Financial Services Industry:
The Elliptic Curve Digital Signature Algorithm (ECDSA)

5.2. Key Pair Generation and Public Key Validation
5.3. Signature Generation
5.4. Signature Verification
の３つの章の内容です。

準備

G: ベースポイント
n: 群の位数(secp256k1ではベースポイントの位数と同じ)
m: メッセージ 32バイト
seckey: 秘密鍵 32バイト(1以上n未満のランダムな値)
A: 公開ポイント( $=seckey \cdot G$ )
pubkey: 点Aのx座標値 32バイト
nonce: 乱数 1以上n-1以下(メッセージ毎に変更する)

署名

STEP1 $nonce \cdot G \mod n$ の x座標を r とする。
STEP2 rが0なら別のnonceを取り直しSTEP1に戻る。
STEP3 ${nonce}^{-1} \cdot (m + {r} \cdot {seckey}) \mod n$ を s とする。
STEP4 sが0ならnonceを取り直しSTEP1に戻る。
(r, s)を署名と呼ぶ。

署名確認

$u_1 = m \cdot {s}^{-1} \mod n$ を計算する。
$u_2 = r \cdot {s}^{-1} \mod n$ を計算する
点 $u_1 \cdot G + u_2 \cdot A$ のx座標が mod n で r と一致するかどうか確認する

lower-S form

楕円曲線上の点Pと点-Pはx座標の値は同じでy座標の値がマイナスになったものです。
rについては一意に決まります。署名確認では、点のx座標値だけを比較するため、sについては、2種類の値を持つことが可能です。
sも一意にしたい場合はsの絶対値が0に近い方を採用します。
これをlower-S formとよびます。
詳しくは、
http://pebble8888.hatenablog.com/entry/2018/04/22/214924
の記事で説明します。

参考: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Signature_generation_algorithm