【社会】NTTと欧州研究機関、232ケタの素因数分解に成功

ＮＴＴは８日、欧州の研究機関と協力して多数のコンピューターを連携させ、
これまでで最大の232ケタの数を素因数分解することに成功した、と発表した。

素因数分解はインターネット通信の暗号技術を支えている計算手法で、現行方式だと
５〜10年後に破られると予想されている。同社は「従来予測の正しさが裏付けられた。
新方式への置き換えなど、対応を急ぐほうがよい」と警鐘を鳴らしている。

素因数分解は数を、素数（１とその数自身でしか割り切れない数）のかけ算に分解する。
ケタの大きい素数を使うと、解くのに高速コンピューターでも天文学的な計算時間が
必要とされ、電子商取引の認証や機密データの秘匿など、ネット通信の暗号に使われている。

*+*+ NIKKEI NET 2010/01/08[23:23:36] +*+*
http://www.nikkei.co.jp/news/shakai/20100108AT1G0803F08012010.html

なにがすごいのかわからない

２

ネットの暗号オワタ

日本語でおｋ

ＦＢＩにはバックドアあげるんだろ？

>>2
暗号が破られうることを証明した

　
総レス数 7

2 KB　[ ２ちゃんねる　３億PV/日をささえる レンタルサーバー　\877/2TB/100Mbps]

へ〜そうなんだ
で・・・一般人の生活にどう響くだ？

俺、展開なら得意よ！

もう、暗号なんか通用しないから。

>>9のクレジットカード番号が流出しますように

