パスワードを忘れた? アカウント作成
4299987 story
IT

解読に数十万年かかるとされた暗号、148日で解読される 77

ストーリー by hylom
暗号は破られるものですが 部門より
Wingard 曰く、

解読に数十万年かかるとされた278桁の暗号「ペアリング暗号」の解読に、情報通信研究機構や九州大、富士通研究所のチームが成功した(MSN産経ニュース)。

コンピュータ21台を使用し、148日で解読に成功したとのことだ。チームは「ペアリング暗号はもろく、情報通信でデータを暗号化する鍵として使うには、より大きな桁数が必要と分かった。安全な暗号や適切な鍵の交換時期を見極めるのに役立つ」としている。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2012年06月19日 18時14分 (#2176626)

    NICT・九大・富士通研究所、次世代標準の「ペアリング暗号」で278桁長の解読に成功:ITpro Active
    http://itpro.nikkeibp.co.jp/article/ActiveR/20120618/403386/ [nikkeibp.co.jp]

    根本的な問題のようで、大々的に使われる前に発覚したのは幸いだったということなんでしょう。

    • by Anonymous Coward on 2012年06月19日 19時47分 (#2176701)

      これはペアリング暗号に使われている(特殊な形式の)離散対数問題を高速で解くことに成功したのか、あるいは一般的な離散対数問題を高速で解いてしまったのか、どっちなの?
      後者だったらペアリング暗号だけの脆弱性の問題ではなくなってくるのでは?

      親コメント
      • by Anonymous Coward on 2012年06月19日 20時55分 (#2176749)

        資料を見る限り、前者で合っていると思います。

        問題設定と解読結果:
        問題の設定としては、まず、有限体GF(397 )をGF(3)[x]/(x97 + x16 + 2) として定め、超特異楕円曲線E(GF(397 )) y2 = x3 − x +1上の離散対数問題から、T η ペアリングを用いて有限体GF(3582 ) 上の離散対数問題に変換したものを用います。次に、楕円曲線上の点を( ( ) 4, ) π π Q = Int π + y , ( ( ) 15, ) e e Q = Int e + y とします。ただし、Int(π ) , Int(e)は、それぞれ円周率π = 3.14159...、ならびに自然対数の底e = 2.71828...を3進展開した値であり、e Q ,Q π は、各々楕円曲線上の点の条件を満たす最も近い値を求めたものです。これは、問題の恣意性(問題の答えが事前に分かっていることが疑われる設定)を排除するために行いました。
        以上の準備の下、T η ペアリングの値を計算し、以下に示す有限体GF(3582 )上の離散対数問題の解読実験を実施しました。
        (http://release.nikkei.co.jp/attach_file/0312246_02.pdf より)

        ちなみに離散対数問題は、一定の式においては解読可能であることが既に明らかになっています。PS3が不適切な実装を行ったECDSAを解読され、えらい目にあったのは記憶に新しい所。

        親コメント
      • by shesee (27226) on 2012年06月19日 21時14分 (#2176766) 日記
        どっちかというと923bit程度の離散対数問題を元にした暗号の実装はちょっと工夫すればコア数とメモリもりもりのブルートフォースに耐えられないよってだけの話ではないかと。RSAも512bitはすでに安全ではないとされてますし、ペアリングも運用では2000bit以上使うんじゃないでしょうか
        親コメント
  • 278桁のベアリング暗号については145日毎に強制変更する運用を開始した?
  • by Anonymous Coward on 2012年06月19日 17時55分 (#2176607)

    解読に必要な時間の期待値は、予測できそうなものですが。

    期待値としてはやはり数十万年で、今回すぐに解読できたのは偶然なのでしょうか?
    (もしそうするなら、どんな勝算があって解読に着手したのかということになりますが)。

    それとも、平均しても100日程度で解読できてしまうものなのでしょうか。

    あるいは、すぐに解読できてしまうということを証明したのだけど学界の大御所が受け入れて
    くれないので、仕方なく実際にやって実証することにしたとか?

    • by Anonymous Coward on 2012年06月19日 18時12分 (#2176624)

      NICTのプレスリリースによる概要の説明

      http://www.nict.go.jp/press/2012/06/18-2.html [nict.go.jp]

      1. 初期値最適化手法の開発。
      書いてないけど、まあ数倍ぐらい早くなる?

      2. 探索方の改良
      数十倍に

      3. 繰り返し解くことになる方程式の処理部分の最適化
      数倍に

      4. 並列化の改善
      数倍に

      全部合わせると、数倍×数十倍×数倍×数倍で1000倍ぐらいは行く?
      で、かかったCPU時間が100年だから、1000倍ぐらいの高速化と考えると10万年でまあ桁はあってる感じ?
      #実際には、「数十万年かかる」と言われてた頃のCPUに比べ今の方が速かったりとかそういうのもかかるんだろうけど。

      親コメント
      • by Anonymous Coward on 2012年06月19日 20時57分 (#2176752)

        新手のウォーズマン理論かと思った。

        親コメント
        • by Anonymous Coward

          さらに友情がミックスされてのこの演算速度と考えれば最初からゆで理論

    • by Anonymous Coward on 2012年06月19日 18時13分 (#2176625)

      http://scan.netsecurity.ne.jp/article/2012/06/18/29280.html [netsecurity.ne.jp]
      こっちの記事によると解読を大幅に高速化する攻撃方法が発見されて、それを実証したということみたい。
      > 期待値としてはやはり数十万年で、今回すぐに解読できたのは偶然なのでしょうか?
      偶然でそんなことが起きる可能性は確かにゼロではないが、本気で心配してるなら二度と放射脳の連中を笑えないな。

      親コメント
      • by Anonymous Coward

        なぜ放射脳の話に飛躍するのか分からないけど、小さな確率のことでも、起こるときは起こりますよ。

        • 小さな確率のことでも、起こるときは起こりますよ。

          そういう考え方をすると統計学の意味がなくなってしまいます。
          男女の生まれる確率は男性の方が若干高いことが統計的に示されていますが、来年から逆になる可能性もゼロではありません。
          解読に数十万年かかるとされた暗号が148日で解読されたら、偶然ではあり得ない、と考えるのが正しい科学のスタンスなわけです。

          親コメント
          • by Anonymous Coward
            それこそ放射脳の考え方ですね。
            「・」を出そうとサイコロを振って「・」が1回目ででっちゃたのという話です。
            • by Anonymous Coward

              違う。
              「・」を連続で278回出そうとして出ちゃったくらいにあり得ない確率。

              • by Anonymous Coward

                > 「・」を連続で278回出そうとして出ちゃったくらいにあり得ない確率。

                全然違う。

                サイコロの「・」が278回連続して出る確率は、(1/6)^278≒5e-217。

                一方、解読に数十万年(例えば25万年)かかるとされた暗号が148日(約1/2年)で解読される確率は、
                約50万分の1 = 2e-6。

                200桁以上も違います。いいかげんなことを言うものではありません。

              • by Anonymous Coward on 2012年06月20日 0時12分 (#2176865)

                >一方、解読に数十万年(例えば25万年)かかるとされた暗号が148日(約1/2年)で解読される確率は、
                >約50万分の1 = 2e-6。

                解読できるかできないかの確立だから50%じゃないの?

                親コメント
              • by Anonymous Coward on 2012年06月20日 2時07分 (#2176905)

                > > >一方、解読に数十万年(例えば25万年)かかるとされた暗号が148日(約1/2年)で解読される確率は、
                > > >約50万分の1 = 2e-6。
                > > ここ、笑うところ?
                > 計算が違ってるのは気付いてたけど面倒だし桁の話をしているときにそんな重箱の隅をつついてくる奴もいないだろうと思ってた。

                なんかよくわかりませんが、

                 ・「解読に25万年かかる暗号」の解読に要する日数は、最小0日から最大25万年の一様分布である

                という仮定に基づいて2e-6という数を算出したのだと思いますが、もし

                 ・「解読に25万年かかる暗号」とは、答え(かぎ)の標本空間をブルートフォースで全部チェックするのに要する時間が25万年という意味である。
                 
                 ・1個のチェック(ある候補をトライしてあってるかどうか調べる)にかかる時間はどれも同じである。

                なのであれば、

                 ・無作為に選ればれた答え(かぎ)をブルートフォースでチェックして探すのに要する時間が148日でおわる確率は2e-6である。

                と計算したのは、笑いどころではなくて、あってると思います。

                親コメント
          • by Anonymous Coward

            1000年に一度の地震が起こる確率はどれくらい?
            巨大隕石が地球に落下する確率はどれくらい?
            いずれも、過去に起こってますよね。
            確率が小さいのと、確率がゼロなのとは、まったく違います。

            小さい確率を無視するのが科学ではありません。
            あることが起こる確率が小さいとき、そこには何か理由(法則)があるに違いないと考え、それを解明するのが科学的な考え方です。
            もうすこし踏み込むなら、「確率が小さい」という表現は定量的ではないので、科学的な考え方に立てば、あまり良い表現ではありません。

            解読に数十万年かかるとされた暗号が148日で解読されることがありうるかどうかは、そもそも科学とは関係ありません。

            • 地球誕生から46億年も経っていればね...
              そりゃ起こるでしょうよ。
              期間を無視するのはやめようよ...
              親コメント
            • by Anonymous Coward

              確率が0でなくとも、狙って出せるほど高い確率でもありません。
              「・」を連続278回狙って出せたなら、そこには確率以外の何かがあるはずだとするのが統計です。
              確率が低いから無視するのではなく、より確率の高そうなほうへ着目するだけのことです。

    • by Anonymous Coward

      読売新聞の記事 [yomiuri.co.jp]では、

      > 研究チームはペアリング暗号を解読する新しい「攻撃法」を開発した

      とありますので、(恐らくは理論的に)脆弱だと思われる部分を突くことで、短時間での解読に至ったんだと思います。

  • by Anonymous Coward on 2012年06月19日 18時08分 (#2176619)

    676ビット長(10進数で204桁に相当)において、汎用コンピュータ18台で33日
    http://www2.nict.go.jp/pub/whatsnew/press/h21/100223/100223.html [nict.go.jp]

    これの数百倍の演算能力相当
    http://www.nikkei.com/article/DGXNASFK1803N_Y2A610C1000000/?uda=DGXZZO... [nikkei.com]

    だとすれば、数十年かければ可能になっていたわけで
    「解読に数十万年かかる」というのは、考案時の
    ものでしょうか。

    • by Anonymous Coward on 2012年06月19日 19時39分 (#2176697)

      コア数で比較すると

      676ビット長 汎用コンピュータ18台(12-24コア)で33日

      923ビット長 252コア で 148日

      コア数で10倍、期間で4倍なので

      計算手法・プログラミングでの高速化は
      5から10倍程度の高速化ということでは。

      親コメント
      • by Anonymous Coward

        京なら数分でできそうな感じですね。

  • こういうニュースは嬉しいね。
    普段から「暗号なんて日本人に解けるわけないだろ」とかそういう先入観持たれているしね。
    俺は持っていないけれども。

    • by Anonymous Coward on 2012年06月19日 19時13分 (#2176675)

      これが「楕円曲線上のペアリングを用いた暗号方式」のことであれば考案者も日本人
      #境・大岸・笠原

      親コメント
    • by Anonymous Coward

      >独法もなかなかよくやっているじゃないか

      自分が興味のある内容に関連したプレスリリースがたまたま出ただけで、
      よくやっていると評価するのもなんだかなーと。思いますがね。

      「メディア受けする記事に踊る市民」
      ってのを感じました。

    • by Anonymous Coward

      >よくやっていると評価するのもなんだかなーと。思いますがね。
      捻くれてるというよりは、普通に頭悪い子がいるな。
      目覚しい成果が出たらしいから、よくやってるて感想でいいんだよ。
      他者の評価基準が自分より低いからて、いちいち絡むのってそれこそなんだかな~。

  • by Anonymous Coward on 2012年06月19日 18時57分 (#2176664)

    タレコみのリンク元の記事ではどの程度の計算をしたのかわからないので適当に予想してみた。

    仮定
    ・今回の暗号はPen4やCoreDuoクラスのCPUでブルートフォースで計算すると50万年で全空間の計算が可能と仮定
    ・Pen4やCoreDuoの計算能力を仮に5GFLOPSと改定
    ・各チームが使ったコンピューターをハイエンドGPU(1枚あたり5TFLOPS)を3枚挿ししたPCと仮定

    かなりいい加減な仮定だけどまあいいや(藁)
    21台のPCの総計算能力は元のPen4クラスのPCの計算能力の63000倍。
    これを使って暗号の全空間を計算するのに必要な日数はおそよ2900日。
    つまり148日あればざっと全体の5%の空間を計算したって話。

    暗号の計算で浮動小数点演算の速度で比較する無意味さとか突っ込みところは満載だけど
    オーダー的に考えればGPU複数挿しのハイエンドPC(といっても個人購入可能なレベル)数十台で
    数百日計算すれば全空間の数10%ぐらいの計算が出来てしまう可能性は十分にあります。
    つまり*たまたま*148日目で解けたとしても別に驚くほどの話ではないような気が。

    • by Anonymous Coward

      次はソロバンで何年掛かるか計算してみて下さい。

    • by Anonymous Coward

      よし、それでAmazonEC2使ってどれぐらい金がかかるか計算してくれ。

  • by Anonymous Coward on 2012年06月19日 19時42分 (#2176699)

    結婚する予定の彼女とお揃いのペアリングにしようと思ったのだが・・・・

typodupeerror

ナニゲにアレゲなのは、ナニゲなアレゲ -- アレゲ研究家

読み込み中...