SEC公開鍵からyを見つけるメソッド

    @classmethod
    def parse(self, sec_bin):
        if sec_bin[0] == 4:
            x = int.from_bytes(sec_bin[1:33], 'big')
            y = int.from_bytes(sec_bin[33:65], 'big')
            return S256Point(x=x, y=y)
        is_even = sec_bin[0] == 2
        x = S256Field(int.from_bytes(sec_bin[1:], 'big'))
        alpha = x**3 + S256Field(B)
        beta = alpha.sqrt()
        if beta.num % 2 == 0:
            even_beta = beta 
            odd_beta = S256Field(P - beta.num)
        else:
            even_beta = S256Field(P - beta.num)
            odd_beta = beta
        if is_even:
            return S256Point(x, even_beta)
        else:
            return S256Point(x, odd_beta)

公開鍵が04, 03, 02かで秘密鍵の点を戻す

SEC圧縮フォーマットは以下の通り

from ecc import S256Point, PrivateKey

p = PrivateKey(5001)
print(p.point.sec(compressed=True).hex())

Pythonのクラスメソッド(@classmethod)

クラスにくっついている関数のようなもので、インスタンス化していないクラスのものから呼び出せる。
メソッドに@classmethodと付けることでクラスメソッドにできる。

class A:

    def test_method():
        print("test")

    @classmethod
    def my_cls_method(cls):
        print("hello")

A.my_cls_method()
A.test_method()

– 第一引数でクラスが取得できる(インスタンスメソッドは第一引数が必ずselfになる)
– クラスの中にあるので、クラスをインポートすれば使える
– クラスメソッドを使わずに関数として書くこともできるが、クラスメソッドの場合は、インポートできて、まとめて管理できる

class Item:
    def __init__(self, id, name):
        self.id = id
        self.name = name

    @classmethod
    def retrieve_from_api(cls, id):
        res = requests.get(f"https://api.example.com/items/{id}")
        data = res.json()
        return cls(id, data["name"])

非圧縮SECフォーマットと圧縮SECフォーマット

楕円曲線暗号の公開鍵は(x, y)形式の一つの座標
ECDSA公開鍵をシリアライズする方法はSECフォーマット(Standards for Efficient Cryptography)と呼ばれる

1. プレフィックスバイトは0x04
2. 32バイトのビッグエンディアン整数としてx座標を追加
3. 32バイトのビッグエンディアン整数としてy座標を追加

圧縮SECフォーマットの場合、yが偶数の場合は0x02とし、奇数の場合は0x03とする。

    def sec(self, compressed=True):
        if compressed:
            if self.y.num % 2 == 0:
                return b'\x02' + self.x.num.to_bytes(32, 'big')
            else:
                return b'\x03' + self.x.num.to_bytes(32, 'big')
        else:
            return b'\x04' + self.x.num.to_bytes(32, 'big') + self.y.num.to_bytes(32, 'big')

from ecc import S256Point, PrivateKey

pkey = PrivateKey(5000)
p = pkey.point.sec(compressed=False).hex()
print(p)

$ python3 main.py
04ffe558e388852f0120e46af2d1b370f85854a8eb0841811ece0e3e03d282d57c315dc72890a4f10a1481c031b03b351b0dc79901ca18a00cf009dbdb157a1d10

Pythonのビッグエンディアンとリトルエンディアン

import binascii

hex_b = 'f0148c'
bytes_be = binascii.unhexlify(hex_b)
bytes_le = bytes_be[::-1]
hex_le = binascii.hexlify(bytes_le).decode()
print(hex_le)

import sys

def dump(data):
    print(data)

    a = int.from_bytes(data, byteorder='big')
    b = int.from_bytes(data, byteorder='little')
    c = int.from_bytes(data, byteorder=sys.byteorder)
    print(a, hex(a))
    print(b, hex(b))
    print(c, hex(c))

dump(b'\x01\x02')
dump(b'\x11\x12\x13\x14\x15\x16\x17\x18\x19')

$ python3 test.py
b’\x01\x02′
258 0x102
513 0x201
513 0x201
b’\x11\x12\x13\x14\x15\x16\x17\x18\x19′
314897056051100063769 0x111213141516171819
462904482303900324369 0x191817161514131211
462904482303900324369 0x191817161514131211

シリアライズとは

シリアライズとは、複数の要素を一列に並べる操作や処理のこと。単にシリアライズといった場合には、プログラムの実行状態や複雑なデータ構造などを一つの文字列やバイト列で表現する「直列化」を指すことが多い。

メッセージ署名のコーディング

class PrivateKey:

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

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

class PrivateKey:

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

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

    def sign(self, z):
        k = randint(0, N-1)
        r = (k*G).x.num
        k_inv = pow(k, N-1, N)
        s = (z + r*self.secret) * k_inv % N
        if s > N/2
            s = N - s
        return(r, s)

