近年、楕円曲線暗号（Elliptic Curve Cryptography）は、その高い効率性と強力なセキュリティにより人気が高まっています。この記事の目的は、現在インターネット上にあるものよりも比較的分かりやすい形でこのテーマを紹介することです。
この記事では、楕円曲線とは何か、それらに対して実行できる基本的な演算、そして暗号の文脈でどのように使用できるかを説明します。記事の大部分は、誤った実装や誤った使用法に対する既知の攻撃の例で構成されています。記事全体を通して、説明を直感的で高水準な部分と、より詳細な数学的な部分に分けるようにしています。読者は、その場所で自分が興味を持った方の部分に集中し、そうでない部分は読み飛ばすことができます。
それでは、楽しくお読みください！
一般に、楕円曲線はある種の曲線です。その例として放物線があり、その方程式は $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ の形をしており、次のように見えます：
暗号の文脈では、次の形の方程式を持つ楕円曲線を使用するのが通例です。
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
例えば、方程式 $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ に対応する楕円曲線は次のように見えます：
曲線の方程式は、曲線上の点の 𝑥 座標とその 𝑦 座標の間の関係を定義します。暗号の文脈では、𝑥、𝑦、𝑎、𝑏 を整数に制限し、計算をある大きな素数を法とするものに制限します。したがって、楕円曲線の方程式は次のようになります：
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$。
これは、曲線上に有限個の点があることを意味します。数学的な言葉で言えば、この曲線は位数 𝑝 の有限体上で定義されます。その結果、すべての 𝑥 座標が必ずしも曲線上の対応する点を持つとは限りません。なぜなら、それに対応する 𝑦 座標が整数でない場合があるからです。
曲線上の点の集合は、曲線の方程式を満たす整数のペア (𝑥, 𝑦) から構成されます。これらの点に加えて、「無限遠点」と呼ばれる特別な点が定義され、𝒪 と表記されます。数学的な言葉で言えば、この点は、次のセクションで定義する加算演算に関して、曲線上の点の集合の単位元です。曲線上の点の数（点 𝒪 を含む）は「曲線の位数」と呼ばれます。
もう1つの観察として、楕円曲線は X 軸に対して対称です。つまり、点 𝑃 = (𝑥, 𝑦) が曲線上にあるならば、点 −𝑃 = (𝑥, −𝑦) も曲線上にあります。実際、これらの点は互いの「逆元」と見なされ（したがって2番目の点に −𝑃 と表記します）、それらの間の加算演算の結果は単位元 𝒪 と定義されます。
ハッセの定理と呼ばれる定理は、曲線の位数である #𝐸 の推定値を提供し、その桁は Θ(𝑝) です。より正確には：
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
曲線上の2つの点が与えられたとき、それらの間の加算演算を定義でき、その結果は曲線上の3つ目の点になります。この点を幾何学的に見つけるには、与えられた2つの点の間に直線を引き、それが曲線と3つ目の点で交差するまで延長します。この点を 𝑋 軸に関して反転させ、その結果得られる点が加算の結果として定義されます。
以下は、点 𝑃 と 𝑄 が与えられたときに、点 𝑃 + 𝑄 をどのように見つけるかを示す図です：
この説明から生じる疑問は、2つの点の間に引いた直線が再び曲線と交差しない場合はどうなるのか、ということです。この場合、直線は「無限遠」で曲線と交差すると言われ、加算の結果は点 𝒪 になります。このケースは、引いた直線が垂直である場合、つまり点 𝑃 をその逆点 −𝑃 と加算しようとしている場合に発生することに注意してください：
これから2つの基本的な恒等式が導かれます。すべての点 𝑃 に対して次のことが成り立ちます：
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
幾何学的な説明から生じるもう1つの疑問は、点をそれ自身に加算するにはどうすればよいかということです。2つの異なる点 𝑃 と 𝑄 を加算するには、それらの間に直線を引き、その延長線と曲線との交点を見るのでした。直感的には、𝑃 を固定したまま、𝑄 を 𝑃 に「どんどん近づけて」移動させるにつれて生じる直線を考え、最終的に 𝑄 が 𝑃 と重なるようにします。得られるのは、点 𝑃 において曲線にますます「接する」直線であり、𝑃 をそれ自身に加算したいときに注目するのはまさにこの直線です：
点 𝑃 をそれ自身に加算するには、点 𝑃 で曲線に接線を引き、それが曲線と2つ目の点で交差するまで延長します。この点を 𝑋 軸に関して反転させ、その結果得られる点が加算の結果として定義されます。加算の結果は 𝑃 + 𝑃 = 2𝑃 と表記するのが通例です。繰り返しになりますが、接線が曲線と2つ目の点で交差しない場合、その接線は「無限遠」で曲線と交差すると言われ、この場合の加算の結果は点 𝒪 になります。
これらの視覚的な幾何学的説明は、点の加算がどのように機能するかをうまく示し、理解を助けます。しかし、実際にはどのように計算するのでしょうか？ もちろん、数学の方程式です！
点 $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ と $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$ が与えられたとき、それらの加算の結果は点 $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ であり、以下の通りです：
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
ここで 𝜆 は、2つの点が異なる場合はそれらの点を結ぶ直線の傾き、点がそれ自身に加算される場合はその点における曲線への接線の傾きと定義されます。正式には：
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
点の加算の背後にある数学的計算は、この記事の残りの部分にとって重要ではありません。そのため、点の加算を、曲線上の2つの点を受け取り、やはり曲線上にある3つ目の点を返すブラックボックスと見なすことができます。
点 𝑃 をそれ自身に加算できることを確認し、その結果の点を 2𝑃 と表記しました。この結果に再び点 𝑃 を加算すると、3𝑃 と表記される点に到達し、以下同様です。このようにして、点をそれ自身に繰り返し加算することにより、点を定数で「乗算」することを定義できます（数の乗算と同様）：
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
一見すると、点を数値 𝑛 で乗算するには、点同士の加算を 𝑛 回実行する必要があるように思えます。なぜなら、開始点が与えられたとき、「最後」の点がどこに落ちるかを事前に知ることは難しく、「一歩一歩」到達するしかないからです。𝑛 は非常に大きくなり得るため、そのような計算は非常に非効率になります。
この目的のために、Double And Add アルゴリズムがあります。これは点 𝑃 から始め、𝑛 の2進表現の各ビットについて、現在の点を 2 倍し（つまり、それ自身に加算し）、ビット値が 1 の場合に結果に加算します。このアルゴリズムの実行時複雑性は 𝑂(log 𝑛) であり、非常に大きな数による点の乗算を効率的に行うことができます。
後で使用する点の乗算の重要な性質は、すべての点 𝑃 と数値のペア 𝑎、𝑏 に対して次が成り立つことです：
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
直感的には、点 𝑃 から始めて、そこから 𝑎 歩進み、点 𝑎𝑃 に到達するとします。この点から、「大きさ」𝑎 の 𝑏 歩進み、点 𝑏(𝑎𝑃) に到達します。あるいは、別のシナリオとして、点 𝑃 から始めて、そこから 𝑏 歩進み、点 𝑏𝑃 に到達したとします。この点から「大きさ」𝑏 の 𝑎 歩進み、点 𝑎(𝑏𝑃) に到達します。
どちらのシナリオでも、点 𝑃 から合計で同じ 𝑎𝑏 歩進んだことになるので、どちらのシナリオでも同じ最終点に到達します。数学的には、点を定数で乗算することは結合的です。
点 𝑃 から始めて、それを何度も何度もそれ自身に加算すると、各ステップで曲線上の何らかの新しい点に到達します。曲線上の点は有限個なので、ある段階で以前に到達した点に再び到達し、何らかのループ、つまり「円」に入ることになります。より正確には、ある段階で点 -𝑃 に到達し、次のステップで点 𝒪 に到達し、その次のステップで再び開始した点 𝑃 に到達します。
このような「円」を生成する点は、その「円」全体をそこから生成できるため、生成元（Generator）と呼ばれ、文字 𝐺 で表記するのが通例です。「円」内の点の数（点 𝒪 を含む）は「生成元 𝐺 の位数」と呼ばれ、通常 𝑛 で表されます。曲線上の各点は、ある種の「円」を形成します。数学的には、この「円」上の点の集合は巡回群です。
これから得られる興味深い性質は、点 𝐺 をその位数 𝑛 で乗算すると無限遠点が得られることです：
𝑛𝐺 = 𝒪
「ある 𝑥 について 𝑄 = 𝑥𝑃 となるような点 𝑃 と 𝑄 が与えられたとき、𝑥 を見つけることは困難である。」
言葉で言い換えると、誰かがある開始点から始めて、そこから一定の歩数進み、最終点に到達したとします。開始点と最終点が与えられたとき、その人が何歩進んだかをどうやって知ることができるでしょうか？
この質問に対する答えはそれほど直感的ではありません。なぜなら、開始点から歩を進めたときにどの点に到達するかを事前に予測することは難しいからです。素朴な解法としては、自分たちで 𝑃 から始めて、そこから1歩ずつ進み、𝑄 に到達するまで歩数を数えるというものがあります。この解法の複雑性は 𝑂(𝑥) であり、𝑥 が大きな数であることが分かっている場合、例えば 𝑥 が 256 bit である場合には実行不可能です。
この問題は楕円曲線離散対数問題（ECDLP）と呼ばれ、困難な問題です。しかし、どの程度困難なのでしょうか？
暗号の文脈では、問題の「困難さ」や「暗号システムの強度」を、Security Level と呼ばれる指標で測定するのが通例です。この指標では、最良の既知の攻撃が $𝑂(2^𝑛)$ ステップで問題を解く場合、その問題は「𝑛 ビットのセキュリティ」を持つと言われます。
現在、ECDLP問題を解く最良のアルゴリズムは、$𝑂(\sqrt n)$ の複雑性でそれを解きます。ここで 𝑛 は点 𝑃 の位数であり、Meet In The Middle攻撃を使用します。十分に大きな位数を持つ点が選択された場合、それを解くことは実行不可能であり、それがこの問題の強度となります。
例えば、256 bit の大きさの 𝑛 を選択すると、ECDLP問題のセキュリティレベルは 128 bit セキュリティになります。比較として、整数分解問題に基づくRSA暗号で同じ 128 bit セキュリティを達成するには、3072 bit の大きさの公開鍵が必要です。このことにより、楕円曲線の使用は比較的計算効率が高くなります。
これまで楕円曲線の世界への導入を見てきましたが、次に暗号の文脈でそれらを用いて何ができるかを見ていきます。ご存知の通り、暗号システムは通常、解くのが困難な「困難な問題」に基づいています。例えば、前述した数の因数分解問題を用いるRSAや、離散対数問題を用いるDiffie-Hellmanプロトコルなどです。楕円曲線上のECDLP問題に基づく暗号システムは、楕円曲線暗号（Elliptic Curve Cryptography）ファミリー、略してECCに属します。
まず、ある物語から始めましょう。あなたがパーティーにいると想像してください。部屋は人でいっぱいで、誰もが誰とでも話すことができ、誰もが全員の話を聞いています。この部屋には、これまで一度も会ったことのないアリスとボブもいます。アリスはボブが好きで、デートに誘いたいと思っています。アリスは少し恥ずかしがり屋なので、他のパーティー客に聞かれることなく、この秘密のメッセージをボブに伝えたいと思っています。アリスとボブは事前に何も打ち合わせておらず、アリスがボブに言うことはすべて、パーティーの他の客全員に聞かれてしまいます。アリスはどうやって他の誰にも聞かれずにメッセージをボブに伝えられるでしょうか？
「楕円曲線」と答えたなら、正解です！
