ここは (*゚∀゚)ゞカガクニュース隊だった

 http://www.scienceplus2ch.com/ 引っ越しました

NTT 「素因数分解問題」で世界記録更新  1024bitRSA鍵が近い将来「解読」可能に  





 NTTは1月8日、グループのNTT情報流通プラットフォーム研究所(NTT研究所)が海外の研究機関と共同で、公開鍵暗号の安全性の根拠となる「素因数分解問題」で世界記録を更新したことを発表した。

 これまでの世界記録は663ビット、10進200ケタだが、新しい世界記録は768ビット、10進232ケタで100ビット以上上回っている。独ボン大学、仏の国立情報学自動制御研究所(INRIA)、オランダの国立情報工学・数学研究所(CWI)と共同で研究した。

poster15.jpg



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

以下略

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




4 :名無しのひみつ:2010/01/08(金) 20:40:01 ID:BNep/C9g
> 公開鍵暗号解読に一歩近づくか
ちょっと違うような気がする。

5 :名無しのひみつ:2010/01/08(金) 20:42:41 ID:ghdS074A
>>4
分かる人か?解説してくれ。

12 :名無しのひみつ:2010/01/08(金) 20:55:37 ID:B+QXZr8C
>>5
他人だが、この話の対象になるのは「大きな数の素因数分解には膨大な時間を要する」を前提とする暗号形式なんだな。

RSAが正にこれでRSAの信頼性はどこまで素因数分解できるかに依存してるので、今回の結果は今の1024bitなRSA鍵が近い将来解読可能になってしまう可能性を示唆する。

ただしRSAでもさらにbit増やせば安全性高まるし、そもそも素因数分解に安全性が依存しない暗号形式なんてのもあるので、この結果自体は公開鍵形式そのものの安全性には関係ないというわけだな。



8 :名無しのひみつ:2010/01/08(金) 20:49:17 ID:q92aIy7F
記事自体が暗号だ、きっと…


9 :名無しのひみつ:2010/01/08(金) 20:50:14 ID:HjNZdXAZ
近づかれても困るわけで。

50 :名無しのひみつ:2010/01/09(土) 09:31:25 ID:pHVr0Uo/
>>9
科学の発展の意味合いにおいては、近づくことは良い事ですよ。



11 :名無しのひみつ:2010/01/08(金) 20:52:21 ID:UYZ16tnx
新記録じゃなきゃだめなんですか?2位じゃだめなんですか?

83 :名無しのひみつ:2010/01/10(日) 22:16:56 ID:leBCB20P
>>11
1位じゃなきゃ駄目なんです。



13 :名無しのひみつ:2010/01/08(金) 21:01:07 ID:fYR98WQt
ここで言ってる「公開鍵」ってのは、現在使われている1024bitRSAのことでしょ?


14 :名無しのひみつ:2010/01/08(金) 21:01:53 ID:yQulTHmn
他者が解読不可能な「完全暗号」なんぞ作ったらアメリカが黙っちゃいないと思うが…


17 :名無しのひみつ:2010/01/08(金) 21:04:11 ID:WuWH9IaB
ナチスのエニグマ暗号って、本当に当時の技術で解読できるんか?未だに信じられないんだが…
確立も150,000,000,000,000,000,000分の1だろ?当時の汎用計算機を独占できたとしても信じられん。

21 :名無しのひみつ:2010/01/08(金) 21:21:53 ID:B+QXZr8C
>>17
もちろん何もないところから解読なんてしてない、実物や暗号入力や解読用の本などを取得して機械的な再現などを踏まえての理論解析。その成功を導いたのが群論。

因みにポーランドはプラグボードが多くなるまでは自力でエニグマ解読に成功してたりするわけだ、それ以前のエニグマなんて極端な話数時間で解読できちゃう代物だった。ついでにエニグマの出力自体に解読のヒントになりうる欠点も多かったからね、今だと総当たりで何とかなるらしいが…

24 :名無しのひみつ:2010/01/08(金) 21:33:25 ID:MN8WrgyQ
>>21
違うだろ?ドイツがポーランドに侵攻して占領するまでだろ。占領後にポーランドのエニグマ解読機を発見・押収したドイツが、ポーランドが実はそれまでのドイツの通信を全て解読されていたことを知って驚いて、それから慌てて対応策を考えてプラグボードを増やすことにした。

そもそもポーランドは大正時代から日本に暗号解読法を教えてきた、日本人にとっての恩師ですよ。

ポーランドからの暗号解読指導者の招致
http://www3.ocn.ne.jp/~y.hirama/Yh_ronbun_dainiji_poland.htm

