2019年12月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
無料ブログはココログ

« ICISC 2009: Accepted Papers | トップページ | ISEC 研究会(2009年12月): プログラム »

Breaking ECC2K-130

IACR ePrint Archive"Breaking ECC2K-130" というプレプリントが公開されました (via Xagawaさん)。著者名から類推するに、SHARCS 2009発表された話の流れにある研究なのでしょう。内容としては、Certicom ECC Challenge Problem の1つである ECC2K-130 を解くぞ!という宣言論文でして、実際に解けたわけではありません。ただし、最後の節に「2010年前半には解ける(解きたい)」とありますので、注意は必要でしょう。実はこのプレプリント、著者名なしの版が数日前に公開されていて、その筋では話題になっていたのでした (via Xagawaさん)。

ざっと読んだ限りでは、このプレプリントは ECC2K-130 をλ法によって解こうとしていて、各種パラメータの最適値を算出し、繰り返し関数 (Iteration 関数) をさまざまな CPU, Cell, GCPU, FPGA で実装した場合の速度を測定、実際に解いた場合の必要時間を予測しています。アプローチ自体は極めてオーソドックスなのですが、著者数23人という人数に気合いの入れようを感じてしまいます。ヘッダーの "Everyone" もなかなかおちゃめで良いですね。

せっかくなのでもう少しコメントしておきましょう。CSS 2009 でダメ出しをくらったことですし。

公開鍵暗号というとRSA暗号が有名ですが、最近では楕円曲線暗号(ECC)が利用される場面が増えてきました。RSA暗号の背後に素因数分解問題があるように、楕円曲線暗号の背後には楕円曲線離散対数問題(ECDLP)という問題があり、ECDLP は簡単に解けないという予想が楕円曲線暗号の安全性を支えています。

セキュリティ系のベンチャー企業である Certticom 社は、楕円曲線暗号の普及を図っており、楕円曲線暗号の安全性をアピールする目的で、Certicom ECC Challenge という ECDLP のチャレンジ問題を公開しています。チャレンジ問題は3段階 (Excercise, Level I, Level II) に分かれており、Excecise は文字通り練習問題のレベル、Level I は頑張って解けるレベル、Level II は相当に頑張っても当面は解けないであろうレベルとなっています。具体的なチャレンジ問題には ECC*-XX という見出しがついていて、* は ECDLP が定義されている有限体・楕円曲線の種類に応じて 2 (標数2の体), 2K (標数2の体における Koblitz 曲線), p (素体) となります。また XX は定義体のサイズとなります。2009年11月10日の時点で、Certicom ECC Challenge の解読状況は以下のようになっています。なお全ての問題は1997年11月に公開されました。

2-79 1997年12月 (設定なし) p-79 1997年12月
2-89 1998年02月 (設定なし) p-89 1998年01月
2-97 1999年09月 2K-95 1998年5月 p-97 1998年03月
2-109 2002年11月 2K-108 2000年04月 p-109 2002年10月
2-131 (未) 2K-130 (未) p-131 (未)
2-163 (未) 2K-163 (未) p-163 (未)
2-191 (未) (設定なし) p-191 (未)
2-239 (未) 2K-238 (未) p-239 (未)
2-359 (未) 2K-358 (未) p-359 (未)
表からわかるかどうかわかりませんが、今回のプレプリントのターゲット問題は「次に解くならこの問題」に位置づけられています。すぐに解けるわけではないでしょうが、状況は Twitter で報告されるらしいので、見守りたいと思います。

« ICISC 2009: Accepted Papers | トップページ | ISEC 研究会(2009年12月): プログラム »

楕円曲線暗号」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: Breaking ECC2K-130:

« ICISC 2009: Accepted Papers | トップページ | ISEC 研究会(2009年12月): プログラム »

リンク