「解読に数十万年かかるとされた暗号、148日で解読される」記事へのコメント

より詳細な情報

[Anonymous Coward]

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

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

詳しい人教えて？

[Anonymous Coward]

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

Re:詳しい人教えて？

[Anonymous Coward]

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

問題設定と解読結果：
問題の設定としては、まず、有限体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を解読され、えらい目にあったのは記憶に新しい所。

Re:詳しい人教えて？

[shesee (27226)]

どっちかというと923bit程度の離散対数問題を元にした暗号の実装はちょっと工夫すればコア数とメモリもりもりのブルートフォースに耐えられないよってだけの話ではないかと。RSAも512bitはすでに安全ではないとされてますし、ペアリングも運用では2000bit以上使うんじゃないでしょうか