Month: November 2023

ビットコインの公開鍵

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}

Python super().__init__()の使い方

継承元のコンストラクタをオーバラーライドする

class Parent:
    def __init__(self, a, b):
        self.a = a 
        self.b = b
    
    def w(self):
        print(self.b)

class Child(Parent):
    def w(self):
        return super().w()

child = Child(0, 'hello')
child.w()

サブクラスで__init__を定義すると親クラスの上書きされてしまう。

class A:
    def __init__(self, name):
        self.name = name 

class B(A):
    def __init__(self, name, mail):
        super().__init__(name)
        self.mail = mail

b = B("yamada", "gmail")
b.name

class Parent:
    def __init__(self, name, age):
        self.name = name 
        self.age = age 

    def my_name(self):
        print("名前は" + self.name + "。年齢は" + str(self.age) + "歳。")

class Child(Parent):
    def __init__(self, name, age):
        super().__init__(name, age)

yamada = Child("yamada", 20)
yamada.my_name()

スカラー倍算のコーディング

    def __rmul__(self, coefficient):
        product = self.__class__(Nonee, None, self.a, self.b)
        for _ in range(coefficient):
            product += self
        return product

coefficient の和訳は係数です。係数の数だけ点を加算します。

ビットの倍算だと以下のようになる。2進展開。

    def __rmul__(self, coefficient):
        coef = coefficient 
        current = self 
        result = self.__class__(Nonee, None, self.a, self.b)
        while coef:
            if coef & 1:
                result += current
            current += current
        return result

群の位数

群とは
-> ある二項演算とその対象となる集合とを合わせて見たときに結合性を伴い単位元と逆元を備えるものをいう。
-> 演算が一つ入った集合で、「結合法則」、「単位元の存在」、「逆元の存在」の３つの条件を満たすものを群という

(a + b)G = ((a + b)%n)G

y**2 = x**3 +7 で(15, 86)

from ecc import FieldElement, Point
 
prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x = FieldElement(num=15, prime=prime)
y = FieldElement(num=86, prime=prime)
p = Point(x, y, a, b)
inf = Point(None, None, a, b)
product = p
count = 1 
while product != inf:
    product += p 
    count += 1
print(count)

どこまで加算すれば無限遠点になるかを計算すれば良いんですね。

楕円曲線のスカラー倍算

from ecc import FieldElement, Point
 
prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x = FieldElement(num=192, prime=prime)
y = FieldElement(num=105, prime=prime)
p = Point(x, y, a, b)
print(vars(p+p))

$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(49), ‘y’: FieldElement_223(71)}

p * p や 2*pとすると、以下のようなエラーとなってしまう。
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(49), ‘y’: FieldElement_223(71)}
Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/main.py”, line 10, in
print(vars(p*p))
TypeError: unsupported operand type(s) for *: ‘Point’ and ‘Point’

Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/test.py”, line 9, in
print(p+p)
File “/home/vagrant/dev/blockchain/ecc.py”, line 89, in __add__
if self == other and self.y == 0 * self.x:
TypeError: unsupported operand type(s) for *: ‘int’ and ‘FieldElement’

他のパターン
x = FieldElement(num=143, prime=prime)
y = FieldElement(num=98, prime=prime)
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(64), ‘y’: FieldElement_223(168)}

x = FieldElement(num=47, prime=prime)
y = FieldElement(num=71, prime=prime)
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(36), ‘y’: FieldElement_223(111)}

4 * (47, 71) の場合
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(194), ‘y’: FieldElement_223(51)}

8 * (47, 71) の場合
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(116), ‘y’: FieldElement_223(55)}

有限体における点の加算

from ecc import FieldElement, Point

prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x1 = FieldElement(num=192, prime=prime)
y1 = FieldElement(num=105, prime=prime)
x2 = FieldElement(num=17, prime=prime)
y2 = FieldElement(num=56, prime=prime)
p1 = Point(x1, y1, a, b)
p2 = Point(x2, y2, a, b)
print(p1+p2)
print(vars(p1+p2))

$ python3 main.py

{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(170), ‘y’: FieldElement_223(142)}

vars()とすることで、オブジェクトの中身を表示します。ここでは、x:170, y:142になります。

(170,142) + (60, 139) = (220, 181)
(47,71) + (17,56) = (215,68)
(143,98) + (76,66) = (47,71)

これをpythonのunittestで記述する

    def test_add(self):
        prime = 223
        a = FieldElement(0, prime)
        b = FieldElement(7, prime)  
        point1 = ((170,142),(47,71),(143,98))
        point2 = ((60,139),(17,56),(76,66))
        result = ((220, 181),(215,68),(47,71))
        for i in range(0, 3):
            x1 = FieldElement(num=point1[i][0], prime=prime)
            y1 = FieldElement(num=point1[i][1], prime=prime)
            x2 = FieldElement(num=point2[i][0], prime=prime)
            y2 = FieldElement(num=point2[i][1], prime=prime)
            x3 = FieldElement(num=result[i][0], prime=prime)
            y3 = FieldElement(num=result[i][1], prime=prime)
            p1 = Point(x1, y1, a, b)
            p2 = Point(x2, y2, a, b)
            p3 = Point(x3, y3, a, b)
            self.assertEqual(p3, (p1+p2))

x1, y1, x2, y2, x3, y3をtuppleにしてforeachでも良かった。

点と曲線の確認をunittestで実行する

ecc.py

from unittest import TestCase

class ECCTest(TestCase):

    def test_on_curve(self):
        prime = 223
        a = FieldElement(0, prime)
        b = FieldElement(7, prime)  
        valid_points = ((192, 105),(17,56),(1,193))
        invalid_points = ((200, 119),(42, 99))
        for x_raw, y_raw in valid_points:
            x = FieldElement(x_raw, prime)
            y = FieldElement(y_raw, prime)
            Point(x, y, a, b)
        for x_raw, y_raw in invalid_points:
            x = FieldElement(x_raw, prime)
            y = FieldElement(y_raw, prime)
            with self.assertRaises(ValueError):
                Point(x, y, a, b)

helper.py

from unittest import TestSuite, TextTestRunner

def run(test):
    suite = TestSuite()
    suite.addTest(test)
    TextTestRunner().run(suite)

main.py

import ecc
from helper import run

run(ecc.ECCTest('test_on_curve'))

$ python3 main.py
.
———————————————————————-
Ran 1 test in 0.000s

OK

Python unittestのTextTestRunner().runを理解する

$ sudo apt install tree
$ tree
.
├── other.py
├── suite.py
└── test.py

test.py

import unittest

class MyTest(unittest.TestCase):
    def test_mytest_01(self):
        print("test_mytest_01 is called")
        one = 1
        self.assertEqual(one, 1, "one is 1")

other.py

import unittest

class OhterTest(unittest.TestCase):
    def test_other_01(self):
        print("test_mytest_01 is called")
        two = 2
        self.assertEqual(two, 2, "two is 2")

suite.py

import unittest

import test
import other

def suite():
    test_suite = unittest.TestSuite()
    test_suite.addTest(unittest.makeSuite(test.MyTest))
    test_suite.addTest(unittest.makeSuite(other.OhterTest))
    return test_suite

if __name__ == "__main__":
    mySuite = suite()
    unittest.TextTestRunner().run(mySuite)

$ python3 suite.py
test_mytest_01 is called
.test_mytest_01 is called
.
———————————————————————-
Ran 2 tests in 0.000s

OK

addTestとして、unittest.TextTestRunner().run() でテストを実行する