シリアライズとは、複数の要素を一列に並べる操作や処理のこと。単にシリアライズといった場合には、プログラムの実行状態や複雑なデータ構造などを一つの文字列やバイト列で表現する「直列化」を指すことが多い。
メッセージ署名のコーディング
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}
Pythonでzfill
s = ‘1234’
print(s.zfill(10))
$ python3 test.py
0000001234
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)}