RSA暗号

　　　　2006/03/20 早稲田大学　後保範 (Waseda University, Ushiro Yasunori )
　　　　2007/04/01　東京工芸大学　後保範 (Tokyo Polytechnic University )

0. はじめに

　　最初にGNFSの理論を教えて頂いた立教大学木田祐司教授に謹んで感謝の意を表します。
　GNFSの説明と具体例は木田教授のHPを参考にさせて頂きました。

　現在、データ通信時に暗号化する方式として1024ビット(10進309桁)のRSA暗号が使用されている。
　RSA暗号の安全性は多数桁(1024ビット)の素因数分解が最大級のスーパーコンピュータを使用し
　ても数千年を必要とする困難性(事実上不可能)を利用している。
　多数桁因数分解は2005年5月にドイツのボン大学チームが10進200桁の世界記録 を達成している。
　日本では立教大学の木田教授のチームが2005年4月に10進176桁の記録 を達成している。
　両記録共に、GNFS(一般数体篩法)を使用している。
　　我々(東大金田研と早大後ゼミ)でも2005年4月から多数桁因数分解の世界記録に向けての研究
　を開始した。多数桁因数分解のアルゴリズムの詳細はあまり公開(特にGNFS)されていない。また、
　2006年2月にGNFSに代わる可能性のあるなアルゴリズムを考案した。そのため、それらの因数分解
　アルゴリズムを公開する。世界記録達成のためのプログラム作成を優先し、公開する資料はその
　準備のために調査、研究したメモを少し整備し順に掲載していく。
　考案したMBPSは2006年6月NAS2006(数値解析シンポジューム)で発表した。
　MBPSはMultiple Base Polynomial Sieve(多重基底多項式篩法)の略である。
　更に、2006年8月にMBPSを改良したMBPS2を考案した。
　世界記録達成のためのプログラム作成は本MBPS2を使用することに決定(2006/8)した。
　　プログラムはFORTRANとCのソースプログラムで公開する。但し、ここでは、計算原理を理解する
　目的のために作成しているので、実用版は東大金田研究室から公開するものを参照してください。

1. RSA暗号の仕組み

　　メッセージを暗号化して送信するための暗号には秘密鍵方式(共通鍵、対称鍵とも言う、DES等)と
　共通鍵方式(非対称鍵)方式がある。共通鍵方式のRSA暗号が一般に使用されている。
　RSA暗号は多数桁因数分解の困難さ(最大級のスーパーコンで分解に数千年必要)を利用している。
　(1) RSA暗号の方法
　　　この鍵の特色は、暗号化する人も復号化は知らないこと、及び認証に利用可能なことである。
　　暗号化するには公開鍵(e,n)が分かっていれば良い。一方復号化するには秘密鍵(d)が必要である。

2. 多数桁因数分解アルゴリズム(RSA暗号解読)

　(1) 主な因数分解アルゴリズム
　　　10進数十桁以上の合成数の因数分解には篩系アルゴリズムと ECMアルゴリズムがある。
　　篩(ふるい)系アルゴリズムは合成数の大きさに計算量が依存する。一方、ECMアルゴリズムは
　　分解後の因数の大きさに計算量が依存する。RSA暗号では合成数はほぼ同一の桁数の因数に
　　するため、分解は合成数の大きさに計算量が依存する、篩系アルゴリズムが高速になる。
　　篩系アルゴリズムは、10進約100桁まではMPQS(複数多項式2次篩法)が最も高速で、それ以上
　　の桁数ではGNFSが最も高速と言われている。その理由はMPQSが2次多項式を使用するため、
　　分解する関数の値が合成数(N)の平方根より大きくなるためである。
　　　これに対し、2006年2月に考案したPS(多項式篩法)は2～4次多項式に適用可能なため、分解
　　する関数の値がNの平方根より小さくなる。
　　　更に、2006年8月に考案したMBPS2(改訂多重基底多項式篩法)を使用すると、GNFSより大幅に
　　高速化が期待できる。
　(2) 各アルゴリズムの比較
　　　MBPS2,PS,GNFS,MPQSのアルゴリズム比較。

