Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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}")
t10471
mercari
フリマアプリ「メルカリ」を、グローバルで開発しています。
https://tech.mercari.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away