P = eG
eは秘密鍵(256ビット)、Pは公開鍵(x, y座標256ビット)
署名アルゴリズムは楕円曲線署名アルゴリズム(Elliptic Curve Digital Signature Algorithm) ECDSA
eG = P
ランダムな256ビットの数字をkとして
kG = R
uG + vP = kG
u,vは0ではない値を署名者が選ぶ GPは既知の数値
-署名ハッシュ
任意のデータを固定サイズのデータにする決定関数
kはランダムな数値を用いて明かさない
ビットこんんはハッシュ関数はhash256(sha256を2回繰り返す)
s = (z + re)/k
### 署名のアルゴリズム
1.署名を(r, s)、署名対称のハッシュをz、署名者の公開鍵をP
2. u = z/s, v = r/s
3. uG + vP = R
4. 点Rのx座標がrと同じであれば署名は有効
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 # u = z/s v = r * s_inv % N # v = r /s print((u*G + v*point).x.num == r) # 点Rのx座標がrと同じであれば署名は有効
$ python3 app.py
True
point = S256Point( 0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c, 0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34) z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60 r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395 s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4 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) point = S256Point( 0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c, 0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34) z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6 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)
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)
def __rmul__(self, coefficient):
coef = coefficient % N
return super().__rmul__(coef)
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
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)
1. zが与えられており、eG=Pを満たすeが分かっている
2. ランダムにkを選ぶ
3. R = kGとrを算出
4. s = (z+re)/kを算出
5. 署名は(r,s)となる
publickeyは誰にも転送されなければならず、zは検証者が必ず知る必要がある
なんか凄いんだなBitcoinって…