3. MPQS(複数多項式2次篩法、Multiple Polynomial QS)

　　現在、10進約100桁までは一番高速な解法と言われている。
　Nが分解対象数でZ²=A mod Nの関係を使用し、Aを素数で分解し、多く集めて2乗の形にする。
　Aを多く集めて、X²=Y² mod Nを作成すれば、(X-Y)×(X+Y)=0 mod Nと分解でる。X+YとX-Yがmod N
　でゼロでなければNはGCD(X+Y,N)及びGCD(X-Y,N)と因数分解できる。これをQS(2次篩法)と言う。
　MPQSはZ²=A mod Nからより小さい値のAがでるように工夫した複数の多項式を使用する。
　SIQS(自己初期化2次篩法、Self Initializition Quadratic Sieve)もMPQSと同様に複数の多項式を
　使用し、その多項式を自動作成する。
　SIQSは昨年MPQSの改善を検討していて方式を発見したが、既に利用されている方式と判明した。
　そのため、MPQSとSIQSを一緒にMPQSの項で記述する。

　(1) MPQSによる因数分解
　(2) MPQSによる因数分解具体例
　(3) MPQSによる因数分解プログラム

4. GNFS(一般数体篩法、General Number Field Sieve)

　　現在、10進約100桁以上で一番高速な解法と言われている。
　Nを分解対象数とするとき、3～7次多項式f(M)=0 mod Nを求めa+bX=A mod Nの関係を使用する。
　a+bXは素数で分解するが、Aは生成元での分解を仮定し、対応する素イデアルで分解する。
　分解した素イデアルを集めて2乗の形にすると、生成元(実際には求めていない)の2乗と一致する。
　但し、実際には単位生成元があるため、平方剰余を追加して2乗を作成する。
　イデアル側は平方根の計算をして、素数とイデアルからX²=Y² mod Nの
　関係を導き、合成数Nを因数分解する。

　(1) GNFSによる因数分解
　(2) GNFSによる因数分解具体例
　(3) GNFSによる因数分解プログラム

5. 多項式ふるい法(PS、Polynomial Sieve)

　　2006年1月に考案した、MBPS(多重基底多項式篩法)の前の解法。
　MBPSの方が高速な解法であるが、研究の進化過程を示すために掲載する。
　2次平方式の剰余による関数値の大きさ(分解数Nの平方根以下での篩ができない)に依存する
　MPQSの限界をPSは超えることができる特色をもつ。

　(1) PSによる因数分解
　(2) PSによる因数分解具体例
　(3) PSによる因数分解プログラム

6. 多重基底多項式篩法(MBPS、Multiple Base Polynomial Sieve)

　　2006年3月に考案した新解法。
　10進100桁以上でGNFSより高速になるかどうかは現在検討中。
　GNFSと結合して使用することも可能で、世界記録への挑戦は合体したものを使用する予定。
　MBPS単独で使用する場合をDBPS(Double Base Polynomial Sieve、2重基底多項式篩)と言う。
　GNFSと合体使用する場合をTBPS(Triple Base Polynomial Sieve、3重基底多項式篩)と言う。
　本MBPSの最大の特長は、篩に一次式基底を導入し、一次式基底による分解はGNFS(一般数体篩法)
　の素イデアルでの分解と異なり、自然に求まることである。また、左辺と右辺に現われる一次式は
　共に一次式基底で処理できる。更に、左辺側の一次式は同一なものが多量に出現する。この性質に
　より、多数桁数の因数分解でGNFSより高速化できると思われる。

　(1) MBPSによる因数分解
　(2) MBPSによる因数分解具体例
　(3) MBPSによる因数分解プログラム

7. 改訂多重基底多項式篩法(MBPS2、Multiple Base Polynomial Sieve 2nd)

