Pebble Coding

プログラマーの作業メモ

素体Fp上の楕円曲線 y^2 = x^3 + D の有理点の数

 {y}^{2} = {x}^{3} + Dの素体 F_p上の有理点の数を調べます。

素数pを3で割って2余る場合は、有理点の数は無限遠点を含み、#E= p + 1 であることが知られています。

 {y}^{2} = {x}^{3} + 7の場合の、有理点の数をpythonで調べた結果がこちらです。

p, p mod 3, #E
2, 2, 3 = (p+1)
3, 0,4
5,2,6
7,1,8
11,2,12 = (p+1)
13,1,7
17,2,18 = (p+1)
19,1,12
23,2,24 = (p+1)
29,2,30 = (p+1)
31,1,21
37,1,39
41,2,42 = (p+1)
43,1,31
47,2,48 = (p+1)

確かにp mod 3 = 2 の場合は成り立っていることが分かります。
この曲線はsecp256k1で使われている曲線ですが、secp256k1の素数
q = {2}^{256} - {2}^{32} - 977 はどうなっているでしょうか?
q mod 3 = 1
残念ながら余りが1なので、単純な式では出てきません。

pを3で割って1余る場合の有理点の数を算出する計算式は知られていますが、6乗根と、2次体を使った複雑なものです。

有理点の数の計算はこちらのpythonコードを使いました。

pebble8888.hatenablog.com

参考: Kenneth Ireland Michael Rosen / A Classical Introduction to Modern Number Theory Springer-Verlag 1990

素体Fpの乗法群

素体 F_pは体であり、元は{0, 1, ..., p-1}のp個あります。
素体という時、pは素数です。
体なので、加法と乗法について閉じているわけですが、乗法演算の部分のみを取り出した群のことを、
素体 F_pの乗法群と呼び F^*_pと書きます。
この乗法群 F^*_pには加法の単位元0は含まれないことに注意します。
この乗法群 F^*_pの元は{1, 2, ..., p-1}のp-1個となります。
巡回群の定義は、全ての元が一つの元のみを使った演算で全ての元を作れることですが、
この乗法群 F^*_p巡回群です。
群の位数が素数なら、その群は巡回群であることが知られています。

任意の元gを一つとったときに、 { g, {g}^{2}, {g}^{3}, ..., {g}^{p-1} }で全ての元を渡るということです。
例えば  F^*_5の場合、g=3をとると、
 {3}^{1} = 3
 {3}^{2} = 9 = 4
 {3}^{3} = 27 = 2
 {3}^{4} = 81 = 1
となり右辺の{3, 4, 2, 1}が全ての元になっています。
また、この最後のp-1乗すると1になるのはフェルマーの小定理として知られています。

 F^*_pにおける写像 f(x) = {x}^{3}を考えます。

この写像はどのようなものかpythonで調べて見ます。
関連があるため、乗法群の位数(元の数) p-1 を3で割った余りも同時に調べます。

#!/usr/bin/env python

ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]  

for p in ps: 
    print("p {0}".format(p))
    print("(p-1)%3 {0}".format((p-1) % 3)) 
    l = []
    for x in range(1, p): 
        a = (x**3) % p 
        l.append(a)
    print(l)
    print(sorted(l))
    print("")
p 2
(p-1)%3 1
[1]
[1]

p 3
(p-1)%3 2
[1, 2]
[1, 2]

p 5
(p-1)%3 1
[1, 3, 2, 4]
[1, 2, 3, 4]

p 7
(p-1)%3 0
[1, 1, 6, 1, 6, 6]
[1, 1, 1, 6, 6, 6]

p 11
(p-1)%3 1
[1, 8, 5, 9, 4, 7, 2, 6, 3, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

p 13
(p-1)%3 0
[1, 8, 1, 12, 8, 8, 5, 5, 1, 12, 5, 12]
[1, 1, 1, 5, 5, 5, 8, 8, 8, 12, 12, 12]

p 17
(p-1)%3 1
[1, 8, 10, 13, 6, 12, 3, 2, 15, 14, 5, 11, 4, 7, 9, 16]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

p 19
(p-1)%3 0
[1, 8, 8, 7, 11, 7, 1, 18, 7, 12, 1, 18, 12, 8, 12, 11, 11, 18]
[1, 1, 1, 7, 7, 7, 8, 8, 8, 11, 11, 11, 12, 12, 12, 18, 18, 18]

p 23
(p-1)%3 1
[1, 8, 4, 18, 10, 9, 21, 6, 16, 11, 20, 3, 12, 7, 17, 2, 14, 13, 5, 19, 15, 22]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]

p 29
(p-1)%3 1
[1, 8, 27, 6, 9, 13, 24, 19, 4, 14, 26, 17, 22, 18, 11, 7, 12, 3, 15, 25, 10, 5, 16, 20, 23, 2, 21, 28]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]

