Category: Blockchain

### 署名検証
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は
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}

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

(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でも良かった。

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座標が異なる時)

    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)

a = 128
print(a.to_bytes(2, 'big'))
print(a.to_bytes(4, 'big'))

print(int.from_bytes(b'\x00\x80', 'big'))
print(int.from_bytes(b'\x00\x00\x00\x80', 'big'))