26 :名無しのひみつ:2010/01/08(金) 21:42:08 ID:B+QXZr8C
>>24
ポーランド侵攻前、1939年前半にはポーランドはエニグマの解読が困難になり、独自解読諦めて英仏に成果を提供してる。そのきっかけは1938年のスクランブラーと1939年初頭のプラクボードの追加(6→10)

29 :名無しのひみつ:2010/01/08(金) 21:46:55 ID:MN8WrgyQ
>>26
>ポーランドはエニグマの解読が困難になり、

普通に考えれば不可能になったのでも諦めたのでもなく、ドイツのポーランド侵攻が目前に迫ったので、この技術の英仏同盟国への分散を図ったんだろ。協同でやればそれだけ成果も早く達成するし、祖国ポーランドはもはや助からないかもしれない(そして助からなかった…)

そんな危急の状況下にバナッハやタルスキという大天才たちを擁する、ポーランド学派の総力を挙げて積み重ねてきたこの技術を抱えたまま墓まで持って行ってしまうほど馬鹿な話は無いわけで、だからこそその秘伝を英仏に渡した。

30 :名無しのひみつ:2010/01/08(金) 21:59:47 ID:B+QXZr8C
>>29
プラグボード追加で組数が増えたことで理論上解読は可能でも、解読できた時点ではその情報にもはや価値がないような状態になった。つまり解読が実質困難になったことにかわりはなかった。

実地では解読できるだけでなく、情報が有用なうちに解読できないとダメだからね。
もちろん解読の努力はしたが間に合わなかった(それすらも翌年には使えない状態に陥ったらしいが)

31 :名無しのひみつ:2010/01/08(金) 22:01:47 ID:MN8WrgyQ
>>30
だから、それアラン・チューリングを持ち上げたいイギリスのプロパガンダ。
敗北したポーランドは過小評価されている、個々の技術者の能力でなく完全に予算の問題。

78 :名無しのひみつ:2010/01/09(土) 19:59:58 ID:iAnpnyM3
>>31
イギリスは、暗号解読のためのコンピュータを開発して、エニグマの解読に成功したが、チューリングは、それの設計に加わっていた。だから、資金+チューリングの技術力といったところ。



20 :名無しのひみつ:2010/01/08(金) 21:20:52 ID:lGJnCYIS
時間かければ誰でもできるだろ、何分で解けたの?


23 :名無しのひみつ:2010/01/08(金) 21:28:58 ID:7q8SiD1+
要は素因数分解が教育要綱から外れるってことだろ。


25 :名無しのひみつ:2010/01/08(金) 21:34:55 ID:YUOXTjc8
二つの素数の積ってことがわかってるなら、最初から素数のリストを持っていてそれで当たった方が早くない?
実際に鍵は一定の長さまでしかない訳だし。

28 :名無しのひみつ:2010/01/08(金) 21:45:42 ID:EKe2cVtK
>>25
総当り法では実用的な時間内では解けないというのが、その時代に使われる暗号化アルゴリズムということを知っておいた方がいい。

30 :名無しのひみつ:2010/01/08(金) 21:59:47 ID:B+QXZr8C
>>25
素数のリスト総当たりは、単純には最悪でO((N/2)^2)の演算になるので極めて効率が悪い。

57 :名無しのひみつ:2010/01/09(土) 10:53:09 ID:Bq+FQpg6
>>25
今回の場合だと、リストに必要な素数の数は、全宇宙に存在する素粒子の数をも軽く超えると思う。



34 :名無しのひみつ:2010/01/08(金) 22:50:25 ID:DwI1aPV7
NTTリリース

公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新
http://www.ntt.co.jp/news/news10/1001/100108a.html

38 :名無しのひみつ:2010/01/08(金) 23:09:08 ID:ghdS074A
>>34
読んでも、全然判りません。

65 :名無しのひみつ:2010/01/09(土) 14:20:49 ID:/rifIpL7
>>34
117桁までの数の中に素数がいくつあって、通常のCPUで総当り検索すると、どれくらい時間がかかるのか示してくれないと何が凄いのかさっぱりわかんない。



35 :名無しのひみつ:2010/01/08(金) 22:50:35 ID:lGJnCYIS
PS3でBOINCすれば1ヶ月で解けそうだな。


39 :名無しのひみつ:2010/01/08(金) 23:10:31 ID:9AynxrNU
この前のNHKスペシャルで素数は万物の真理であるって言ってたよ。
あらゆる物理法則の根本原理が、素数の中に隠されてるらしい。



