228. NTT、232ケタ整数の素因数分解に成功−世界記録を更新 現在使用の309ケタはあと10年は大丈夫!

 2010年 1月11日掲載  2014年 4月17日再掲


232ケタ整数の素因数分解に、3年の年月と300台のコンピュータを用いて成功したというニュースである。スーパーコンピュータもそうであるが、高機能のコンピュータを並列に用いて数値解析する手法は強力である。一時、日本でも、家庭のコンピュータの空き時間を束ねて利用することにより、数学的な問題を解こうとの流れがあった。

さて、この232ケタの整数は途方もなく大きな数字である。1億で9ケタ、1兆で13ケタ、1京で17ケタ・・・・。とても追いつかない。

今暗号に実際に使われている桁数は、WikipediaのRSA暗号では次のように記載されている。すでに、本ニュースで報道された、2009年12月12日の232ケタの素因数分解の成功も収録されている。


引用

RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号(Cipher)とデジタル署名(Digital signature)を実現できる方式として最初に公開されたものである。

RSA暗号解読コンテスト
RSA社は「RSA Factoring Challenge」を1991年から2007年まで実施し、最新の計算機環境でどの程度のビット数の整数が素因数分解可能かを調べた。

  Wikipediaに記載                   整数の桁数

  1991.04.01 RSA-100 (330ビット)            100
  1992.04.14 RSA-110 (364ビット)            110
  1993.06.09 RSA-120 (397ビット)            120
  1994.04 RSA-129 (426ビット)              129
  1996.04.10 RSA-130 (430ビット)            130
  1999.02.02 RSA-140 (463ビット)            140
  2004 RSA-150 (496ビット)                150
  1999.08.22 RSA-155 (512ビット)            155
  2003.04.01 RSA-160 (530ビット)            160
  2009.12.29 RSA-170 (563ビット)            170
  2003.12.03 RSA-576 (576ビット,10進174桁)     174
  yet RSA-180 (596ビット)                 180
  yet RSA-190 (629ビット)                 190
  2005.11.02 RSA-640 (640ビット)            193
  2005.05.09 RSA-200 (663ビット,10進200桁)     200
  yet RSA-210 (696ビット,10進210桁)          210
  yet RSA-704 (704ビット)                 212
  2009.12.12 RSA-768 (768ビット)            232

 以下は未踏

  RSA-896                          270
  RSA-1024                          309
  RSA-1536                          463
  RSA-2048                          617

この結果を図にすると、2022年ごろまでは現在使用の1024ビット(309ケタ)暗号が使えそうである。2022年にこの桁数の暗号を解くのに、今回と同じく3年の月日を要するようであるならば、もう少しこの桁数の暗号は延命することになる。



さて、予断ではあるが、本日の日付、2010年1月11日、すなわち20110111は3で割れて6700037となるが、次に何で割れるかを探そうとすると一苦労である。8桁の整数でも、コンピュータなしに素因数分解することは難しい。

答えは、3×101×66337の素因数に分解されるです。



asahi.comより引用

NTT、232ケタ整数の素因数分解に成功−世界記録を更新  2010年1月11日

 NTTは、世界最長となる232ケタの整数を素因数分解することに成功した。2進数で768ビットに当たり、従来の世界記録663ビット(200ケタ)を更新した。現在、インターネット上の電子署名方式の9割以上を占める公開鍵暗号「RSA暗号」は、1024ビットの鍵長が使われている。同ビットも今後約10年で、素因数分解による解読の危険性が高まったという。

 スイス連邦工科大学やドイツのボン大学など海外4機関と協力し、一般数体ふるい法と呼ばれる高速な計算手法を使い、300台のパソコンによる並列計算処理で約3年かけて解いた。

 現在ネット上の決済や電子署名に使う公開鍵暗号は、ビット数の増加で計算量が膨大に増える素因数分解の難しさを安全性の基準にしている。

 鍵長は将来、2048ビット以上が必要になるとみている。




CNET Japan 1月8日より部分引用

NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか

 素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。

 これまでの世界記録を大きく上回る700ビットを超える素因数分解が可能になったが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も達成できる可能性があることを示唆するものと注目される。その延長線上として、RSA暗号より強度が高く、より効率的な暗号技術を利用する必要性も高まるだろうと、NTTは見ている。

 RSA暗号に使われるような、大きな2つの素数の積から構成される合成数の素因数分解法は「数体篩(ふるい)法」が用いられる。現在、RSA暗号に使われる合成数には「一般数体篩法」と呼ばれるやり方が高速とされている。今回の世界記録更新にも、この一般数体篩法を活用している。

 一般数体篩法は、「多項式選択」「篩」「filtering」「線形代数」「平方根」――という5つのステップから構成される。このうちの篩と線形代数が最も計算量を要するステップとされる。各ステップで選択すべきパラメータが多数存在し、パラメータの選択で計算量が大きく変化するが、有効な選択方法はあまり解明されていないという。今回の共同研究では、このパラメータを適切に選択することで、高速に計算することに成功したとしている。




NTT News Release 1月8日 部分引用

公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新
〜768ビット合成数を一般数体篩法にて完全分解に成功〜

