ビットコインの署名プログラムを理解する

ECDSA(secp256k1)での署名と検証をpythonで行う(外部ライブラリ使用なし)内のプログラムで分からないところを調べました。

ビットコインの署名・楕円暗号曲線についてはこの文章に図があり、とても分かりやすいと思います。

法素数

secp256k1で使う値(少し計算してある) $ y^{2} \mod p = (x^{3} ＋ 7) \mod p $ の p

P = 2 ** 256 - 2 ** 32 - 977

位数 (order)

署名で使用する

O = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

ベースポイント

Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = (Gx, Gy)

冪剰余

$ 7^{5} \mod 13 $ を $ ((7^{4} \mod 13) \times (7^{1} \mod 13)) \mod 13 $ と分解する

# 5なら101と2進数に分解して1が立っているところで合算する
def expmod(b, e, m):
    if e == 0:
        return 1
    # 段々半分にしている 9 4 2 1みたいな感じ
    result = expmod(b, e // 2, m) ** 2 % m
    if e & 1:
        result = (result * b) % m
    return result

モジュラ逆数

wiki
オイラーの定理

# mが素数の場合のモジュラの逆数の求め方
def inv(x, m):
    return expmod(x, m - 2, m)

点の倍算

def scalarmult(p, e):
    if e == 0:
        return (-1, -1)
    q = scalarmult(p, e // 2)
    q = add_pt(q, q)
    if e & 1:
        q = add_pt(q, p)
    return q

2点が同じ場合の加算

$ y^{2} \mod p = x^{3} + 7 \mod p $ を微分した結果が楕円曲線の接線の傾きになる

def double_pt(p):
    x, y = p[0], p[1]
    if y == 0:
        return (0, 0)
    nu = 3 * expmod(x, 2, P) * inv(2 * y, P)
    x3 = (expmod(nu, 2, P) - 2 * x) % P
    y3 = (nu * (x - x3) - y) % P
    return (x3, y3)

２点を通る直線の方程式

def add_pt(p, q):
    x1, y1 = p[0], p[1]
    x2, y2 = q[0], q[1]
    if x1 == -1 and y1 == -1:
        return q
    if x2 == -1 and y2 == -1:
        return p
    if x1 == x2:
        if (y1 + y2) % P == 0:
            return (-1, -1)
        else:
            return double_pt(p)
    #  (y1- y2) /  (x1- x2)  が傾き
    lm = (y1 - y2) * inv(x1 - x2, P)
    #  ((lm ** 2  % P) - (x1 + x2)) % P 楕円曲線の解がx1 + x2 + x3 = lm ** 2 だから x3 = lm ** 2 - x1 - x2
    x3 = (expmod(lm, 2, P) - (x1 + x2)) % P
    # x1 x2 を通る直線は y - y1 = lm(x - x1) なので yにy3 xにx3を代入する
    y3 = (lm * (x1 - x3) - y1) % P
    return (x3, y3)

# 法素数で割って0なら曲線上の点
def isoncurve(point):
    x, y = point[0], point[1]
    return (y ** 2 - x ** 3 - 7) % P == 0

署名のためのka関数

# big endian
def bit(h,  i):
    return (h[i // 8] >> (7 - (i % 8))) & 1

# 32 byte array to big endian integer
def decodeint(s):
    assert(len(s) == 32)
    return sum(2 ** (256 - 1 - i) * bit(s, i) for i in range(0, 256))

署名

(この記事が分かりやすい)

secret_key = 3
public_key = scalarmult(G, secret_key)
print("secret_key = %x" % secret_key)
print("public_key = (%x, %x)" % (public_key[0], public_key[1]))

# string to byte array
msg = str("0000").encode('utf-8')
print(f"msg {msg}")

# -- sign

# STEP1 nonce * G mod O の x座標を r とする。
nonce = 2
print("nonce = %d" % nonce)
R = scalarmult(G, nonce) 
r = R[0] % O

# STEP2 rが0なら別のnonceを取り直しSTEP1に戻る。
#   not implement

# STEP3 nonce ** −1 * (m + r * seckey) mod P を s とする。

msg_digest = hashlib.sha256(msg).digest()
print("msg_digest:" + msg_digest.hex())
msg_i = decodeint(msg_digest)
print("msg_i:" + str(msg_i))
s = (inv(nonce, O) * (msg_i + r * secret_key)) % O

# STEP4 sが0ならnonceを取り直しSTEP1に戻る。
#   not implement

# (r, s)を署名と呼ぶ。

print("r = %d" % r)
print("r = 0x%x" % r)
print("s = %d" % s)
print("s = 0x%x" % s)

# -- verify
# u1　=　m * s **　− 1 mod O を計算する。
# u2　=　r * s **　− 1 mod Oを計算する
# 点 u1 * G + u2 * public_key( scalarmult(G, secret_key)と一緒)のx座標が mod O で r と一致するかどうか確認する
si = inv(s, O)
u1 = (msg_i * si) % O
u2 = (r * si) % O
V = add_pt(scalarmult(G, u1), scalarmult(public_key, u2)) 
print("V = (%d, %d)" % (V[0], V[1]))
result = (((V[0] - r) % O) == 0)

print(f"result {result}")