41 :名無しのひみつ:2010/01/09(土) 00:00:37 ID:OgYW+ok9
同業者だけども、論文をIACRのe-printでみた。これまで彼らが培った知識の集大成だね。
素晴らしいし敬意を表したいと…こんなことを書きたいんじゃなくって、NTTのプレスリリースは間違っているぞ。

最小公約数じゃなくって最大公約数だろ?最小公約数使ってたら、最後の最後で素因数分解に失敗する。

43 :名無しのひみつ:2010/01/09(土) 00:42:29 ID:/1zetZ6F
>>41
英語版のプレスリリースではちゃんと最大公約数って書いてある。
つまり、元ネタは英語で第三者が英語に翻訳したってこった。



48 :名無しのひみつ:2010/01/09(土) 08:24:21 ID:GQeB0r7q
NIST「1024ビットの鍵長が許されるのは2010年までだよねー」
http://www.itmedia.co.jp/enterprise/articles/0811/21/news022.html

総務省「2014年度から本気出す」
http://www.soumu.go.jp/main_sosiki/kenkyu/kouteki_kojin/pdf/090126_gaiyou.pdf

59 :名無しのひみつ:2010/01/09(土) 11:16:43 ID:+f0AVu80
>>48を見ると、
2011年度末を目途に新たな暗号アルゴリズムに対応する住基カードの交付を、開始することが検討されているって書いてあるから、2~3年したら再発行してもらえばいいんじゃね?



58 :名無しのひみつ:2010/01/09(土) 10:53:23 ID:LYdBSoMt
俺が持ってるRSA-2048非対応の住基カード(2018年まで有効)はどうなるの?


61 :名無しのひみつ:2010/01/09(土) 12:54:00 ID:cyf6Paz9
地球シミューレータを使えば、もっと早く分解できるのじゃなかろうか?
あるいはPS3を沢山並べたり、GPUを沢山並べるとか。

62 :名無しのひみつ:2010/01/09(土) 13:20:35 ID:7GnhetiF
>>61
そりゃ、最適化された計算機が沢山あったとすれば総当りの時間は幾らでも短く出来るだろ。

63 :名無しのひみつ:2010/01/09(土) 13:28:02 ID:+f0AVu80
>>62
多分「篩」部分で 1000台弱のパソコンを 2 年間動かしたんだろうから、お前ら10000人ぐらいが協力すれば1月ぐらいで出来るかもね。



66 :名無しのひみつ:2010/01/09(土) 16:43:19 ID:FpXtjkZ0
楕円曲線って、フェルマーの大定理の話でしか聞かないな。


71 :名無しのひみつ:2010/01/09(土) 19:24:02 ID:34Nmf8zc
楕円曲線暗号はNTTのお家芸だもんな。


72 :名無しのひみつ:2010/01/09(土) 19:27:02 ID:u3sAaAOn
新しい方式かと思ったら、深度が深くなっただけだったという。
結局ヒューマンエラーで漏れる訳ですよね?


84 :名無しのひみつ:2010/01/10(日) 23:14:30 ID:sJIop77n
RSAが2048ビットくらいないと話にならないのは、ずいぶん前から常識だろ?
楕円暗号は、明日にも完全解読されかねないから論外だし。


85 :名無しのひみつ:2010/01/11(月) 03:47:47 ID:1hfPJ2CB
リーマン予想が証明されてRSA全滅という悪夢はおとずれるのだろうか?

86 :名無しのひみつ:2010/01/11(月) 05:05:22 ID:Ko1l9yF3
>>85
リーマン予想ってゼータ関数のゼロ点は直線上に並ぶってだけで、素数の値は何か?
つまり直線上のどの点に現れるかまでは踏み込んでないじゃね?



88 :名無しのひみつ:2010/01/11(月) 06:26:27 ID:k7WynJj4
全部同じ共通の暗号にするから解読されるんだよ。暗号そのものをプログラムにして、それ自身を送ったほうがアルゴリズムをのものが変われば解読っていうものは無力、そしてアルゴリズムに対応してもその種類が豊富なら、その対応自体は自動では不可能なのでやはり自動解読は不可能に近い。

89 :名無しのひみつ:2010/01/11(月) 08:02:13 ID:10L0ewZF
>>88
暗号を解くってのは鍵が絶対必要な訳でその鍵は実際問題、人間が憶えられるレベルじゃない。
今流行ってる公開鍵方式が一番楽ちんなんだよ。

