パスワードを忘れた? アカウント作成
120970 story
暗号

200 台の PS3 で 112 ビット楕円曲線暗号の解読に成功 26

ストーリー by reo
「暗号解読」を読み終えたら次は何がおすすめでしょう 部門より

mek 曰く、

暗号学者ヨッパ・W・ボス (Joppe W. Bos)、マルセロ・E・カイハラ (Marcelo E. Kaihara)、トルステン・クラインユング (Thorsten Kleinjung)、アリエン・K・レンストラ(Arjen K. Lenstra)、ピーター・L・モンゴメリ (Peter L. Montgomery) の発表によると、112 ビットの楕円曲線上の離散対数問題の解を求めることに成功、新記録を出したという (スイス連邦工科大学、暗号アルゴリズム研究室の発表記事本家 /. 記事より) 。

前回の記録は 109 ビット暗号の解読で 2002 年 10 月にさかのぼる。今回のプロジェクトはスイス連邦工科大学ローザンヌ校 (EPFL) にある200 台を越える PS3 を利用して計算が行われた (前回、MD5 衝突攻撃による偽 SSL 証明書の作成に使われたものと同じ設定) 。PS3 上では、今回の問題を解くための計算量は 56 ビット DES のキーサーチを 14 回行うのに相当するものだ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • How long did it take? (スコア:2, 参考になる)

    by suntear (11933) on 2009年07月16日 13時42分 (#1605947) ホームページ 日記

    The calculation was started on January 13, 2009, and finished on July 8, 2009. It ran on and off, occasionally interrupted by other cryptanalytic projects such as this [win.tue.nl] or this or PlayLaB [documents.epfl.ch] visits as described here [documents.epfl.ch] (in French), on a cluster of more than 200 PlayStation 3 (PS3) game consoles. When run continuously using the latest version of our code, the same calculation would have taken 3.5 months.

    今年の 1/13 から始めて 7/8 に終わったようです。途中、別のプロジェクト [win.tue.nl]やこんな行事 [documents.epfl.ch]によって中断があったそうで、最新のコードで続けて計算すれば 3.5 ヶ月ぐらいかかるでしょうとのこと。

    • Re: (スコア:0, フレームのもと)

      最新のコードで続けて計算すれば 3.5 ヶ月ぐらいかかるでしょうとのこと。

      「最新のコード続けて計算していたなら 3.5 ヶ月かかったでしょう」かな。

      • by Anonymous Coward
        いや

        「最新のコードに変えて連続計算していたなら 3.5 ヶ月かかったでしょう」だよたぶん。
    • by Anonymous Coward
      MD5のと別のPS3じゃなかったのかorz

      by クタラン
  • by MISSION (13232) on 2009年07月16日 15時18分 (#1606015) 日記

     112bitの楕円曲線暗号の強度は(56bitDES暗号14回 nearly equal 56bitDES暗号2^4回ってことで)、60bitのDES暗号程度と考えて良いと言うことでしょうか?

    --
    ここは自由の殿堂だ。床につばを吐こうが猫を海賊呼ばわりしようが自由だ。- A.バートラム・チャンドラー 銀河辺境シリーズより
    • by kokorohamoe (38645) on 2009年07月18日 14時12分 (#1607120)
      この場合の56bitって56桁という意味であって、2^nを意味していないはずだから、54桁x14回=756bitと考える方がまだ近似するんじゃないでしょうか?
      親コメント
      • by MISSION (13232) on 2009年07月19日 13時43分 (#1607456) 日記

         なるほど、ってことは桁数(この場合は=データ量)を(56->112と)倍にしたことで試行回数が14回増える。このことによる強度の違いを考えればよいって事ですね。
         でも暗号化方式の違いがあるとはいえ、56桁(この場合2^56)分組み合わせが増えたのに、解読に必要な試行回数が14回しか増えないので、楕円曲線暗号はDESに比べるとあまり強くないって事になるような? まだどっか勘違いしている?

        --
        ここは自由の殿堂だ。床につばを吐こうが猫を海賊呼ばわりしようが自由だ。- A.バートラム・チャンドラー 銀河辺境シリーズより
        親コメント
  • 別にどのデバイスを使って解読したというより、解読にどれだけの時間がかかったという方が重要だと思うのだが、たれ込みには書いてなかったのかなぁ・・・

    # 英語苦手だからあれだけど、2009年1月13日〜2009年7月8日、実質半年と半月ぐらいかかったという事かしら。これが暗号解読では早いのか遅いのかわからんが。

    • by Anonymous Coward
      半年は早いと言わざるを得ない
  • ふーん (スコア:1, すばらしい洞察)

    by Anonymous Coward on 2009年07月20日 17時34分 (#1607897)
    全数探索で解けたからって、ふーん何がすごいの?って印象しかない。
    単にやってみました。できました。だけの話題でしょ。
    そもそもこの手の研究って技術力とか必要なの?資金は必要だろうけど。

    安全面で考えたら鍵長を長くすればいいだけなんだし、
    暗号自体を破ったような騒ぎ方も止めてほしいな
    • by kieru_haim (37792) on 2009年07月21日 9時05分 (#1608179) 日記
      今の私には出来ないから、それなりの技術(知識)は必要だと思う
      それでも「お金と時間を掛けて出来ました」っという話だというのにも一理ある。
      ただ、これが
      一般人が何も苦もなく解読出来るようになったら、
      破られたって事でいいんじゃない?
      ここでいう破られたというのは、暗号として使いもものに
      ならなくなったという意味。
      親コメント
    • by Anonymous Coward
      たとえ総当たりでも解読のための機械が早くなったり、大量の機械を用意したりして
      十分に短い時間でカギにたどり着いたら破られたことになると思います。
      • by Anonymous Coward
        全くもって見当はずれな指摘だね。
        破られたということ自体に異を唱えたつもりはないんだが。

        資金力でごり押ししただけでしかない研究にどれほどの価値を見出せるのかという主張だよ。
    • by Anonymous Coward

      まず並列コンピューティングや効率的な解読の実装には技術が必要です。

      「実際にごり押しでできた」ということの重要性がわかんないですか?たしかに鍵長を長くすれば強度は上がりますが、実装や運用を考えればむやみやたらと長くできるわけではないですね。どこでトレードオフを取るばいいかという実証になりますね。

  • by Anonymous Coward on 2009年07月16日 12時44分 (#1605892)

    暗号解読が終えたら破られなさそうな暗号の試験とかに…。

    • by Anonymous Coward
      学術分野での貢献度は高いな。
  • by Anonymous Coward on 2009年07月16日 12時53分 (#1605903)
    >おすすめ
    PS3が売れるためには、どんなソフトを出せば良いか・・・という市場分析でもするとか
  • by Anonymous Coward on 2009年07月16日 13時13分 (#1605930)

    本当に分からないから教えてくれ。
    「56bitDESなんてすぐ破られるから使うなヴォケ」と言われてるが、それの14回分なんてやっぱりすぐじゃないのか?
    たいしたことない印象だぞ?

    原文は"14 full 56-bit DES key searches"だけど、
    これってTripleDESのような、ただし3重を14重にしたものなんじゃないの?
    それなら確かに計算量は多そうなんだけど。

    素人の印象からの素朴な質問だよ。茶々じゃないから。念のため。

    • 確認したわけではないのですが、その直前には "approximately 1018 modular additions and multiplications on 112-bit integers" とあるので、56bit DESの全数探索 (256のキーを全部試してみる) 14回分で大体合う気がしますが如何。

      親コメント
    • by Anonymous Coward

      楕円曲線暗号については、米国のNISTでアルゴリズムと処理方法について公開されていたと思います。

      RSA1024ビット暗号系に対し、感覚では約300ビット前後の楕円曲線暗号が同等な暗号強度をもっていたような。。。?
      もともとDES等のブロック暗号と、離散対数暗号を比較するのは??という感覚ですが、
      どうでしょう、専門家のみなさん。

      わたしは専門ではありませんので、AC。

  • by Anonymous Coward on 2009年07月16日 13時59分 (#1605958)
    誰か馬鹿な私にもわかるように説明して下さい。
    • by Anonymous Coward

      PS3を200台位買う経済力と3.5ヶ月待てる根気があれば3.5ヵ月後には解読される危険性があるので、4ヶ月とか半年以上秘密にしたいなら使わないようにしようといった話です。

      • by Anonymous Coward
        つまり、PS3が2万台あれば1日ちょい、ってことですね。
  • by Anonymous Coward on 2009年07月16日 20時42分 (#1606182)

    10年前に傍受した暗号通信とか、傍受データが残ってたら面白いのに。
    今なら簡単に読解できるでしょ。
    データ持ってる人がいたとしても、おおっぴらにはやらないか。

  • by Anonymous Coward on 2009年07月18日 18時53分 (#1607209)

    マルセロ・E・カイハラ (Marcelo E. Kaihara)

typodupeerror

Stableって古いって意味だっけ? -- Debian初級

読み込み中...