　　2006年8月に考案したMBPSの改良版。
　本方式で世界記録に挑戦する。原理プログラムを作成し、現在は試作プログラムの作成中
　試作プログラムが完成すれば、ほぼ計算量の予測が可能であるが、本方式で数年以内に1024ビットの
　RSA暗号の解読は可能になると思われる。
　MBPS(多重基底多項式篩法)に対して、多項式f(x)を法とし、素イデアル基底で分解できるイデアルの積
　で作られるイデアルも素イデアル基底で分解できる、特長を利用した方法。
　この性質のため、f(x)=Ax²+Bx+Cに対して、Sx+T=(Ax+a)(x+b)-f(x)とすると、Ax+a及びx+b
　が素イデアル基底で分解できると、Sx+Tも素イデアル基底で分解できる。
　AM+a及びM+bは素数基底でも分解可能なものを選ぶ(逆にこれを分解する素数を素数基底に入れる)と
　(AM+a)(M+b)=SM+T (mod f(M)=N)で(AM+a)(M+b)は素数基底で分解でき、更にSx+Tは素イデアル基底で分解
　できる。即ち、ふるいで得られた等式となる。ここで、Nは分解対象数である。
　ここで、非常に嬉しいのはAx+aをm1個、x+bをm2個用いると、Sx+Tはm1・m2個作成される。そのため、
　ふるいで得られる等式の数が、素数基底と素イデアル基底の合計数を容易に超えることが可能となる。
　現在、f(x)は2次多項式及び3次多項式の適用が可能である。
　MBPS単独で使用する場合をDBPS2(Double Base Polynomial Sieve 2nd、改訂2重基底多項式篩)と言う。
　　この場合は、上記原理でSx+T=g(sx+t)としたとき、gの値が異なり、sx+tは同一なものが多数発生する
　　性質を利用する。
　GNFSと合体使用する場合をTBPS2(Triple Base Polynomial Sieve 2nd、改訂3重基底多項式篩)と言う。
　　この場合は、上記原理をそのまま使用する。このとき、自明解の増加を抑える工夫が必要である。
　(1) MBPS2による因数分解
　(2) MBPS2による因数分解具体例
　(3) MBPS2による因数分解プログラム

8. 0-1行列計算(従属行の取り出し)

　　MPSQ,GNFS及びPSのいずれの篩系アルゴリズムを使用しても、篩で求めた多くの候補のから
　2乗の形になる組み合わせを求めるために必要となる。
　10進200桁の世界記録では約6000万次元で超スパース(1行1000個以下の非ゼロ)の行列である。
　係数は1か0の行列で、従属になる行の組み合わせを複数(100組程度)求めればよい。
　ガウス消去法に基づく直接法とランチョス法に基づく反復法がある。
　ここでは、計算原理を理解するためのものを掲載する。
　実際には、0-1行列のため64ビット整数に64要素入れて排他和で計算でき、直接法はスパース性
　を利用したスパースソルバーで、ランチョス法もブロックランチョス法を使用する。
　大規模になるとブロックランチョス法が使用されているが、メモリの多いスーパーコンの利用
　を予定しているためスパースソルバーの適用する予定。
　10TBのメモリで数億次元の行列はスパースソルバーで分解可能と考えている。

　(1) 0-1行列による従属行の取り出し
　(2) 0-1行列の具体的計算例
　(3) 0-1行列計算プログラム

9. RSA暗号分解の世界記録

　(1) RSA暗号問題と世界記録
　(2) RSA暗号の分解対象数
　(3) RSA-576の世界記録(2進576桁、10進174桁、2003/12/5、GNFS)
　(4) 10進174桁の世界記録(10進174桁、2005/4/22、GNFS)
　(5) RSA-200の世界記録(10進200桁、2005/5/9、GNFS)
　(6) RSA-640の世界記録(2進640桁、10進193桁、2005/11/8、GNGS)