有限体における点の加算

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() でテストを実行する

Pythonでunittest

unittestモジュールをimportし、unittest.TestCaseクラスを継承したテストクラスを作成する。その際、テストメソッドはtestという単語で始まる必要がある。

import uittest
from my_module import my_function

class MyTest(unittest.TestCase):
    def test_my_function(self):
        result = my_function(2)
        self.assertEqual(result, 4)

if __name__ == '__main__':
    unittest.main()

具体例

import unittest

def add(a, b):
    return a + b

class TestAddFunction(unittest.TestCase):

    def test_add_integer(self):
        result = add(2, 3)
        self.assertEqual(result, 5)

    def test_add_floats(self):
        result = add(2.5, 3.5)
        self.assertAlmostEqual(result, 6.0, places=2)

    def test_add_strings(self):
        result = add("Hello, ", "world!")
        self.assertEqual(result, "Hello, world!")

if __name__ == '__main__':
    unittest.main()

$ python3 test.py
…
———————————————————————-
Ran 3 tests in 0.000s

OK

return a + b + 1 とすると、
$ python3 test.py
FFE
======================================================================
ERROR: test_add_strings (__main__.TestAddFunction)
———————————————————————-
Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/test.py”, line 17, in test_add_strings
result = add(“Hello, “, “world!”)
File “/home/vagrant/dev/blockchain/test.py”, line 4, in add
return a + b + 1
TypeError: can only concatenate str (not “int”) to str

======================================================================
FAIL: test_add_floats (__main__.TestAddFunction)
———————————————————————-
Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/test.py”, line 14, in test_add_floats
self.assertAlmostEqual(result, 6.0, places=2)
AssertionError: 7.0 != 6.0 within 2 places (1.0 difference)

======================================================================
FAIL: test_add_integer (__main__.TestAddFunction)
———————————————————————-
Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/test.py”, line 10, in test_add_integer
self.assertEqual(result, 5)
AssertionError: 6 != 5

———————————————————————-
Ran 3 tests in 0.000s

FAILED (failures=2, errors=1)

Test Classの中で、setUp, tearDownを入れると、テストの実行前後でそれぞれ実行される。

class TestAddFunction(unittest.TestCase):

    def setUp(self):
        print("setUp() called")

    def test_add_integer(self):
        result = add(2, 3)
        self.assertEqual(result, 5)

    def test_add_floats(self):
        result = add(2.5, 3.5)
        self.assertAlmostEqual(result, 6.0, places=2)

    def test_add_strings(self):
        result = add("Hello, ", "world!")
        self.assertEqual(result, "Hello, world!")

    def tearDown(self):
        print("tearDown() called")

有限体で点の組み合わせが曲線上にあるかの確認

d = {192:105, 17:56, 200:119, 1:193, 42:99}
prime = 223
for x, y in d.items():
    a = (x**3 + 7)%prime
    b = (y**2)%prime
    if a == b:
        print('{}, {} is on the curve'.format(x, y))
    else:
        print('sorry {}, {} is not on the curve'.format(x, y))

$ python3 test.py
192, 105 is on the curve
17, 56 is on the curve
sorry 200, 119 is not on the curve
1, 193 is on the curve
sorry 42, 99 is not on the curve

こうとも書ける

from ecc import FieldElement, Point

a = FieldElement(num=0, prime=223)
b = FieldElement(num=7, prime=223)
x = FieldElement(num=192, prime=223)
y = FieldElement(num=105, prime=223)
p1 = Point(x, y, a, b)
print(p1)

楕円曲線

y^2 = x^3 + ax + b

-> yが2乗となっているため、x軸に対して対象となる。
-> ビットコインは y^2 = x^3 + 7 で表されている(secp256k1)

2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 -1を 有限体上で定義された楕円曲線

曲線 y^2 = x^3 + ax + bをclassで表現すると

class Point:

    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y
        if self.y**2 != self.x**3 + a * x + b:
            raise ValueError('({}, {}) is not on the curve'.format(x, y))
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b
        