p 31
(p-1)%3 0
[1, 8, 27, 2, 1, 30, 2, 16, 16, 8, 29, 23, 27, 16, 27, 4, 15, 4, 8, 2, 23, 15, 15, 29, 1, 30, 29, 4, 23, 30]
[1, 1, 1, 2, 2, 2, 4, 4, 4, 8, 8, 8, 15, 15, 15, 16, 16, 16, 23, 23, 23, 27, 27, 27, 29, 29, 29, 30, 30, 30]

p 37
(p-1)%3 0
[1, 8, 27, 27, 14, 31, 10, 31, 26, 1, 36, 26, 14, 6, 8, 26, 29, 23, 14, 8, 11, 29, 31, 23, 11, 1, 36, 11, 6, 27, 6, 23, 10, 10, 29, 36]
[1, 1, 1, 6, 6, 6, 8, 8, 8, 10, 10, 10, 11, 11, 11, 14, 14, 14, 23, 23, 23, 26, 26, 26, 27, 27, 27, 29, 29, 29, 31, 31, 31, 36, 36, 36]

p 41
(p-1)%3 1
[1, 8, 27, 23, 2, 11, 15, 20, 32, 16, 19, 6, 24, 38, 13, 37, 34, 10, 12, 5, 36, 29, 31, 7, 4, 28, 3, 17, 35, 22, 25, 9, 21, 26, 30, 39, 18, 14, 33, 40]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]

p 43
(p-1)%3 0
[1, 8, 27, 21, 39, 1, 42, 39, 41, 11, 41, 8, 4, 35, 21, 11, 11, 27, 22, 2, 16, 27, 41, 21, 16, 32, 32, 22, 8, 39, 35, 2, 32, 2, 4, 1, 42, 4, 22, 16, 35, 42]
[1, 1, 1, 2, 2, 2, 4, 4, 4, 8, 8, 8, 11, 11, 11, 16, 16, 16, 21, 21, 21, 22, 22, 22, 27, 27, 27, 32, 32, 32, 35, 35, 35, 39, 39, 39, 41, 41, 41, 42, 42, 42]

p 47
(p-1)%3 1
[1, 8, 27, 17, 31, 28, 14, 42, 24, 13, 15, 36, 35, 18, 38, 7, 25, 4, 44, 10, 2, 26, 41, 6, 21, 45, 37, 3, 43, 22, 40, 9, 29, 12, 11, 32, 34, 23, 5, 33, 19, 16, 30, 20, 39, 46]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]

p 53
(p-1)%3 1
[1, 8, 27, 11, 19, 4, 25, 35, 40, 46, 6, 32, 24, 41, 36, 15, 37, 2, 22, 50, 39, 48, 30, 44, 43, 33, 20, 10, 9, 23, 5, 14, 3, 31, 51, 16, 38, 17, 12, 29, 21, 47, 7, 13, 18, 28, 49, 34, 42, 26, 45, 52]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]

実験結果を見ると、p-1を3で割ったあまりが0でない時は、全ての元が出てくるようです。
これを、写像  f(x)= {x}^{3} が自己同型写像であるといいます。
 F^*_p の元を 群F^*_p の元に移していますし、変換前と変換後の元が1対1対応しているからです。

この現象は次の群論の定理とも関係があります。
定理 Gを群、aをGの位数nの元とし、kを整数、d=gcd(k, n)とする。このとき、 {a}^{k}の位数は \frac {n} {d}である。

k=3,nを3で割った余りが0でない場合は、d=1となるので、 {a}^{3}の位数はnとなります。

群論における写像

群論における写像の定義メモ。
準同型写像、同型写像、自己同型写像
写像というのはプログラムで考えると、引数を一つ入力として持ち、戻り値を一つ返す関数だとイメージすることができますが、 要するに関数f(x)のことです。

準同型写像

関数f(x)が f(x)f(y) = f(xy)を満たすものを準同型写像と言います。
ここでは群が乗法演算により群になっている場合を考えているのでこのような式になっていますが、
加法演算により群になっている場合はf(x) + f(y) = f(x+y)と考えてください。
準同型写像は性質がいいのです。
どのようにいいかというと、群Gの元を群Hの元に移す写像f(x)が準同型写像で、さらに、
群Hの元を群Iの元に移す写像g(x)も準同型写像だとします。
この2つの関数を連続して行った写像 f(g(x))は群Gの元を群Iに移すと考えます。
するとf(x)f(y) = f(xy)、g(x)g(y) = g(xy)なので、以下のように式変形できます。
g(f(xy)) = g(f(x)f(y)) = g(f(x))g(f(y)) これはg(f(x))の関数が準同型写像であることを示しています。

準同型写像の場合は、群Gの2つの異なる元が群Iの同じ元に移されることがあるので、
逆関数の性質が不定となり、性質がよくありません。
もっと性質が良い写像が同型写像です。

同型写像

関数f(x)が準同型であることに加えて、写像全単射であるものを同型写像と言います。
全単射とは、群Gの全ての元が群Hに移される時、群Gの元が異なれば、移された群Hの元が異なり、 群G上の全ての元と群Hの全ての元が1対1対応しているとイメージしてください。

