技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く色々なことに興味があります。

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)

pythonでは a^{m-2}\pmod{m}

pow(a, m-2, m)

の1行で書ける

参考にしている本

仮想通貨の教科書

仮想通貨の教科書