【研究】64ビット暗号、分散コンピューティングでついに解読

デヴィッド・ドイッチュだろ。

>>114
観測された時点で確定するから多次元宇宙とはまた違うんじゃないか？
よく知らないけど。

hazukasii>>114gairusuredesuka?
romajisikamowakatigatisinaitoyominikuitaro.

David Deutsch’s Home Page
http://www.qubit.org/people/david/David.html

これ読んで勉強しれ。俺には理解できん。

>>122
意外と男前だったが。

量子コンピュータ用のアルゴリズムって結構未開拓なんかな？
それとも応用研究だけは進んでる？

>>123
理論の研究はそれなりに進んでるよ。

4年もの時間と33万1000人もかかってやっと解読出来るのなら暗号として成功では

>>125
ソース読んだでつか？

>>124
サンクス。
じゃあ俺ではチューリング賞は無理か。元々無理だが。

>>125
賞金額もそれなりだしまぁだいたい予想通りだったんでは。

tonchinkannayatugairukawaisou

んで、具体的に何がすごいんですか？
解読した程度で・・・

6502の勉強をしている俺にとっては異次元の話だな

mac や linux でも参加できる Folding@Home はいかが？
http://pc3.2ch.net/test/read.cgi/pc/1003864665/
http://pc.2ch.net/test/read.cgi/pcnews/1033305670/
あたり参考にして。

>>1
ありがとうございます
>103
だまされたわ

RC5 Crackingとは一言でいうと「暗号解読コンテスト」の事です。
　RC5とはRSA Data Security社が所有している暗号の名称で、このコンテストは同社が
暗号の強さ（あるいは弱さ）を実証するために開催しています。

＜暗号の解読方法＞
　暗号を解読するための方法は色々とありますが、今回は力技で鍵の組み合わせを片っ端
から試して合う組み合わせを探す方法で挑みます。
　RC5-64は鍵の長さが６４ｂｉｔ、つまり２の６４乗通りの鍵があります。１０進数だと
18,446,744,073,709,551,616通りにもなります。これをたとえばPentium166MHzのマシンで
解読したとすると、毎秒約２１万個の鍵しか試せないので約８７兆秒かかります。つまり
約２７９万年かかると言うことになります。
　これだけ計算に時間がかかるから暗号は安全だと言えるのですが、これを１台ではな
くて何万台ものコンピュータを使って分担して調べようと言う壮大なプロジェクトが
「RC5 Cracking」です。

＜アメリカの暗号輸出規制と戦う＞
　またこの試みはアメリカの暗号輸出規制とも関わっています。アメリカは４０ｂｉｔの暗号
（一部条件付きで１２８ｂｉｔ）しか輸出を認めていません。私たちが６４ｂｉｔの鍵を破ることで
アメリカ政府に４０ｂｉｔ程度では暗号強度が不足していることをアピールし暗号の輸出規制
を撤廃させるという目的もあります。

暗号を作ったヤツ拉致して拷問にかければすぐ解けるのに

重要な書類は、紙縒りにして編み笠に編み込んで運ぶ。
これ最強。

６４ビットっつーとDVDがそのくらいだっけ？

暗号破りコンテストとは？

　そこで、自社製品にDESを実装しておりRC5の特許を持つRSA社が自ら賞金をかけて、
アルゴリズムが安全でないことを証明するために暗号破りコンテストを開催している。
米国行政法案（法案S-909）の欠陥を明らかにし、暗号輸出政策を考え直すことを訴える
ものだ。

　これまでに破られたのは　DES（56bit鍵） 2回、 RC5-56 （56bit鍵）だ。それぞれの所要
時間は DES-II（2回目）39日、RC5-56 250日だった。これらの暗号を破ったのはdsitributed.
netというプロジェクト。彼らは可能な鍵を片っ端から試していき、照合する強行突破を成し
遂げた (brute-force cracking) 。

　現在はRC5-64を相手に奮戦している。RC5-64は名前の通りに64ビット鍵を使用している
暗号アルゴリズムである。2^64ということは、1.8 x 10^19種類以上の膨大な数の「鍵の
可能性」を探らなければいけない。これは、海を含めた地球上のどこかに落ちているコンタ
クトレンズを探すようなものだ。

