プログラムの全体はこちら。
https://github.com/anang0g0/ecc/blob/master/cm.rb
楕円曲線の離散対数問題は量子計算機に弱いので、もうオワコンなのだが意外なところで復活の兆しを見せている。
それは同種写像と呼ばれているものと関係がある。同種写像なんていうといかにも難しそうに聞こえるが、同じj不変量を持つ楕円曲線同士を対応付ける写像のことである。
点の数が同じというだけで同種写像が存在するのであればかなり楽ではある。
直感的には点の個数が同じ方がイメージしやすいのだが私の認識が間違っているようだ。
単に点の数が同じであれば何でもいいのか詳しく検討していない。ウィキによると既に素体上ではなく二次拡大を使っているようなので、単なる素体では実現できないのかもしれない。その場合はCM法を二次拡大に対応できるように改造する必要がある。
この暗号系は既存のリソースが活かせるので、楕円曲線暗号をやっていた人がPQCに乗り換えるとしたら一番の近道なのではないかと思う。ここで言う超特異というのは、楕円曲線のj-不変量と呼ばれているもので、この値が0になる楕円曲線を超特異とよぶ。
たしかそう書いてあったような気がするが、自信がない。
もしそうなら、j不変量が０になる虚数乗法をもつ楕円曲線は判別式D=3の場合に限られる。
そこで何が必要かといえば、同じ数の点を持つ楕円曲線をどうやって見つけるかだ。
その方法の一つがCM法と言われている方法だ。
ここに上げる実装では素数個の点をもつ楕円曲線に限られているが、素数を固定した上で楕円曲線の係数をかえて並列計算してやれば同じ数の点を持つ曲線が見つかるかもしれない。
CMというのは虚数乗法と言われる数学からの物体X（失礼）であり、暗号をやっていく上で何が出てくるか予測の出来ない手強い理論の一つである。ちょっと参考文献を探してみたのだが適当なのがネットにないので、楕円曲線暗号というベタなタイトルの書籍を紹介する。
以下にサンプルソースを上げておく。
同種写像暗号に使えるかどうかはまだ研究途上なのでよくわからないが、オリジナルのアプリに組み込むための独自の楕円曲線を生成するのに使えるのではないだろうか。
def alp()
h = [7, 8, 12, 11, 19, 27, 43, 67, 163]
#h=[1,2,3,7,11,19,43,67,163]
jj = [3375, -8000, -54000, -32768, -884736, -12288000, -884736000, -147197952000, -262537412640768000]
# set a half of bit size random number
ii = 0b1010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
for i in 0..1000000
for j in 0..8
for u in 0..6500
uu = (ii * ii) + h[j] * @uint16_prime[u] * @uint16_prime[u]
@V = -1
if (uu % 4 == 0)
oo = uu / 4
mm = oo + 1 - ii
k = 0
cond = 0
if (oo % 2 == 1 && 4 * oo - ii * ii == h[j] * @uint16_prime[u] * @uint16_prime[u])
k = k + 1
while (@uint16_prime[k] != 65521)
# cout << k << " ";
if (oo % @uint16_prime[k] == 0 || mm % @uint16_prime[k] == 0)
cond = 0
break
end
if (oo % @uint16_prime[k] != 0 && mm % @uint16_prime[k] != 0)
cond = 1
end
k = k + 1
end
if (cond == 1)
if (fr(oo) == 1 && fr(mm) == 1)
print "\n"
# print "t=", ii, "\n";
# print "j=", jj[j], "\n"
# print "p=", oo, "\n"
# print "m=", mm, "\n"
m2 = 2 * oo - mm
print "m2=", m2, "\n"
k = (jj[j]) * inv(1728 - jj[j], oo) % oo; a = 3 * k % oo; b = 2 * k % oo
# print "a=", a, "\n"
# print "b=", b, "\n"
# k=jj[j]*inv(1728+jj[j],oo)%O;
if (k < 0)
while (k < 0)
k = k + oo
end
end
@CRV_a = 3 * k % oo
@CRV_b = 2 * k % oo
pgcm_G_y = PC(@CRV_b, oo)
@CRV_n = mm
@CRV_p = oo
if (pgcm_G_y > 0)
pgcm_G_x = 0
@G_x = 0
@G_y = pgcm_G_y
v = mktable(@G_x, @G_y)
if (v != -1)
print "a=", @CRV_a, "\n"
print "b=", @CRV_b, "\n"
print "n=", mm, "\n"
print "p=", oo, "\n"
ellip(mm)
print "v=", @V, "\n"
if (@V == 0)
bit(mm); print "-bit prime\n"; w()
print "ママ！ここにいたのね！\n"
end
if (@V == -1)
p = inv(@CRV_a, @CRV_p) * (-3) % @CRV_p
print (@CRV_p - @CRV_a * p) % @CRV_p, "\n"
print p, "\n"
c = PC(p, @CRV_p)
if (c != -1)
# print "E' twist!\n"
#print "a'=",@CRV_a=(@CRV_a*c*c%@CRV_p)-@CRV_p,"\n"
#print "b'=",@CRV_b=(@CRV_b*c**3)%@CRV_p,"\n"
#y=PC(@CRV_b,@CRV_p)
#if(y != -1)
# mktable(0,y)
# ellip(oo+1+ii)
# if(@V==0)
# bit(m2); print "-bit_m2 prime\n"; w();
# print "(･∀･)ｲｲ!!\n";
# exit();
# end
# end
end
end
#end
end
end
end
end
end
end
end
end
ii = ii + 1
end
end
このプログラムは上記の本にあったことを参考に、自分のアレンジで書いたものだ。
オリジナルの方法ではまず素数を決めて、その上でコルネッキアという式を解いて高い類数の曲線を計算する方法を取る。
しかし高次の多項式を解くのは巨大整数なので遅くなる。その代わり、いろんな素数を試して簡単に曲線を生成したいと思ってこの方法にした。だから類数は1の場合に限られる。この方法では、素数をスライドさせて使い捨てにする。素数判定自体は簡単にできるはずなので、総当りで素数を試していけばいつかは素数位数の点を持つ楕円曲線に当たるだろうというナイーブな方法である。こんな方法でもいろいろ楕円曲線が見つかるのだから不思議である。
そして実験的にわかることは、素数位数の楕円曲線は判別式が163の楕円曲線でよく見つかり、一見するとその存在が偏っているかのように見えることだ。これはこの方式のバグなのかどうか検討が必要である。
この実装では便宜的に巨大整数を扱うためにrubyで書いてあるが、C++で書いたほうがOpenMPとかを使って並列計算できるし更に速くなる可能性がある。また、ツイストと呼ばれる曲線を取りこぼしているのが残念である。今後修正するかもしれない。
同種写像暗号はまだ出来たばかりのものなので、かつての楕円曲線がそうだったように今後の研究の結果使えないものになる可能性もある。今後どのようなアルゴリズムや攻撃が考案されるかが気になるところである。