pythonでコードを書きながら楕円曲線暗号を理解する

仮想通貨についての勉強
楕円曲線暗号とは、ビットコインのデジタル署名で使われてる公開鍵暗号方式。

この記事にあるコードを写経しながら勉強する。

自分自身まだ深く理解してないところがあるので解説は別の機会に書くことにしてメモ書き程度にとどめておく。

コード

from hashlib import sha256

class ECDSA:
    def __init__(self):
        # parameters are based on SPEC256k1
        self.cp = pow(2,256) - pow(2,32) - pow(2,9) - pow(2,8) - pow(2,7) - pow(2,6) - pow(2,4) - pow(2,0)
        self.cb = 7
        self.ca = 0
        self.base_x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
        self.base_y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
        self.base = (self.base_x, self.base_y)
        self.secret_key = None
        self.public_key = None

    def generate_key(self, string):
        secret_hash = sha256(string.encode('utf-8')).hexdigest()
        secret_key = int(secret_hash, 16)
        pt = self.EC_multi(secret_key)
        public_key = int("04" + "%064x" % pt[0] + "%064x" % pt[1], 16)
        self.secret_key = secret_key
        self.public_key = public_key
        return (public_key, secret_key)

    def EC_add(self, P, Q):
        lam = ((Q[1] - P[1]) * inv_mod(Q[0] - P[0], self.cp)) % self.cp
        x = ((pow(lam, 2)) - P[0] - Q[0]) % self.cp
        y = (lam * (P[0]- x) - P[1]) % self.cp
        return (x,y)

    def EC_double(self, P):
        lam = ((3 * (pow(P[0], 2) + self.ca) * inv_mod(2 * P[1], self.cp))) % self.cp
        x = (pow(lam, 2) - 2*P[0]) % self.cp
        y = (lam * (P[0] - x) - P[1]) % self.cp
        return (x,y)

    def EC_multi(self, scalar):
        if scalar == 0:
            raise ValueError('invalid scalar/ purivate key')
        scalar_bin = str(bin(scalar))[2:]
        point = self.base
        for i in range(1, len(scalar_bin)):
            point = self.EC_double(point)
            if scalar_bin[i] == "1":
                point = self.EC_add(point, self.base)
        return point

def inv_mod(k, mod):
    return pow(k, mod-2, mod)


if __name__=="__main__":
    ecdsa = ECDSA()
    pk, sk = ecdsa.generate_key("Satoshi Nakamoto")
    print(sk)
    print(pk)

（補足）モジュラ逆数

モジュラ逆数とは $a^{-1}\equiv x \pmod{m}$ となる $x$ のこと。
素数 $m$ と互いに素な $a$ に対して

$a^{-1}\equiv a^{m-2} \pmod{m}$

となることを使っている。（フェルマーの小定理）

(証明)
オイラー関数 $\phi(m)$ を用いて、mが素数の時
$\displaystyle \left\{ \begin{array}{1} a^{\phi(m)}\equiv 1 \pmod{m}\\ \phi(m) = m-1 \end{array} \right .$
なので
$a^{\phi(m) - 1} \equiv a^{-1} \pmod{m} \\ a^{m-2} \equiv a^{-1} \pmod{m}$
(Q.E.D)