BTC_楕円曲線暗号

F103（位数103の有限体）のもとで以下の楕円曲線を考えてみる。

例えば点（17, 64）が曲線上にあることを証明するには右辺と左辺それぞれ計算し、等しいことを確認する

有限体上の楕円曲線をグラフにすると以下のようになる

楕円曲線の点の加算は有限体上でも機能し、暗号化のベースとなる

同じ点を加算でき、結合性があるのでさらに点を加算していくことができる

同じ加算を何度も繰り返すことをスカラー倍算という

点（170, 142）のスカラー倍算は以下になる

スカラー倍算の結果は有限体上の楕円曲線のグラフで見たような完全に離散した点となる。スカラー倍算の結果は計算により出せるが、逆に遡ることは難しい。これを離散対数問題と呼び、楕円曲線暗号の基本原理となる

公開鍵暗号で作成したいのは、有限巡回群（ある点Gを無限遠点になるまでスカラー倍算する集合）

有限巡回群：nG = 0 のとき、{G, 2G, 3G,..., ng}

群にある演算は加算の1種類のみで、以下の特性がある

1. 同一性：単位元は無限遠点。0 + A = A 0を無限遠点と呼ぶ
2. 閉包：aG + bG = (a + b)G が群に含まれる
3. 可逆性：aGに対して、　aG + (n-a)G = (a + n -a)G = nG = 0 となる(n-a)Gが存在する
4. 可換性：A + B = B + A
5. 結合性：(A + B) + C = A + (B + C)

• 楕円曲線の式：　y**2 = x**3 + 7
• 有限体の位数：　p = 2**256 - 2**32 - 977
• 生成点Gのx座標：　0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
• 生成点Gのy座標：　0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
• 群の位数（スカラー倍算で無限遠点になる数）：　0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

有限体、群の位数は10進数にすると78桁ある（無量大数を超えてる。。さらば青春の光のぼったくりバーのコント思い出した。。）

数が意味不明すぎてイメージわかないが、1兆台のコンピュータが毎秒1兆回の計算を1兆回行っても計算回数は10**56にも達しないくらいなので、どえらい数なのは間違いない

ちなみに全宇宙の原子数は10**80と言われており、ビットコインの秘密鍵を計算で見つけるには全宇宙の原子数をチェックするような恐ろしいことになるという仕組みになっている

ビットコインで使われている楕円曲線暗号はsecp256k1と呼ばれる

公開鍵暗号の演算は以下になる

Pを公開鍵、eを秘密鍵と呼ぶ（Gは群の生成点）

PはeとGが分かれば求めることができるが（スカラー倍算）、eはPとGがわかっても求めることができない（離散対数問題）

公開鍵は座標（x, y）でxとyはそれぞれ256ビットの数である

署名アルゴリズムは楕円曲線デジタル署名アルゴリズム（Elliptic Curve Digital Signature Algorithm）、略してECDSAと呼ばれる

検証に必要な要素は以下となる（kとe以外は事前にわかっている）

G: ベースポイント座標 P：署名者の公開鍵

k: 署名のためのランダムな数（署名のための一時的な秘密鍵、これがバレたら秘密鍵流出） R：ベースポイントにkをスカラー倍算した座標（r, y） r, s : 署名（rはRのx座標、sは後述） z: 署名ハッシュ(送信データをハッシュしたもの、hash256（sha256を2回）、32バイト) e: 署名者の秘密鍵

検証に必要な式

上記の式を用いて以下を計算する

式補足：

上記で算出されたRのx座標と、署名のrが等しければ検証は有効となる（公開鍵に対して正しい秘密鍵で署名が作成されたことが確認できる）

A = 0
B = 7
P = 2**256 - 2**32 - 977
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

class S256Field(FieldElement):

    def __init__(self, num, prime=None):
        super().__init__(num=num, prime=P)

    def __repr__(self):
        return '{:x}'.format(self.num).zfill(64)

class S256Point(Point):

    def __init__(self, x, y, a=None, b=None):
        a, b = S256Field(A), S256Field(B)
        if type(x) == int:
            super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)
        else:
            super().__init__(x=x, y=y, a=a, b=b)  # <1>

    def __repr__(self):
        if self.x is None:
            return 'S256Point(infinity)'
        else:
            return 'S256Point({}, {})'.format(self.x, self.y)

    def __rmul__(self, coefficient):
        coef = coefficient % N  # <1>
        return super().__rmul__(coef)

    def verify(self, z, sig):
        s_inv = pow(sig.s, N - 2, N)  # <1>
        u = z * s_inv % N  # <2>
        v = sig.r * s_inv % N  # <3>
        total = u * G + v * self  # <4>
        return total.x.num == sig.r  # <5>

G = S256Point(
    0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
    0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

class Signature:

    def __init__(self, r, s):
        self.r = r
        self.s = s

    def __repr__(self):
        return 'Signature({:x},{:x})'.format(self.r, self.s)

class PrivateKey:

    def __init__(self, secret):
        self.secret = secret
        self.point = secret * G  

    def hex(self):
        return '{:x}'.format(self.secret).zfill(64)

    def sign(self, z):
        k = self.deterministic_k(z)  
        r = (k * G).x.num
        k_inv = pow(k, N - 2, N) #フェルマーの小定理
        s = (z + r * self.secret) * k_inv % N
        if s > N / 2:
            s = N - s
        return Signature(r, s)

    def deterministic_k(self, z):
        k = b'\x00' * 32
        v = b'\x01' * 32
        if z > N:
            z -= N
        z_bytes = z.to_bytes(32, 'big')
        secret_bytes = self.secret.to_bytes(32, 'big')
        s256 = hashlib.sha256
        k = hmac.new(k, v + b'\x00' + secret_bytes + z_bytes, s256).digest()
        v = hmac.new(k, v, s256).digest()
        k = hmac.new(k, v + b'\x01' + secret_bytes + z_bytes, s256).digest()
        v = hmac.new(k, v, s256).digest()
        while True:
            v = hmac.new(k, v, s256).digest()
            candidate = int.from_bytes(v, 'big')
            if candidate >= 1 and candidate < N:
                return candidate  # <2>
            k = hmac.new(k, v + b'\x00', s256).digest()
            v = hmac.new(k, v, s256).digest()