from ecc import Point

p1 = Point(-1, -1, 5, 7)
p1 = Point(-1, -2, 5, 7)

楕円曲線上にあるかの判定

d = {2:4, -1:-1, 18:77, 5:7}
for x, y in d.items():
    try:
        Point(x, y, 5, 7)
        print(x, y)
    except ValueError:
        pass

$ python3 main.py
-1 -1
18 77

### 点の加算
2つの点を演算して、同じ曲線上に3つ目の点を得ることを加算と呼ぶ
垂直、接線の場合は、直線が2点で交差する

無限遠点とは、限りなく遠いところ（無限遠）にある点のこと
点Aに換算すると点Aになる　A + I = A
Pythonでは無限遠点をNoneで表現する
from ecc import Point

p1 = Point(-1, -1, 5, 7)
p2 = Point(-1, 1, 5, 7)
inf = Point(None, None, 5, 7)

print(p1 + inf)
print(inf + p2)
print(p1 + p2)

__init__を修正してaddをoverloadする

class Point:

    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y
        if self.x is None and self.y is None:
            return
        if self.y**2 != self.x**3 + a * x + b:
            raise ValueError('({}, {}) is not on the curve'.format(x, y))
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b

    def __ne__(self, other):
        return not (self == other)

    def __add__(self, other):
        if self.a != other.a or self.b != other.b:
            raise TypeError('Point {}, {} are not on the same curve'.format(self, other))
        
        if self.x is None:
            return other
        if other.x is None:
            return self

x1 != x2 の時の加算コーディング

        if self.x != other.x:
            s = (other.y - self.y) / (other.x - self.x)
            x = s**2 - self.x - other.x
            y = s(self.x - x) - self.y
            return self.__class__(x, y, self.a, self.b)

P1 = P2(x座標が同じでy座標が異なる時)

Pythonで有限体

ecc.py

class FieldElement:
    
    def __init__(self, num, prime):
        if num >= prime or num < 0:
            error = 'Num {} not in field range 0 to {}'.format(num, prime - 1)
            raise ValueError(error)
        self.num = num
        self.prime = prime

    def __repr__(self):
        return 'FieldElement_{}({})'.format(self.prime, self.num)

    def __eq__(self, other):
        if other is None:
            return False
        return self.num == other.num and self.prime == other.prime

main.py

from ecc import FieldElement
a = FieldElement(7, 13)
b = FieldElement(6, 13)
print(a==b)
print(a==a)

pythonのpow

pow(self.nom, exponent, self.prime)で計算できる

prime = 7
for i in range(1, prime):
    a = pow(i, prime-1, 6)
    print(a)

for prime in (7, 11, 17 , 31):
    for i in range(1, prime):
        a = pow(i, prime-1, 6)
        print(a)

for prime in (7, 11, 17 , 31):
    print([pow(i, prime-1, prime) for i in range(1, prime)])

$ python3 test.py
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

3/24 のF31は

prime = 31
a = 3 * pow(24, prime-2)
print(a % prime)

print(pow(17, -3, prime))

print(pow(4, -4, prime)*11 % prime)

Pythonのtype()と__class__

type() は、オブジェクトのタイプまたはクラスを見つけるために使用できる事前定義された関数
__name__ は、基本的にそれが使用されている現在のモジュールの名前を与える特別な組み込み変数

class Num:
    def __init__(self, num):
        self.num = num

x = Num(1)
print(type(x).__name__)

$ python3 test.py
Num

__class__ プロパティを使用して、オブジェクトのクラスまたはタイプを検索することもできる。これは基本的に、オブジェクトが作成されたクラスを指す。

class Num:
    def __init__(self, num):
        self.num = num

x = Num(1)
print(x.__class__)
print(x.__class__.__name__)

$ python3 test.py

Num

有限体 加算

    def __add__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot add two numbers in different Fields')
        num = (self.num + other.num) % self.prime
        return self.__class__(num, self.prime)