ビットコインに使われているk系楕円曲線暗号(係数a=0)を解読する
ρ法の高速化(超ρ法)に成功。解読平均反復回数が大幅削減した。
平均反復回数: ρ法:sqrt(πr/2), 超ρ法:sqrt(πr/1200)。
平均反復回数はρ法の1/25程度。計算時間は1/35程度。
計算時間が平均反復回数以上に削減した理由は、比較対象のρ法の
多倍長(逆元と法乗算)がgmpで、超ρ法の多倍長はCで自作のため。
自作多倍長はgmpの2倍弱高速で、追加処理を含めても高速である。
楕円曲線暗号(ECC:y^2=x^3+ax+b (mod p),rは位数)はk系(係数a=0)と
r系(乱数系でaはゼロでない)。secp256k1やsecp256r1が代表例。
x,yは座標値でx,y,a,bは整数。p,rは素数。
50ビット及び60ビットのECCを各500個作成し、比較評価した。
50ビットECCの解読：
平均反復回数: ρ法=4200万回、超ρ法=170万回
平均計算時間: ρ法=28秒、 超ρ法=0.85秒
60ビットECCの解読：
平均反復回数: ρ法=13.3億回、超ρ法=5500万回
平均計算時間: ρ法=890秒、 超ρ法=25秒
計算はC言語で4Ghzのパソコンを使用。
詳細はHP( https://ecc-256.com/ )の超ρ法を参照。
超ρ法のρ法に対する主な特長は下記。
1. ρステップ
Q=n×Bから整数nを求めるT=f(T)のρステップ
(1) T=f(T)にQを関与させない。TとBだけ関与。
(2) T=(Tx,Ty)でTyはp/2以下(Ty正と表示)にする。
(3) (2)の計算でループしたら2倍算
注) (2)(3)は112ビットECCの世界記録に使用されている。
2. k系(a=0)の利用
(1) T=(Tx,Ty)でTyが同じでTxが異なるものが3個存在する。
(2) 対象ECC固有の整数mが存在し、3個のTは1,m,m^2倍の関係。
(3) 3個内(Tyの正負を入れると6個)の変換は容易。
3. ρテーブル作成の工夫
(1) n個のρテーブル(ix=Tx (mod n))の作成法に工夫
(2) R=(Rx,Ry),S=(Sx,Sy),ix=Rx,Sx (mod n)とする。
T=S-Rでix番テーブル作成。
(3) R,Sを特徴点(ループ結合点)として、衝突点テーブルに登録
(4) R,Sの作成は2n又は3n個で止める。
4. その他
(1) T=f(T)にT=T+TB[ix]とT=T-TB[ix]のk系変換後の選択を追加
注) 1.の(2)と2.及び本項の適用で平均反復数はsqrt(πr/2)
からsqrt(πr/24)に減少する。
ただし、逆元計算は増えないが乗算が増える。
(2) 3で使用したR,S,TにAIを適用し、特徴点を作成し衝突点
テーブルに登録。
(3) 他数件