「RSA暗号の素因数分解法における各種方法の処理時間比較」

中間発表用レポート

１． RSA暗号とは

２． 素因数判定

３． 素因数分解法

（研究では試行割算法・ρ法・楕円曲線法について調べます）

３，１． 試行割算法

３，２． ρ法（モンテカルロ法）

３，３． ｐ−１法

３，４． ｐ＋１法

３，５． 連分数法

３，６． 複数多項式二次ふるい法

３，７． 楕円曲線法

４．データ

４，１． 試行割算法

４，２． ρ法（モンテカルロ法）

４，３． 楕円曲線法

戻る

RSA暗号の素因数分解法における各種方法の処理時間比較

１．はじめに

　インターネットの普及により電子商取引が本格的な広がりを見せ始めた。しかしインターネットはハッカーにとって格好の犯罪の舞台となる。電子的に送金される決済データを横取りしたり、クレジットカード番号を盗み見したり、安全・確実に商品の売買や代金の振り込みをするには、暗号技術が必要となる。現在最も使われているRSA暗号の安全性について研究する。

２．問題設定

　素因数分解法（試行割り算法・ρ法・連分数法…etc）についてプログラムを作りそれぞれの処理時間を比較する。ただし、分解する数はあらかじめn=p*q(p.qは素数)と設定しておく。

３．問題の解法

３．１試行割り算法（1st）

　合成数nを２，３，４…と順に割って行く、必ず素数p.qは見つかるが一番時間がかかる。

３．２試行割り算法（２nd）

　合成数nを２，３，５，７…と順に割って行く、上記の方法より幾分処理時間は速くなるが時間はかかる。

４．得られた結果

試行割り算法

５．まとめ

　試行割り算法では合成数が2桁、分解式が100倍づつ増えていくと処理時間は約10倍となった。試行割り算（2nd）では割っていく数が1/2となるので処理時間は約半分となった。15桁で処理時間が約26時間となり17桁では約260時間（10日）程かかるのでこの辺りで止めることにした。

　今後の課題は他の素因数分解法についてプログラムを作り比較していきたいと思う。

１．秘密鍵と公開鍵の作成

　まず、暗号化を行う前に、予め以下の手順に従って秘密鍵と公開鍵を作成しておく必要があります。

1,２つの大きな素数ｐ、ｑを選択する。

2,ｎ＝ｐｑとφ(ｎ)＝（ｐ−１）（ｑ−１）を計算する。このｎを係数と呼ぶ。

3,gcd（ｅ,φ(ｎ)）＝１の関係をもつ乱数ｅ（公開指数）を選択する。この公開指数ｅと係数ｎが公開鍵（ｅ,ｎ）となる。

4,ｄｅ＝１ mod φ(ｎ)となるｄ（秘密指数）を計算する。この秘密指数ｄと係数ｎが秘密鍵（ｄ,ｎ）となる。

5,公開鍵（ｅ,ｎ）を公開する。ｐ、 ｑ、ｄは誰にも知られないようにしておく。