<研究の内容>
 今回の素因数分解は、巨大な合成数に対して現段階で最も高速な解法として知られている一般数体篩法により実現しました。一般数体篩法は、多項式選択、篩(ふるい)、filtering、線形代数、平方根の5つのステップからなります。このうち、篩と線形代数が最も計算量を要するステップです。各ステップにおいて、選択すべきパラメータは多数あります。このパラメータの選択によって計算量が大きく変化しますが、その有効な選択方法については多くの場合についてはまだ解明されていません。今回の共同研究ではこのパラメータを適切に選択することにより、高速に計算することに成功しました。以下、今回の分解におけるそれぞれのステップの詳細を示します。

(1)多項式選択
 このステップは残りの計算量を決める重要なステップではありますが、どの程度の時間をかけどのように多項式を探せばよいのかについては現在のところ有効な手段は見つかっていません。今回は、2005年夏、ボン大学においてOpteron※5 2.2GHzをおよそ20年かけたのと同程度の計算量で探索して得られた多項式を選択しました。その後、2007年はじめにEPFLで、さらによい多項式の探索を試みましたが、Opteron 2.2GHz換算で20年かけたのと同程度の計算量を費やしても、見つかりませんでした。

(2)篩(ふるい)処理
 このステップは全体の計算量の大半を占めますが、比較的容易に分散計算可能であることから多数の参加組織により並列に計算を行いました。今回の計算では利用可能計算機のメモリ容量に応じいくつかのパラメータを準備しました。2007年夏から開始し、2009年4月に終了しました。殆んどの処理は2008年春から2009年3月にかけて行なわれました。篩処理は主にNTT研究所、EPFL、ボン大、INRIA、CWIにある多種多様のPCやクラスタを用いました。全体ではおよそOpteron 2.2GHz換算で1500年かけたのと同程度の計算量を要しました。

(3)filtering
 このステップを実行することにより、この次の線形代数ステップを桁違いに高速に実行することができるようになります。EPFLにある10TBのハードディスクを備えた8コア計算機とクラスタを利用しました。さまざまなパラメータで何度かやりなおしたことにより不必要になった計算を含みますがCore2※6 2.66GHz換算で6カ月以下の計算量でした。

(4)線形代数(連立方程式の解法)
 このステップは理論的には最も計算量を要するステップのひとつであり、分散計算※7が困難です。今回は、少数のクラスタを利用し、またそれぞれのクラスタの速度や空き時間が異なっていても効率的に計算できる手法を開発・利用しました。NTT研究所及びEPFLのクラスタ、またINRIAはフランスにあるALADDIN-G5K※8を効率的に用い、filteringで生成された疎行列からなる連立方程式を解きました。Opteron 2.2GHz換算でおよそ155年の計算量を要しました。その結果、分解に利用可能な解が得られました。

(5)平方根(代数的数の平方根の計算及び最小公約数の計算)
 このステップは数学的には高度な理論を用いますが計算量はさほど要しません。EPFLに設置された計算機を用い、数時間で以下の解が得られました。
12301866845301177551304949583849627207728535695953347921973224521517264005 07263657518745202199786469389956474942774063845925192557326303453731548268 50791702612214291346167042921431160222124047927473779408066535141959745985
6902143413
=
33478071698956898786044169848212690817704794983713768568912431388982883793 878002287614711652531743087737814467999489
X
36746043666799590428244633799627952632279158164343087642676032283815739666 511279233373417143396810270092798736308917



暗号に関する歴史や文献など 素因数分解に続く関連情報として

因数分解に関連して、暗号に関する文献類を列挙いたしました。2年前のまとめと少し古くなりますが、参考までです。


CNET Japan 1月8日より引用

NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか

 素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。



NTT News Release 1月8日 部分引用

公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新
〜768ビット合成数を一般数体篩法にて完全分解に成功〜



【1】暗号年表
http://contest2007.thinkquest.jp/tqj2007/90242/nenpyou.html

【2】ドイツ軍が第二次世界大戦で使った「エニグマ」シミュレータ
http://gigazine.net/index.php?/news/comments/20060911_enigma/

【3】SSL(Wikipedia)
http://ja.wikipedia.org/wiki/Secure_Socket_Layer

【4】暗号がわかる本 神保雅一監修 (2006年9月、オーム社)

【5】マンガでわかる暗号 三谷政昭、佐藤伸一著 (2007年4月、オーム社)

【6】暗号講座
http://akademeia.info/index.php?%B0%C5%B9%E6%B9%D6%BA%C2#x3502a8f

【7】SHA-1によるハッシュ変換の実施
http://fictionlife.com/tools/sha1/

【8】MD5(Wikipedia)
http://ja.wikipedia.org/wiki/MD5

【9】MD5からSHA-1へのアルゴリズムの変更理由
http://www.verisign.co.jp/server/help/faq/110095/index.html

【10】SSLによるサーバ認証とその問題点     リンク元の情報削除
http://www.ecom.jp/qecom/seika/cardwave/cw9909.htm

【11】フィッシング詐欺(Wikipedia)
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%B3%E3%82%B0_%28%E8%A9%90%E6%AC%BA%29

【12】重要性を増す情報セキュリティ        リンク元の情報削除
http://www.jipdec.jp/chosa/hakusho/press2006.pdf

【13】ワンクリック詐欺の被害累計156億円!
http://www.rbbtoday.com/news/20061129/36341.html

【14】「正規の証明書を持っているサイトも信用するな」、フィッシング研究者が警告
http://itpro.nikkeibp.co.jp/article/NEWS/20060210/229014/

【15】量子コンピュータが拓く未来社会
http://www.nedo.go.jp/kankobutsu/mirai/ft041119-1.pdf

【16】暗号(Wikipedia)
http://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7



文書リストに戻る ホームに戻る