[bitcoin基礎技術] ECDSA署名と検証

m: 署名対象のメッセージ
Q = dG : Q公開鍵、dは秘密鍵、Gはsecp256k1ベースポイント
n: secp256k1の位数

### ECDSA署名の生成
1. ハッシュ関数にメッセージmを渡し、ハッシュ値m’を取得する(m’=H(m))
2. [1, n-1]の範囲からkを選択し、楕円曲線上の点Rを k*Gで求める (R = kG)
3. R= rx, ry とする。Rのx座標rxを位数nで割った余剰を求める r = rx mod n
4. s = (m'(ハッシュしたメッセージ) + d(秘密鍵)*r(Rのx座標)) / k(任意の点) mod n
5. (r, s)が m に対する署名となる

### ECDSA署名の検証
1. P = (px, py)とする
P = m’/s * G + r / s * Q (公開鍵)(mod n)
この時、Px = r(mod n) となるとき、署名検証に成功

パラメータkを生成
$ openssl ecparam -genkey -name secp256k1 -out k.pem; ls k.pem
$ openssl ec -in k.pem -outform DER | tail -c +8 | head -c 32 | xxd -p -c 32
read EC key
writing EC key
a891fce013c907a3ce5e157d1edc474bbdf7efc0c133b41cad14aca3566c914c
$ k=a891fce013c907a3ce5e157d1edc474bbdf7efc0c133b41cad14aca3566c914c

Rを生成
$ openssl ec -in k.pem -pubout -outform DER | tail -c 65 | xxd -p -c 65
read EC key
writing EC key
042ce7c2a48e71ad11e4445b3901d4afe715c0298ed1504cb4ce47b426d83bfaa7bb4665d4c92b9484c4b0ce5cfcabe089e1e2a7c8e32a3c6b5f2d2c0ba301fb97
$ R=042ce7c2a48e71ad11e4445b3901d4afe715c0298ed1504cb4ce47b426d83bfaa7bb4665d4c92b9484c4b0ce5cfcabe089e1e2a7c8e32a3c6b5f2d2c0ba301fb97

Rからrxを取り出し、変数rxに格納
$ rx=`echo $R | cut -c3-66`; echo $rx
2ce7c2a48e71ad11e4445b3901d4afe715c0298ed1504cb4ce47b426d83bfaa7

メッセージのハッシュ値を生成し、変数mhに格納
$ mh=`cat message.txt | xxd -r -p | openssl dgst -sha256 | cut -c10-`; echo $mh
stdin)= 45f83d17e10b34fca01eb8f4454dac34a777d9404a464e732cf4abf2c0da94c4

公開鍵をQに格納
$ Q=$pubKey; echo $Q
047a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def multiply_inv(a, m):
    if a < 0:
        a = a % m
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('multiply modular inverse does not exist')
    else:
        return x % m