公開秘密鍵方式

質問

素因数分解の困難さを利用したRSA方式は理解できましたが
楕円曲線を利用する方式はもっと短い鍵で同レベルの安全性を確保できるようです。そこで次のことに興味が出てきました。
1.楕円曲線の離散対数問題とはその概要
2.RSAと比べて、鍵の量はどの程度で済むのでしょうか？
高校レベルの数学で何とか分かるように説明をいただけないでしょうか

http://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7

回答No.1

Tacosan · ベストアンサー

そもそも楕円曲線を使って暗号システムを作るときには, 楕円曲線上の 2点 P, Q に対する「加算」P+Q をもとに「スカラー倍」mP (m は整数) という演算を定義します. で, P と Q = mP から m を求めるという問題が「楕円曲線上の離散対数問題」です. どこが「対数」なのかよくわからないかもしれませんが, RSA では a, b に対し「乗算」ab から「べき乗」a^m を定義し, これに基づいて暗号システムを作っています. で, この場合 a と b = a^m から m を求める計算が「離散対数問題」なので, 問題の本質は (「乗算」を「加算」に, 「べき乗」を「スカラー倍」に読み替えると同じ) です.
ただし, (一般的な場合には) index calculus という「普通の離散対数問題に対しては準指数時間アルゴリズムとなる方法」が使えないようなので, その分だけ「短い鍵でも安全」ということになります.
2. で, RSA に比べると「力ずくで解こうとしても時間がかかる」分「安全」といわれるわけですが, だいたい RSA などの 1/6 程度とされているんじゃないかなぁ. 今だと RSA の 1024bits に対して ECDH とかでは 160bits とかではないかな.

お礼

ありがとうございます。
お礼が遅くなり済みませんでした。
何となく分ったような気がします。