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

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 $ と分解する

https://ja.wikipedia.org/wiki/%E5%86%AA%E5%89%B0%E4%BD%99

# 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)


2点を通る直線の方程式

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}")