Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

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

一つ前の記事

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

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

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

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

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

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

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

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

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

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

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

参考文献:

代数学から学ぶ暗号理論: 整数論の基礎から楕円曲線暗号の実装まで

代数学から学ぶ暗号理論: 整数論の基礎から楕円曲線暗号の実装まで

暗号理論入門 原書第3版

暗号理論入門 原書第3版

楕円曲線論入門

楕円曲線論入門

暗号技術入門 第3版

暗号技術入門 第3版

余談

こちら、ドイツ軍のエニグマ暗号を解読したアランチューリングに関する書籍とそれを映画化したものです。
暗号に関するモチベーションが上がること間違いなしなので、お勧めします。

エニグマ アラン・チューリング伝 上

エニグマ アラン・チューリング伝 上

エニグマ アラン・チューリング伝 下

エニグマ アラン・チューリング伝 下