自己同型写像

群Gを群G自身へ移す同型写像のことを自己同型写像と言います。

Bitcoin フルノードを立てるのに必要なもの

Bitcoinルノードを立てるのに必要なものをメモしておきます。

最低限必要なスペック

  • 最新バージョンのWindows, Mac OS X, Linuxが動作するするハードウェア
  • 145GB の空きディスクスペース
  • 2GBメモリ
  • 400Kbpsのアップロードスピードの通信回線
  • 高いアップロードレートリミットを持つ、無制限の回線
    ルノードは1ヶ月で200GBのアップロードを行い、20GBのダウンロードを行う。
  • 1日に6時間稼働し続けられること。

参考:
Running A Full Node - Bitcoin

Objective-Cとswift3 で NSView* を void* に変換してまたNSView*に戻す

NSView をvoidに変換するのはObjective-Cですが、これはキャストするだけです。

- (void)convert:(NSView*)view {
    void* ptr = (void*)view;
}

void*はswiftではUnsafeMutableRawPointerと表現されます。

func convert(p:UnsafeMutablePointer) {
    let view:NSView = Unmanaged<NSView>.fromOpaque(p).takeUnretainedValue()
}

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

ビットコインで使われている楕円暗号 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コマンドで生成した鍵ペアの公開鍵の値に一致していることが分かります。

楕円関数の加法公式

楕円関数  {y}^{2} = {x}^{3} + a {x} + b の形式の加法公式をメモしておきます。

アフィン座標での加算公式

1) PとQが同一点の場合。
 x_3 = {\nu}^{2} - a - x_1 - x_2
 y_3 = {\nu} ( x_1 - x_3 ) - y_1
 {\nu} = \frac {3 {x_1}^{2} + 2 a x_1 + b} {2 y_1}

2)  x_1 \ne x_2の場合
 x_3 = {\lambda}^{2} - a - x_1 - x_2
 y_3 = {\lambda} (x_1 - x_3) - y_1
 {\lambda} = \frac {y_1 - y_2} {x_1 - x_2}

これをアフィン座標(affine coordinate)と呼びます。

素体  F_p 上の割り算は掛け算に比べて10倍〜50倍くらいの計算量なので、
割り算の回数を減らすように別の座標系を取ることが多いです。

点(x,y)の代わりに3つの値(X,Y,Z)を使い、2点(X', Y', Z'),(X, Y, Z)の間に、
X'=cX, Y'=cY, Z'=cZの関係がある場合、この2点を同一視する座標系を射影座標(projective coordinates)と呼びます。
(X, Y, Z)と(X/Z, Y/Z, 1)は同じ点ということになりますが、これを(x,y)と同一と考えます。

同じようにして、 X'= {c}^{2} X, Y'= {c}^{3} Y, Z'= {c} Zの関係を使って同一視した座標系をJacobian射影座標(Jacobian projective coordinates)と呼びます。

加法公式を射影座標に変換してみると、次のようになることが簡単な計算でわかります。
1) PとQが同一点の場合
 x_3 = {\nu}^{2} - a - x_1 - x_2
 y_3 = {\nu} ( x_1 - x_3 ) - y_1
 {\nu} = \frac {3 {x_1}^{2} + 2 a x_1 + b} {2 y_1}

2)  x_1 \ne x_2の場合
 x_3 = {\lambda}^{2} - a - x_1 - x_2
 y_3 = {\lambda} (x_1 - x_3) - y_1
 {\lambda} = \frac {y_1 - y_2} {x_1 - x_2}

Projective座標系での加算公式

式は単純に x_1 = X_1 / Z_1, y_1 = Y_1 / Z_1を代入すれば、得られます。
割り算を全てZ座標に集めることによって、割り算の数をProjective座標とアフィン座標の変換時のみにすることができます。

1) PとQが同一点の場合
 w = z {Z_1}^{2} + 3 {X_1}^{2}
 s = Y_1 Z_1
 B = X_1 Y_1 a
 h = {w}^{2} - 8B

 X_3 \to 2 h s
 Y_3 \to w ( 4B - h ) - 8 {Y_1}^{2} {s}^{2}
 Z_3 \to 8 {s}^{3}

2)  x_1 \ne x_2の場合
 u = Y_2 Z_1 - Y_1 Z_2
 v = X_2 Z_1 - X_1 Z_2
 A = {u}^{2} Z_1 Z_2 - {v}^{3} - 2 {v}^2 X_1 Z_2

 X_3 \to v A
 Y_3 \to u ( {v}^{2} X_1 Z_2 - A) - {v}^{3} Y_1 Z_2
 Z_3 \to {v}^{3} Z_1 Z_2

参考:

https://written.4403.biz/source/ecc_rev30r.pdf

https://link.springer.com/content/pdf/10.1007%2F3-540-49649-1_6.pdf