ＮＴＴと欧州研究機関
「こ、こんなに大きいのに・・・割り切れないよ！割り切れないよ！(；´Д`)ﾊｧﾊｧ」

公開鍵暗号やべーじゃん

>>9
アマゾンとか楽天とか、どこのネットショップで買い物しても情報ダダ漏れ

１０００円の価値の暗号解くのでも１０万の電気代食いそうだが

２３２桁ってちいさすぎだろ。１億桁とかにしる。

>>9のアカウント情報が盗聴されますように

リーマン予想の証明まだー？

>>15
今現在となにが違うの？

いまのRSAって６００桁くらいだっけ。念のため１０００桁くらいにしとけば
計算時間が１兆倍とかになって結局解読不可能。

量子コンピュータとか言われると知らん

つーか、向かいの二階に住んでる田中さんに頼んだ方が早くないか？

>>9の口座情報と信用情報が漏れますように

素因数分解して232桁の素数を割り出したのなら凄いが、232桁の合成数を分解しただけなら、まだまだだな。
まあ、じきに成功しちゃうとは思うけど。

一番大きい素数って何？

これ筆算でやったらどのくらい時間かかる？

>>13
素数を見付けた訳じゃないだろ

>>20
今は1台１台のPCじゃ暗号を解読できないがその気になればそのうち力任せに暗号を解けるようになる
もっと強度を高めた暗号化を標準的に採用しないと盗聴し放題

になるかもしれない

ビット数の少ない鍵で暗号化したエロ画像はもはや安全ではない

今のところ因数分解アルゴリズムに致命的なブレークスルーは起きておらず
主に計算機の性能向上に寄っているな。
利用する側も性能の上がった計算機でより多い桁数を用いれば良いし
1種類の解読手法が洗練されてくれば別の類似暗号化方式に切り替えるだけだ。
まだ、既存の全ての一方通行関数を一般論として短時間に解く手法や計算機は公表されとらん。

欧州と組んでやったのか
これは反米活動なのに違いない
米に仕分けされちゃうぞ

だからなに？ってかんじ

いや、これはかなり重要な話だよ
インターネッツするならね

多数のコンピューターって何台？１０台以下？以上？

しばらくは暗号の桁上げてりゃいいよね

ブラウザで右下に南京錠のマークが出ている状態で、
右クリック→プロパティを見ると、そのページの暗号強度が分かる。

アマゾンは RC4形式の暗号で、暗号強度は 128bit (38桁)
ヤフオクはAES形式、256bit (77桁)

また暗号化方式が増えるお・・・

なんかしらんがスゲー

>>34
解読コンテストみたいなちょっと力入ったグループだと
分散コンピューティングで軽く数十万台

>>9
ちまたに出回っているカードや端末を回収するために大手カード会社は数百億円を負担することになります。
もちろんそれは年会費や手数料として利用者に転嫁されます。
たぶんその前には偽造カード事件があちこちで起きるでしょうね。

>>21
まだ400桁(1024bit)あたりが主流

NEC&蛆痛のスパコン利権ガチガチ社員「スパコンはこうでないといけないんですよ！」

>>41
その横で松井(三菱ww)がほくそ笑んでるわけかw

素数を数えていると心が落ち着くんだ
　　　　　　　　　　　　　　　　　『プッチ神父語録』より

>>21
１０００桁(3000bit)だと現状一枚あたり５００円ぐらいで発行している
ICカードの単価が１０倍になりますよ。

素数の分解は汎用のコンピュータよりFPGAが得意な分野で
本気になれば１００分の１以下のコストで同じことができる。

豆な

こっちのソースのほうが詳しいような気がする。

http://japan.cnet.com/news/sec/story/0,2000056024,20406400,00.htm

verysignﾋﾟﾝﾁ

はいはいリーマン予想リーマン予想

２位じゃダメなんですか？

えーとこないだテレビでやってた。
リーマン予想がどうのこうの。

これどうやって計算するの？
2で割って3で割って・・・て最後まで繰返の？
なら世界中のPCに分散させれば簡単に出来そうな気がする。

>>51
ためしに電卓でやってみればいいと思うよ
15の素因数分解
187の素因数分解
2407の素因数分解
14453の素因数分解

どこでやる気が起きなくなったか
コンピュータも基本的にはそれと同じだから。処理速度の違いだけで

とりあえずは力技ってことすかね。
量子コンピュータが実用化されたら、
一気にブレイクスルーってことになるのか。

>>28
要するに「盗み」という目的にしか使えない馬鹿なものをわざわざお金かけて証明したわけだ？
ホント馬鹿だな、こんなことやるなら正規雇用を増やせよ。
「破られうる可能性」があるなら、始めから「破られうる可能性」のな」暗号にすればいいだけのこと。

NTTのプレスリリース
http://www.ntt.co.jp/news/news10/1001/100108a.html

因数分解に5段階のプロセスを踏んでいて、
無視できる程度の計算量の第5段階以外にかかった計算量は
AMD Opteron 2.2GHzを 1675年間分　+　Intel Core2 2.66GHz　6ヶ月分

1994年にRSA129を破った研究チームは、暗号鍵を10桁増やすと、
だいたい計算量は10倍になると言っている。
てことは、1024bit（308桁）をクラックするには
（AMD Opteron 2.2GHzを 1675年間分　+　Intel Core2 2.66GHz　6ヶ月分）×76だけの
コンピューターを用意すりゃいいって事かいな。

>>54
設備投資する前にその有効性を調べることはコストダウンでしょ。

クレジットカード偽造被害額
平成 9年 12億円
平成10年 28億円
平成11年 90.9億円
平成12年 140.2億円
平成13年 146.4億円
平成14年 165.億円
平成15年 164.4億円
平成16年 105.6億円
平成17年 83.4億円
平成18年 45.6億円

偽造されにくいICカードへの入れ替えで平成１６年以降落ち着いてきたけど、
そのために投資された総額はおそらく数千億円
破られる可能性のない暗号方式(RSA1280bit以上)にするには今まで以上の
投資が必要です。
もしもまた昔に戻れば消費者市場が崩壊しますよ。

>>55
10^7.6≒3980万倍では？

>>52
14453は97で割れるな。

>>55
ほんの一年前は270年かかると言ってたのに
ttp://jp.fujitsu.com/group/labs/downloads/business/activities/activities-3/fujitsu-labs-security-003.pdf

>>57
その通り。76の前にEが抜けてる。
自分で書いといて、「コレぐらいなら何とかなりそう。1024bitしょぼいな」と一瞬思ってしまった。

すっげ。
232桁つったら600ビット以上じゃん。
まあ鍵は1024ビットとか普通になったから問題ないだろうけど、
計算機ってつくづく速くなったもんだな。
俺のアンドロイドって15年前のSparcより速いしw

>>54
お前二行目が言いたいだけだろ

ttp://ameblo.jp/70rock/entry-10426319221.html

>>54
「安全」が無料だと思ってる馬鹿？

仕分けしろ

某所で72bit解読中

>>61
RSA暗号のRさんは1977年に
「RSAは超安全だからww試しに125桁をクラックしてみ。4京年かかるから（ｷﾘｯ」って言ってたそうな。
で、17年語に129桁がクラックされた。1024bitもそんなに安泰じゃない気がする。

今回のNTTの方法は、まだまだ改良の余地があるらしい。

>>36と>>67
アマゾンの情報ってすでにダダ漏れってこと？

RSA涙目

通信の暗号破るよりバカがメモしたパスワードや
パスを共有してる奴を見つけ出した方が早い気もする

どういう手法でやったんだろ
まさか力技じゃないだろうな・・・

132人目の素数は・・・743！

まぁ絶対安全なんてないってことで

サバン症候群の俺に任せれば１０秒

>>55
調べてみた(｀・ω・´)
768bitと1024bitの計算量を比較すると約7500倍だそうです。

http://www.cryptrec.go.jp/report.html
「CRYPTREC Report 2006 暗号技術監視委員会報告書」
> 3.1.4 素因数分解問題の計算量の見積(ソフトウェアの場合)
> 表3.3: 評価結果 Athlon 2.2GHz (2GB RAM)
> 768bit 1108年
> 1024bit 840万年

2006年当時使用したFPGA (Virtex4)はAthlon 2.2GHz (2GB RAM)の
約４倍の計算能力で、768bitなら270年で分解するそうです。
最近のVirtex6で10倍の処理性能として768bitで27年、1024bitなら
20万年ぐらい、FPGA1000個なら200年ぐらいか
量産ならFPGA一個あたり一万円総額1000万円ぐらいで動くかな

でもRSAの鍵生成ってコストの問題でたいていは素数性を完全には
保証できていないからもっと簡単に分解されてしまいそう。

>>71
素因数分解は基本力技だろ
計算機の高速化で力技が通用するようになっちゃうのが脅威

おもしろいな

意外とこの手の話題に興味や知識がない人って多いんだな

>>76
思うんだが力技でやって何になるのかね？

これって数学的な進歩の話じゃなくて
計算機の計算能力の進歩の報告だったのか

数学的な進歩の話として、画期的な解法を見つけたことで
２３２桁云々言ってるのかと思ってしまった

>>79
素因数分解に画期的な解法があったらフィールズ賞貰えるよ

>>70
ソーシャルハックか。

サイモン・シンって最近どうしてるの？

>>52
5 ' Fermat method
10 input "n=";N
20 X=isqrt(N)+1:Y=isqrt(X^2-N):print X,Y
30 W=X^2-N-Y^2
40 if W=0 then print X+Y,X-Y,X,Y:end
50 if W>0 then inc Y:goto 30
60 if W<0 then inc X:goto 30

http://www.asahi-net.or.jp/~kc2h-msm/mathland/math12/math1206.htm

>>79
暗号技術は実生活の話だから実際にやってみてコストを調べなきゃ
いけないんじゃないかな

>>80
貰えるまで生きてられたらいいけどな
暗号で儲けてる連中が数千億円の投資をフイにされると知って見過ごすとは思えない

>>70
ドアにどれだけ頑丈な鍵をかけても裏口が開いてれば誰でも入れますよね。
子供の頃に見たドリフのコントでドア枠ごと外すのがあったような

>>79
＞計算機の計算能力の進歩の報告だったのか
そのとおり
まあグリッドコンピューティングだかの手法の進歩とも言えるかもしれんが
予めこの強度では危険だということを確認して騒いでおかないといざ力技の解読が一般的な計算機で現実になったとき
対応が遅れるんじゃないかと思おう。まあそこまでの手間じゃないと思うけど今でさえセキュリティスカスカだったりするからね。
大手が致命的なセキュリティホール放置してたりするし。
まあいくら暗号が安全でも渡った先でちゃんと情報管理してないと意味ないんだけどね

意外と桁数がすくないな。

>>84
数学の業績をもみ消すのは無理だろう。
誰かに話していればそれを理解するのは容易ではなくとも可能だし、そうでなければ誰にも話さず全く秘密にしている。
そんな人間を相手にするような奴がいるかどうか。

解法を知ってるやつは企業から口止め料もらっているに決まっている。

>>75
一般のPCで比較してたのか。おもしろいな。
図3.1を下のほうに補外したらエライことになるような気がする。
128bitで1E-2 yearぐらい？速すぎない？そんなもんか？

素数を自由に1個考えて、これをpとします

次に、1〜(p-1)までの数をかけていき
これをpで割って余りを出します
例えばp=5のときは
1×2×3×4÷5＝4・・・4


そして、この余りからpを引くと、答えはずばりメール欄ですね？

>>54
そんなものは無い。
絶対に開かない鍵もないし、絶対に破られない暗号もない。
正しく鍵を開ける方法があり、正しく暗号を複合する方法がある限り。

>>54
お前、馬鹿だろ？
ちょっとは暗号理論勉強してから発言しろよ。

宇宙人に委託すれば暗号安全は保持されると思う。

>>79
１．数体ふるい法というアルゴリズム自体にまだ未知の部分がたくさんある
・何も考えずに実装すると大きな数の素因数分解はまず不可能
・アルゴリズムで使う複素数の種類をうまく選ぶと、大幅に計算時間を減らすことができる
・どんな方法でどの複素数を選べばいいのかはまだよくわかっていない

２．数体ふるい法というアルゴリズムを、どんな計算モデルで実現すると
どれほど高速に素因数分解できるのか、まだよくわかっていない
・Shamir（RSAのSさん）らが、アルゴリズムの特定部分を
光計算素子を使った特殊な計算機で実装すれば
素因数分解全体を高速に実行できると主張して、この分野に旋風を巻き起こした
・もしも現実的なコストで数体ふるい法を高速に実行する特殊ハードを製造できるなら
素因数分解ベースの暗号の寿命が大幅に短くなる
・分散計算や非ノイマン型プロセッサやGPGPUにアルゴリズムを実装したときはどうなるのか

てことで、「数学的なアルゴリズムが示されているから、それで理論的な研究は終わり」
という分野では全然ないんですよ

10 ^ 233 < 10 ^ 3 ^ 80 < 2 ^ 10 ^ 80 = 2 ^ 800
また1024bitも無理だし犯罪者がこんな大掛かりな計算し始めたらバレるんじゃないか
それに楕円曲線暗号とかもあるんじゃなかったっけ

昔NTTの作った暗号が米国のコンテストでけっこういい線いってたなそういえば

>>96
そのためのボットネットです

暗号数学について語ろう。ROUND 4
http://science6.2ch.net/test/read.cgi/math/1243318266/

以外にもジョジョスレになってないのがワラタｗｗｗ
みんなスゲーなアカデミックな話はついて行けん。

みかかはプロテクト関連が妙に強い

>>56
ICカード導入より利用規約の改正で「暗証番号が漏れた（解析された）場合は保証しません」になった事が大きいんじゃね？

PIN入力が周囲からモロ見えなのはなんとかしろよ

見えやすい構造にﾜｻﾞﾜｻﾞしてるのか？

これってどういうこと？
２３２桁の数字の素因数分解に成功したのか
２３２桁の素数である因数を含む数字の素因数分解に成功したのか

まあ、個人の口座取引なんかを解読するためにここまでの手間をかける馬鹿はいないだろう。
軍事情報とかやばいな。

もっとも、CIAとか防衛省とかのずさんさを見ると
暗号が破られることよりも、昔ながらの方法で機密が漏れることを心配したほうがよさそうだが。

インテルがCPUに判明してる素数全部埋め込んで出荷することで
PCの暗号解読能力を飛躍的に向上させたりはできねえの？

これ素数？↓
28498401928409715817985798758721857298572983748217
29384247908787928781888888827817999900010824108102
00989767861876847918409180481000898091840280980080
10987841491001000021894801987862109800089801980120
01843084010400809808958183704809850185089384878787
00001928943810980980980418049802840810840184021840
01840938408140148018401840383401840180498104810501
11928401840917566680000000000099283940100894511908
42018401857140185010000084298214915098105981098401
01387766567387981893849103981204971197493240912887

>>106
大きな素数はネットの暗号の会社が金庫で保管してるってテレビでやってた。
外にもれたらネット通信の暗号が破られるから、他の会社には教えないだろうな。
まして個々のPCのハード内に置く事は多分ないんじゃないか。

>>107
それ３で割れますけど？

じゃ皆のＰＣ繋いで小沢の

リーマン予想の証明はまだ公表しないほうがいいな・・・

>>101
みかかの研究開発能力を恐れて分割されたといわれているようで御座いますね

所詮公開鍵の暗号なんて「破ってもコストが見合わん」という程度で
十分だと思うんだけどね。
必要な投資が10億円切ったんなら、そろそろ考えなきゃいけないんだろうと
思うけど、結局幾らかかったのかを教えてくれてないよね。

映画「キューブ」で、女の子が素因数分解を繰り返して
各部屋の安全性を確認していくけど、
あれと比べてどうなの？

ネタばれすると、女の子は最後に殺されて、障害者一人生き残る。

ハイブリッドなんだから
共通鍵通信の部分をどうにかすれば
もっと簡単じゃないの？

鍵を作る時間　＜＜　鍵を解く時間
は変わりないんだろ。

しかし、円周率の計算は結構な数をやってるのに、
素因数分解は、たった２３２桁ですか

有限の桁数なら、有限の時間で素因数分解できる。
これは自明？

将来的にはすべての暗号技術が解読技術に追い越されすべてのオンライン取引は対面取引に先祖返りします。

単純計算じゃなくてなんかコツがあるのか？

>>118
桁は少ないけど、数が多いからじゃない？
全部つなげると相当な桁数になるけど
ＫＹぎみに

民主レンホー「２３１桁じゃだめなんですか？」

どうやってるの？
エラトステネス？

ゼータ関数の非自明なゼロ点は
すべて一直線上にあるはずだ。

国際事業仕分けの当然第一対象ざます

>>118
円周率はひとつの値だが、こっちは10^231個の数字について調べるんだぜ。
すべての計算結果を紙に書き並べようとしたら宇宙中の物質をかき集めても全然足りない。
（宇宙に存在する原子の個数が10^79〜10^81個）

>>125
リーマン乙

俺のトリップがやばい(´；ω；`)

