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


[ECDSA(secp256k1)での署名と検証をpythonで行う(外部ライブラリ使用なし)](https://www.pebblewind.com/entry/2018/04/21/210617)内のプログラムで分からないところを調べました。

ビットコインの署名・楕円暗号曲線については[この文章](https://paiza.hatenablog.com/entry/2018/05/25/Python%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E8%A9%A6%E3%81%99%E3%83%BBBitcoin%E3%81%AE%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7%E3%81%A7%E4%BD%9C%E3%82%89%E3%82%8C%E3%82%8B%E3%82%A2%E3%83%89)に図があり、とても分かりやすいと思います。

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

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

##  位数 (order) 
署名で使用する

```python
O = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
```

## ベースポイント

```python
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

```python
# 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](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E9%80%86%E6%95%B0
)
[オイラーの定理](https://mathtrain.jp/phi)

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

## 点の倍算

```python
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 $ を微分した結果が楕円曲線の接線の傾きになる

```python
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)
```

### [２点を通る直線の方程式](http://www.geisya.or.jp/~mwm48961/koukou/tyoku13.htm)

```python
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)
```

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

## 署名のためのka関数

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

## 署名
([この記事](https://www.etarou.work/posts/4968764)が分かりやすい)

```python
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]))
```

```python
# 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}")
```