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のコリジョンを探していた。現在は暫定解答として、チャレンジの主催者に連絡し、確認を待っているところだ。
1へぇ (スコア:2, 参考になる)
1985年にKoblitz氏とMiller氏がほぼ同時に独立に考案した公開鍵型の暗号方式。楕円曲
線と呼ばれる数式によって定義される特殊な加算法に基づいて暗号化・復号化を行なう暗
号方式。解読の困難さは、楕円曲線上の離散対数問題を解くのと同程度と言われ、効率の
よい解読法はまだ発見されていない。短い鍵で高い安全性が確保でき、また計算も高速に
行なうことができる。1024ビットの鍵を使うRSA暗号と同程度の安全性を、楕円曲線暗号
では160ビットで実現することができる。また、暗号化・復号化はRSA暗号に比べ約10倍
高速であると言われている。 [e-words.jp]
楕円曲線暗号 [faireal.net]
検索したら記事が出てきた
109ビットの楕円曲線暗号が解読 2000/04/14 [impress.co.jp]
#暗号って数年持てばいい方なんですかね?
Re:1へぇ (スコア:1, 興味深い)
ecc で 109 bit ってのは、強度的に RSA 1024bit よりも下。
実運用では誰も使わない。
現時点で弱い暗号の部類に入る 56bit DES の鍵長を、
わざわざ短くして 40bit DES にしたようなもの。
やぶられて当然。
てゆーか、破られてナンボの challenge なんだし。
Re:1へぇ (スコア:0)
妄想というかヨタ (スコア:2, おもしろおかしい)
yp
Re:1へぇ (スコア:0)
それは、暗号化したい内容によるのでは。
たとえば、重要な内容を含む暗号通信を、盗聴されたとすると、
盗聴内容は10年後に解読されうる、という状況だとすると、
10年以上秘匿にしたい情報には使えないですよね。
Re:1へぇ (スコア:1)
>10年以上秘匿にしたい情報には使えないですよね。
暗号化は所詮暗号化なので、10年以上の長い間秘匿したような情報に対して使用するものではありません
私的には、2-3年程度がほぼ破られる可能性のない妥当な隠匿期間だろうと思っています。
この隠匿期間の判断は、個人や組織によって違うと思いますが
各チャレンジの結果を参考にして決めると良いでしょう。
その考慮した隠匿期間以降に洩れても意味の無くなる情報に対して暗号は使用すべきです
暗号は時間をかければ解ける事は、過去のチャレンジでも証明されていますが、基本的に解かれる物です。
そしてその期間はコンピューターの進化によって短縮されていきます。
10年以上もの長期間保持したいのであれば、まずは通信内容が洩れないように物理的に隔離するのが先決です。
その上で暗号化をかけておくのが好ましいでしょう
#隠匿期間はかなり大幅に安全のマージンを取って居るのは判っています
#コンピューターの進化速度が予測しきれないのがその原因です
Re:1へぇ (スコア:1)
つまり、現時点で解読に10年かかる暗号が 一ヶ月弱で解読できるようになってますよ。
Re:1へぇ (スコア:0)
たとえば解読結果が『かゆ、うま』だったら‥‥
Re:1へぇ (スコア:0)
>たとえば解読結果が『かゆ、うま』だったら‥‥
そりゃ単に二重に暗号化されているだけの話しじゃん。
Re:1へぇ (スコア:1)
Re:1へぇ (スコア:0)
> ... 解読の困難さは、楕円曲線上の離散対数問題を解くのと同程度と言われ、効率の
> よい解読法はまだ発見されていない。短い鍵で高い安全性が確保でき、また計算も高速に
> 行なうことができる。1024ビットの鍵を使うRSA暗号と同程度の安全性を、楕円曲線暗号
Re: どこが「へぇ」やねん (スコア:4, 興味深い)
> よい解読法はまだ発見されていない。
これだけだと、楕円曲線暗号には疵が無いように読めるますが、一部の曲線に弱点が見つ
かっています。もちろん、実装で避けることが出来るのですが。
あと、楕円曲線暗号は鍵長の利点から小型機器などへの組み込みによく使われています。
その場合、曲線決定のパラメータが埋め込まれていることが多いのですが、これも実装が
悪いと暗号の強度が落ちます(で、実際まずいものが多いらしい)。
> 短い鍵で高い安全性が確保でき、また計算も高速に
> 行なうことができる。1024ビットの鍵を使うRSA暗号と同程度の安全性を、楕円曲線暗号
> では160ビットで実現することができる。
RSA暗号と楕円曲線暗号を並べて書いてありますが、使い方としては全然別物です。
楕円曲線暗号は鍵合意と署名にしか使えませんし。一般的にはそれで十分なのでしょう
けど、RSA暗号ならもっといろいろ面白いことが出来るのに。
> また、暗号化・復号化はRSA暗号に比べ約10倍高速であると言われている。
どこから出てきたんだろう、この10倍は。
署名で楕円曲線暗号(ECDSA)が6倍、検証では逆にRSA暗号が7倍速い。合計すると楕円曲線暗号
(ECDSA)が2倍速い。
もちろん実装によってこの数値は大きく変わるのですが、傾向は変わらないはず。
検証の回数が署名よりはるかに多い用途なら、RSA暗号の方がパフォーマンスは良いです。
# 「IT用語辞典」や「goo辞書」を鵜呑みにするのは止めて欲しい。
Re: どこが「へぇ」やねん (スコア:3, 興味深い)
そんなのぜんぜん重要じゃないでしょ。辞書サイトの DES の
項には「DES には弱鍵があるが、しばしば実装で回避している」
とか書かなきゃいかんの?
Re: どこが「へぇ」やねん (スコア:2)
>
>そんなのぜんぜん重要じゃないでしょ。辞書サイトの DES の
>項には「DES には弱鍵があるが、しばしば実装で回避している」
>とか書かなきゃいかんの?
実装として回避することに問題がないなら書かなくても問題ないと思うけど、有名なものとかは書いておいてくれるとうれしいし、実装で回避するのが難しいとき、たとえばすでにでハードが出回ってるWEPとか、は書いておいてくれないと困る。
楕円曲線暗号については、検証途中の技術という感じで辞書サイトの記述については考える余地が有るけど、まだまだみんなが持っている情報が少ないと思うので、こういう雑談の場では、そのことを説明してくれるのはうれしいです。もちろん「間違いが多すぎる」というだけではなくね。
ところでWEPはRC4が原因だけど、おなじRC4を使ってるSSLは大丈夫なの?という疑問にストレートに答えてくれる情報をぐぐってもなかなか見つけられない。これ [nikkeibp.co.jp]とかを見るに、SSLは問題ないと思ってるのですが、どうなんでしょう?
Re: どこが「へぇ」やねん (スコア:1)
こっちの記事 [itmedia.co.jp]の方が判りやすいと思います。
SSLの方には、こういう鍵生成アルゴリズムの穴は見つかっていませんが、通信時に選択されたアルゴリズムがRC4の鍵長40bitだと、力業で破られる [aiai-hiroba.com]可能性はあります。
Re: どこが「へぇ」やねん (スコア:0)
ですから、ほとんどのメーカーではRSAからドキュメントと一緒にライブラリも買ってきて、同じRSA社のライブラリが使われているという現実があります。
そのため、どのメーカーのWEP実装にも同じ脆弱性が存在する事になってしまっています。
実は
Re: どこが「へぇ」やねん (スコア:0)
> そんなのぜんぜん重要じゃないでしょ。辞書サイトの DES の
> 項には「DES には弱鍵があるが、しばしば実装で回避している」
> とか書かなきゃいかんの?
上記のコメント(#529586)の親コメント(#529553)を書いた者ですが、どうして
このような至極まっとうなコメントをマイナスモデレートするのか。
Re: どこが「へぇ」やねん (スコア:0)
>このような至極まっとうなコメント
かどうかは俺は知らんけど、他に理解できる人がいればあげてくれるよ。
たった一人の評価をいちいち気にしてちゃだめだろ。
#モデする方も、理解しかねるならマイナスモデは慎むべきだとは思うがね…。
これまでの経験上 (スコア:0, オフトピック)
逆に、議論を盛り上げたいときにそういう表現を使うと、効果的であるともいえます。
Re: どこが「へぇ」やねん (スコア:0)
一度でもそんな例を見た人はモデレートを無視して読むようになるから、気にしなくて良いですよ。(そうなった男)
Re: どこが「へぇ」やねん (スコア:2, 参考になる)
>かっています。もちろん、実装で避けることが出来るのですが。
この表現、(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 --
Re: どこが「へぇ」やねん (スコア:0, すばらしい洞察)
一般人には、「IT用語辞典」で言っていることと、
「あなた」が言っている事に違いはありません。
専門家にとって大きな違いであっても、一般人
バカはコメントするな。 (スコア:1, すばらしい洞察)
Re: どこが「へぇ」やねん (スコア:0)
Re: どこが「へぇ」やねん (スコア:0)
発言の趣旨がよくわかっていないので的外れなことを言っているかも知れませんが、Elliptic Curve ElGamalというのがあって、それは楕円曲線上でElGamal暗号を形成するので、それで
Re:1へぇ (スコア:1, すばらしい洞察)
Re:1へぇ (スコア:1, すばらしい洞察)
どこが間違えているのかの指摘か,何を読めば その間違いが分かるのかが書いてあると助かります.
Re:1へぇ (スコア:0)
Re:1へぇ (スコア:0)
Re:1へぇ (スコア:1)
その逆は何かを復号にするわけではないので復号*化*は
日本語としておかしい、ということでしょう。
Re:1へぇ (スコア:0)
まあ、平文化、あたりかな。
「復号化」ではなくて「復号する」と動詞で使えば良いんだろうけどね。
で、今回は (スコア:1)
それとは別の方法で解く方法を見つけたの?
1を聞いて0を知れ!
Re:で、今回は (スコア:2, 参考になる)
詳細データは見てないから分からんが、恐らく、想定通りの計算力が投入されたんじゃないかな?
-- Buy It When You Found It --
Re:で、今回は (スコア:1)
とりあえず、今のところはビット数を増やせば解けなくなるんですね。
# 即席スパコンの人たちがこれにも挑戦したりとかないかなぁ。
1を聞いて0を知れ!
なんで109ビットなの? (スコア:0)
Re:なんで109ビットなの? (スコア:1, おもしろおかしい)
騙された……… (スコア:0)
もちろん、とっくの昔に解かれてます
Re:なんで109ビットなの? (スコア:0)
あと、仮に「君が考えた暗号を 110 ビットで使った場合と、僕が考えた暗号を 109
Re:なんで109ビットなの? (スコア:1, すばらしい洞察)
Re:なんで109ビットなの? (スコア:1)
2の109乗だと計算が面倒なので、同じ素数の5を使って、必要なyxzを30として#529828の話を考えてみると、
「必要な数値は30で、表現するのに必要なのは5ビットだ。」
という話で、特に矛盾も感じないし、30は5で素因数分解できるしで、#529988は#529828のどんな間違いを指摘しているのか、さっぱり分かりません。
#という事で、#529988が素晴らしい洞察なのかどうかM2出来ませんでした。
Re:なんで109ビットなの? (スコア:0)
typo? (スコア:0)