>>54
すげぇ。ゆとりっているんだ。初めて見た。
ｶﾜｲｿｲﾝｽｳ。

ダンブラウンの小説、パズルパレスを思い出した。

コンピュータが進化して暗号が強化されても、所詮扱うのは人間。
端末の端にパスワードを平文で張り付けてる人間や
情報を外部に勝手に持ち出したり、
機密文書を一般ごみとして廃棄するような人間とかいるかぎり
無意味ですよ、ね？NTTさんとその下にいる関連企業さん。

>>132
これは公開鍵基盤の大本を担う
ルート認証局の秘密鍵とか
そういうものの安全性まで測る研究だからねえ・・・

こういった力技で破られる程度だったらまだ安心だな。
1回の取引の解読に必要なコスト >>>> 解読によって得られる利益
な現状だから国家機密でもない限り警戒する必要はないな。

問題は素因数分解を求める計算方法が見つかった場合。
PayPal宛てのパケットを解析すればクレジットカード番号ぬすみ放題。
有る程度番号が溜まったら、すべてのクレジットカードから口座に指定振込させてガッポリ。
な〜んて事が出来たらいいが、普通はすぐばれるけどね。

これって無意味って言ってる人は
ハガキに秘密の情報書いて通信するような物？
バカなんだろうな

