ビットコインで使われている楕円暗号 secp256k1 をpythonで実装してみます。
なお、動作確認にはopensslを用います。
こちら
で示したように、計算効率を考えなければpythonで実装するのは割と容易です。
#!/usr/bin/env python # # secp256k1 # http://www.secg.org/SEC2-Ver-1.0.pdf # # q is prime q = 2**256 - 2**32 - 977 # l is prime l = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 def expmod(b,e,m): if e == 0: return 1 t = expmod(b,e/2,m)**2 % m if e & 1: t = (t*b) % m return t def inv(x): return expmod(x,q-2,q) 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) 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 == 0 and y1 == 0: return Q if x2 == 0 and y2 == 0: return P if x1 == x2: if (y1 + y2) % q == 0: return [0, 0] else: return double_pt(P) lm = (y1-y2)*inv(x1-x2) 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 [0, 0] 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 Bx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 By = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 B = [Bx, By] B2 = double_pt(B) print "q = %x" % q print "Bx = %x" % Bx print "By = %x" % By print "l = %x" % l if isoncurve(B): print "B is on curve" else: assert False, "B is not on curve!" T = scalarmult(B, l) print "T = (%x, %x)" % (T[0], T[1]) privkey=0x00948dda57c9964c62703b1d54f40008e351da1cc0e0a562eac4c3f7dd369c5feb pubkey=scalarmult(B, privkey) print "calc_pubkey = (%x, %x)" % (pubkey[0], pubkey[1])
secp256k1では、ランダムな32バイトが秘密鍵となり、秘密鍵をLittleEndianで正の整数として、ベースポイントを秘密鍵だけスカラー倍した点が公開鍵になります。
公開鍵は、x座標が32バイト、y座標が32バイトとなるので、64バイトの長さになりますが、これを、uncompress形式と呼びます。
楕円曲線が決まっているので、x座標が決まれば、y座標は2種類の値しか取らないので、x座標と２種類のうちどちらかかの情報だけでも表現できることが分かります。
これをcompress形式と呼びます。法素数は奇数と決まっているので、y座標のどちらかが偶数ならもう片方は奇数です。通常は偶数の方を取ることが多いようです。
compress形式でy座標が偶数の場合は04ではなく02となります。
opensslで鍵ペアを生成し、表示してみます。
$ openssl ecparam -name secp256k1 -genkey -out ec-priv.pem
$ openssl ec -in ec-priv.pem -text -noout
Private-Key: (256 bit)
priv:
00:94:8d:da:57:c9:96:4c:62:70:3b:1d:54:f4:00:
08:e3:51:da:1c:c0:e0:a5:62:ea:c4:c3:f7:dd:36:
9c:5f:eb
pub:
04:39:52:76:4a:8d:90:53:26:38:53:2f:cb:7b:a0:
b6:15:18:1e:f2:d2:2b:7d:64:a6:d3:5e:66:59:00:
e2:42:ad:66:1b:4d:da:0a:d3:ac:24:80:ff:0f:b2:
35:c6:22:02:43:76:4a:42:76:16:2d:36:26:b6:64:
f4:78:c7:58:9e
ASN1 OID: secp256k1
priv:部分は32バイトあることが分かります。
pub:の先頭の04はuncompress形式であることを示しています。
続く32バイトがx座標、その後に続く32バイトがy座標を表しています。
pythonのコードではこのprivの部分をprivkeyという変数にセットしています。
privkey=0x00948dda57c9964c62703b1d54f40008e351da1cc0e0a562eac4c3f7dd369c5feb
スクリプトを実行するとこのようになります。
$ ./secp256k1.py q = fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f Bx = 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 By = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 l = fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 B is on curve T = (0, 0) calc_pubkey = (3952764a8d90532638532fcb7ba0b615181ef2d22b7d64a6d35e665900e242ad, 661b4dda0ad3ac2480ff0fb235c6220243764a4276162d3626b664f478c7589e)
最後のx座標とy座標が opensslコマンドで生成した鍵ペアの公開鍵の値に一致していることが分かります。
参考までにopensslのElliptic Curve実装のリンクを上げておきます。
https://github.com/openssl/openssl/tree/master/crypto/ec
openssl では多くの楕円曲線暗号に対応しています。
$ openssl ecparam -list_curves
secp112r1 : SECG/WTLS curve over a 112 bit prime field
secp112r2 : SECG curve over a 112 bit prime field
secp128r1 : SECG curve over a 128 bit prime field
secp128r2 : SECG curve over a 128 bit prime field
secp160k1 : SECG curve over a 160 bit prime field
secp160r1 : SECG curve over a 160 bit prime field
secp160r2 : SECG/WTLS curve over a 160 bit prime field
secp192k1 : SECG curve over a 192 bit prime field
secp224k1 : SECG curve over a 224 bit prime field
secp224r1 : NIST/SECG curve over a 224 bit prime field
secp256k1 : SECG curve over a 256 bit prime field
secp384r1 : NIST/SECG curve over a 384 bit prime field
secp521r1 : NIST/SECG curve over a 521 bit prime field
prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field
prime192v2: X9.62 curve over a 192 bit prime field
prime192v3: X9.62 curve over a 192 bit prime field
prime239v1: X9.62 curve over a 239 bit prime field
prime239v2: X9.62 curve over a 239 bit prime field
prime239v3: X9.62 curve over a 239 bit prime field
prime256v1: X9.62/SECG curve over a 256 bit prime field
sect113r1 : SECG curve over a 113 bit binary field
sect113r2 : SECG curve over a 113 bit binary field
sect131r1 : SECG/WTLS curve over a 131 bit binary field
sect131r2 : SECG curve over a 131 bit binary field
sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field
sect163r1 : SECG curve over a 163 bit binary field
sect163r2 : NIST/SECG curve over a 163 bit binary field
sect193r1 : SECG curve over a 193 bit binary field
sect193r2 : SECG curve over a 193 bit binary field
sect233k1 : NIST/SECG/WTLS curve over a 233 bit binary field
sect233r1 : NIST/SECG/WTLS curve over a 233 bit binary field
sect239k1 : SECG curve over a 239 bit binary field
sect283k1 : NIST/SECG curve over a 283 bit binary field
sect283r1 : NIST/SECG curve over a 283 bit binary field
sect409k1 : NIST/SECG curve over a 409 bit binary field
sect409r1 : NIST/SECG curve over a 409 bit binary field
sect571k1 : NIST/SECG curve over a 571 bit binary field
sect571r1 : NIST/SECG curve over a 571 bit binary field
c2pnb163v1: X9.62 curve over a 163 bit binary field
c2pnb163v2: X9.62 curve over a 163 bit binary field
c2pnb163v3: X9.62 curve over a 163 bit binary field
c2pnb176v1: X9.62 curve over a 176 bit binary field
c2tnb191v1: X9.62 curve over a 191 bit binary field
c2tnb191v2: X9.62 curve over a 191 bit binary field
c2tnb191v3: X9.62 curve over a 191 bit binary field
c2pnb208w1: X9.62 curve over a 208 bit binary field
c2tnb239v1: X9.62 curve over a 239 bit binary field
c2tnb239v2: X9.62 curve over a 239 bit binary field
c2tnb239v3: X9.62 curve over a 239 bit binary field
c2pnb272w1: X9.62 curve over a 272 bit binary field
c2pnb304w1: X9.62 curve over a 304 bit binary field
c2tnb359v1: X9.62 curve over a 359 bit binary field
c2pnb368w1: X9.62 curve over a 368 bit binary field
c2tnb431r1: X9.62 curve over a 431 bit binary field
wap-wsg-idm-ecid-wtls1: WTLS curve over a 113 bit binary field
wap-wsg-idm-ecid-wtls3: NIST/SECG/WTLS curve over a 163 bit binary field
wap-wsg-idm-ecid-wtls4: SECG curve over a 113 bit binary field
wap-wsg-idm-ecid-wtls5: X9.62 curve over a 163 bit binary field
wap-wsg-idm-ecid-wtls6: SECG/WTLS curve over a 112 bit prime field
wap-wsg-idm-ecid-wtls7: SECG/WTLS curve over a 160 bit prime field
wap-wsg-idm-ecid-wtls8: WTLS curve over a 112 bit prime field
wap-wsg-idm-ecid-wtls9: WTLS curve over a 160 bit prime field
wap-wsg-idm-ecid-wtls10: NIST/SECG/WTLS curve over a 233 bit binary field
wap-wsg-idm-ecid-wtls11: NIST/SECG/WTLS curve over a 233 bit binary field
wap-wsg-idm-ecid-wtls12: WTLS curvs over a 224 bit prime field
Oakley-EC2N-3:
IPSec/IKE/Oakley curve #3 over a 155 bit binary field.
Not suitable for ECDSA.
Questionable extension field!
Oakley-EC2N-4:
IPSec/IKE/Oakley curve #4 over a 185 bit binary field.
Not suitable for ECDSA.
Questionable extension field!
ちなみにed25519の実装はこちらにありました。
https://github.com/openssl/openssl/blob/master/crypto/ec/curve25519.c