毎回アルゴリズム変えれば簡単だけど、毎回鍵を知らせなくちゃならない。通信や伝達するには途中で読まれる可能性があるというリスクが付き纏うからやっかい。しかも一番の問題はめんどくさいしね。

軍の厳重なセキュリティレベルだと軍用通信使って更に鍵も毎回変えてるっぽいけど、民生だとそこまでのコストはかけらんないな。



90 :名無しのひみつ:2010/01/11(月) 10:37:27 ID:5KIckBor
これって、SETIみたいに分散でやったらダメなの?それに「解く」のは時間がかかるかもしれないけど、一度といた素数のペアを記録しといて、そのマッチング表を見ればいいだけじゃねーの?

91 :名無しのひみつ:2010/01/11(月) 11:04:05 ID:dmFaLZ/a
>>90
今回はざっと116桁の素数のペアだけど、116桁の素数がどれだけ存在するかだな。素数定理ってのを使えばだいたい分かるらしいが…10の100乗個以上あるんじゃね?

で、観測可能な宇宙に存在する素粒子の数が10の88乗だから記録は無理と。

92 :名無しのひみつ:2010/01/11(月) 11:50:37 ID:A+NKG8iY
>>90
2年かけた篩の部分はかなり短縮できると思うが、SETIほど理解者が得られないのがネック。それにハードディスクが足りない。ペアを記録しとく為には 2^768 bit程度のメモリが要るんじゃないか?



98 :名無しのひみつ:2010/01/11(月) 16:29:38 ID:D+Nt9fPg
原文が薩摩弁だったら解読されない。


関連
モールス信号を喘ぎ声に変換するジェネレーター作ってみた
サマーウォーズ:曜日の求め方とか2056桁の暗号とかの解説
関連記事



12874 :  2010.01.16 Sat 13:34  

最後の奴は大戦時の日本で実際に使った奴だよな。なんか不思議だな
NTTの労組が超左翼だけど大丈夫なんだろうか
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12875 :  2010.01.16 Sat 13:39  

戦時中ドイツとの国際電話で外交官が九州弁で話したが
米軍の中に九州弁が分かる奴が居て・・・という話を思い出した
  • #n.BaIJrE
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12876 :  2010.01.16 Sat 14:04  

この記事が言いたいのは

短時間での解読がいずれ可能になりますよ

ってことだろ
現在だって時間をかければ解読はできる
いずれ現在のスパコン並みの性能を持つようになるから素因数分解は暗号としての意味をなくしますよと
そういうことだろ
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12877 :  2010.01.16 Sat 14:06  

ちょっと量子暗号買ってくる
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12878 :  2010.01.16 Sat 14:33  

>>12876
違うね。今のままの鍵長でやってるといずれ短時間で解読されるようになるよ、というのが正確。
そういう時代になったらまた鍵長長くすればいいだけ。
  • #-
  •   
  • [URL]
  • [Edit]

12879 :  2010.01.16 Sat 14:53  

馬鹿な俺にはこの人達が言ってることがすでに暗号
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12880 :  2010.01.16 Sat 15:47  

RSAで暗号化するのにただでさえ時間かかるのに、さらにbit増やしたら鈍足すぎるだろ
ただ増やせばいいってもんじゃない
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12881 :  2010.01.16 Sat 16:33  

>>12880
でも、その頃には普及してるPCの性能も上がるから、ビット数増やしても問題ないってことじゃない?
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12883 :  2010.01.16 Sat 16:54  

エニグマの解読のきっかけとなったのは、ドイツ兵がやらかしたポカなんだよな
ナチスは情報をかく乱するためにダミーの通信文をばら撒くなんてことをやるんだけど、文章を考えるのが面倒なときは、全部一種類の文字で構成された文書を流すことがあった。暗号化された文書は一見するとデタラメに見えるけど、暗号解読者は使われていない文字が一文字だけあることに気がついた。
その事実から、もしやオリジナルは一種類の文字で構成されていたのでは? という予測が立ち、調べを進めて行った。ついに全ての文字がLだということを突き止めることに成功。そこから研究が一気に加速したという。
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12884 :  2010.01.16 Sat 19:09  

ケンジが一晩で解いてくれました
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12885 :  2010.01.16 Sat 21:29  

>>12881
個人用という想定ならそうだろうが、商用等そう簡単に切り替えできない場合も多くあるだろう
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12887 :  2010.01.17 Sun 01:01  

何言ってるんだかさっぱり分からん
さっぱり妖精が出てくるレベル
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12889 :  2010.01.17 Sun 06:13  

元スレでもここのコメント欄でも既に指摘されてるけど一応。

