Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

ビットコインで使われている楕円暗号 secp256k1 をpythonで実装してopensslで確認してみる

ビットコインで使われている楕円暗号 secp256k1 をpythonで実装してみます。
なお、動作確認にはopensslを用います。

こちら

secp256k1仕様 - Pebble Coding

で示したように、計算効率を考えなければ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座標と2種類のうちどちらかかの情報だけでも表現できることが分かります。
これを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