ECDSA(secp256k1)での署名と検証をpythonで行ってみます。
まずコードです。
ちなみにpython3です。
#!/usr/bin/env python # # secp256k1 # http://www.secg.org/SEC2-Ver-1.0.pdf # import sys import hashlib sys.setrecursionlimit(1500) b = 256 # q is prime q = 2**256 - 2**32 - 977 # l (order of group) is prime l = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # no depend q,l def expmod(v,e,m): if e == 0: return 1 t = expmod(v,e//2,m)**2 % m if e & 1: t = (t*v) % m return t # no depend q,l def inv(x, m): return expmod(x,m-2,m) def double_pt(P): x = P[0] y = P[1] if y == 0: return [0, 0] nu = 3*expmod(x,2,q)*inv(2*y,q) x3 = expmod(nu,2,q)-2*x y3 = nu*(x-x3)-y return [x3 % q, y3 % q] def add_pt(P, Q): x1 = P[0] y1 = P[1] x2 = Q[0] y2 = Q[1] if x1 == -1 and y1 == -1: return Q if x2 == -1 and y2 == -1: return P if x1 == x2: if (y1 + y2) % q == 0: return [-1, -1] else: return double_pt(P) lm = (y1-y2)*inv(x1-x2, q) x3 = expmod(lm,2,q)-(x1+x2) y3 = lm*(x1-x3)-y1 return [x3 % q, y3 % q] def scalarmult(P, e): if e == 0: return [-1, -1] Q = scalarmult(P, e//2) Q = add_pt(Q, Q) if e & 1: Q = add_pt(Q, P) return Q def isoncurve(P): x = P[0] y = P[1] return (y**2 - x**3 - 7) % q == 0 Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 G = [Gx, Gy] # big endian def bit(h, i): return (h[i//8] >> (7-(i%8))) & 1 # 32 byte array to big endian integer def decodeint(s): assert(len(s) == 32) return sum(2**(b-1-i) * bit(s,i) for i in range(0,b)) print("q = %x" % q) print("Gx = %x" % Gx) print("Gy = %x" % Gy) print("l = %x,%d" % (l, l)) if isoncurve(G): print("G is on curve") else: assert False, "G is not on curve!" T = scalarmult(G, l) print("T = (%x, %x)" % (T[0], T[1]) ) sk = 3 PK = scalarmult(G, sk) print("sk = %x" % sk) print("pk = (%x, %x)" % (PK[0], PK[1])) # string to byte array msg = str("0000").encode('utf-8') # -- sign # STEP1 nonce = 2 print("nonce = %d" % nonce) R = scalarmult(G, nonce) r = R[0] % l # STEP2 check r is not 0 # not implement # STEP3 msg_digest = hashlib.sha256(msg).digest() print("msg_digest:" + msg_digest.hex()) msg_i = decodeint(msg_digest) print("msg_i:" + str(msg_i)) s = (inv(nonce,l) * (msg_i + r * sk)) % l # STEP4 check s is not 0 # not implement print("r = %d" % r) print("r = 0x%x" % r) print("s = %d" % s) print("s = 0x%x" % s) # -- verify si = inv(s,l) u1 = (msg_i * si) % l u2 = (r * si) % l V = add_pt(scalarmult(G, u1), scalarmult(PK, u2)) print("V = (%d, %d)" % (V[0], V[1])) result = (((V[0] - r) % l) == 0) print("result %d" % result)
rubyの場合でやった
ECDSA(secp256k1)での署名と検証をrubyで行う(ecdsaライブラリ使用) - Pebble Coding
のと同じですが、ここではsecp256k1計算を関数として実装してしています。
q = fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f Gx = 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 Gy = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 l = fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,115792089237316195423570985008687907852837564279074904382605163141518161494337 G is on curve T = (-1, -1) sk = 3 pk = (f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9, 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672) nonce = 2 msg_digest:9af15b336e6a9619928537df30b2e6a2376569fcf9d7e773eccede65606529a0 msg_i:70082618269937651554445935544647643695199256361993126870837541449102805772704 r = 89565891926547004231252920425935692360644145829622209833684329913297188986597 r = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 s = 111494102406131234412316855906883406462147064785892425994642684023738105619079 s = 0xf67f6cf81a19873091aa7c9578fa2e96490e9bfc78ae7e9798004e8252c06287 V = (89565891926547004231252920425935692360644145829622209833684329913297188986597, 12158399299693830322967808612713398636155367887041628176798871954788371653930)