RSA暗号

    2006/03/20 早稲田大学 後 保範 (Waseda University, Ushiro Yasunori )
    2013/06/18 8年間捜し求めていた解法を見つけ、更新

0. はじめに

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

 現在、データ通信時に暗号化する方式として1024ビット(10進309桁)のRSA暗号が使用されている。
 RSA暗号の安全性は多数桁の素因数分解の困難性に依存している。
 コンピュータの進歩は著しく、現暗号(1024ビット)は最大級スパコンで1年程度になった。
 このため、2019年までに2048ビットに移行するように、世界的に勧告されている。
 もし、GNFS(1次式-多項式)の千倍以上の高速化がなされると、GPGPUで個人でも解読可能になる。
 現在、その可能性が否定できない状況で、考案アルゴリズムの公開は混乱を避けるため中止。
 アルゴリズムの検証、評価とプログラム開発はネット接続無しのPCに全面移動した。

1. トピックス

 (1) ふるい系はPCに比較し、GPUで約100倍、地球シミュレータ(1ノード)で800倍高速
 (2) 地球シミュレータでRSA-1024の解読は2千数百ノード・年と推定。(2013/1/30)
 (3) 8年間探し求めていた解読アルゴリズムを発見した可能性が高い。(2013/1/30)
 (4) より高効率のアルゴリズム(GNFSと発想が逆)を発見した可能性が高い。(2013/2/23)
 (5) 開発PCをネットから切り離し、関係ファイルを暗号化した。(2013/3/23)
 (6) ふるい処理は超高速化が可能。行列サイズの大幅縮小方法が課題。(2013/4/3)
 (7) 方式検討完。原型,実証,PC本番,GPU本番プログラムと進む。年内目標。(2013/4/5)
 (8) 行列サイズの縮小化も順調。線形計算はI/O量を考慮し、スパースダイレクト。(2013/4/20)
(9) 初の壁。ふるい高速化で自明解が増加。悪さする少量データの削除に苦戦中(2013/6/18)
   必要なふるいデータは高速に求まる。根気よく、悪さするデータの特性を分析する。

2. RSA暗号の仕組み

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

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

 (1) 主な因数分解アルゴリズム
   10進数十桁以上の合成数の因数分解には篩(ふるい)系アルゴリズムと ECMアルゴリズムがある。
  篩(ふるい)系アルゴリズムは合成数の大きさに計算量が依存する。一方、ECMアルゴリズムは
  分解後の因数の大きさに計算量が依存する。RSA暗号では合成数はほぼ同一の桁数の因数に
  するため、分解は合成数の大きさに計算量が依存する、篩系アルゴリズムが高速になる。
  篩系アルゴリズムは、10進約100桁まではMPQS(複数多項式2次篩法)が最も高速で、それ以上
  の桁数ではGNFSが最も高速と言われている。その理由はMPQSが2次多項式を使用するため、
  分解する関数の値が合成数(N)の平方根より大きくなるためである。

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

  現在、10進約100桁までは一番高速な解法と言われている。
 Nが分解対象数でZ2=A mod Nの関係を使用し、Aを素数で分解し、多く集めて2乗の形にする。
 Aを多く集めて、X2=Y2 (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はZ2=A mod Nからより小さい値のAがでるように工夫した複数の多項式を使用する。
 SIQS(自己初期化2次篩法、Self Initializition Quadratic Sieve)もMPQSと同様に複数の多項式を
 使用し、その多項式を自動作成する。
 SIQSは2005年にMPQSの改善を検討していて方式を発見したが、既に利用されている方式と判明した。
 そのため、MPQSとSIQSを一緒にMPQSの項で記述する。

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

5. GNFS(一般数体篩法、General Number Field Sieve):現在最速解法

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

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

5. 多項式ふるい法(PS、Polynomial Sieve):遅く実用にならない

  2006年1月に考案した、MBPS(多重基底多項式篩法)の前の解法。
 研究の進化過程を示すために削除しないで残しておく。(2013/2/13)
 2次平方式の剰余による関数値の大きさ(分解数Nの平方根以下での篩ができない)に依存する
 
 (1) PSによる因数分解
 (2) PSによる因数分解具体例
 (3) PSによる因数分解プログラム

6. 多重基底多項式篩法(MBPS、Multiple Base Polynomial Sieve):遅く実用にならない

  2006年3月に考案した新解法。遅く実用にならない。(2008/1/30)
 アルゴリズム考案の過程を示すので、削除しないで残しておく。(2013/2/13)
 MBPS単独で使用する場合をDBPS(Double Base Polynomial Sieve、2重基底多項式篩)と言う。
 GNFSと合体使用する場合をTBPS(Triple Base Polynomial Sieve、3重基底多項式篩)と言う。
 本MBPSの最大の特長は、篩に一次式基底を導入し、一次式基底による分解はGNFS(一般数体篩法)
 の素イデアルでの分解と異なり、自然に求まることである。また、左辺と右辺に現われる一次式は
 共に一次式基底で処理できる。更に、左辺側の一次式は同一なものが多量に出現する。
 
 (1) MBPSによる因数分解
 (2) MBPSによる因数分解具体例
 (3) MBPSによる因数分解プログラム

7. 改訂多重基底多項式篩法(MBPS2、Multiple Base Polynomial Sieve 2nd):遅く実用にならない

  2006年8月に考案したMBPSの改良版。遅く実用にならない(2008/1/30)
 アルゴリズム考案の過程を示すので、削除しないで残しておく。(2013/2/13)
 MBPS(多重基底多項式篩法)に対して、多項式f(x)を法とし、素イデアル基底で分解できるイデアルの積
 で作られるイデアルも素イデアル基底で分解できる、特長を利用した方法。
 この性質のため、f(x)=Ax2+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進232桁の世界記録では約2億次元で超スパース(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)
 (7) RSA-704の世界記録(2進704桁、10進212桁、2012/07/01、GNGS(1次-6次式))
 (8) RSA-768の世界記録(2進768桁、10進232桁、2010/12/12、GNGS(1次-6次式))