No.316 - 高校数学で理解する楕円曲線暗号の数理（２）

（前回のNo.315より続く）

---

16. 楕円曲線上の点

---

有限体 ${\mathbb{F}}_p$ の元 $x$ と $y$ のぺア $\left(x,y\right)$ の集合を ${\mathbb{F}}_p^2$ と記述します。集合 ${\mathbb{F}}_p^2$ の元で楕円曲線上の "点" はどれだけあるでしょうか。まず、楕円曲線の式を満たす ${\mathbb{F}}_p^2$ の元がどのように計算できるかを調べます。

平方数と平方根

楕円曲線の式を、

$\{\begin{array}{l}{y}^2=z\\ z=x^3+ax+b\end{array}$

と書くとき、$z$（$z\ne 0$）が ${\mathbb{F}}_p$ での平方数なら、$y$ の解が２つ求まります。ここで、次の命題が成立します。

16.1	平方数である条件
$z$ を $0$ ではない ${\mathbb{F}}_p$ の元とする。 $z^{{\displaystyle \frac{p-1}{2}}}=1$ であるとき（かつ、そのときに限り）$z$ は平方数である（＝ オイラーの規準）。

${\mathbb{F}}_p$ で考えているので「平方数」と書きましたが、整数の世界では「平方剰余」です。つまり、$x^2=a\left(modn\right)$ となるような $x$ が存在する $a$ が平方剰余です。16.1 の証明ですが、${\mathbb{F}}_p$ から $0$ を除いた乗法群 ${\mathbb{F}}_p^{\ast }$ で考えます。12.1（No.313）により、$z$ は ${\mathbb{F}}_p^{\ast }$ の生成元（の一つ）を $g$ として、

$z=g^k$

と表現できます。つまり、命題の条件は、

$g^{k{\displaystyle \frac{p-1}{2}}}=1$

です。このとき $k$ は偶数のはずです。なぜなら、もし $k$ が奇数だとすると、$k{\displaystyle \frac{p-1}{2}}$ は $p-1$ で割り切れないので、

$$\begin{gathered} k{\displaystyle \frac{p-1}{2}}=s\left(p-1\right)+t \\ \left(1\le t<p-1\right) \end{gathered}$$

と表現できます。すると、

$\begin{array}{ll}{g}^{k{\displaystyle \frac{p-1}{2}}}& =g^{s\left(p-1\right)+t}\\ & ={\left(g^{p-1}\right)}^s·g^t=g^t\end{array}$

となり、$g^t=1\left(1\le t<p-1\right)$ になりますが、これは $g$ が生成元であることと矛盾します。従って $k$ は偶数です。そうすると $k=2m$ とおいて、

$z={\left(g^m\right)}^2$

となり、$z$ は平方数になります。

---

$z$ は平方数だとわかったとき、実際に ${\mathbb{F}}_p^{\ast }$ で $y$（＝ $z$ の平方根）を求める手段が必要になります。整数であれば平方数の平方根を求めるのは容易ですが、${\mathbb{F}}_p^{\ast }$ ではそうはいきません。特に、楕円曲線暗号で使われる $p$ は10進数で数10桁以上の巨大素数なので、総当たりで求めたり、解の存在範囲を限定していって求めるわけにはいかないのです。ただ、もし $p\equiv 3\left(mod4\right)$ なら求めるのは容易で、

$y=z^{{\displaystyle \frac{p+1}{4}}}$

が解の一つとなります（もう一つの解は $-y$ で、つまり $p-y$）。確認してみると、

$\begin{array}{ll}{y}^2& ={\left(z^{{\displaystyle \frac{p+1}{4}}}\right)}^2=z^{{\displaystyle \frac{p+1}{2}}}\\ & =z^{{\displaystyle \frac{p-1}{2}}}·z=z\end{array}$

となって、確かに $y$ が解であることがわかります。しかし、$p\equiv 1\left(mod4\right)$ なら、このような簡便な式では求まりません。この場合は「トネリ - シャンクスのアルゴリズム」で解を求めます（Tonelli は19世紀イタリア、Shanks は20世紀米国の数学者）。なお、このアルゴリズムは説明が長くなるので割愛します。

---

いま、${\mathbb{F}}_p$ において $z$ を $0$ から $p-1$ まで振ったときの $y^2=z$ の解の総数を求めてみます。$z$ を、${\mathbb{F}}_p^{\ast }$ の生成元 $g$ を使って、

$$\begin{gathered} z=\{\begin{array}{l}0\\ g^k\end{array} \\ \left(k=1\text{, }2\text{, }\text{ ⋯ }\text{, }p-1\right) \end{gathered}$$

と表すと、

・	$z=0$ のとき、解は1個
・	$k$ が偶数のとき、解は2個
・	$k$ が奇数のとき、解は無し

となり、${\mathbb{F}}_p^2$ における解、$\left(z,y\right)$ の総数は $p$ となります。では、${\mathbb{F}}_p^2$ における楕円曲線上の点、$\left(x,y\right)$ の総数はどうなるでしょうか。$x$ が ${\mathbb{F}}_p$ の全ての元に渡るとき、$z$ が ${\mathbb{F}}_p$ で均等にバラつくとは限りません。しかし $\left(x,y\right)$ の総数は「だいたい $p$ に近い値」だと考えられます。

つまり、群 $E\left(a,b,p\right)$ の元で、零元 $O$ 以外の ${\mathbb{F}}_p^2$ に属するものは、だいたい $p$ 個あると考えられる。群 $E\left(a,b,p\right)$ の元の数を $\text{\#}E$ と書くと、$\text{\#}E$ は 零元 $O$ を含んで $p+1$ に近い値だと考えられます。

$E\left(a,b,p\right)$ の元の数を評価する式があります。「ハッセの定理」です（Helmut Hasse は20世紀ドイツの数学者）。この定理にによると、

$p+1-2\sqrt{p}\le \text{\#}E\le$$p+1+2\sqrt{p}$

であり、想定どおり $\text{\#}E$ は $p+1$ の周辺であることが分かります。$\text{\#}E$ を具体的に求めるアルゴリズムは、1985年にオランダ出身の数学者、レネ・ショーフ（ Rene Schoof。英語読みでスクーフとも書かれる）が開発しました。その「ショーフのアルゴリズム」は、数学用語で言うと最初の「決定論的多項式時間アルゴリズム」です。平たく言うと「計算結果が100%正しいと数学的に保証される（＝決定論的）計算可能な（＝多項式時間）アルゴリズム」です。「ショーフのアルゴリズム」の具体的内容は、ここでは割愛します。

---

17. 位数

---

楕円曲線暗号を構成する上で必要になるのが、有限群における「位数」の概念です。以下の位数の話はすべての有限群に共通するので、群の演算を乗法的に書くことにします（掛け算、冪乗、単位元 $e$、などの記法を使います）。No.315 でやったように、演算を加法と考えても全く同じことになります。

元の数が有限個の群 $G$ を「有限群」といい、その元の個数を「群位数（group order）」と呼びます。群位数を $\text{|}G\text{|}$ と表します。群の演算則だけから次のことが言えます。

単位元 $e$ でない群 $G$ の元を $a$ とします。$a$ の冪乗 $a^n\left(1\le n\right)$ の $n$ を増やしていくと、ある時点で $a^n=e$ となります。その理由ですが、

$a^1\text{, }{a}^2\text{, }\text{ ⋯ }\text{, }{a}^{\text{|}G\text{|}}$

という $\text{|}G\text{|}$ 個の元を考えてみます。もし $\text{|}G\text{|}$ 個が全て相異なると、どれかが $e$ のはずです。全てが相異なる元ではないとき、

$a^j=a^i\left(1\le i<j\le \text{|}G\text{|}\right)$

となったとすると、両辺に $a$ の逆元を $i$ 回掛けて、

$a^{j-i}=e$

が得られます。$1\le j-i<\text{|}G\text{|}$ なので、この範囲に $e$ があります。そこで、つぎのように元 $a$ の位数を定義できます。

17.1	位数の定義
有限群 $G$ の任意の元 $a$ について、 $a^d=e$ となる最小の$d$ を $a$ の "位数（order）" と言う。

さらに、元の位数については次の命題が成り立ちます。

17.2	位数と群位数
有限群 $G$ の任意の元 $a$ の位数を $d$ とすると、$d$ は群位数 $\text{|}G\text{|}$ の約数である。

これはラグランジュの定理と呼ばれるものです。この定理が成り立つ理由は次の通りです。有限群 $G$ の任意の元を $a$ とし、集合 $A$ を、

$A=\left\{a^1,a^2,\text{ ⋯ },a^d=e\right\}$

とします。集合 $A$ の元は全て相異なります。なぜなら、もし、

$a^j=a^i\left(1\le i<j\le d\right)$

となったとすると、両辺に $a$ の逆元を $i$ 回掛けて、

$a^{j-i}=e$

となり、$d$ が $a^d=e$ となる最小の数であるという位数の定義に反するからです。さらに、集合 $A$ の任意の元の逆元は集合 $A$ に含まれます。つまり、$a^d=e$ なので $a^j\left(1\le j<d\right)$ に対して $a^{d-j}\left(1\le d-j<d\right)$ が逆元です（ということは集合 $A$ もまた群であり、これを $G$ の部分群と言います）。

集合 $A$ が $G$ の全ての元を尽くしているなら 17.2 は成立します。そこで、集合 $A$ に含まれない $G$ の元があったとし、それを $b_1$ とします。集合 $A$ の全ての元に左から $b_1$ を掛けて、集合 $B_1$ を作ります。つまり、

$B_1=\left\{b_1{a}^1,b_1{a}^2,\text{ ⋯ },b_1{a}^d\right\}$

です。集合 $A$ の元は全て相異なるので、集合 $B_1$ の元も全て相異なります。さらに、集合 $B_1$ の元で集合 $A$ の元と同じものはありません。なぜなら、もし、

$b_1{a}^i=a^j\left(1\le i<j\le d\right)$

だとすると、$a^i$ の逆元、$a^{d-i}$を右から掛けて、

$$\begin{gathered} b_1{a}^d=a^{d-i+j} \\ {b}_1=a^{d-i+j}=a^{j-i} \end{gathered}$$

となりますが、$1\le j-i<d$ なので、これは $b_1$ が集合 $A$ の元であることを意味していて仮定に反します。つまり、集合 $B_1$ の元で集合 $A$ の元と同じものはありません。

集合 $A$ と $B_1$ で $G$ の元の全てを尽くしているなら、$2d=\text{|}G\text{|}$ となって 17.2 は証明できたことになります。そうではない場合、集合 $A$ と $B_1$ に含まれない $G$ の元の一つを $b_2$ として、集合 $B_2$ を、

$B_2=\left\{b_2{a}^1,b_2{a}^2,\text{ ⋯ },b_2{a}^d\right\}$

と定義します。そうすると先ほど同じように、集合 $B_2$ の元は全て相異なり、かつ、集合 $A$ との重複はありません。さらに、集合 $B_2$ の元は集合 $B_1$ の元とも重複しません。なぜなら、もし、

$b_2{a}^i=b_1{a}^j\left(1\le i<j\le d\right)$

だとすると、$a^i$ の逆元、$a^{d-i}$を右から掛けて、

$b_2=b_1{a}^{d-i+j}=b_1{a}^{j-i}$

となりますが、$1\le j-i<d$ なので、$b_2$ が 集合 $B_1$ の元という意味になり仮定に反します。つまり、集合 $B_2$の元は集合 $B_1$ の元と重複しません。

以上の操作は $G$ の元が残っている限り $B_3{B}_4\text{ ⋯ }$ と続けられます。そしてある時点で 残っている $G$ の元がちょうど切りのよいところで無くなるはずです。$B_{n-1}$ まで作ったときに $G$ の元の全てを尽くしたとしたら、$nd=\text{|}G\text{|}$ です。これで 17.2 が証明できました。17.2 から直ちに次の２つが結論づけられます。

17.3
有限群 $G$ の任意の元 $a$ について、 $a^{\text{|}G\text{|}}=e$ である。

これは、群位数 $\text{|}G\text{|}$ が 元 $a$ の位数の倍数なのでそうなります。$p$ を素数とし、$G$ が $p$ 未満の自然数からなる乗法群 ${\mathbb{F}}_p^{\ast }$ だとすると、$\text{|}G\text{|}=p-1$ なので、フェルマの小定理（ 3.1 ）そのものです。

また、$n$ 未満の自然数で $n$ と互いに素なものの集合を $G$ とすると、$G$ は $modn$ の乗算に関して閉じた集合になり、逆元も定義できるので（2.3 参照）、群となります（＝ 既約剰余類群）。オイラー関数を用いると $\text{|}G\text{|}=\phi \left(n\right)$ と表せて、オイラーの定理（ 7.1 ）になります。

つまり 17.3 は、フェルマの小定理の一般化であると同時に、フェルマの小定理を一般化したオイラーの定理をさらに一般化したものと言えるでしょう。

17.4	群位数が素数の群
有限群 $G$ の群位数 $\text{|}G\text{|}$ が素数だとすると、 単位元 $e$ を除く $G$ の全ての元の位数は $\text{|}G\text{|}$ である。

素数の約数は $1$ と素数自身しかないので、単位元以外の元の位数は群位数に等しくなります。従って、群位数が素数の群では任意の元 $a$ の冪乗が群全体に "バラける" ことになります。

---

楕円曲線暗号の構成：スカラー倍と離散対数

---

ここから具体的な楕円曲線暗号のしくみに入ります。楕円曲線上の ${\mathbb{F}}_p^2$ の点と零元 $O$ が作る加法群を $E\left(a,b,p\right)$ とし、その群位数を $\text{\#}E$ と書きます。楕円曲線暗号では $E\left(a,b,p\right)$ における「スカラー倍」の演算を利用します。

楕円曲線上の ${\mathbb{F}}_p^2$ の点の一つを $B=\left(B_x,B_y\right)$ とし、$d$ を $B$ の位数、$n$ を $1\le n\le d$ とします。$B$ の $n$ 倍（＝スカラー倍）を $nB$ と書き、

$nB=\stackrel{\stackrel{n}{⏞}}{B+B+\text{ ⋯ }+B}$

と定義します。そして、

$nB=A$

と書くことにすると、$A$ を求める計算は、$E\left(a,b,p\right)$ の２倍式と加法式を使って可能です。例として $133B$ の場合だと、$133=2^7+2^2+1$ なので、

$133B=2^{7}B+2^{2}B+B$

となります。つまり、$E\left(a,b,p\right)$ の２倍式を７回使って、

$2^{1}B\text{, }{2}^{2}B\text{, }\text{ ⋯ }\text{, }{2}^{6}B\text{, }{2}^{7}B$

と順次計算し、加法式を２回使うと $A$ が求まります。これは $n$ がたとえ巨大数であっても可能です。$2^{256}$ は10進数で約80桁（256ビット）の巨大数ですが、それでも256回程度の２倍算と最大で256回程度の加算をすれば $A$ が求まります。このあたりは 4.2 の「冪剰余の計算アルゴリズム」と同じです。もちろん冪剰余と違って、２倍算も加算も単純な掛け算ではありません。$E\left(a,b,p\right)$ の群演算は、定義式どおりの少々ややこしい式です。しかし計算が可能なことは確かです。

スカラー倍の計算は可能ですが、その逆、つまり $A$ と $B$ を知って $n$ 求めるのは困難になります。この $n$ を求める問題を、加法群 $E\left(a,b,p\right)$ における「離散対数問題」と呼びます。離散対数問題を解くのが不可能になるのは、$B$ の位数 $d$ が10進数で数10桁以上といった巨大数の場合です。その場合、$A$ は $d$ 種のバリエーションをとるので、$n$ を求めるのは不可能になります。

位数 $d$ が巨大数である $B$ を求める方法の一つは、$p$ を巨大な素数とし、群位数 $\text{\#}E$ も素数であるような $E\left(a,b,p\right)$ を選ぶことです。そうすると 17.4 により、零元 $O$ 以外の $E\left(a,b,p\right)$ の全ての元の位数 $d$ は $\text{\#}E$ になり、その $\text{\#}E$ は $p+1$ の近辺にあるので、$B$ をどのように選ぼうとも位数 $d$ は巨大数になります。

$\text{\#}E$ が素数である $E\left(a,b,p\right)$ では、任意の元 $A$ と $B$ について、$nB=A$ となる $n$ が唯一存在することになります。このことを、

${log}_{B}A=n$

と書くと、$B$ は実数における通常の対数の "底（base）" に相当します。$B$ は $E\left(a,b,p\right)$ の元 ＝ ${\mathbb{F}}_p^2$ の元なので、$B$ を「ベースポイント（base point）」と呼びます。このペースポイントを含め、楕円曲線暗号では、

・	$E\left(a,b,p\right)$
・	$\text{\#}E$
・	$B=\left(B_x,B_y\right)$
・	$d$（$B$ の位数）

が公開されます。そして暗号化通信では、$d$ より小さい数 $k$ をランダムに選び

・	公開鍵 ： $kB$
・	秘密鍵 ： $k$

とします。公開鍵だけを知っても秘密鍵は計算できない。これが楕円曲線暗号の原理です。

---

スカラー倍のイメージをつかむため、$p$ がごく小さい数の場合で実験してみます。計算してみると、$p=29\text{, }a=-1\left(=28\right)\text{, }b=1$ のとき $\text{\#}E=37$ となって、群位数が素数になります。$y^2=x^3-x+1$ の解の一つは $\left(0,1\right)$ なので、これをベースポイント $B$ としてスカラー倍を順次計算してみると次の通りとなります。

$\left.\begin{array}{rrr}B=\text{(}& 0\text{, }& 1\text{ ) }\\ 2B=\text{(}& 22\text{, }& 10\text{ ) }\\ 3B=\text{(}& 27\text{, }& 13\text{ ) }\\ 4B=\text{(}& 9\text{, }& 24\text{ ) }\\ 5B=\text{(}& 14\text{, }& 18\text{ ) }\\ 6B=\text{(}& 11\text{, }& 25\text{ ) }\\ 7B=\text{(}& 23\text{, }& 20\text{ ) }\\ 8B=\text{(}& 12\text{, }& 8\text{ ) }\\ 9B=\text{(}& 26\text{, }& 8\text{ ) }\\ 10B=\text{(}& 2\text{, }& 23\text{ ) }\\ 11B=\text{(}& 3\text{, }& 24\text{ ) }\\ 12B=\text{(}& 1\text{, }& 1\text{ ) }\\ 13B=\text{(}& 28\text{, }& 28\text{ ) }\\ 14B=\text{(}& 5\text{, }& 18\text{ ) }\\ 15B=\text{(}& 17\text{, }& 5\text{ ) }\\ 16B=\text{(}& 25\text{, }& 17\text{ ) }\\ 17B=\text{(}& 20\text{, }& 21\text{ ) }\\ 18B=\text{(}& 10\text{, }& 18\text{ ) }\\ \multicolumn{3}{c}{}\end{array}\right|\begin{array}{rrr}19B=\text{(}& 10\text{, }& 11\text{ ) }\\ 20B=\text{(}& 20\text{, }& 8\text{ ) }\\ 21B=\text{(}& 25\text{, }& 12\text{ ) }\\ 22B=\text{(}& 17\text{, }& 24\text{ ) }\\ 23B=\text{(}& 5\text{, }& 11\text{ ) }\\ 24B=\text{(}& 28\text{, }& 1\text{ ) }\\ 25B=\text{(}& 1\text{, }& 28\text{ ) }\\ 26B=\text{(}& 3\text{, }& 5\text{ ) }\\ 27B=\text{(}& 2\text{, }& 6\text{ ) }\\ 28B=\text{(}& 26\text{, }& 21\text{ ) }\\ 29B=\text{(}& 12\text{, }& 21\text{ ) }\\ 30B=\text{(}& 23\text{, }& 9\text{ ) }\\ 31B=\text{(}& 11\text{, }& 4\text{ ) }\\ 32B=\text{(}& 14\text{, }& 11\text{ ) }\\ 33B=\text{(}& 9\text{, }& 5\text{ ) }\\ 34B=\text{(}& 27\text{, }& 16\text{ ) }\\ 35B=\text{(}& 22\text{, }& 19\text{ ) }\\ 36B=\text{(}& 0\text{, }& 28\text{ ) }\\ 37B=\phantom{\text{(}}& O& \end{array}$

群位数が素数なので $B$ の位数は $37$ となり、群位数と一致します。この計算を ${\mathbb{F}}_p^2$ の平面に表示すると次の通りです。$B$ と $36B$ は赤丸、$2B$ ～ $35B$ は黒丸です。矢印は加算を示し、赤矢印は $B+B$ と $35B+B$ の加算です。

図18：$\mathit{E}\left(\mathit{-}\mathit{1},\mathit{1},\mathit{29}\right)$（零元を除く） $\text{\#}E=37\text{, }B=\left(0,1\right)\text{, }d=37$

スカラー倍を繰り返すごとに "楕円曲線" 上の合計36点を通り、それが乱雑に変化することが分かります。

---

振り返ってみると、RSA暗号（No.311）の安全性は巨大数の因数分解の困難性に依存しているのでした。またディフィー・ヘルマンの鍵交換（No.313）は、乗法群 ${\mathbb{F}}_p^{\ast }$ における離散対数問題を解くことの困難性に依存しています。これらに使われる演算はいずれも整数の乗除算です。それに対して楕円曲線暗号に使われるのは、整数の乗除算よりは遙かに複雑な、楕円曲線上の加法群における「加算」です。ここに楕円曲線暗号の解読しにくさの要因があります。

---

実用的な楕円曲線暗号で公開するパラメータをどうやって作るか、その一例をあげます。

①  素数の大きさを決め（たとえば10進数で50～100桁程度）、素数判定法によってその大きさの素数 $p$ を求める。 ②  $p$ より小さい数、$a$、$b$ をランダムに決め、加法群 $E\left(a,b,p\right)$ の群位数 $\text{\#}E$ を計算する。 ③  $\text{\#}E$ が素数なら次へ。素数でなければ ② に戻る。 ④  $p$ より小さい数、$B_x$ をランダムに選び、$B_x$ が平方数ならその平方根 $B_y$ を求めてベースポイント $B=\left(B_x,B_y\right)$ とする。

$\text{\#}E$ が素数なので、$B$ の位数 $d$ は $\text{\#}E$ に等しくなります。なお、$\text{\#}E$ がたまたま $p$ と一致すると離散対数問題が解けることが分かっているので、③ でそのようなケースを排除しておきます。

この決め方では、群位数 $\text{\#}E$ の計算と素数判定を繰り返すことになり、多大な計算時間がかかることは想像に難くありません。しかしパラメータは１度計算すれば暗号通信の仕様として公開し、皆がそれを使えばいいわけです。最初の１回だけの計算時間より、その後の通信の安全性の方が重要です。

楕円曲線暗号のパラメータの一例を次に掲げます。secp160r1 という名称で公開されているパラメータです。群位数 $\text{\#}E$ は素数です。

secp160r1
　

$\begin{array}{lll}p& =& 1461501637330902918203684\\ & & 832716283019653785059327\\ & & \hfill \left(=2^{160}-2^{31}-1\right)\\ a& =& 1461501637330902918203684\\ & & 832716283019653785059324\\ & & \hfill \left(=p-3\right)\\ b& =& 1632357913061681105466049\\ & & 19403271579530548345413\\ \text{\#}E& =& 1461501637330902918203687\\ & & 197606826779884643492439\\ B_x& =& 4258262317238883504465415\\ & & 92701409065913635568770\\ B_y& =& 2035201141629041078739914\\ & & 57957346892027982641970\\ d& =& 1461501637330902918203687\\ & & 197606826779884643492439\\ & & \hfill \left(=\text{\#}E\right)\end{array}$

---

楕円曲線暗号版ディフィー・ヘルマンの鍵交換（ECDH）

---

ディフィー・ヘルマンの鍵共有（No.313）を、楕円曲線暗号を使って実現できます（ECDH と略称される）。鍵共有のプロセスは次のように進みます。しかるべき「公開鍵センター」が、皆が使う公開鍵として、

・	$E\left(a,b,p\right)$
・	$\text{\#}E$
・	$B=\left(B_x,B_y\right)$
・	$d$（$B$ の位数）

をオープンにして（暗号通信の仕様書として公開して）おきます。以下のスカラー倍演算はすべて ${\mathbb{F}}_p$ で行います。Alice と Bob が秘密鍵を共有したい場合、

暗号文による通信の開始にあたって、Alice は $0<k_A<d$ である乱数 $k_A$ を発生させ、$k_{A}B$ を Alice の公開鍵として（盗聴されている通信路を介して） Bob に送付

します。乱数 $k_A$ は Alice の秘密鍵として秘匿します。次に同様に、

Bob は $0<k_B<d$ である乱数 $k_B$ を発生させ、$k_{B}B$ を Bob の公開鍵として（盗聴されている通信路を介して） Alice に送付

します。もちろん $k_B$ は秘匿します。そして、

Alice は $K_A=k_A{k}_{B}B$ を共有の秘密鍵

Bob は $K_B=k_B{k}_{A}B$ を共有の秘密鍵

とします。この作り方から $K_A=K_B=K$ となるので、秘密鍵 $K$を共有できたことになり、以降はこれを使って暗号化通信（公開鍵ではない、高速な暗号化通信）を行います。使った秘密鍵は通信が終わったら捨てます。

原理は、オリジナルのディフィー・ヘルマンの鍵交換（DH）と全く同じです。ただ、オリジナルが ${\mathbb{F}}_p^{\ast }$ での離散対数問題を利用していたのに対し、ECDH は $E\left(a,b,p\right)$ での離散対数問題を利用した暗号であることが違います。

---

18. 結合則が成り立つことの検証と証明

---

前回の No.315 で、"結合則が成り立つ" ことの証明を後回しにしたので、ここに書きます。楕円曲線上の３点について、

$\left(P_1+P_2\right)+P_3=P_1+\left(P_2+P_3\right)$

となるのが結合則ですが、加法は数式で示されています。そこで数式を使って簡単な例で確かめてみます。

図15：楕円曲線の例２
$y^2=x^3-x+1$

楕円曲線として、No.315 の図15でとりあげた、

　$y^2=x^3-x+1$

を例とし、この楕円曲線上に２つの固定点と１つの任意点を取って計算してみます。使う記号は次の通りです。

$$\begin{gathered} P_1=\left(0,1\right) \\ {P}_2=\left(p,q\right)\left(q^2=p^3-p+1\right) \\ {P}_3=\left(1,1\right) \\ {P}_4=P_1+P_2 \\ {P}_5=P_4+P_3=\left(P_1+P_2\right)+P_3 \\ {P}_6=P_2+P_3 \\ {P}_7=P_1+P_6=P_1+\left(P_2+P_3\right) \end{gathered}$$
　
$P_5=P_7$ が示せれば結合則が成り立っています。以下、No.315 の加法式（第２形）、

$$\begin{gathered} P_0=P_1+P_2 \\ \{\begin{array}{ll}{x}_0& ={\lambda }^2-x_1-x_2\\ y_0& =\lambda \left(x_1-x_0\right)-y_1\\ \lambda & ={\displaystyle \frac{{x_1}^2+x_1{x}_2+{x_2}^2-1}{y_1+y_2}}\end{array} \end{gathered}$$

を使って計算を進めると次のようになります。

$\begin{array}{ll}{P}_4& =\left(x_4,y_4\right)=P_1+P_2\\ & =\left(0,1\right)+\left(p,q\right)\\ {\lambda }_4& =\frac{p^2-1}{q+1}\\ x_4& ={{\lambda }_4}^2-p\\ y_4& =-{\lambda }_4{x}_4-1\\ & ={\lambda }_{4}p-{{\lambda }_4}^3-1\\ & \\ P_5& =\left(x_5,y_5\right)\\ & =P_4+P_3=P_3+P_4\\ & =\left(1,1\right)+\left(x_4,y_4\right)\\ {\lambda }_5& =\frac{{x_4}^2+x_4}{{\lambda }_{4}p-{{\lambda }_4}^3}=\frac{p-{{\lambda }_4}^2-1}{{\lambda }_4}\\ x_5& ={{\lambda }_5}^2-x_4-1\\ & ={{\lambda }_5}^2-{{\lambda }_4}^2+p-1\\ & =\frac{-p^2+2q+3}{{\left(p+1\right)}^2}\end{array}$
途中、$x_5$ の計算で $q^2$ を $p^2-p+1$ で置き換えました。さらに、${\lambda }_4=\frac{p^2-1}{q+1}$ を使って ${\lambda }_5$ の式から ${\lambda }_4$ を消去すると、
　${\lambda }_5=\frac{-p^2+2q+3}{\left(p+1\right)\left(q+1\right)}$
となります。これを用いて $y_5$ を計算すると、

$$\begin{gathered} y_5={\lambda }_5\left(1-x_5\right)-1 \\ =\frac{p^2\left(x_5-1\right)-p\left(q+1\right)-2q{x}_5+q-3x_5+2}{\left(p+1\right)\left(q+1\right)} \\ =\frac{-2p^4-p^3\left(q+7\right)+p^2\left(3q+5\right)+p\left(q+7\right)-11\left(q+1\right)}{{\left(p+1\right)}^3\left(q+1\right)} \end{gathered}$$

となり、$P_5=\left(x_5,y_5\right)$ が求まりました。

$\begin{array}{ll}{P}_6& =\left(x_6,y_6\right)\\ & =P_2+P_3=P_3+P_2\\ & =\left(1,1\right)+\left(p,q\right)\\ {\lambda }_6& =\frac{p^2+p}{q+1}\\ x_6& ={{\lambda }_6}^2-p-1\\ y_6& ={\lambda }_6\left(1-x_6\right)-1\\ & ={\lambda }_6\left(p+2-{{\lambda }_6}^2\right)-1\\ & \\ P_7& =\left(x_7,y_7\right)=P_1+P_6\\ & =\left(0,1\right)+\left(x_6,y_6\right)\\ {\lambda }_7& =\frac{{x_6}^2-1}{y_6+1}=\frac{{\left({{\lambda }_6}^2-p-1\right)}^2-1}{{\lambda }_6\left(p+2-{{\lambda }_6}^2\right)}\\ x_7& ={{\lambda }_7}^2-x_6\\ & ={{\lambda }_7}^2-{{\lambda }_6}^2+p+1\\ & =\frac{p^2}{{{\lambda }_6}^2}-p+1\\ & =\frac{-p^2+2q+3}{{\left(p+1\right)}^2}\end{array}$

ここで ${\lambda }_6=\frac{p^2+p}{q+1}$ を使って ${\lambda }_7$ の式から ${\lambda }_6$ を消去すると、
　${\lambda }_7=-\frac{2\left(p^2+p-q-1\right)}{\left(p+1\right)\left(q+1\right)}$
となります。この ${\lambda }_7$ を使って $y_7$ を計算すると、

$$\begin{gathered} y_7=-{\lambda }_7{x}_7-1 \\ =\frac{p^2\left({\lambda }_7-1\right)-2p-\left(2q+3\right){\lambda }_7-1}{{\left(p+1\right)}^2} \\ =\frac{-2p^4-p^3\left(q+7\right)+p^2\left(3q+5\right)+p\left(q+7\right)-11\left(q+1\right)}{{\left(p+1\right)}^3\left(q+1\right)} \end{gathered}$$
　

J.H.シルヴァーマン、J.テイト 「楕円曲線論入門」

となり、$P_7=\left(x_7,y_7\right)$ が求まりました。以上の計算で、$P_5$ と $P_7$ は同じ点であることが分かり、この例では結合則が検証できました。

もちろんこれで結合則が証明できたわけではありません。しかし上の検証から分かるように、加法式によって結合則を証明するには計算が膨大になると推測できます。そこで以下は、シルヴァーマン、テイト著「楕円曲線論入門」にある証明を紹介します。

結合則が成り立つのは、楕円曲線上の加法を「３次曲線と直線の交点」で決めていることに理由があります。「楕円曲線論入門」に、結合則が成り立つことを示した次の図があります。加法群の零元 $O$ を楕円曲線上にとった場合の図です。

図11：結合則
「楕円曲線論入門」より引用

楕円曲線上に点 $P$、$Q$、$R$ をとったとき、

$\left(P+Q\right)+R=P+\left(Q+R\right)$

となるのが結合則ですが、

$$\begin{gathered} \left(P+Q\right)+R=\left(\left(P+Q\right)\ast R\right)\ast O \\ P+\left(Q+R\right)=\left(P\ast \left(Q+R\right)\right)\ast O \end{gathered}$$

です。ここで $\ast$ の記号は、$A\ast B$ と書くと $A$ と $B$ を結ぶ直線が楕円曲線と交わる点（で $A$、$B$ 以外の点）の意味です。$O$ は零元でした。従って、結合則を証明するためには、

$\left(P+Q\right)\ast R=P\ast \left(Q+R\right)$

が証明できればよいことになります。言葉で書くと、

$P+Q$ と $R$ を通る直線が楕円曲線と交わる点を $T_1$ とし、$P$ と $Q+R$ を通る直線が楕円曲線と交わる点を $T_2$ とすると、 $T_1$ と $T_2$ は同じ点である

となります。上の図はそれを表しています。以下の証明では同じことですが、次を示します。

18.1	結合則
$P+Q$ と $R$ を結ぶ直線と、$Q+R$ と $P$ を結ぶ直線の交点を $T$ とすると、楕円曲線は $T$ を通る。

これは楕円曲線上の２点、$\left(P+Q\right)\ast R$ と $P\ast \left(Q+R\right)$ が等しい（＝ 図11）ことと同じなので、以降は 18.1 が成り立つことを示します。そのためにまず、次の命題 18.2 を証明します。この証明の筋道は「楕円曲線論入門」に書かれているものです。

18.2	３つの３次曲線の交差
２つの３次曲線、$C_1$ と $C_2$ が相異なる９点、$P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_9$ を通るとする。 別の３次曲線 $D$ が ９点のうちの８点、$P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_8$ を通るとき、$D$ は $P_9$ も通る。

これは「ケーレー・バカラック（Cayley-Bacharach）の定理」と呼ばれるものです（Cayleyは英国、Bacharachはドイツの数学者。いずれも19世紀）。この定理は、

$d_1$次曲線と $d_2$次曲線が $d_1{d}_2$個の異なる交点で交わるとき、別の $\left(d_1+d_2-3\right)$次曲線が交点のうちの $\left(d_1{d}_2-1\right)$個を通ると、その別の曲線は残りの1点も通る

というもので、その３次元曲線の場合が 18.2 です。ここで言う３次曲線とは次の一般形で表される "３次曲線のすべて" であり、楕円曲線もその一部です。

[３次曲線の一般形]
$a{x}^3+b{x}^{2}y+cx{y}^2+d{y}^3+$$e{x}^2+fxy+g{y}^2+$$hx+iy+j=0$

10個の係数（＝パラメータ）、$a\text{, }b\text{, }\text{ ⋯ }\text{, }i\text{, }j$ を決めると３次曲線が一つ決まります。もちろん、各係数を定数倍した曲線は同じ曲線です。つまり、この形の３次曲線の係数は実質的に "９次元" と言えます。３次曲線なので $a\text{, }b\text{, }c\text{, }d$ のうち少なくとも一つは $0$ でないものがあります。その係数で全体を割れば、係数の数は９個になることからもわかります。つまり「相異なる８点を通る３次曲線」は無数にあります。

そこで、相異なる８点を通る３次曲線が一般的にどういう式で表現できるかを考えます。相異なる８点の座標を、

$$\begin{gathered} P_1=\left(x_1,y_1\right) \\ {P}_2=\left(x_2,y_2\right) \\ \text{⋮} \\ {P}_8=\left(x_8,y_8\right) \end{gathered}$$

とします。まず、３次曲線が $P_1$ を通るということは、10個のパラメータは次の制約条件を満足しなければなりません。

${x_1}^{3}a+{x_1}^2{y}_{1}b+x_1{y_1}^{2}c+{y_1}^{3}d+$${x_1}^{2}e+x_1{y}_{1}f+{y_1}^{2}g+$$x_{1}h+y_{1}i+j=0$

これは 10個の変数 $a$ ～ $j$ についての線型方程式（１次方程式）なので、係数を変数の前に記述しました。同様にして、３次曲線が $P_2$ から $P_8$ を通ることから７個の制約条件が得られます。これらをまとめると、

　

の、合計８つの制約条件が得られます。８個の点を通る３次曲線の10個のパラメータは、この８つの制約条件（連立１次方程式）を満たさなければなりません。ということは、$10-8=2$ で、これらのパラメータは、制約条件のない自由な２つのパラメータで表現できることになります。

たとえば $a$ と $b$ を "２つのパラメータ" に選ぶと、残りの $c$ ～ $j$ は、${\alpha }_{n}a+{\beta }_{n}b$$\left(n=c\text{ ⋯ }j\right)$ という「$a$ と $b$ の１次式」で表現できます（${\alpha }_n\text{, }{\beta }_n$ は連立１次方程式の係数で決まる値）。しかしこれでは $a=0$ かつ $b=0$ のときに、すべてのパラメータが $\mathit{0}$ という自明な解しか得られません。$x^3$ の項と $x^{2}y$ の項がない３次曲線はいくらでもありうるので、自明ではない解の中に $a=0\text{, }b=0$ となるものは当然あるはずです。つまり、${\alpha }_{n}a+{\beta }_{n}b$ の形は連立１次方程式の解の全部は表していません。

では、上記の連立１次方程式の「自明ではない解すべてを表す一般解」はどういう形でしょうか。それには８つの方程式を満たす独立な数値の組（＝連立１次方程式の解）を２組用意します。つまり無数にある解の中から２つをピックアップし、それをベクトル表現で、

$$\begin{gathered} {\mathbb{V}}_1=\left(a_1,b_1,\text{ ⋯ },j_1\right) \\ {\mathbb{V}}_2=\left(a_2,b_2,\text{ ⋯ },j_2\right) \end{gathered}$$

とします。"独立" とはこの場合、２つの数値群が異なった３次曲線を表現しているということです。そして、同時に $0$ にはならない新たな２つのパラメータを導入します。それを ${\lambda }_1\text{, }{\lambda }_2$ とすると、

${\lambda }_1{\mathbb{V}}_1+{\lambda }_2{\mathbb{V}}_2$

が連立１次方程式の一般解（不定解）になります。自由な２つのパラメータの１次式で表現されていて、８つの方程式を満たすことが明らかだからです。この一般解をもとに３次曲線の方程式を表現します。そこで、

$\begin{array}{ll}{f}_1=& a_1{x}^3+b_1{x}^{2}y+\text{ ⋯ }\\ & \text{ ⋯ }+h_{1}x+i_{1}y+j_1\end{array}$

$\begin{array}{ll}{f}_2=& a_2{x}^3+b_2{x}^{2}y+\text{ ⋯ }\\ & \text{ ⋯ }+h_{2}x+i_{2}y+j_2\end{array}$

の２つの関数を考えると、$f_1=0$ の３次曲線と $f_1=0$ の３次曲線は、共に８点を通ります。従って、

${\lambda }_1{f}_1+{\lambda }_2{f}_2=0$

は８点を通り、２つの自由なパラメータで表現された３次曲線群です。従って、これが $P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_8$ を通るすべての３次曲線を表す一般形です。

---

以上を踏まえて命題 18.2 を検討します。命題を再掲すると、

２つの３次曲線、$C_1$ と $C_2$ が相異なる９点、$P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_9$ を通るとする。 別の３次曲線 $D$ が ９点のうちの８点、$P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_8$ を通るとき、$D$ は $P_9$ も通る。

でした。この前半の２つの３次曲線の関数式を

$$\begin{gathered} C_1\text{ : }{F}_1=0 \\ {C}_2\text{ : }{F}_2=0 \end{gathered}$$

とします。$F_1=0$ も $F_2=0$ も９点、$P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_9$ を通る３次曲線です。従って $F_1=0$ と $F_2=0$ は $P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_8$ の８点を通る２つの３次曲線でもある。ということは、$P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_8$ の８点を通るすべての３次曲線は、

$F={\lambda }_1{F}_1+{\lambda }_2{F}_2=0$

で表されます。従って、命題の後半に出てくる別の３次曲線 $D$ が $P_1\text{, }{P}_2\text{, }$$\text{ ⋯ }\text{, }{P}_8$ の８点を通るとすると、$D$ は $F=$${\lambda }_1{F}_1+{\lambda }_2{F}_2$$=0$ で表現できます。

ここでよく考えてみると、３次曲線 $F=0$ は９点目の $P_9$ を通るのでした。従って $D$ も $P_9$ を通ります。これで 18.2 が成り立つことが証明できました。以上を振り返ってまとめると次のようになります。

・  ８つの点を通る３次曲線は無数に存在する。 ・  ８つの点を通る２つの３次曲線が、２つとも９つ目の（特別な）点 $P$ を通るとしたら、８点を通るすべての３次曲線は $P$ を通る。

18.2 を踏まえて、楕円曲線の加法群で結合則が成り立つことを証明します。ポイントは「相異なる３つの直線を "３次曲線" として扱う」ことです。この扱いがなぜ可能かと言うと、３つの直線を、

$$\begin{gathered} f_1=a_{1}x+b_{1}y+c_1=0 \\ {f}_2=a_{2}x+b_{2}y+c_2=0 \\ {f}_3=a_{3}x+b_{3}y+c_3=0 \end{gathered}$$

としたとき、

$F_L=f_1·f_2·f_3$=0 で表される２次元平面上の点の集合は３つの直線を表しているが、３次曲線の一般形である

からです。もちろん、$F_L=0$ の３次曲線の一般形は、係数 $a\text{, }b\text{, }\text{ ⋯ }\text{, }i\text{, }j$ に特別の関係があります。だからこそ３つの直線を表現しているわけです（数学用語で言うと "退化した" ３次曲線）。しかし特別の関係があるとしても 18.2 を証明した議論の筋道には全く影響しません。このことを踏まえて結合則を証明すべき図11を再掲します。

図11：結合則
「楕円曲線論入門」より引用

証明すべきことは 18.1 の、

$P+Q$ と $R$ を結ぶ直線と、$Q+R$ と $P$ を結ぶ直線の交点を $T$ とすると、楕円曲線は $T$ を通る。

でした。図11で、

$C_1$ ： 点線の３直線から成る３次曲線
$C_2$ ： 実線の３直線から成る３次曲線

とすると、$C_1$（点線） と $C_2$（実線）は次の９つの点を通ります。

$P_1$	：	$O$
$P_2$	：	$P$
$P_3$	：	$Q$
$P_4$	：	$R$
$P_5$	：	$P\ast Q$
$P_6$	：	$Q\ast R$
$P_7$	：	$P+Q$
$P_8$	：	$Q+R$
$T$	：	$P+Q$ と $R$ を結ぶ直線と、$Q+R$ と $P$ を結ぶ直線の交点

９つの点を通るのはそういう風に作図したからです。一方、楕円曲線は $T$ 以外の $P_1$ ～ $P_8$ の８点を通ります。８点は楕円曲線上の点として作ったからです。$T$ だけは違って、楕円曲線上の点として作ったのではなく２直線の交点です。しかし 18.2 によって楕円曲線は $T$ も通る。これで、楕円曲線上の有理点が作る加法群で結合則が成り立つことの証明が完成しました。

---

零元を無限遠点にとる加法群ではどうなるでしょうか。この場合は「射影平面での３次曲線」を考える必要があります。射影平面での３次曲線の一般形は、

[射影平面における３次曲線の一般形]
$A{X}^3+B{X}^{2}Y+CX{Y}^2+D{Y}^3+$$E{X}^{2}Z+FXYZ+G{Y}^{2}Z+$$HX{Z}^2+IY{Z}^2+J{Z}^3=0$

ですが、証明の筋道は $xy$平面と全く同じです。というのも、証明のコアのところは「10変数の連立１次方程式（方程式数が８）の不定解が、一般形でどう表現できるか」であり、曲線方程式の未知数が $\left(x,y\right)$ の２つであっても $\left(X,Y,Z\right)$ の３つであっても証明の論理に影響がないからです。

というわけで、楕円曲線暗号で実際に使われる「無限遠点を零元にした加法群」においても結合則が成り立つのでした。

---

19. パスカルの定理

---

最後に余談ですが、18.2（ケーレー・バカラックの定理）から証明できる別の定理があります。「パスカルの定理」です。これはパスカルが16歳のときに発表した「円錐曲線試論」にあります。最も一般的な形で言うと次の通りです。

19.1	パスカルの定理
円錐曲線上に異なる６点、$P_1$ ～ $P_6$ をとる。 直線 $P_1{P}_2$ と $P_4{P}_5$ の交点を $Q_1$ 直線 $P_2{P}_3$ と $P_5{P}_6$ の交点を $Q_2$ 直線 $P_3{P}_4$ と $P_6{P}_1$ の交点を $Q_3$ とすると、$Q_1\text{, }{Q}_2\text{, }{Q}_3$ は同一直線上にある。

これは美しい定理です。どんな円錐曲線かを言っていないし（円、楕円、放物線、双曲線）、円錐曲線上の６点の位置も、その順序も何も言ってない。それにもかかわらず「同一直線上にある」という、シンプルで強い断定が結論にくる ･･････。個人的経験を言うと、高校生時代にこの定理を知ってその "不思議さ" が印象的だったことを覚えています。

この定理の例を図19と図20、図21に示します。$Q_1$ を $P_7$、$Q_2$ を $P_8$、$Q_3$ を $T$ と書きました。円錐曲線が円か楕円であり、６点を円・楕円の周上に順に（＝ 一周するように）とった場合には、パスカルの定理は、

円・楕円に内接する６角形の対辺が作る２直線の交点３つは同一直線上にある

と簡潔に表現できます（図19）。図20の楕円上の点の位置は図19と同じですが、名前付けが違います。しかし３点が同一線上に並ぶのは同じです。このように６点は楕円上のどの位置にどの順序で配置してもよいわけです。

図19 パスカルの定理（１）

図20 パスカルの定理（２）

図21 パスカルの定理（３）

定理の証明は次の通りです。３次曲線、$C_1\text{, }{C}_2\text{, }D$ を、

$C_1$	：	赤色の３次曲線
$C_2$	：	青色の３次曲線
$D$	：	$P_7$ と $P_8$ を（$T$ とは関係なく）結んだ直線と円錐曲線が作る、黒色の３次曲線

とします。$C_1$ と $C_2$ は 、$P_1$ ～ $P_8$ と $T$ を通ります。そういう風に作図したからです。一方、$D$ は $P_1$ ～ $P_8$ を通ります。そうすると 18.2 より $D$ は $T$ も通ります。$D$ は $P_7$ と $P_8$ を通るように作図しましたが、$T$ を通るようには作図していません。それでも $T$ を通る。

その $T$ は、$D$ の円錐曲線部分にはありません。なぜなら、$T$ は直線 $P_3{P}_4$ 上に（ないしは直線 $P_6{P}_1$ 上に）ありますが、円錐曲線と直線の交点は高々２つであり、$P_3\text{, }{P}_4$ が（ないしは $P_6\text{, }{P}_1$ が）すでに円錐曲線上にあるからです。従って $T$ は $D$ の直線部分にあるしかない。これで証明が終わりました。

パスカルの定理のよくある証明は、円の場合に補助円を用いて証明し、それを "斜めから見たら" 楕円でも成り立つ、とするものです。しかしこの定理は、すべての円錐曲線（＝２次曲線の一般形、$a{x}^2+bxy+c{y}^2+$$dx+ey+f=0$ で表される曲線）で成り立つことが上の証明から分かります。

ちなみに、パスカルの定理は「円錐曲線」を「２直線」に置き換えても、交点ができるように点を配置すれば成り立ちます（パップスの定理と呼ばれる。パップスは４世紀のアレキサンドリアの数学者）。

図22 パップスの定理

軸を含む平面で円錐を２分割すると（平行でない）２直線になり、それは（退化した）円錐曲線とも言えますが、たとえ平行な２直線であっても２次曲線の一般形で表現できるので定理は成り立ちます。

---

楕円曲線暗号は「楕円曲線上の有理点による加法群」の上に作られた暗号ですが、

楕円曲線上の有理点で加法群を構成できることと、パスカルの定理が成り立つことには、意外にも共通の数学的理由がある

のでした。

---

---

タグ：楕円曲線 楕円曲線暗号 楕円曲線論入門 公開鍵暗号 ３次曲線 無限遠点 有理点 加法群 有限体 群 群位数 位数 平方数 平方根 平方剰余 ベースポイント ディフィー・ヘルマンの鍵交換 パスカルの定理 高校数学 パップスの定理

No.315 - 高校数学で理解する楕円曲線暗号の数理（１）

このブログでは、インターネットをはじめとする情報通信インフラで使われている「公開鍵暗号」について、今まで３回にわたって書きました。

No.310-高校数学で理解するRSA暗号の数理（１）　
No.311-高校数学で理解するRSA暗号の数理（２）　
No.313-高校数学で理解する公開鍵暗号の数理　

の３つです。今回はその継続として、公開鍵暗号の一種で広く使われている「楕円曲線暗号」について、その数学的な背景を書きます。楕円曲線暗号は、1985年に米国 IBM の Victor Miller と米国 Washington 大学の Neal Koblitz によって独立に提案されました。暗号に限らず科学技術の世界では、同時期に同じアイディアが独立に考案されるというケースが見られます。

例によって高校レベルの数学知識だけを前提にし、証明なしに用いる定理や命題はないものとします。ただし、No.310、No.311、No.313 の内容やそこで証明した定理は既知とします。特にその中の、

有限体と乗法群　
生成元、および離散対数　

です。なお、楕円曲線（Elliptic Curve）は、２次曲線である楕円（Ellipse）とは関係ありません。楕円の弧長を積分で求める時に出てくる数式なのでその名があるだけです。暗号の名を楕円暗号とするむきもありますが、誤解されるでしょう。楕円曲線暗号（Elliptic Curve Cryptography）が正しい言い方です。

---

15. 楕円曲線（Elliptic Curve）とは

---

楕円曲線とは、次の式で表される平面３次曲線です。

$y^2=x^3+ax+b$

係数の $a$ と $b$ は有理数とします。楕円曲線の式の「標準形」と呼ばれるものは何種類かありますが、上式はその最も簡単な形です。楕円曲線暗号ではこの形を使うので、以降、楕円曲線といえばこの形で表される３次曲線とします。Wikipedia に非常にわかりやすい「楕円曲線のカタログ」が載っているのでそれを引用します。

	$b=-1$	$b=\phantom{-}0$	$b=\phantom{-}1$	$b=\phantom{-}2$
$a=-2$
$a=-1$
$a=0$
$a=1$
図１：楕円曲線のカタログ
Wikipediaより。楕円曲線には曲線の "成分" が１つのものと２つのものがある。なお、この図で $a=b=0$ だけは楕円曲線ではない。後述。

図でわかるように楕円曲線は成分（＝ ひとつながりの曲線）が１つのものと２つのもの（その１つは閉じた曲線）があります。この違いは何でしょうか。また、図の中にある $a=0\text{, }b=0$ の曲線は、実は楕円曲線ではありません。このあたりの説明は以降の通りです。楕円曲線の $x$ の式を、

$x^3+ax+b=f\left(x\right)$

と書きます。$y=f\left(x\right)$ のグラフは少なくとも１回、$x$軸を横切るので、$f\left(x\right)=0$ の３次方程式は少なくとも１つの実数解を持ちます。この３次方程式が３つの異なる実数解を持つ条件を調べます。関数 $f\left(x\right)$ が極値をとるとしたら、そのときの $x$ は方程式、

$f^{\text{'}}\left(x\right)=0$

の解です。この解を $x_1$ と $x_2$ とすると、

$$\begin{gathered} x_1=\phantom{-}\sqrt{{\displaystyle \frac{-a}{3}}} \\ {x}_2=-\sqrt{{\displaystyle \frac{-a}{3}}} \end{gathered}$$

です。$x$ がこの値をとるときの２つの極値がゼロでなく符号が逆であれば、$f\left(x\right)=0$ は３つの異なる実数解をもちます。つまりその条件は、

$f\left(x_1\right)·f\left(x_2\right)<0$

です。$x_1\text{, }{x}_2$ を入れて計算してみると、この条件は、

$4a^3+27b^2<0$

となります。不等号の向きが逆なら実数解は１つだけです。この不等号の左辺は「３次方程式の判別式」の符号を逆にしたものです。３次方程式の判別式 $D$ は、いま扱っている楕円曲線の式の場合、

$D=-\left(4a^3+27b^2\right)$

です。従って、

・	$D>0$ のとき、$f\left(x\right)=0$ は３つの実数解をもち、楕円曲線で $y=0$ となる点は３つある。このとき楕円曲線の成分は２つになる（図２）。
・	$D<0$ のとき、$f\left(x\right)=0$ の実数解は１つであり、楕円曲線で $y=0$ の点も１つである。このとき楕円曲線の成分は１つになる（図３）。

となります。この２つのケースで楕円曲線をを図示すると、図２（$a=-2\text{, }b=1$）、図３（$a=-2\text{, }b=2$）のようになります。

図２：成分が２つの楕円曲線 $y^2=x^3-2x+1$

図３：成分が１つの楕円曲線 $y^2=x^3-2x+2$

ここで $D=0$ のときにどうなるかを調べてみます。不定方程式、

$4a^3+27b^2=0$

の整数解を求めるために、$a=-3k^2\left(0\le k\right)$ と置くと、

$$\begin{gathered} a=-3k^2 \\ b=\pm 2k^2 \end{gathered}$$

が解です。$k=0\text{, }1$ とすると、

$\left(a,b\right)=\left(0,0\right)\text{, }\left(-3,2\right)\text{, }\left(-3,-2\right)$

が解のうちの３組です。まず、$\left(a,b\right)=\left(0,0\right)$ のとき曲線の式は、

$y^2=x^3$

となり、図４のように「尖点」をもつ曲線となります（Wikipedia の "楕円曲線のカタログ" にあったものです）。尖点では微係数が定まらず、曲線の接線が引けません。

図４：尖点をもつ３次曲線 $y^2=x^3$

$\left(a,b\right)=\left(-3,2\right)$ のときの曲線の式は、

$$\begin{gathered} y^2=x^3-3x+2 \\ \phantom{y^2}=\left(x+2\right){\left(x-1\right)}^2 \end{gathered}$$

となり、図５のように「結節点」をもつ自己交差曲線となります。結節点において接線は引けますが、２種類あって一意に定まりません。

図５：結節点をもつ３次曲線 $y^2=x^3-3x+2$

$\left(a,b\right)=\left(-3,-2\right)$ のときの曲線の式は、

$$\begin{gathered} y^2=x^3-3x-2 \\ \phantom{y^2}=\left(x-2\right){\left(x+1\right)}^2 \end{gathered}$$

となり、図６のように $\left(-1,0\right)$ に「孤立点」が発生します。この孤立点でも接線は引けません。

図６：孤立点をもつ３次曲線 $y^2=x^3-3x-2$

尖点、結節点、孤立点を曲線の「特異点」と言い、特異点をもつ３次曲線を特異３次曲線と言います。そして特異３次曲線は $y^2=x^3+ax+b$ の形であっても楕円曲線とは言いません。つまり、楕円曲線の正確な定義は次の通りです。

15.1	楕円曲線の定義
次の式で表される平面曲線を楕円曲線と言う。 $$\begin{gathered} y^2=x^3+ax+b \\ \left(4a^3+27b^2\ne 0\right) \end{gathered}$$

この定義による楕円曲線は "なめらか" であり、曲線上の全ての点で唯一の接線が引けます。以降、この楕円曲線の性質を調べていきます。

---

楕円曲線暗号は「楕円曲線上の点の加法群」で構成する暗号です。そこでまず、No.313 でも触れた「群（group）」とは何かを復習します。

---

群の定義

---

群（$G$ で表します）とは、何らかの２項演算 "$\circ$" が定義された集合です。演算が定義されているとは、集合 $G$ の任意の２つの元（同じ元であってもよい）、$a$、$b$ を演算した結果の $a\circ b$ が $G$ の元であることを意味します。この２項演算は次の３つの条件を満たす必要があります。この「条件を満たす２項演算が定義された集合」が群 $G$ です。

（単位元）	$a\circ e=e\circ a=a$ となる元 $e$ が存在
（逆元）	$a\circ b=b\circ a=e$ となる $b$ が、任意の $a$ について存在
（結合則）	$\left(a\circ b\right)\circ c=a\circ \left(b\circ c\right)$

演算 "$\circ$" を乗算と考えるとき、$G$ を乗法群といいます。乗法群では２項演算を $a\times b\text{, }a·b\text{, }ab$ などと書きます。単位元は $1$ と書くこともあります。また、逆元 b は $a^{-1}$ です。同一の $n$ 個の元 $a$ に対して演算 "$\circ$" を $n-1$ 回行った結果は $a^n$ で「累乗（あるいは冪乗）」と呼びます。

演算 "$\circ$" を加算と考えるとき、$G$ を加法群といいます。加法群では２項演算を $a+b$ と書きます。加法群の単位元を零元と呼び、$0$ と書くことがあります。また逆元 b は $-a$ です。同一の $n$ 個の元 $a$ に対して演算 $\circ$ を行った結果は $na$で「スカラー倍」と呼びます。

乗法群か加法群かは多分に "言葉の綾" の面があり、どちらがイメージしやすいかによります。但し、加法群と言った場合は暗黙に可換則、$a\circ b=b\circ a$ が成り立つ群を言います。可換則が成り立つ群を、ノルウェーの数学者 Abel の名前をとって「アーベル群」と呼びます。もちろん「乗法」や「加法」のイメージとは結びつきにくい群もたくさんあります。

---

楕円曲線上の有理点

---

楕円曲線上の有理点からなる加法群を構成することができます。有理点とは、楕円曲線上の点、$\left(x_0,y_0\right)$ で、$x_0$ も $y_0$ も有理数の点です。一般に、楕円曲線が有理点を持つかどうかを有限回の手続きで決定する方法は知られていません。しかし、１個か２個の有理点があれば、次のような手続きで次々と有理点を見つけることができます。以下の記述では $P$、$Q$、$R$ などを有理点とし、

・	$P$ と $Q$ を結ぶ直線がふたたび楕円曲線と交わる点を $P\ast Q$（図７の左）
・	$P$ 点における接線が楕円曲線と交わる点を $P\ast P$（図７の右）

と定義します。ここでの "$\ast$" は乗算の記号ではなく「"$\ast$" の前後に書かれた楕円曲線上の点ではない、もう一つの直線と楕円曲線の交点」の意味です。

図７：楕円曲線上の有理点

J.H.シルヴァーマン、J.テイト著「楕円曲線論入門」（シュプリンガー・フェアラーク東京 1995）より引用

J.H.シルヴァーマン、J.テイト 「楕円曲線論入門」 （シュプリンガー・ フェアラーク東京 1995）

図７で、$P\ast Q$ も $P\ast P$ も有理点です。なぜなら、係数が有理数の３次曲線と直線の交点を求める式は３次方程式になりますが、３次方程式の２つの異なる根が有理数なら（左図の $P$ と $Q$）、もうひとつの根 $P\ast Q$ も有理数だからです。もう１つが有理数でないと（＝無理数や複素数）、３次曲線の係数が有理数という前提に反します。同じように３次方程式の重根（右図の $P$）が有理数だと、もう一つの根も有理数です。

つまり、楕円曲線上に１つ、ないしは２つの有理点があったとしたら、上記の操作で有理点を増やしていけます（但し有理点が無限個なのか有限個なのかは楕円曲線によります）。そこで有理点の存在を前提として以下の議論を進めます。

なお、楕円曲線暗号で使う加法群は「有限体上の楕円曲線における加法群」であり、有理点を見つけるアルゴリズムがあります（後述）。もちろん有理点の数は有限個です。

---

楕円曲線上の有理点が作る加法群

---

楕円曲線上の有理点を "群" にするためには、そこに何らかの演算を定義する必要がありますが、その定義を次のようにします。加法群なので演算を $+$ と書きます。

群演算

・	任意の有理点を零元（＝ $O$ ）とする。
・	$P$ と $Q$ を楕円曲線上の有理点とするとき、点 $P\ast Q$ と $O$ を結ぶ直線が再び楕円曲線と交わる点を $P+Q$ とする。つまり、 $P+Q=\left(P\ast Q\right)\ast O$ とする。

図８：楕円曲線上の群演算

シルヴァーマン、テイト「楕円曲線論入門」より引用。零元の記号には、英大文字 O の筆記体が使ってある。以下同様

零元

この演算における零元 $O$ が、群の零元の条件を満たしているかどうかを検証すると、

$P+O=\left(P\ast O\right)\ast O=P$

となって、零元の条件を満たしていることがわかります（図９）。もちろん、$O+P=P$ です。

図９：$\mathit{O}$ が零元であることの検証

「楕円曲線論入門」より引用

逆元

逆元は次のように定義します。零元 $O$ における接線が楕円曲線と交わる点を $S$ とします。まず、

$S=O\ast O$

です。そして 点 $Q$ と $S$ を結ぶ直線が再び楕円曲線を交わる点を、$Q$ の逆元（＝ $-Q$）とします。つまり、

$-Q=Q\ast S$

です。このように定義すると

$\begin{array}{ll}Q+\left(-Q\right)& =\left(Q\ast \left(-Q\right)\right)\ast O\\ & =S\ast O\\ & =O\end{array}$

となり、群の逆元の条件を満たすことがわかります（図10）。$S$ と $O$ を結ぶ直線は $O$ で２回交差するので、$S\ast O=O$ です。

図10：点の逆元

「楕円曲線論入門」より引用

結合則

群を構成するためには、以上の群演算の定義が結合則を満たしていななければなりません。楕円曲線上に点 $P$、$Q$、$R$ をとったとき、

$\left(P+Q\right)+R=P+\left(Q+R\right)$

となるのが結合則ですが、

$$\begin{gathered} \left(P+Q\right)+R=\left(\left(P+Q\right)\ast R\right)\ast O \\ P+\left(Q+R\right)=\left(P\ast \left(Q+R\right)\right)\ast O \end{gathered}$$

なので、

$\left(P+Q\right)\ast R=P\ast \left(Q+R\right)$

が示せればよいことになります。「楕円曲線論入門」にはこのことを示した図が載っています（図11）。

図11：結合則の検証

「楕円曲線論入門」より引用

$\left(P+Q\right)\ast R$ の点と $P\ast \left(Q+R\right)$ の点が、楕円曲線上で同一の点になることの証明は少々複雑なので「18. 結合則が成り立つことの検証と証明」にまわします。

---

以上のように楕円曲線上の有理点は、直線との交点を使って加法と逆元をうまく定義することで "群" になることがわかりました。ここで注意すべきは、零元は楕円曲線上の任意の有理点でよいことです。これを利用し「零元＝無限遠点」としたのが、実用的に使われる楕円曲線上の加法群です。

---

無限遠点を零元とする加法群

---

以下では「対称点」という言葉を使いますが、

$P=\left(x_p,y_p\right)$ とするとき、点 $\left(x_p,-y_p\right)$ を$P$ の対称点と呼ぶ

ことにします。楕円曲線は $x$軸について対称なので、点 $P$ を $x$軸で "折り返した" 点が $P$ の対称点です。$y=0$ となる点が楕円曲線上に１つ、または３つありますが、その点の対称点は同じ点です。

次に「$y$軸方向の無限遠点」を導入し、「楕円曲線上の有理点と無限遠点を合わせた集合」に群を定義します。ここからは無限遠点を $O$ と書きます。

無限遠点は図に表せないのでイメージしにくいのですが、$\mathit{y}$軸方向の無限遠に $\mathit{O}$ があると考えます。$y$ 軸の正方向でも負の方向でもかまいません。

楕円曲線上の点 $P$ を $P=\left(x_p,y_p\right)$ とし、$x_p$ をどんどん大きくすると、楕円曲線の式では $x^3$ の項が支配的になるので、${y_p}^2={x_p}^3$ と近似できます。つまり $y_p=\pm {x_p}^{\frac{3}{2}}$ となり、$x_p$ が大きいと $y_p$ は $y$軸の遙か上方（と下方）になります。この極限が無限遠点 $O$ と考えます。さらに、

楕円曲線上の任意の点 $P$ を通る $y$軸に平行な直線を引くと、その直線は $P$ の対称点で楕円曲線と交差すると同時に、無限遠点 $O$ でも交差する

と考えます。この $\mathit{y}$軸方向の無限遠点 $\mathit{O}$ を零元とする群を構成します。

群演算

まず、群演算の加法ですが、

$P+Q=P\ast Q$ の対称点

と定義します（図12）。

図12：加法則

「楕円曲線論入門」より引用

こうすると、$P\ast Q$ と $P+Q$ を結ぶ直線は $y$軸と平行になり、それは無限遠点 $O$ で楕円曲線と交差します。つまり、

$P+Q=\left(P\ast Q\right)\ast O$

です。この定義は 零元を楕円曲線上の点にとった図８と合致します。この加法の定義で $O$ が群の零元の要件を満たしているかを検証すると、

$P+O=\left(P\ast O\right)\ast O=P$

となって要件を満たしていることがわかります。$P\ast O$ は $P$ の対称点ですが、$P$ の対称点と $O$ を結ぶ直線が楕円曲線と交差する点は $P$ なので上式が成立します。これは楕円曲線上に $O$ をとった図９と同じです。さらに逆元ですが、$Q$ が楕円曲線上にあったとき、

$Q$ の対称点が $Q$ の逆元（$-Q$ と表記）

と定義します（図13）。

図13：逆元

「楕円曲線論入門」より引用

こうすると、

$\begin{array}{ll}Q+\left(-Q\right)& =\left(Q\ast \left(-Q\right)\right)\ast O\\ & =O\ast O\end{array}$

となりますが、$O\ast O=O$（＝無限遠点の対称点は無限遠点）との自然な定義を行うと、

$Q+\left(-Q\right)=O$

となって逆元の要件を満たします。結合則についても零元を楕円曲線上にとった場合（図11）と同じ様に成立します。「18. 結合則が成り立つことの検証と証明」でそのこと書きます。

射影平面

無限遠点は図で表現できず、何だか "怪しげな" 感じがしますが、数学的に厳密に定義できます。それには射影平面を使います。

平面 $\left(x,y\right)$ に対し、３つの数 $\left(X,Y,Z\right)$ で表される "平面" を射影平面と言います。３つの数がありますが３次元空間ではありません。ただし $\left(0,0,0\right)$ の点は除きます。また、

$\lambda \ne 0$とするとき
$\left(X,Y,Z\right)$ と $\left(\lambda X,\lambda Y,\lambda Z\right)$ は同じものである（同値である）

と定義します。$xy$平面から射影平面の対応は、

$\left(x,y\right)\stackrel{}{\to }\left(x,y,1\right)$

とし、その逆の対応は、

$Z\ne 0$ のとき
$\left(X,Y,Z\right)\stackrel{}{\to }\left({\displaystyle \frac{X}{Z}},{\displaystyle \frac{Y}{Z}}\right)$

です。この対応からわかるように、射影平面には $xy$平面にない点が含まれています（$Z=0$ の点）。

射影平面での楕円曲線の式は、$xy$平面の楕円曲線の式で、$x={\displaystyle \frac{X}{Z}}\text{, }y={\displaystyle \frac{Y}{Z}}$ とおき、全体に $Z^3$ をかけて同次化（＝変数項の合計次数をそろえる）します。その結果、

$Y^{2}Z=X^3+aX{Z}^2+b{Z}^3$

の同次方程式が、射影平面での楕円曲線になります。ためしに、図２の楕円曲線（$a=-2\text{, }b=1$）と $y$軸との交点を計算してみると、$xy$平面では、

$\{\begin{array}{l}{y}^2=x^3-2x+1\\ x=0\end{array}$

の連立方程式を解いて、$\left(0,\pm 1\right)$ となります。一方、射影平面では、$x=0$ は $X=0$ なので、

$\{\begin{array}{l}{Y}^{2}Z=X^3-2X{Z}^2+Z^3\\ X=0\end{array}$

が、楕円曲線と直線の交点を求める連立式になります。この解は、$\alpha$ と $\beta$ を $0$ ではない数として、$\left(0,\alpha ,\pm \alpha \right)\text{, }\left(0,\beta ,0\right)$ です。射影平面の同値関係を利用すると、

$$\begin{gathered} \left(0,\pm 1,1\right) \\ \left(0,1,0\right) \end{gathered}$$

が楕円曲線と直線の交点になり、交点は３つあることになります。ここで $xy$平面の交点には現れなかった $\left(0,1,0\right)$ が $y$軸方向の無限遠点です。これを一般化すると次のようになります。つまり、楕円曲線と $y$軸に平行な直線の式を、

$\{\begin{array}{l}{y}^2=x^3+ax+b\\ x=c\end{array}$

とすると、これに対応する射影平面の式は、

$\{\begin{array}{l}{Y}^{2}Z=X^3+aX{Z}^2+b{Z}^3\\ X=cZ\end{array}$

です。$\left(0,1,0\right)$ はこの２式を必ず満たします。つまり全ての楕円曲線は $\left(0,1,0\right)$ を通り、全ての $y$軸に平行な直線は $\left(0,1,0\right)$ を通る。従って、楕円曲線と$y$軸に平行な直線は（$y$軸方向の）無限遠点で交わることになります。

楕円曲線の計算には現れませんが、無限遠点にもいろいろあって、$\left(1,0,0\right)$ は $x$軸方向の無限遠点、$\left(\alpha ,\beta ,0\right)$ は任意方向の無限遠点です（$\alpha$、$\beta$ は $0$ ではない数）。

$xy$平面の２直線は、平行なときには交点がありませんが、射影平面の２直線は必ず１点で交わります。また射影平面の楕円曲線の１点を通る直線は、楕円曲線と必ず３点で交わります（直線が楕円曲線の接線の場合は、接点での交差数を２と数えます）。このように、交差を統一的に扱えるのが射影平面の特徴の一つです。

以上のような数学的裏付けのもとに導入したのが無限遠点です。これを $xy$平面では、

・	$\mathit{y}$軸方向の無限遠のところに無限遠点 $\mathit{O}$ がある
・	楕円曲線は $\mathit{O}$ を通る
・	$\mathit{y}$軸に平行な直線は $\mathit{O}$ で楕円曲線と交わる

とイメージしてよいわけです。

---

加法式・２倍式

---

楕円曲線上の加法を計算式で表します。楕円曲線上の３点を次のように定義します。

$$\begin{gathered} P_1+P_2=P_3 \\ {P}_1=\left(x_1,y_1\right) \\ {P}_2=\left(x_2,y_2\right) \\ {P}_3=\left(x_3,y_3\right) \end{gathered}$$

とします。$P_1$ と $P_2$ を結ぶ直線を $y=\lambda x+\mu$ とすると、連立方程式、

$\{\begin{array}{l}{y}^2=x^3+ax+b\\ y=\lambda x+\mu \end{array}$

の解が $P_1\text{, }{P}_2\text{, }\left(x_3,-y_3\right)$ です。この２つの式から $y$ を消去すると、

$x^3+ax+b-{\left(\lambda x+\mu \right)}^2=0$

が得られますが、この式は、

$\left(x-x_1\right)\left(x-x_2\right)\left(x-x_3\right)=0$

と同一のはずです。そこで $x^2$ の係数を比較すると、

$-{\lambda }^2=-x_1-x_2-x_3$

が得られます。つまり、

$x_3={\lambda }^2-x_1-x_2$

となります。この $x_3$ を直線の式に入れると、

$-y_3=\lambda x_3+\mu$

ですが、$y_1=\lambda x_1+\mu$ なので $\mu$ を消去すると、

$y_3=-y_1+\lambda \left(x_1-x_3\right)$

となります。これが基本の加法式です。これを $P_1$ と $P_2$ の配置パターンごとにまとめると、次の通りです。

${\mathit{x}}_{\mathit{1}}\mathit{\ne }{\mathit{x}}_{\mathit{2}}$ のとき

$\{\begin{array}{ll}{x}_3& ={\lambda }^2-x_1-x_2\\ y_3& =\lambda \left(x_1-x_3\right)-y_1\\ \lambda & ={\displaystyle \frac{y_2-y_1}{x_2-x_1}}\end{array}$

${\mathit{x}}_{\mathit{1}}\mathit{=}{\mathit{x}}_{\mathit{2}}\mathit{\text{, }}{\mathit{y}}_{\mathit{1}}\mathit{=}{\mathit{y}}_{\mathit{2}}\mathit{\ne }\mathit{0}$ のとき

この場合は $P_1$ と $P_2$ を通る直線は $P_1$ における楕円曲線の接線となり、直線の傾き $\lambda$ は上の式のままでは計算できません。そこで $y^2=x^3+ax+b$ を $x$ で微分すると

$2y{\displaystyle \frac{dy}{dx}}=3x^2+a$

なので、

$\lambda ={\displaystyle \frac{3{x_1}^2+a}{2y_1}}$

となります。$x_2$ を $x_1$ に置き換えてまとめると、

$\{\begin{array}{ll}{x}_3& ={\lambda }^2-2x_1\\ y_3& =\lambda \left(x_1-x_3\right)-y_1\\ \lambda & ={\displaystyle \frac{3{x_1}^2+a}{2y_1}}\end{array}$

が $P_1+P_1$ の計算式です。これは $P_1$ の "２倍"（一般にはスカラー倍）であり、$2P_1$ と書きます。

${\mathit{x}}_{\mathit{1}}\mathit{=}{\mathit{x}}_{\mathit{2}}\mathit{\text{, }}{\mathit{y}}_{\mathit{1}}\mathit{\ne }{\mathit{y}}_{\mathit{2}}$ のとき、あるいは ${\mathit{y}}_{\mathit{1}}\mathit{=}{\mathit{y}}_{\mathit{2}}\mathit{=}\mathit{0}$ のとき

この場合、$P_2=-P_1$ なので、定義により

$P_1+P_2=O$

です。

---

なお、$P_1$ と $P_2$ は、楕円曲線の定義式、

$$\begin{gathered} {y_1}^2={x_1}^3+a{x}_1+b \\ {y_2}^2={x_2}^3+a{x}_2+b \end{gathered}$$

を満たしますが、この左辺と右辺のそれぞれを引き算すると、

$$\begin{gathered} \left(y_1+y_2\right)\left(y_1-y_2\right)= \\ \left(x_1-x_2\right)\left({x_1}^2+x_1{x}_2+{x_2}^2\right) \\ +a\left(x_1-x_2\right) \end{gathered}$$

$\begin{array}{ll}{\displaystyle \frac{y_1-y_2}{x_1-x_2}}& ={\displaystyle \frac{{x_1}^2+x_1{x}_2+{x_2}^2+a}{y_1+y_2}}\\ & =\lambda \end{array}$

となって $\lambda$ の別の表現が得られますが、これは $x_1=x_2$ でも使えます。従って「加法式（第２形）」を次のようにも表現できます。

${\mathit{y}}_{\mathit{1}}\mathit{+}{\mathit{y}}_{\mathit{2}}\mathit{\ne }\mathit{0}$ のとき

$\{\begin{array}{ll}{x}_3& ={\lambda }^2-x_1-x_2\\ y_3& =\lambda \left(x_1-x_3\right)-y_1\\ \lambda & ={\displaystyle \frac{{x_1}^2+x_1{x}_2+{x_2}^2+a}{y_1+y_2}}\end{array}$

${\mathit{y}}_{\mathit{1}}\mathit{+}{\mathit{y}}_{\mathit{2}}\mathit{=}\mathit{0}$ のとき

$P_1+P_2=O$

---

楕円曲線の具体例

---

楕円曲線とその有理点、加法則の適用例として、整数係数の３つの楕円曲線を調べてみます。以後の記述では、$P=\left(x,y\right)$ とするとき、$nP\text{, }-P\text{, }-nP$ の記述を使いますが、それぞれの定義は、

$\begin{array}{ll}nP& =\stackrel{\stackrel{n}{⏞}}{P+P+\text{ ⋯}+P}\\ -P& =\left(x,-y\right)\\ -nP& =\stackrel{\stackrel{n}{⏞}}{\left(-P\right)+\left(-P\right)+\text{ ⋯}+\left(-P\right)}\end{array}$

です。また、$nP=\left(x_n,y_n\right)$ とすると、加法の定義から $-nP=\left(x_n,-y_n\right)$ です。

${\mathit{y}}^{\mathit{2}}\mathit{=}{\mathit{x}}^{\mathit{3}}\mathit{+}\mathit{1}$

図14：楕円曲線の例１ $y^2=x^3+1$

この楕円曲線上の有理点は、次の５つの整点（＝ 座標値が整数の点）です。

$$\begin{gathered} P_1=\left(2,3\right) \\ {P}_2=\left(0,1\right) \\ {P}_3=\left(-1,0\right) \\ {P}_4=\left(0,-1\right) \\ {P}_5=\left(2,-3\right) \end{gathered}$$

ここで、群の演算式を使って $n{P}_1$ を計算してみると、

$\begin{array}{ll}2P_1=\left(0,1\right)& =P_2\\ 3P_1=\left(-1,0\right)& =P_3\\ 4P_1=\left(0,-1\right)& =P_4\\ 5P_1=\left(2,-3\right)& =P_5\\ 6P_1=O& \end{array}$

となります。$P_1$ は 6倍する（＝ 6個加算する）と $O$（＝零元）になる。このことを「$P_1$ の位数（order）が 6 である」と言います。また、

$3\left(P_2\right)=3\left(2P_1\right)=6P_1=O$

なので、$P_2$ の位数は 3 です。同様にして、$P_3\text{～}{P}_5$ の位数はそれぞれ $2\text{, }3\text{, }6$ になります。

楕円曲線 $y^2=x^3+1$ の有理点は $P_1\text{～}{P}_5$ の点しかありません。また位数が有限値なので、これらは有限位数の点です。これらの点と 零元 $O$ を合わせて群を構成します。

しかし楕円曲線上の有理点が有限位数をもつとは限りません。それが次の例です。

${\mathit{y}}^{\mathit{2}}\mathit{=}{\mathit{x}}^{\mathit{3}}\mathit{-}\mathit{x}\mathit{+}\mathit{1}$

図15：楕円曲線の例２ $y^2=x^3-x+1$

方程式 $y^2=x^3-x+1$ の整数解を調べると、手計算で $\left(-1,\pm 1\right)\text{, }$$\left(0,\pm 1\right)\text{, }$$\left(1,\pm 1\right)\text{, }$$\left(3,\pm 5\right)\text{, }$$\left(5,\pm 11\right)$ の10個の解が容易に見つかります。今、$P_1=\left(1,1\right)$ とし、$n{P}_1$ を順に計算してみると、次のようになります。

$\begin{array}{ll}1P_1& =\left(1,1\right)\\ 2P_1& =\left(-1,1\right)\\ 3P_1& =\left(0,-1\right)\\ 4P_1& =\left(3,-5\right)\\ 5P_1& =\left(5,11\right)\\ 6P_1& =\left(\frac{1}{4},\frac{7}{8}\right)\\ 7P_1& =\left(-\frac{11}{9},-\frac{17}{27}\right)\\ 8P_1& =\left(\frac{19}{25},-\frac{103}{125}\right)\\ 9P_1& =\left(56,-419\right)\\ 10P_1& =\left(\frac{159}{121},\frac{1861}{1331}\right)\\ & =\left(\frac{3·53}{{11}^2},\frac{1861}{{11}^3}\right)\\ & \fallingdotseq \left(1.31405,1.39820\right)\\ 11P_1& =\left(-\frac{255}{361},\frac{7981}{6859}\right)\\ & =\left(-\frac{3·5·17}{{19}^2},\frac{23·347}{{19}^3}\right)\\ & \fallingdotseq \left(-0.70637,1.16358\right)\\ 12P_1& =\left(-\frac{223}{784},-\frac{24655}{21952}\right)\\ & =\left(-\frac{223}{2^4·7^2},-\frac{5·4931}{2^6·7^3}\right)\\ & \fallingdotseq \left(-0.28444,-1.12313\right)\\ 13P_1& =\left(\frac{5665}{2809},-\frac{399083}{148877}\right)\\ & =\left(\frac{5·11·103}{{53}^2},-\frac{43·9281}{{53}^3}\right)\\ & \fallingdotseq \left(2.01673,-2.68062\right)\\ 14P_1& =\left(\frac{26239}{2601},\frac{4231459}{132651}\right)\\ & =\left(\frac{19·1381}{3^2·{17}^2},\frac{4231459}{3^2·{17}^2}\right)\\ & \fallingdotseq \left(10.08804,31.89919\right)\\ 15P_1& =\left(\frac{23464}{49729},\frac{8824453}{11089567}\right)\\ & =\left(\frac{2^3·7·419}{{223}^2},\frac{11·59·13597}{{223}^2}\right)\\ & \fallingdotseq \left(0.47183,0.79574\right)\end{array}$

途中で $\left(56,-419\right)$ という、手計算では分からない整点が現れました。計算してみると、

${56}^3-56+1=175561={419}^2$

となって、確かにこれが楕円曲線上の点であることが分かります。$15P_1$ までの結果を掲げましたが、この計算は $O$（＝ 零元）で終わることがなく、無限に続きます。つまり、$P_1=\left(1,1\right)$ は無限位数の点です。

さらに、同様の計算を$-P_1=\left(1,-1\right)$ から始めると、$y$ 座標の符号が逆転した点列、$-n{P}_1$ が得られます。そして実は、

楕円曲線 $y^2=x^3-x+1$ の有理点の全ては、

$m{P}_1$（$m$は正負の整数）

の形で表現できる

ことが分かっています。$0P_1=O$ と定義すれば、楕円曲線で定義された加法群の元は $m{P}_1$（$m$ は整数）の形で表現できるとも言えます。この性質を有限生成と言い、$P_1$ を生成元（generator）と呼びます。一般には、生成元は複数個あります。つまり楕円曲線上の有理点は $r$ 個の有理点 $Q_i$ を使って、

$m_1{Q}_1+m_2{Q}_2+\text{ ⋯}+m_r{Q}_r$

の形で表現できます。この $r$ を楕円曲線の階数（rank）と言います。なお、有限個の有理点しかもたない 図14 のような楕円曲線の階数は $0$ とします。

楕円曲線 $y^2=x^3-x+1$ の階数は $1$ です。そして今までの結果から、階数が $1$ の楕円曲線の有理点と零点 $O$ は、加法に関して整数（＝ 正の自然数と負の自然数と $0$）と全く同じ構造をもつことが分かります。ただ、楕円曲線の有理点の加法は普通の整数の加法よりよほど複雑な演算です。これが楕円曲線暗号を作るときの基礎となっています。

${\mathit{y}}^{\mathit{2}}\mathit{=}{\mathit{x}}^{\mathit{3}}\mathit{-}\mathit{4}\mathit{}\mathit{x}\mathit{+}\mathit{1}$

図16：楕円曲線の例３ $y^2=x^3-4x+1$

この楕円曲線の階数は $2$ です。従って生成元は２つで、

$$\begin{gathered} P_1=\left(0,1\right) \\ {P}_2=\left(3,4\right) \end{gathered}$$

です。曲線上には無限個の有理点がありますが、すべてはこの２つの生成元から「有限生成」されます。無限個の有理点のうち、生成元を含めて 22個が整点ですが（$y$座標の正負を無視すると 11個）、もちろんそれらの整点も生成元で表現できます。実際に計算してみると以下の通りです。

$\begin{array}{llll}& P_1+& P_2& =\left(-2,1\right)\\ 2& P_1& & =\left(4,7\right)\\ 2& P_1-& P_2& =\left(114,-1217\right)\\ 2& P_1+& P_2& =\left(2,-1\right)\\ 2& P_1+2& P_2& =\left(20,-89\right)\\ 3& P_1+& P_2& =\left(-1,-2\right)\\ 4& P_1+& P_2& =\left(10,-31\right)\\ 4& P_1+2& P_2& =\left(12,41\right)\\ 8& P_1+3& P_2& =\left(1274,-45473\right)\end{array}$

もちろん、計算していくと上記の整点だけでなく有理点が次々と生成され、それが無限に続きます。上の計算で $P_1\text{, }{P}_2$ の符号を逆転させると $y$ 座標の符号が逆の整点が得られます。たとえば、

$$\begin{gathered} -2P_1-P_2=\left(2,1\right) \\ -2P_1+P_2=\left(114,1217\right) \end{gathered}$$

です。以上を含めてこの楕円曲線の整点は、

$\left(-2,\pm 1\right)\text{, }$ $\left(-1,\pm 2\right)\text{, }$ $\left(0,\pm 1\right)\text{, }$ $\left(2,\pm 1\right)\text{, }$ $\left(3,\pm 4\right)\text{, }$ $\left(4,\pm 7\right)\text{, }$ $\left(10,\pm 31\right)\text{, }$ $\left(12,\pm 41\right)\text{, }$ $\left(20,\pm 89\right)\text{, }$ $\left(114,\pm 1217\right)\text{, }$ $\left(1274,\pm 45473\right)$

となります。最大の整点は $\left(1274,\pm 45473\right)$ ですが、実際に計算してみると、

$$\begin{gathered} {1274}^3-4·1274+1 \\ =2067793729 \\ ={37}^2·{1229}^2 \\ ={45473}^2 \end{gathered}$$

となって、楕円曲線上の点であることが確認できます。この最大の整点を２つの生成元に分けて、それぞれを計算してみると、

$\begin{array}{ll}8P_1& =\left(\frac{59965740}{625681},\frac{464259138209}{494913671}\right)\\ & =\left(\frac{2^2·3^2·5·79·4217}{7^2·{113}^2},\frac{455419·1019411}{7^3·{113}^3}\right)\\ 3P_2& =\left(\frac{130403}{2209},-\frac{47063372}{103823}\right)\\ & =\left(\frac{7·13·1433}{{47}^2},-\frac{2^2·353·33331}{{47}^3}\right)\end{array}$

となりますが、この２つの有理点を楕円曲線の加法式で $8P_1+3P_2$ とすると整数（整点）が現れるのも不思議な感じがします。

---

以上の「楕円曲線の有理点から成る加法群」を踏まえ、これ以降は楕円曲線暗号で使われる「有限体上の楕円曲線による加法群」に移ります。

---

有限体上の楕円曲線による加法群

---

以降に出てくる有限体 ${\mathbb{F}}_p$ と 乗法群 ${\mathbb{F}}_p^{\ast }$ については、No.313「高校数学で理解する公開鍵暗号の数理：10. 有限体と乗法群」 で定義したものです。

楕円曲線暗号に使われる楕円曲線は、有限体 ${\mathbb{F}}_p$ で定義された "曲線" で、次の式を満たすものです。

$$\begin{gathered} y^2=x^3+ax+b \\ \left(4a^3+27b^2\ne 0\right) \end{gathered}$$

$x$、$y$、$a$、$b$ は全て ${\mathbb{F}}_p$ の元です。「この式を満たす全ての $\left(x,y\right)$ と 零点 $O$ の集合」に対して演算を定義して群を構成します。演算を加法と考えて $+$ と書きます。この "曲線" 上の３点を、

$$\begin{gathered} P_1+P_2=P_3 \\ {P}_1=\left(x_1,y_1\right) \\ {P}_2=\left(x_2,y_2\right) \\ {P}_3=\left(x_3,y_3\right) \end{gathered}$$

とするとき、群の演算式は次のように定義されます。

${\mathit{x}}_{\mathit{1}}\mathit{\ne }{\mathit{x}}_{\mathit{2}}$ のとき

$\{\begin{array}{ll}{x}_3& ={\lambda }^2-x_1-x_2\\ y_3& =\lambda \left(x_1-x_3\right)-y_1\\ \lambda & ={\displaystyle \frac{y_2-y_1}{x_2-x_1}}\end{array}$

${\mathit{x}}_{\mathit{1}}\mathit{=}{\mathit{x}}_{\mathit{2}}\mathit{\text{, }}{\mathit{y}}_{\mathit{1}}\mathit{=}{\mathit{y}}_{\mathit{2}}\mathit{\ne }\mathit{0}$ のとき

$\{\begin{array}{ll}{x}_3& ={\lambda }^2-2x_1\\ y_3& =\lambda \left(x_1-x_3\right)-y_1\\ \lambda & ={\displaystyle \frac{3{x_1}^2+a}{2y_1}}\end{array}$

${\mathit{x}}_{\mathit{1}}\mathit{=}{\mathit{x}}_{\mathit{2}}\mathit{\text{, }}{\mathit{y}}_{\mathit{1}}\mathit{\ne }{\mathit{y}}_{\mathit{2}}$ のとき、あるいは ${\mathit{y}}_{\mathit{1}}\mathit{=}{\mathit{y}}_{\mathit{2}}\mathit{=}\mathit{0}$ のとき

$P_1+P_2=O$

つまり、実数平面の有理点と無限遠点（＝零元）で構成された群の演算式と全く同じです。もちろん加減乗除は ${\mathbb{F}}_p$ で行います。これが群になる理由は、有理数体（有理数全体の集合）も有限体 ${\mathbb{F}}_p$ も「体」であり、加減乗除は全く同一形式で記述できるからです。ただ、有理数体と違って ${\mathbb{F}}_p$ の元の数は有限個であり、群の元の数も有限個（＝有限群）です。以降、${\mathbb{F}}_{\mathit{p}}$ 上の楕円曲線、${\mathit{y}}^{\mathit{2}}\mathit{=}{\mathit{x}}^{\mathit{3}}\mathit{+}\mathit{a}\mathit{}\mathit{x}\mathit{+}\mathit{b}$ による有限群を $\mathit{E}\mathit{}\left(\mathit{a},\mathit{b},\mathit{p}\right)$ と表記します。

${\mathbb{F}}_p$ 上の楕円曲線は、もはや "曲線" の形をしていませんが、これを可視化した図が Wikipedia にあるので、引用します。

図17：有限体上の楕円曲線 $E\left(-1,0,89\right)$　 ${\mathbb{F}}_{89}\text{, }{y}^2=x^3-x$

赤丸が "楕円曲線上の点" を表し、計79個ある。零元（無限遠点）と合わせて、群の元の総数は 80 である。

（Wikipedia より）

---

以上が「有限体上の楕円曲線が作る加法群」で、楕円曲線暗号はこの加法群で構成されます。その話を次回にします。

（次回に続く）

---

タグ：逆元 零元 結合則 楕円曲線 楕円曲線暗号 公開鍵暗号 ３次曲線 楕円曲線論入門 判別式 射影平面 無限遠点 有理点 加法群 有限体 群 高校数学