kがrandintではなく、一意であるようにする。

    def sign(self, z):
        k = self.deterministic_k(z)
        r = (k*G).x.num
        k_inv = pow(k, N-1, N)
        s = (z + r*self.secret) * k_inv % N
        if s > N/2
            s = N - s
        return(r, s)

    def deterministic_k(self, k):
        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).giest()
        v = hmac.new(k, v, s256).digest()
        k = hmac.new(k, v + b'\x01' + secret_bytes + z_bytes, s256).giest()
        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 
            k = hmac.new(k, v + b'\x00', s256).giest()
            v = hmac.new(k, v, s256).digest()

署名作成・検証のプログラミング

### 署名検証
1. s_inv(1/s)は、群の位数n上で、フェルマーの小定理
2. u = z/s、群の位数であるnでモジュロ演算
3. v = r/s、群の位数であるnでモジュロ演算
4. uG + vP は　Rになる
5. x座標がrであることを確認

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 S256Point(Point):
   ...

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

### 署名の作成
1. zが与えられており、eG = Pを満たすeがわかっている
2. ランダムにkを選ぶ
3. R=kGとrを算出
4. s = (z+re)/kを算出
5. 署名は(r, s)になる

from ecc import S256Point, G, N
from helper import hash256

e = int.from_bytes(hash256(b'my secret'), 'big')
z = int.from_bytes(hash256(b'my message'), 'big')
k = 1234567890
r = (k*G).x.num 
k_inv = pow(k, N-2, N)
s = (z+r*e) * k_inv % N 
point = e*G
print(point)
print(hex(z))
print(hex(r))
print(hex(s))

$ python3 main.py
S256Point(028d003eab2e428d11983f3e97c3fa0addf3b42740df0d211795ffb3be2f6c52, 0ae987b9ec6ea159c78cb2a937ed89096fb218d9e7594f02b547526d8cd309e2)
0x231c6f3d980a6b0fb7152f85cee7eb52bf92433d9919b9c5218cb08e79cce78
0x2b698a0f0a4041b77e63488ad48c23e8e8838dd1fb7520408b121697b782ef22
0xbb14e602ef9e3f872e25fad328466b34e6734b7a0fcd58b1eb635447ffae8cb9

Pointは検証者に知られる必要がある。

ビットコインの公開鍵

P(公開鍵) = e(秘密鍵) * G
公開鍵は離散対数となっている。
公開鍵は座標(x, y)で、それぞれ256ビット

### 署名と検証
署名をr, s, 署名対象のハッシュをz、署名者の公開鍵をPとする
u = z / s, v = r / sを計算する
uG + vP = Rを計算する
点Rの x座標がrと同じならば署名は有効

### 署名の検証
ドキュメントの署名ハッシュがz
rはランダム
sが署名

from ecc import S256Point, G, N
z = 0xbc62d4b80d9e36da29c16c5d4d9f11731f36052c72401a76c23c0fb5a9b74423
r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6
s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec
px = 0x04519fac3d910ca7e7138f7013706f619fa8f033e6ec6e09370ea38cee6a7574
py = 0x82b51eab8c27c66e26c858a079bcdf4f1ada34cec420cafc7eac1a42216fb6c4
point = S256Point(px, py)
s_inv = pow(s, N-2, N)
u = z * s_inv % N
v = r * s_inv % N
print((u*G + v*point).x.num == r)

検証
from ecc import S256Point, G, N
z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60
r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395
s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4
px = 0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c
py = 0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34
point = S256Point(px, py)
s_inv = pow(s, N-2, N)
u = z * s_inv % N
v = r * s_inv % N
print((u*G + v*point).x.num == r)

z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d
r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c
s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6
px = 0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c
py = 0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34

いずれもTrueになる。

ビットコインの曲線とsecp256k1の実装

secp256k1は
a=0, b=7 すなわち　y**2 = x **3 + 7
p(※有限体の素数prime) = 2**256 – 2**32 – 977
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
n(※群位) = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
すなわち2*256は32バイトで記憶することができ、秘密鍵の記憶が比較的簡単にできるという特徴を持つ

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 – 2**32 – 977
print(gy**2 % p == (gx**3 + 7) % p)
$ python3 test.py
True

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 - 2**32 - 977
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
x = FieldElement(gx, p)
y = FieldElement(gy, p)
seven = FieldElement(7, p)
zero = FieldElement(0, p)
G = Point(x, y, zero, seven)
print(n*G)

256ビットの数を常に64文字で表示する。

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

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)

a, bの初期化

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)

群の位数

N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

class S256Point(Point):
    def __rmul__(self, coefficient):
        coef = coefficient % N
        return super().__rmul__(coef)

x, yも定数として定義Gしておく

G = S256Point(
    0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
    0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
)

from ecc import G, N
print(vars(N*G))
$ python3 main.py
{‘a’: 0000000000000000000000000000000000000000000000000000000000000000, ‘b’: 0000000000000000000000000000000000000000000000000000000000000007, ‘x’: None, ‘y’: None}