楕円曲線上の離散対数問題(ECDLP)

一つ前の記事

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding

で有限体 $F_{p}$ での楕円曲線の群構造をpythonを使って実験的に調べました。
分かったことは、
- 群の位数=群の元の個数=有理点の個数(無限遠点を含む)である。
- 群の位数は必ずしも素数ではない、むしろそうでない場合が多い。
- 有理点の位数は群の位数の約数になるっぽい。

ここで、
有理点の位数(もしくは群の元の位数)の定義は、
有理点Pをn個加算した時に初めてO(無限遠点)になることです。

楕円曲線上の離散対数問題(Elliptic Curve Discrete Logarithm Problem)を定義します。

離散対数問題の解説はこちら離散対数問題(Discrete Logarithm Problem)とは - Pebble Coding

有限体 $F_{p}$ 上の楕円曲線の２つの元(有理点)であるH,Gに対して、
H=xG (つまりGをx回加算する)となるxが存在するならxを求めよ。
という問題です。

各種攻撃法はいくつかありますが、攻撃を回避するように注意して設定すれば、
問題ありません。

この群の位数(有理点の数)は必ずしも素数である必要はありません。
群の位数Nが例えばN=8rだとします。
rは $2^{160}$ くらいの大きな素数とします。

有理点の位数は群位数の約数になるので、
2, 4, 8, r, 2r, 4r, 8r
の7パターンのどれかとなりますが、2, 4, 8 の点を選ぶのは論外なので、
r, 2r, 4r, 8r のどれかの点をGとして選びます。
そうすれば、ECDLPの強度としては十分だと言えます。

実際に
Edwards-Curve Digital Signature Algorithm (EdDSA)
のRFC8032ではベースポイントGをこのように選ぶようにと記載されています。
RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)

このような楕円曲線をどのように選べば良いのでしょうか？
加算の計算が高速にできるものを選ぶ必要もあります。
この問題は暗号学者でない我々にとってはあまり気にする必要はありません。
というのも、現在普及しているEd25519は、
楕円曲線の形、有限体、ベースポイント(ベースポイントの位数)、の全てがほぼ決まっておりRFCとなっているからです。
opensslなどにはすでに実装されていますし、各種言語のライブラリにもそのうち実装されるでしょう。

参考文献: