なんだか不可思議なRSA暗号

なんとなくは分かるが・・・難しいなぁ・・安全性の証明なのは分かるけど
もっと簡単にできないのかｗ

NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか
http://japan.cnet.com/news/sec/story/0,2000056024,20406400,00.htm
NTTは1月8日、グループのNTT情報流通プラットフォーム研究所（NTT研究所）が海外の研究機関と共同で、公開鍵暗号の安全性の根拠となる「素因数分解問題」で世界記録を更新したことを発表した。
これまでの世界記録は663ビット、10進200ケタだが、新しい世界記録は768ビット、10進232ケタで100ビット以上上回っている。独ボン大学、仏の国立情報学自動制御研究所（INRIA）、オランダの国立情報工学・数学研究所（CWI）と共同で研究した。

素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。
これまでの世界記録を大きく上回る700ビットを超える素因数分解が可能になったが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も達成できる可能性があることを示唆するものと注目される。その延長線上として、RSA暗号より強度が高く、より効率的な暗号技術を利用する必要性も高まるだろうと、NTTは見ている。
NTT研究所は、暗号技術全般の安全性を継続的に評価していくとともに、次世代暗号として、楕円曲線上の演算規則を利用した「楕円曲線暗号」の普及に務めていくとしている。

素因数分解問題は、合成数を素数の積に分解するというもの。
小さな合成数に対しては、短時間で素因数分解できるが、大きな数の場合、現実的な時間内に計算できることは困難といわれている。

ようは暗号化して解読するのが時間的に難しくなるって話かな？

素因数分解
http://ja.wikipedia.org/wiki/%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3
いみがわからないよ・・orz
素因数分解アルゴリズムにたいして楕円曲線法 (ECM, Elliptic curve method)を使用しているということかな・・・とおもったら違うし・・

サルでも分かるRSA暗号
http://www.maitou.gr.jp/rsa/rsa01.php
解読法と素数
http://www.maitou.gr.jp/rsa/rsa14.php
基本的にこのニュースは安全性を保証したって話ではあるのはわかるのだけど・・
その証明方法が良くわかりませんｗ

ニュースソースならわかるかも・・・・

公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新～768ビット合成数を一般数体篩法にて完全分解に成功～
http://www.ntt.co.jp/news/news10/1001/100108a.html
＜研究の背景及び意義＞
　インターネットの本格的な普及に伴い、ネット決済やインターネット銀行などネットワークを活用した便利なサービスが身近な存在となり、インターネット上における機密情報のやり取りが大幅に増加しました。そのため、ネットワークを利用した社会経済活動において、情報セキュリティを十分に確保することが不可欠な状況にあります。
　NTT情報流通プラットフォーム研究所（以下、ＮＴＴ研究所）では、情報の安全性を確保するため、新たな暗号技術を研究するとともに既存暗号の安全性の検証に取り組んできました。
　現在公開鍵暗号※3として広く用いられているRSA暗号※4は素因数分解の難しさを安全性の根拠としているため、素因数分解可能なビット数の検証はRSA暗号の安全性、強度の有効性をより精密に予測する上で極めて重要なものです。
　今回700ビットを大幅に超える素因数分解を達成しましたが、これは近い将来RSA暗号で広く使われている1024ビットの素因数分解も達成される可能性があることを示唆しており、より強度が高く効率的な暗号技術を利用する必要性が高まっています。

128byteコード(1024bit)を使った形になるか・・確かに其処まで逝くと解読は難しいだろうなぁ・・
まあ、コンピューターの性能次第ではあろうけど一般的に解読できる類のものではない。（時間的に）
量子コンピューターとかそういった類のものが実現できればまた別の話ではある・・

＜研究の内容＞
　今回の素因数分解は、巨大な合成数に対して現段階で最も高速な解法として知られている一般数体篩法により実現しました。一般数体篩法は、多項式選択、篩（ふるい）、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

まあ、平方根だからいろいろ解読方法はあるんだろうｗ

＜今後の展望＞
　情報通信社会の進展に伴って、情報セキュリティを確保するために暗号技術の重要性はますます高まります。
　NTT研究所は暗号技術全般の安全性を継続的に評価していくとともに、次世代暗号として楕円曲線上の演算規則を利用した新しい公開鍵暗号方式「楕円曲線暗号※9」の普及にも努めていきたいと考えています。
　今後も、暗号理論から社会的影響まで幅広い領域におけるセキュリティ研究を推進し、ネットワーク社会の安心・安全を追求してまいります。

国際的な暗号技術に関わるのは必須事項ですし、それらの汎用性も考えると面白いなぁ・・

楕円曲線ってたしかフェルマーの最終定理にもつかわれているのよねぇ・・
フェルマーの最終定理と有限体（その２）
http://www.geocities.jp/ikuro_kotaro/koramu/642_flt.htm

NTT、日立、三菱電機の共同プロジェクトが楕円曲線暗号の実装技術を開発
http://japan.cnet.com/news/ent/story/0,2000056022,20060161,00.htm
前は3社でやっていたのか・・

＜用語解説＞
※1 素因数分解問題
　合成数を素数の積に分解する問題。小さな合成数に対しては、短時間で素因数分解実施可能であるが、大きな数については現実的な時間内に計算を終えることは困難である。ただし、あまり大きくない素因子を持つ場合は、楕円曲線法によりその素因子を求めることができる。
　RSA暗号の法に使うような大きな2つの素数の積から構成される合成数の素因数分解法としては、数体篩（ふるい）法が用いられる。現在、RSA暗号の法に使われる合成数に対しては一般数体篩法が最も高速である。

※2 一般数体篩法
　Pollardらにより提案され1990年代前半にLenstraらにより完成された素因数分解アルゴリズム。RSA暗号の法に使うような一般的な形の合成数の素因数分解では既知のアルゴリズムで漸近的に最も高速である。2, 3, 5, 7, …と割っていくいわゆる試し割り法の実行時間が指数時間であるのに対し、一般数体篩法は準指数時間で完了すると評価されている。しかし現在知られている実行時間の評価は平均の上限であるので、具体的な数に対する実際の実行時間を精度よく見積もるためには計算機実験の積み重ねが必要である。

※3 公開鍵暗号
　1976年にDiffieとHellmanにより提案された概念。実現方式としてはRSA暗号が有名。従来の暗号方式は暗号化と復号に用いられる鍵と呼ばれる情報は同一であり、秘密に保持しておく必要があったが、公開鍵暗号では暗号化に用いる鍵を公開することができ、復号に用いる鍵のみを秘密に保持しておけば十分である。

※4 RSA暗号
　1978年に公表された公開鍵暗号および電子署名方式で、Rivest、Shamir、Adlemanの3人の開発者の名前の頭文字からRSAの名がついた。電子署名方式として現在最も広く使われている。これまでにさまざまな改良が施され、いくつかのものは電子署名法の指針や電子政府推奨暗号リストに含まれている。RSA暗号の安全性は「法」と呼ばれるがパラメータに依存し、大きいほど安全であるが、処理性能は落ちる。現在、法のサイズとしは1024ビットが広く使われている。

※5 Opteron
　AMDはインテルが開発した32ビットアーキテクチャIA-32を拡張しいわゆる「64ビットCPU」用のアーキテクチャとしてAMD64を発表した。OpteronはAMD64アーキテクチャに基づくCPUである。

※6 Core2
　インテルは64ビットアーキテクチャとしてAMD64互換のEM64Tを発表した。Core2はEM64Tに基づくCPUコア名称である。

※7 分散計算
　大規模な計算を分割して多数の計算機により計算する技術。分割した計算それぞれに依存関係があると分散計算できない。

※8 ALADDIN-G5K
　フランスの9箇所に配置された大規模並列分散システム研究のための基盤。

※9 楕円曲線暗号
　楕円曲線上の点に対して数式によって定義される特殊な加算法に基づいて暗号化・復号を行なう暗号方式。解読の困難さは、楕円曲線上の離散対数問題を解くのと同程度と言われ、効率のよい解読法はまだ発見されていない。
　ＮＴＴ研究所では、「PSEC-KEM」という楕円曲線暗号を開発している。

ヽ(≧ο≦)人(≧Ｖ≦)ﾉＦｒｅｅ Ｊａｐａｎヽ(≧ο≦)人(≧Ｖ≦)ﾉ


拡散推奨~外国人参政権付与反対の陳情 
こちらが誰でもできる地方自治体への陳情提出です。

間寛平アースマラソンについて

日本ユ偽フ様の実態です

気軽にポチポチとねｗ
（#￣▽￣）<アッチはクリックできて・・コッチはしてくれないんだ

クリックщ(ﾟДﾟщ)ｶﾓｫｫｫﾝ