米TVドラマ「numbers」は、日本では流行らなかった。

ＲＳＡ、いつまでもつのかね。

計算機のブレイクスルーが起きたら、
今の暗号化なんて、全部だだもれになるんだろうな・・・

まあ、そこまで今の人たちは生きていないだろうが。

誰かガンダムに例えて！

>>134
そんな日はあと百年は来ないだろうと、ただのリーマンの俺は予測してる

素因数分解解析のアルゴリズムが発表されたらどうなるんだろう？

発表者「すごいだろ？」
他の数学者「おまんま食い上げ」
セキュリティ会社「おまんま食い上げ」
ネット通販業者「おまんま食い上げ」
ネットユーザ「＼(^o^)／」
ロシア「一方我々は伝書鳩を使った」

>>127
そんなには調べないだろ。
全探索でも2から10^116.5程度までの素数をすべて調べればすむ。(素因数分解なんだから合成数で割ってみる必要はない)

素数定理で、10^116.5までに含まれる素数の割合は全体の3.7*10^(-4)程度とされるから10^113個程度の全探索となる。

>>140
発表する前に諜報機関に買収されるか、消されそう。
もしかしたらもう既に…。

>>75
Virtex6が一万円は無いな。100万ぐらいじゃね？

>>134
>問題は素因数分解を求める計算方法が見つかった場合。
>PayPal宛てのパケットを解析すればクレジットカード番号ぬすみ放題。
すべてのカードで共有しているカード発行者の鍵が1024bitでそれを
因数分解されたら決済情報が盗み放題になります。
実はカード一枚ごとの鍵でいいならなら512bitしかないから今でも個人のPCで
一日もかけずに分解できてしまったり

もしもクレジットカードの発行者鍵やSSL通信のルート鍵が解読されたら決済の停止やカード再発行にかかる
世界中の被害額は数千億円でも足りないかも