　一台のコンピュータでこれだけの膨大な可能性を検索するには数千年かかるが、
distributed.netチームは、インターネットに接続された何千台ものマシンに処理を分散する
ことにより、解読までの期間を大幅に短縮した。RC5-56は250日で解読されたが、RC5-64
はその256倍の時間が必要かと思われる。インテル設立者による「ムーアの法則」によれば、
18ヶ月ごとにコンピュータの性能は倍になるそうだ。たとえそうでも、RC5-64を解読するには
、現在よりさらに多くの参加者が必要になる。

>>129
「本当に力技で解読できることが立証された」ということですな。
計算能力の向上率とか100%まで達するのにかかる時間の予想とかも。

例：XX年後のクラスタだとXXX日で解けるようになる、とか

不定期に暗号を書き換えるプログラムっての作れないかな?

512ビットじゃ危ないからって1024ビットにしたのに64ビット解いたってなぁ

ちなみにDES-II（56ビット）の後に開催されたDES-III（同じく56ビット）は
破るのに24時間かからなかった。
DES-IIは39日かかったのに。

>>32
「猿マン」の例の図？

>>133
>これをたとえばPentium166MHzのマシンで解読したとすると、
>毎秒約２１万個の鍵しか試せないので約８７兆秒かかります。
>つまり約２７９万年かかると言うことになります。

２７９万台のパソコンを用意すれば１年で解けるじゃん（ｗ

RSAは弱い暗号なんでかなり大きくしないと強度が保てないってだけ

おまいら、アメリカの暗号輸出規制はスルーかよ！！

>>106〜

暗号が無力化するということは波束が収縮するということなので多元宇宙論は意味をなさないし、
今開発に成功したとか言ってるＴＶなんかに出てくる量子コンピュータは全く関係ない。
あれはシリコンの変わりに分子がどうとかいうものに過ぎず、量子コンピュータに対する理解の妨げになるだけ。
真の量子コンピュータは１０の-１７乗cmという世界間を取り入れる必要がある。

>>111
それは既に3DNow!とかSSEで実現してるだろ。

例え、全ての組み合わせを試すのに何億年かかろうとも、
偶然、最初の１つ目が「鍵」だったら、一瞬で解読され
るので、暗号の安全性につながるとは思えないと言ったら、
会議室は大爆笑。
なぜなら、最初に一致する確率そのものが低いからだそうだ。
でも、偶然とはそういうものだと思う。

【さすが】「８６時間連続ゲーム」の２０代、疲労で死亡【韓国】
http://japanese.joins.com/html/2002/1008/20021008221652400.html

>>147
おそらくジョークとおもわれたんではないか。
ただそれは道で通り魔恐れるのと同じ論理だろ

　ジマーマンは、政府対インターネット・コミュニティの暗号戦争におけるもっとも勇敢な闘士
のひとりであろう。1980年代のレーガン政権の軍事志向に危機感を抱いたジマーマンは、平
和運動へとのめりこむ。その過程で彼は、プライバシーを守ること、政府から情報を守ること
の重要性に気づいた。たとえば、平和運動に献金をしてくれた人のリストが政府の手に渡ら
ないようにすることは、運動の維持のために不可欠であった。そこから暗号技術への取り組
みが始まる。

　ジマーマンは、ほぼ独学で暗号のプログラミングを始め、PGP（Pretty Good Privacy）という
個人用の暗号ソフトウェアを書いていた。そこに、議会で暗号利用を規制する法案が審議さ
れるとの情報が入り、彼は急ぎPGPを完成させた。彼は完成したソフトウェアを友人に渡し、
友人を介してPGPはインターネット上にアップロードされ、世界中の人がそれをダウンロードし
、あっという間に拡散してしまった。1991年のことである。

　そこへ突然、アメリカ政府の税関担当官がやってきた。どうやってPGPが公開されたのかを
調べ始めたのである。インターネットで公開するということは、海外からもアクセスできるよう
になるということであり、輸出に当たるのではないかという嫌疑をかけてきた。当時の区分け
では、暗号は兵器であり、政府の許可なく輸出してはいけなかったのである。

