| ２２８． ＮＴＴ、２３２ケタ整数の素因数分解に成功－世界記録を更新 現在使用の３０９ケタはあと１０年は大丈夫！ ２０１０年 １月１１日掲載 ２０１４年 ４月１７日再掲 ２３２ケタ整数の素因数分解に、３年の年月と３００台のコンピュータを用いて成功したというニュースである。スーパーコンピュータもそうであるが、高機能のコンピュータを並列に用いて数値解析する手法は強力である。 一時、日本でも、家庭のコンピュータの空き時間を束ねて利用することにより、数学的な問題を解こうとの流れがあった。 さて、この２３２ケタの整数は途方もなく大きな数字である。１億で９ケタ、１兆で１３ケタ、１京で１７ケタ・・・・。とても追いつかない。 今暗号に実際に使われている桁数は、ＷｉｋipediaのＲＳＡ暗号では次のように記載されている。すでに、本ニュースで報道された、２００９年１２月１２日の２３２ケタの素因数分解の成功も収録されている。 引用 RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号(Cipher)とデジタル署名(Digital signature)を実現できる方式として最初に公開されたものである。 RSA暗号解読コンテスト RSA社は「RSA Factoring Challenge」を1991年から2007年まで実施し、最新の計算 Ｗｉｋｉｐｅｄｉａに記載 整数の桁数 1991.04.01 RSA-100 (330ビット) １００ 1992.04.14 RSA-110 (364ビット) １１０ 1993.06.09 RSA-120 (397ビット) １２０ 1994.04 RSA-129 (426ビット) １２９ 1996.04.10 RSA-130 (430ビット) １３０ 1999.02.02 RSA-140 (463ビット) １４０ 2004 RSA-150 (496ビット) １５０ 1999.08.22 RSA-155 (512ビット) １５５ 2003.04.01 RSA-160 (530ビット) １６０ 2009.12.29 RSA-170 (563ビット) １７０ 2003.12.03 RSA-576 (576ビット,10進174桁） １７４ yet RSA-180 (596ビット) １８０ yet RSA-190 (629ビット) １９０ 2005.11.02 RSA-640 (640ビット) １９３ 2005.05.09 RSA-200 (663ビット,10進200桁) ２００ yet RSA-210 (696ビット,10進210桁) ２１０ yet RSA-704 (704ビット) ２１２ 2009.12.12 RSA-768 (768ビット) ２３２ 以下は未踏 RSA-896 ２７０ RSA-1024 ３０９ RSA-1536 ４６３ RSA-2048 ６１７ この結果を図にすると、２０２２年ごろまでは現在使用の１０２４ビット（３０９ケタ）暗号が使えそうである。２０２２年にこの桁数の暗号を解くのに、今回と同じく３年の月日を要するようであるならば、もう少しこの桁数の暗号は延命することになる。
さて、予断ではあるが、本日の日付、２０１０年１月１１日、すなわち２０１１０１１１は３で割れて６７０００３７となるが、次に何で割れるかを探そうとすると一苦労である。８桁の整数でも、コンピュータなしに素因数分解することは難しい。 答えは、３×１０１×６６３３７の素因数に分解されるです。 ａｓａｈｉ．ｃｏｍより引用 ＮＴＴ、２３２ケタ整数の素因数分解に成功－世界記録を更新 2010年1月11日 ＮＴＴは、世界最長となる２３２ケタの整数を素因数分解することに成功した。 ２進数で７６８ビットに当たり、従来の世界記録６６３ビット（２００ケタ）を更新した。 現在、インターネット上の電子署名方式の９割以上を占める公開鍵暗号「ＲＳＡ暗号」は、１０２４ビットの鍵長が使われている。同ビットも今後約１０年で、素因数分解による解読の危険性が高まったという。 スイス連邦工科大学やドイツのボン大学など海外４機関と協力し、一般数体ふるい法と呼ばれる高速な計算手法を使い、３００台のパソコンによる並列計算処理で約３年かけて解いた。 現在ネット上の決済や電子署名に使う公開鍵暗号は、ビット数の増加で計算量が膨大に増える素因数分解の難しさを安全性の基準にしている。 鍵長は将来、２０４８ビット以上が必要になるとみている。 CNET Japan １月８日より部分引用 NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号 解読に一歩近づくか 素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。 これまでの世界記録を大きく上回る700ビットを超える素因数分解が可能になったが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も達成できる可能性があることを示唆するものと注目される。その延長線上として、RSA暗号より強度が高く、より効率的な暗号技術を利用する必要性も高まるだろうと、NTTは見ている。 RSA暗号に使われるような、大きな2つの素数の積から構成される合成数の素因数分解法は「数体篩（ふるい）法」が用いられる。現在、RSA暗号に使われる合成数には「一般数体篩法」と呼ばれるやり方が高速とされている。今回の世界記録更新にも、この一般数体篩法を活用している。 一般数体篩法は、「多項式選択」「篩」「filtering」「線形代数」「平方根」――という5つのステップから構成される。このうちの篩と線形代数が最も計算量を要するステップとされる。各ステップで選択すべきパラメータが多数存在し、パラメータの選択で計算量が大きく変化するが、有効な選択方法は あまり解明されていないという。今回の共同研究では、このパラメータを適切に選択することで、高速に計算することに成功したとしている。 ＮＴＴ Ｎｅｗｓ Ｒｅｌｅａｓｅ １月８日 部分引用 公開鍵暗号の安全性の根拠である「素因数分解問題」 で世界記録を更新 ～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に設置された計算機を用い、数時間で以 下の解が得ら れました。 123018668453011775513049495838496272077285356959533479219732245215172 640050726365751874520219978646938995647494277406384592519255732630345 3731548268 5079170261221429134616704292143116022212404792747377940806 65351419597459856902143413 ＝ 334780716989568987860441698482126908177047949837137685689124313889828 83793878002287614711652531743087737814467999489 X 367460436667995904282446337996279526322791581643430876426760322838157 39666 511279233373417143396810270092798736308917 暗号に関する歴史や文献など 素因数分解に続く関連情報として 因数分解に関連して、暗号に関する文献類を列挙いたしました。２年前のまとめと少し古くなりますが、参考までです。 CNET Japan １月８日より引用 NTTなど、「素因数分解問題」で世界記録更新--公開鍵 暗号解読に一歩近づくか 素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。 ＮＴＴ Ｎｅｗｓ Ｒｅｌｅａｓｅ １月８日 部分引用 公開鍵暗号の安全性の根拠である「素因数分解問題」 で世界記録を更新 ～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】暗号がわかる本 神保雅一監修 （２００６年９月、オーム社） 【5】マンガでわかる暗号 三谷政昭、佐藤伸一著 （２００７年４月、オーム社） 【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
|