暗号の鍵長を大きくすれば安全性は高くなるが、その分計算コストが大きくなる。
特にRSA暗号は計算コストが重いので、鍵長を大きくすれば安全だからといって、あまりにも大きな鍵で運用しようとすると、携帯端末で使えなかったり商用サイトへの接続に時間がかかったりいろいろ不都合なことが起きる。
だから、「現行の鍵長で将来いつまでもつのか」を正確に見積もることはとても重要。

また、一度運用し始めた暗号方式の規格を変更するのはとても手間がかかる。
だから、「誰もが納得できるような、信頼性の高い方法で」危険性を示す結果が出ないと、世の中の人々は動いてくれない。
論文を発表して、オープンな場で議論して、誰もが内容を検証できるようにするのはそのため。
「こんな研究をやって、公に発表してどうするんだ」と言う人がたまにいるけど、「犯罪者やどっかの国がこっそり技術を開発して、世界中の人々や企業や政府が気付かずに暗号を使っているのに、そいつらには筒抜けでした」という状況とどっちがマシか、考えればすぐわかるはず。
>>12874
NTTは暗号では世界的な業績をあげている日本でもトップクラスだ
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12890 :  2010.01.17 Sun 06:24  

>>12889のコメントが途中で途切れちゃった

>>12874
NTTは暗号では世界的な業績をあげている日本でもトップクラスの企業だぞ
技術の心配する前に自分のネトウヨ脳の心配しろよw
全然見当違いなくせにさも事情を知る俺は心配だぜ(キリッみたいな書き込みされると、見てる方が恥ずかしくなっちゃうんだぜw
まあたぶん俺も自分が詳しくない話題では同じようなことやって、専門知識のある人間に「全然そういう問題じゃねーよバカw」とか思われてるんだろうな
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12891 :  2010.01.17 Sun 10:56  

そういうそんなことあるはず無いと自分の常識しか見えていないところにつけこまれて技術って流出するんだろうな~
NTT労組は研修と称して昔地図に載らなかった島で合宿したり戦中の日本はいかに悪かったかを教えている。代表は最近強制連行は無かったと言われているがそんなことは無いと証拠を出さずにコメント。
間違った認識からは間違った認識しか産まれないが、中華の手先みたいなことやっている人間やその周辺が技術パクらないって保障はどこにあるのかと心配だよ
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12892 :  2010.01.17 Sun 11:02  

心配
  • #-
  • 名無し 
  • [URL]
  • [Edit]

12893 :  2010.01.17 Sun 11:24  

先の選挙でNTT労組は売国奴の巣窟民主党をプッシュした
いかに危険かじゃなくて民主党はこんなにも素晴らしいと平気で人をだますような奴らだよ
残念ながら

勝手に見て勝手に恥ずかしがってろよ
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12895 :  2010.01.17 Sun 12:43  

んじゃ、そもそも左翼の労組のせいで技術が流出した事例がどんだけあるのか、無知な俺に教えてくれませんか?
日本最強の極左過激派を内部に抱えるJR東日本からは、新幹線や鉄道システムやSuicaの技術がバンバン海外に流出したってことですか?
てか、今回の研究のどこに秘密の技術があるの?
著者らが計算機を回して発見した、アルゴリズムを高速に実行するためのパラメータの値?
論文で全部公開されてますけど
http://eprint.iacr.org/2010/006/
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12896 :  2010.01.17 Sun 13:08  

12895
まずお前さんは、左翼とサヨクの違いから勉強せねばならんよ。
「サヨク 左翼」でググってごらん。

定義が違い分かってからまた質問においで
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12904 :  2010.01.17 Sun 14:54  

>>12896
結局NTTって言葉で連想ゲームしちゃっただけ?
逃げ口上まで上から目線なのが笑えますね
今日もまたつまらんアホウヨを斬ってしまった(キリリッ
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

12921 :  2010.01.17 Sun 22:23  

技術とウヨサヨ云々は別問題
労組ごときに技術流出の指示なんて出来る立場ではない
混同させてる方がアホだから弁解の余地はない
  • #-
  • 名無し隊員さん 
  • [URL]
  • [Edit]

13055 :  2010.01.23 Sat 06:12  

*12921

流出させるのは大体役員クラスの幹部だもんな、技術者が
態々流出させる事例なんて某国くらいしか思いつかん。
  • #-
  • ねむいよ!ななしさん 
  • [URL]
  • [Edit]






(編集・削除用)


管理者にだけ表示を許可

ブログパーツ

月別アーカイブ

テスト

Powered by 複眼RSS

Copyright © 中身