楕円曲線論はじめの一歩 (14) - VIPPOOL開発者ブログ

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、楕円曲線上の有理点がなす群が、有限巡回群である、というお話をしました。

「楕円曲線論」としてはこのくらいにしておいて、
そろそろ「楕円曲線暗号」に応用していくお話をして、
この連載を〆ようかと思います。

有限体上で定義される楕円曲線

これまで、楕円曲線は暗黙のうちに実数上で定義して、
その中の有理点について見てきました。

つまり、x 座標、y 座標ともに実数で考えれば、グラフに滑らかな曲線を描けるし、
その中で x 座標と y 座標がともに有理数になる点についてのみ考えてきたわけです。

これまでの知見を楕円曲線暗号として活用しようとすると、
コンピュータでは真の意味での実数は扱えないし、
有理数は桁が無限に必要という問題があります。

そこで、有限体上で楕円曲線を定義することを考えます。

有限体で定義した楕円曲線なら、扱う数は全て有限体の元なので、
固定長の自然数（ここでは 0 を含む）として扱えるため、
コンピュータで計算するにはうってつけなのです。

「楕円曲線を有限体上で定義する」とはどういうことでしょうか。

楕円曲線の定義は $y^2=x^3+ax+b$ の形の方程式でした。
「ここで出てくる全ての係数、変数が、有限体の元であるとする」
というわけです。

例えば、y は有限体の元なので、 $y^2$ は、
有限体の位数を p としたとき、 $y^2 \bmod p$ で計算します。
a も x も有限体の元なので、 $ax$ は $ax \bmod p$ で計算します。

これならコンピュータで扱いやすそうですね。

で、今まで有理点にこだわってきた理由ですが、
実は、実数上で定義された楕円曲線の解（つまりグラフの点）の中でも、有理点には、
有限体上で定義された楕円曲線でも対応する点がある、という事実があります。

つまり、今まで有理点について考えてきたお話が、
すべて、有限体上で定義された楕円曲線についても通用するというわけです。

楕円曲線上の有理点について考えることは、
楕円曲線暗号にも役立つ、というわけです。

楕円曲線上の有限巡回群と ECDLP

楕円曲線上の有理点は有限巡回群をなす、というお話は前回しました。
これは、有限体上で定義された楕円曲線においても通用します。

楕円曲線のパラメータと、ベースポイントとなる点 G が公開されていて、
秘密の値、x をランダムに決めたとき、G を x 倍した点、 $P=xG$ を計算することは簡単です。

愚直に x 回足すと、x のビット数 l に対して最大 $2^l-1$ 回の足し算を行う必要がありますが、
バイナリ法を使えば $2l$ 回の足し算で済みますから。

じゃあ、逆に、G を何倍かした値 P が与えられたとき、それが G を何倍した値なのか、
つまり、P から秘密の値 x を求めるにはどうするかと言うと、愚直にやって $2^l-1$ 回の足し算、
もしくは、現在知られているもっと効率の良い方法を使っても、指数関数になる回数の足し算が必要になります。
つまり、「逆は難しい」のです。

この後者でお話した問題、秘密の値 x を求めることを、ECDLP、楕円曲線上の離散対数問題と呼びます。

楕円曲線暗号は、前者が簡単で後者が難しい（現実的な時間で解けない）ことを仮定して設計されています。