　ジマーマンは政府にいやがらせをするためにPGPを作って公開したわけではない。アメリカ
人には政府の干渉を受けることなくプライバシーを守る権利がある。さらに、抑圧的な政府を
持つ国々で、政府の追及の手を逃れながら反政府運動を組織するツールとしてもPGPは有
効であると考えたのである（実際に、そうした人々からジマーマンに対してPGP公開のお礼の
メールが届くようになった）。

　彼は政府の捜査に対抗するために、いくつかの手段を講じた。まず、マサチューセッツ工科
大学（MIT）のFTPサイトでPGPを公開してもらった。その結果、MITとジマーマンは同罪になっ
たのである。ジマーマンは、「MITと自分を同等に扱わなくてはならない」と主張した。MITを訴
えるということになれば、人々の広範な関心を引きつけることになるにちがいなかった。

　次に彼は、PGPのソース・コードすべてを記載した本をMIT出版から発売した。本の出版は
、表現の自由の保護という点から、アメリカでは聖域になっている。言論に政府が口を出すこ
とはほとんど不可能である。出版された本の流通に規制をかけることもむずかしい。したがっ
て、本は輸出可能である。MIT出版というプレステージの高い学術出版社の本の輸出を、政
府は止められるだろうか。ジマーマンたちは、政府が止められないことを知っていてあえてそ
うしたのである。

　輸出された本をスキャナーで読みとれば、手間はかかるが、完全なソフトウェアの複製をア
メリカ国外で作ることができる。ジマーマンは筆者とのインタビューのなかで、「私たちは暗号
の輸出規制の効果を台無しにしたのです。そして、輸出規制の継続を意味ないものにしまし
た」と述べた。

　結局、ジマーマンは3年間捜査対象となったものの、1996年1月に突然、捜査打ち切りを宣
言するファクシミリを受け取り、訴追されることなく、裁判も行われなかった。ただ、この3年間
、彼は訴追されないようにするためにさまざまな法的対応をせねばならず、弁護士の助けを
必要とした。しかし、弁護士たちの多くがボランティアで彼を支援した。彼の暗号輸出規制に
対する挑戦を知ったインターネット・コミュニティの住人からも、支援の電子メールや資金援
助が寄せられ、ジマーマンは「たくさんの人が味方していると感じた」という。

１４６追記
>>106
どっちかというと暗号無しで最強のセキュリティーを得られるようになる。
なぜなら波動関数の崩壊により、盗んだデータは全て元々壊れていたことになるから。

>>147
恥丘が沢山要るね。

>>148
スレ違いながら嫌韓士の漏れとしては明るいニウスだ。

>>147
でも、平均すれば全数を調査する時間の約半分の時間になるはずだよな。

もしかして当てたの漏れのＰＣかも(･∀･)

結局このニュースは、現段階ではこれほどのリソースを使わないと
解けないくらい、この暗号は強固であると考えていいのか？

>>155

・・・軍事目的では使えないくらい強度が弱いから
民間では自由に使わせろよ！ってことです

>>155
逆だな。
3年後には1/4のリソースで解けると考えた方がいいかも。

（・∀・）ﾑｰｱ!!

ブルートは偉大だったと

うーん、時間さえかければブルート最強ってことだな

>155
それなりって所。
個人の短期の歩行の高くない秘密保持ぐらいには使える。

その筋が、その気になれば破れるってこと。

しかも、連中は既に穴を見付けている可能性もある。
そんなもん発表する訳ないしな。
安全に見せて筒抜けというのは美味しいから。

暗号化するプログラムはどうやってテストするんだろ？全パターン試すわけにもいかないだろうし

>>156
>>157
>>161
なるほど。さんきゅ。

FSFに寄付したのか、偉いな

>>162
そりゃまぁ暗号化と復号だけできればいいんでないの。

>>164
寄付先は投票つーか解析した鍵数による多数決でFSFに決まった。

>>165
>そりゃまぁ暗号化と復号だけできればいいんでないの。
いや、暗号（復号）化ルーチンが理論どおりに実装されているかをどうテストするのかってことじゃないの？

>>166
ftp://ftp.isi.edu/in-notes/rfc2040.txt
これの通り実装されているかどうか？
ってこのRFCにCのソースあるから
この通りやるしかないとは思うんだが・・・

>>16
>>32