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

ECC2-109楕円曲線暗号の解読に成功 47

ストーリー by Oliver
時の問題 部門より

109ビット楕円曲線暗号の解読に1万米ドルの賞金をかけたCerticom ECC2-109チャレンジの解を見付けることにeCompute ECC2-109プロジェクトが成功した(本家ストーリー)。ECCチャレンジはカナダの暗号開発企業が1997年に楕円曲線暗号(Elliptic Curve Cryptosystem, ECC)の強度を検証するために開設したもので、最高の359ビット版の解読には10万ドルの賞金がかけられている。eCompute ECC2-109プロジェクトには2002年11月のスタート以来、2000人近いメンバーが参加し、解読の手がかりとなるdistinguished ponitのコリジョンを探していた。現在は暫定解答として、チャレンジの主催者に連絡し、確認を待っているところだ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
    • Re:1へぇ (スコア:1, 興味深い)

      by Anonymous Coward on 2004年04月10日 3時46分 (#529432)
      > #暗号って数年持てばいい方なんですかね?

      ecc で 109 bit ってのは、強度的に RSA 1024bit よりも下。
      実運用では誰も使わない。

      現時点で弱い暗号の部類に入る 56bit DES の鍵長を、
      わざわざ短くして 40bit DES にしたようなもの。
      やぶられて当然。

      てゆーか、破られてナンボの challenge なんだし。
      親コメント
    • by Anonymous Coward
      定期的に鍵を替えれば済む話では?
      • 妄想というかヨタ (スコア:2, おもしろおかしい)

        by YOUPohwa (17275) on 2004年04月10日 5時34分 (#529445) ホームページ 日記
        ヒミツのファイルを暗号化してしまっておいたら、なにかの原因で(自分が)急死してしまい、なぜか家族がハードディスクを形見として保存、さらに運悪くそのディスクを別の家族が10年後に発見して、暗号を解読・・・とか?
        --
        yp
        親コメント
      • by Anonymous Coward
        >定期的に鍵を替えれば済む話では?

        それは、暗号化したい内容によるのでは。

        たとえば、重要な内容を含む暗号通信を、盗聴されたとすると、
        盗聴内容は10年後に解読されうる、という状況だとすると、
        10年以上秘匿にしたい情報には使えないですよね。
        • by mocchino (13752) on 2004年04月12日 11時03分 (#530285)
          >盗聴内容は10年後に解読されうる、という状況だとすると、
          >10年以上秘匿にしたい情報には使えないですよね。

          暗号化は所詮暗号化なので、10年以上の長い間秘匿したような情報に対して使用するものではありません
          私的には、2-3年程度がほぼ破られる可能性のない妥当な隠匿期間だろうと思っています。

          この隠匿期間の判断は、個人や組織によって違うと思いますが
          各チャレンジの結果を参考にして決めると良いでしょう。

          その考慮した隠匿期間以降に洩れても意味の無くなる情報に対して暗号は使用すべきです

          暗号は時間をかければ解ける事は、過去のチャレンジでも証明されていますが、基本的に解かれる物です。
          そしてその期間はコンピューターの進化によって短縮されていきます。

          10年以上もの長期間保持したいのであれば、まずは通信内容が洩れないように物理的に隔離するのが先決です。
          その上で暗号化をかけておくのが好ましいでしょう

          #隠匿期間はかなり大幅に安全のマージンを取って居るのは判っています
          #コンピューターの進化速度が予測しきれないのがその原因です
          親コメント
        • by lss (2577) on 2004年04月12日 22時43分 (#530665) ホームページ 日記
          10年たったらPCの性能は100倍になってます。
          つまり、現時点で解読に10年かかる暗号が 一ヶ月弱で解読できるようになってますよ。
          親コメント
    • by Anonymous Coward
      「暗号が解読できた」っていう判断ができなければ問題ないような気がします。
      たとえば解読結果が『かゆ、うま』だったら‥‥
      • by Anonymous Coward
        >「暗号が解読できた」っていう判断ができなければ問題ないような気がします。
        >たとえば解読結果が『かゆ、うま』だったら‥‥

        そりゃ単に二重に暗号化されているだけの話しじゃん。

        • by miri (12057) on 2004年04月12日 5時54分 (#530191) 日記
          似たような考え方で、複数の似たような文章を突っ込んで、正規の方法で解読すればどれが本物かわかるけど、力技で解読した場合はどれだかわからない、なんていう暗号はないんですかね。分類としては公開鍵ではなく共通鍵暗号に入ると思うけど、ちゃんと勉強してないからわからない。
          親コメント
    • by Anonymous Coward
      > 楕円暗号(Elliptic Curve Cryptosystem)
      > ... 解読の困難さは、楕円曲線上の離散対数問題を解くのと同程度と言われ、効率の
      > よい解読法はまだ発見されていない。短い鍵で高い安全性が確保でき、また計算も高速に
      > 行なうことができる。1024ビットの鍵を使うRSA暗号と同程度の安全性を、楕円曲線暗号
      • by Anonymous Coward on 2004年04月10日 12時58分 (#529553)
        > ... 解読の困難さは、楕円曲線上の離散対数問題を解くのと同程度と言われ、効率の
        > よい解読法はまだ発見されていない。

        これだけだと、楕円曲線暗号には疵が無いように読めるますが、一部の曲線に弱点が見つ
        かっています。もちろん、実装で避けることが出来るのですが。
        あと、楕円曲線暗号は鍵長の利点から小型機器などへの組み込みによく使われています。
        その場合、曲線決定のパラメータが埋め込まれていることが多いのですが、これも実装が
        悪いと暗号の強度が落ちます(で、実際まずいものが多いらしい)。

        > 短い鍵で高い安全性が確保でき、また計算も高速に
        > 行なうことができる。1024ビットの鍵を使うRSA暗号と同程度の安全性を、楕円曲線暗号
        > では160ビットで実現することができる。

        RSA暗号と楕円曲線暗号を並べて書いてありますが、使い方としては全然別物です。
        楕円曲線暗号は鍵合意と署名にしか使えませんし。一般的にはそれで十分なのでしょう
        けど、RSA暗号ならもっといろいろ面白いことが出来るのに。

        > また、暗号化・復号化はRSA暗号に比べ約10倍高速であると言われている。

        どこから出てきたんだろう、この10倍は。
        署名で楕円曲線暗号(ECDSA)が6倍、検証では逆にRSA暗号が7倍速い。合計すると楕円曲線暗号
        (ECDSA)が2倍速い。
        もちろん実装によってこの数値は大きく変わるのですが、傾向は変わらないはず。
        検証の回数が署名よりはるかに多い用途なら、RSA暗号の方がパフォーマンスは良いです。

        # 「IT用語辞典」や「goo辞書」を鵜呑みにするのは止めて欲しい。
        親コメント
        • by Anonymous Coward on 2004年04月10日 14時55分 (#529586)
          > 一部の曲線に弱点が見つかっています。

          そんなのぜんぜん重要じゃないでしょ。辞書サイトの DES の
          項には「DES には弱鍵があるが、しばしば実装で回避している」
          とか書かなきゃいかんの?
          親コメント
          • >> 一部の曲線に弱点が見つかっています。
            >
            >そんなのぜんぜん重要じゃないでしょ。辞書サイトの DES の
            >項には「DES には弱鍵があるが、しばしば実装で回避している」
            >とか書かなきゃいかんの?

            実装として回避することに問題がないなら書かなくても問題ないと思うけど、有名なものとかは書いておいてくれるとうれしいし、実装で回避するのが難しいとき、たとえばすでにでハードが出回ってるWEPとか、は書いておいてくれないと困る。

            楕円曲線暗号については、検証途中の技術という感じで辞書サイトの記述については考える余地が有るけど、まだまだみんなが持っている情報が少ないと思うので、こういう雑談の場では、そのことを説明してくれるのはうれしいです。もちろん「間違いが多すぎる」というだけではなくね。

            ところでWEPはRC4が原因だけど、おなじRC4を使ってるSSLは大丈夫なの?という疑問にストレートに答えてくれる情報をぐぐってもなかなか見つけられない。これ [nikkeibp.co.jp]とかを見るに、SSLは問題ないと思ってるのですが、どうなんでしょう?
            親コメント
            • >WEPはRC4が原因だけど、おなじRC4を使ってるSSLは大丈夫なの?
              こっちの記事 [itmedia.co.jp]の方が判りやすいと思います。
              SSLの方には、こういう鍵生成アルゴリズムの穴は見つかっていませんが、通信時に選択されたアルゴリズムがRC4の鍵長40bitだと、力業で破られる [aiai-hiroba.com]可能性はあります。
              親コメント
              • 補足的に言っておくと、WEPの実装ではIV(Initialization Vector)を24bit(3octet)使って、IVはパケットに入った形でやり取りされる事になります(IVは誰でも傍受可能)が、IEEEの802.11グループから発行されている仕様書では「IVの生成などアルゴリズムに付いてはRSA社に聞け。ウチは知らん」と言っています。
                ですから、ほとんどのメーカーではRSAからドキュメントと一緒にライブラリも買ってきて、同じRSA社のライブラリが使われているという現実があります。
                そのため、どのメーカーのWEP実装にも同じ脆弱性が存在する事になってしまっています。

                実は

          • >> 一部の曲線に弱点が見つかっています。
            > そんなのぜんぜん重要じゃないでしょ。辞書サイトの DES の
            > 項には「DES には弱鍵があるが、しばしば実装で回避している」
            > とか書かなきゃいかんの?

            上記のコメント(#529586)の親コメント(#529553)を書いた者ですが、どうして
            このような至極まっとうなコメントをマイナスモデレートするのか。
            • たまたま内容を理解できなかった者がmoderateしただけでしょ。

              >このような至極まっとうなコメント

              かどうかは俺は知らんけど、他に理解できる人がいればあげてくれるよ。
              たった一人の評価をいちいち気にしてちゃだめだろ。
              #モデする方も、理解しかねるならマイナスモデは慎むべきだとは思うがね…。
            • 日本語の表現に、音便などが多く含まれたり、その他口語的であったり感情的な言い回しがあるような場合、マイナスモデレートされる確率が高いように思われます。特に短文の場合は顕著でしょう。

              逆に、議論を盛り上げたいときにそういう表現を使うと、効果的であるともいえます。
            • >まっとうなコメントをマイナスモデレートするのか。

              一度でもそんな例を見た人はモデレートを無視して読むようになるから、気にしなくて良いですよ。(そうなった男)
        • by BIWYFI (11941) on 2004年04月11日 19時35分 (#530052) 日記
          >これだけだと、楕円曲線暗号には疵が無いように読めるますが、一部の曲線に弱点が見つ
          >かっています。もちろん、実装で避けることが出来るのですが。

           この表現、(typoを除いても)なんとなく引っかかるので後述

          >その場合、曲線決定のパラメータが埋め込まれていることが多いのですが、これも実装が
          >悪いと暗号の強度が落ちます(で、実際まずいものが多いらしい)。

           憶測だが、これは、鶏と卵の関係じゃないかな?
           つまり、
          1) 実装に適した(と思われる)曲線が提唱される
          2) その実装が現れる(and/or普及する)
          3) その曲線が注目されて、解析の対象となり、弱点が見つかる
          4) 強度が落ちたことを知らず(或いは無視して)、使用を続ける
           と云う具合では無いかと。
           この場合、現実問題は4であるが、それ以前に、実は、1で選ばれた曲線が本質的に弱点を持っている可能性がある。つまり、初期の時点では「実装に適した曲線=実装での計算量が少ない曲線」なので、「弱点があるから実装し易かった」のかも知れない。

           ただ、楕円曲線暗号にはパラメータが多いから、求める精度での「実装での計算量が少ない上に、弱点の無い」曲線を一つ見つければ、その精度については、他の曲線は無くても良い。

           現実に、現在では、適切な曲線が幾つか提唱されている訳で、上で引っかかった「楕円曲線暗号には疵が無いように読めるます」は、実装を含めた実際問題としては、事実では無いかと。
          //但し、「独自の楕円曲線暗号を搭載しているから高性能云々」と云う謳い文句には要注意

          >RSA暗号と楕円曲線暗号を並べて書いてありますが、使い方としては全然別物です。
          >楕円曲線暗号は鍵合意と署名にしか使えませんし。一般的にはそれで十分なのでしょう

           細かい使い方としては別物かも知れないけれど、楕円曲線暗号は、RSA暗号より鍵長が短いので、同容量なら複数の情報を埋めて組み合わせることが出来る。その結果、アプリケーションから見て同じことが出来れば、実用上は、全く同じ物。

          >どこから出てきたんだろう、この10倍は。

           確かに、リソースは不明。多分、鍵長から類推した「権威者」が居たんじゃないかな?
           でも、後述の理由で、個人的には、その意見を肯定したい。

          >署名で楕円曲線暗号(ECDSA)が6倍、検証では逆にRSA暗号が7倍速い。合計すると楕円曲線暗号
          >(ECDSA)が2倍速い。
          >もちろん実装によってこの数値は大きく変わるのですが、傾向は変わらないはず。

           これって、汎用計算機上での特定の実装の比較ですよね?
           組み込み機器等では、ハードウェアのアクセラレータを載せたりするから、一概には言えないかと。
           で、個人的には、鍵長が短い分、ハードの実装が容易になる気がするけど、これは、勘違いかな?
          //ま、公開鍵暗号は、絶対的計算量の多さが安全性を保証するから、究極的な計算速度は、単純に強度に依存する訳だけど。

          >検証の回数が署名よりはるかに多い用途なら、RSA暗号の方がパフォーマンスは良いです。

           これは、アプリケーションである程度回避出来る。
           計算能力の低いICカード等では、署名だけをさせて、検証を計算能力の高いホスト側で行えば、総合パフォーマンスは、ECDSAの方が高くなる。(と何処ぞ書いてあった。実用性は知らんが...)
           あと、検証用のデータをオンラインで引き出す場合には、検証の計算コストは殆ど無視出来るかと。

           と云う事で、鮮度の問題を除けば、“「IT用語辞典」や「goo辞書」を鵜呑みに”しても問題無いんじゃ?
          // 一番の問題は、新技術の登場速度が、人手でまとめる速度よりも速いことかと
          --
          -- Buy It When You Found It --
          親コメント
        • by Anonymous Coward
          > # 「IT用語辞典」や「goo辞書」を鵜呑みにするのは止めて欲しい。

          一般人には、「IT用語辞典」で言っていることと、
          「あなた」が言っている事に違いはありません。

          専門家にとって大きな違いであっても、一般人
        • > # 「IT用語辞典」や「goo辞書」を鵜呑みにするのは止めて欲しい。 なぜ鵜呑みにした人を責めて、そんな嘘、いい加減な辞書を作って公開している人たちを非難しないのですか? #「IT用語辞典」「goo辞書」は日経並なのですね。信じないようにします。
        • >楕円曲線暗号は鍵合意と署名にしか使えませんし

          発言の趣旨がよくわかっていないので的外れなことを言っているかも知れませんが、Elliptic Curve ElGamalというのがあって、それは楕円曲線上でElGamal暗号を形成するので、それで

      • Re:1へぇ (スコア:1, すばらしい洞察)

        by Anonymous Coward on 2004年04月10日 9時03分 (#529473)
        その「多すぎる」間違い、もっと具体的に指摘してもらえると読者のためになるかと。
        親コメント
      • Re:1へぇ (スコア:1, すばらしい洞察)

        by Anonymous Coward on 2004年04月10日 10時23分 (#529500)

        どこが間違えているのかの指摘か,何を読めば その間違いが分かるのかが書いてあると助かります.

        親コメント
      • by Anonymous Coward
        いいかげん復号化なんて書くの止めろって言いたいよな。
        • by Anonymous Coward
          なんで?
          • by junnohta (10945) on 2004年04月12日 0時09分 (#530125)
            暗号化というのは何かを暗号にするから暗号*化*ですが、
            その逆は何かを復号にするわけではないので復号*化*は
            日本語としておかしい、ということでしょう。
            親コメント
            • by Anonymous Coward
              じゃあ、明号化? (笑)
              まあ、平文化、あたりかな。

              「復号化」ではなくて「復号する」と動詞で使えば良いんだろうけどね。
  • by greentea (17971) on 2004年04月10日 14時24分 (#529581) 日記
    楕円曲線上の離散対数問題とやらを効率よく解く方法を見つけたの?
    それとは別の方法で解く方法を見つけたの?
    --
    1を聞いて0を知れ!
    • Re:で、今回は (スコア:2, 参考になる)

      by BIWYFI (11941) on 2004年04月11日 19時43分 (#530056) 日記
       元記事とか読めば分かるけど、(比較的)効率良く解く方法(しかも並列実行で高速化出来る物)は、既知であって、それを使って、力業で解くことが出来たってだけ。
       詳細データは見てないから分からんが、恐らく、想定通りの計算力が投入されたんじゃないかな?
       
      --
      -- Buy It When You Found It --
      親コメント
      • by greentea (17971) on 2004年04月12日 2時23分 (#530163) 日記
        結局は力技ですか。
        とりあえず、今のところはビット数を増やせば解けなくなるんですね。

        # 即席スパコンの人たちがこれにも挑戦したりとかないかなぁ。
        --
        1を聞いて0を知れ!
        親コメント
  • by Anonymous Coward on 2004年04月10日 12時46分 (#529549)
    なんか半端じゃない?
    • Re:なんで109ビットなの? (スコア:1, おもしろおかしい)

      by Anonymous Coward on 2004年04月10日 13時16分 (#529558)
      解読で悩ませるために煩悩の数より多くする必要があるので最低が109となるのです(USO)
      親コメント
      • by Anonymous Coward
        ECCチャレンジの最小ビット数は79ビットだった。
        もちろん、とっくの昔に解かれてます
    • たとえば「この暗号に充分な強度を持たせるために必要な数値は yxz で、その数値を表現するのに必要なビット数は 109ビットだ」と考えれば、少し理解しやすいんじゃないですかね。

      あと、仮に「君が考えた暗号を 110 ビットで使った場合と、僕が考えた暗号を 109
      • by Anonymous Coward on 2004年04月11日 14時12分 (#529988)
        先生! 109は素数なのでyxzと素因数分解できません。
        親コメント
        • 誰かもうちょっと説明してもらえませんか?
          2の109乗だと計算が面倒なので、同じ素数の5を使って、必要なyxzを30として#529828の話を考えてみると、
          「必要な数値は30で、表現するのに必要なのは5ビットだ。」
          という話で、特に矛盾も感じないし、30は5で素因数分解できるしで、#529988は#529828のどんな間違いを指摘しているのか、さっぱり分かりません。

          #という事で、#529988が素晴らしい洞察なのかどうかM2出来ませんでした。
          親コメント
  • by Anonymous Coward on 2004年04月11日 0時10分 (#529784)
    s/ponit/point/
typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond

読み込み中...