ECElgamal暗号

# (ここでの)楕円曲線
有限体$F_{p}=\mathbf{Z}/p\mathbf{Z}$上で定義される
$$
y^{2} = x^{3}+ax+b
$$
を満たす点集合。代表元$x \in [0, p-1]$によって実数とみなし、Euclid空間$R^{2}$上の点集合として図示しても曲線には見えないが、代数曲線という意味で曲線。

ここで、$p$は素数であり、これは、$\mathbf{Z}/p\mathbf{Z}$が体となるための条件である。$\mathbf{Z}/p\mathbf{Z}$が体となるための非自明な条件は、$\mathbf{Z}/p\mathbf{Z}$の元$a$について、$a\neq0$なら逆元$a^{-1}$が存在することだが、これは次の定理で証明される。

#### 定理

$pが素数 \Leftrightarrow \forall a \neq 0 \in \mathbf{Z}/p\mathbf{Z}が逆元を持つ$

proof.
以下が同値より明らか。
1. $p$と$a$が互いに素
2. $px + ay = 1$が解を持つ

以降、$p=17$として話を進める。

楕円曲線$y^{2}=x^{3}+7$のグラフを書くと、
![plain.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/126131/828accf0-b620-d846-6fa1-41949db3a37f.png)
となる。

# 楕円曲線上の加法

まずは実数の楕円曲線を考える。この場合の実数領域のグラフは、以下の通り[*](#constant)。
![ec.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/126131/9a33fdbf-e400-e68e-6667-2c2272191233.png)

初めに、楕円曲線上の2点$P(x_{P}, y_{P})$、$Q(x_{Q}, y_{Q})$を結ぶ直線を$l_{PQ}$とする。

- $x_{P} \neq x_{Q}$のとき

$s = \frac{y_{P}-y_{Q}}{x_{P}-x_{Q}}$とおくと、直線$l_{PQ}$の方程式は、
$$
y = s(x-x_{P})+y_{P}
$$
と書ける。これを楕円曲線の式に代入して、
$$
\begin{aligned}
&\left\\{s(x-x_{P})+y_{P}\right\\}^{2} = x^{3} + 7 \\\
\therefore \ &x^{3} - s^{2}x^{2} + \dots = 0\ \cdots(\*)
\end{aligned}
$$
となる。
ここで、$(\*)$が解として$\alpha$、$\beta$、$\gamma$を持つとき[*](#heitai)、
$$
\begin{aligned}
x^{3} - s^{2}x^{2} + \dots &= (x-\alpha)(x-\beta)(x-\gamma) \\\
&= x^3 - (\alpha+\beta+\gamma)x + \dots
\end{aligned}
$$
となり、係数比較によって$s^{2} = \alpha+\beta+\gamma$を得る。

直線$l_{PQ}$と楕円曲線の交点のうち、$P$や$Q$でない点を$R(x_{R}, y_{R})$とする。$(\*)$は解として、$x_{P}$、$x_{Q}$を持つので、これら以外の解は$x_{R}$であり、
$$
x_{R} = s^{2} - x_{P} - x_{Q}
$$
となる。一方、$x_{R}$が定まれば、点$R$が直線$l_{PQ}$上の点という条件により、$y_{R}$は一意的に定まり、
$$
y_{R} = s(x_{R}-x_{P}) + y_{P}
$$
と分かる。

このように、二点$P$、$Q$から第三の点$R$を一意的に決定することができる。そこで、楕円曲線上の加法を、$P+Q+R=0$で定める。これが加法としてwell-definedであることの証明は省略するが、特に結合則が自明でないことに注意が必要である。

- $x_{P} = x_{Q}$のとき

1. まず、$P=Q$のとき
$s$が定義できないので、別の方法を考える必要がある。この場合は、点$P(Q)$における接線を直線
$l_{PQ}$とする。すると、
$$
\begin{aligned}
&y^{2} = x^{3}+7 \\\
\therefore\ &y = \pm\sqrt{x^{3}+7} \\\
\therefore\ &y' = \pm\frac{3x^{2}}{\sqrt{x^{3}+7}} = \frac{3x^{2}}{y}
\end{aligned}
$$
より、
$$s = \frac{3x_{P}^{2}}{y_{P}}$$
となる。$y_{P}=0$の時は、、省略する。

2. $P \neq Q$のとき
グラフを見れば明らかだが、直線$l_{PQ}$と楕円曲線は点$P$、$Q$以外では交わらない。よって、$P+Q=0$とする。

$P$の逆元$-P$は、最後の場合より、$P$とx軸対称の点。

# 楕円曲線上の乗法

楕円曲線上の乗法は、単純に加法を用いて、
$$
nP = \sum^{n}_{i=1}P
$$
と定義する。

接線を使うと、$P$から$2P$を計算できた。これを繰り返すと、$2^{n}P$をn回の計算で求めることができる。

# 有限体上での楕円関数

先ほどは実数上での議論だったが、それと同じことが$F_{p}$上でも成り立つと認めることにする。

$F_{17}$上での乗法の様子を見てみる。

![output.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/126131/b60d6472-f826-6d02-1112-790b56cb7991.gif)

これは、$G=(2, 10)$を生成元とする巡回群$\<G\>$の様子を表している。この巡回群の位数は9だと分かる。

# 楕円曲線上の離散対数

楕円曲線上の点$G$と$P$が与えられたとき、
$$
P = nG
$$
を満たす$n$を離散対数(discrete logarithm)という。そして、これを求める問題をDLP(discrete logarithm problem)という。楕円曲線暗号の安全性はこのDLPが難しいことに依拠している。

逆に、$n$と$G$が与えられた時に$P$を求めるのは簡単である。この場合は、$G$から$2^{n}G$がn回の計算で求められることを使うと、$\log n$の時間で求められる(気がする)。

# Elgamal暗号

$G$: 生成元
$x$: 正の整数(秘密鍵)
$m$: 平文
とする。

公開鍵$P$は、$P = xG$により生成する。

暗号化には、適当な正の整数$\gamma$を選んで、
$$
\begin{aligned}
c_{1} &= \gamma G \\\
c_{2} &= m+\gamma P
\end{aligned}
$$
とする。

復号には、

$$
\begin{aligned}
c_{2} - xc_{1} &= m+\gamma P-x\gamma G \\\
&= m+\gamma xG - x\gamma G \\\
&= m
\end{aligned}
$$

とする。逆元を求めるには、実数の時からの類推で、$y$の符号を変えれば良い。

# 余談
- トーラス上の楕円曲線

![torus.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/126131/5f0cbc11-e144-df91-c92a-303a549187fd.png)

- <span id=constant>楕円曲線のバリエーション</span>

![ec.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/126131/b290b1b8-7c2f-0b9f-7846-b263a32746b2.png)

楕円曲線$y^{2}=x^{3}+a$の$a$を変化させるとこうなる。中心部の一番こぶになっているところが、secp256k1で使われているもの。

- <span id=heitai>代数的閉体</span>

一般に、3次方程式が重複度込みで3つの解を持つことを保証するためには、実数では条件不足。今回の場合は、一旦複素数体に議論を拡張して、$s^{2} = x_{P}+x_{Q}+x_{R}$より$x_{R}$は実数であることを確認したと見るのが良いと思う。実際、$x^{3} + 1 = 0$は実数解として$x=-1$しか持たない。一般に、n次方程式の解が重複度込みでn個あることが保証されている体を、代数的閉体という。

- 実装

https://qiita.com/angel_p_57/items/ede8feb2bbb9a2013c6b