楕円ElGamal暗号(ElGamal Cryptosystem on Elliptic Curves)

# 楕円ElGamal暗号(ElGamal Cryptosystem on Elliptic Curves)

## はじめに

調べてて、疑問に思った事があったので、楕円曲線(Elliptic Curves)を利用した、
ElGamal暗号についてサンプルコードも含め実装してみました。

## ElGamal暗号

まずは、通常のElGamal暗号を見てみます。
基本情報は以下のとおりです。

```math
\begin{align*}
g &: \text{生成元} \\
p &: \text{位数} \\
\end{align*}
```

```math
\begin{align*}
x &: \text{秘密鍵} \\
y &: \text{公開鍵, } y=g^x\\
\end{align*}
```

```python
g = 2
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
x = random.randint(2, p)
y = pow(g, x, p)
print('y  = {:064x}'.format(y), ' # 公開鍵')
```

### 暗号

相手の公開鍵$y$を用いて、メッセージ$m$を暗号します。

```math
\begin{align*}
m &: \text{メッセージ} \\
r &: \text{ナンス} \\
c_1 &= g^r \\
c_2 &= m\cdot y^r \\
(c_1,c_2) &: \text{暗号文} \\
\end{align*}
```

```python
message = "hello" #@param {type:"string"}
m = int.from_bytes(message.encode('utf-8'), 'big')
r = random.randint(2, p)
c1 = pow(g, r, p)
c2 = (m * pow(y, r, p)) % p
print('c1 = {:064x}'.format(c1), ' # 暗号１')
print('c2 = {:064x}'.format(c2), ' # 暗号２')
```

### 復号

暗号文から、メッセージを復号します。

```math
\begin{align*}
m = \frac{c_2}{c_1^x}
\end{align*}
```

```python
m = (c2 * pow(pow(c1, x, p), p-2, p)) % p
print(m.to_bytes((m.bit_length() + 7) // 8, 'big').decode('utf-8'))
```

## 楕円ElGamal暗号

```math
\begin{align*}
G &: \text{生成元} \\
x &: \text{秘密鍵} \\
P &: \text{公開鍵, } P=xG \\
\end{align*}
```

```python
x = random.randint(2, S256P.n)
P = x * G
print('P  =', P.compress().hex(), '# 公開鍵')
```

### 暗号
メッセージ$m$から、楕円曲線上の点$M$を算出します。
楕円曲線の$X$座標を以下の値として、点として成立する$X$座標を探します。
$m_x = 100m + i\ ,\ 0 \le i < 100$
その点を$M$とします。
相手の公開鍵$P$を用いて、$M$を暗号します。

```python
message = 'hello'  # @param {type:"string"}
m = int.from_bytes(message.encode('utf-8'), 'big') * 100
M = S256P(None, None)
for i in range(100):
    try:
        bs = b'\x02' + (m+i).to_bytes(32, 'big')
        M = parse(bs)
        break
    except ValueError as e:
        continue
```

```math
\begin{align*}
m &: \text{メッセージ} \\
M &: \text{メッセージから生成した点} \\
r &: \text{ナンス} \\
C_1 &= rG \\
C_2 &= M + rP \\
(C_1,C_2) &: \text{暗号文} \\
\end{align*}
```

```python
r = random.randint(2, S256P.n)
C1 = r * G
C2 = M + r * P
print('C1 =', C1.compress().hex(), '# 暗号１')
print('C2 =', C2.compress().hex(), '# 暗号２')
```

### 復号

暗号文から、$M$を取得します。

```math
\begin{align*}
M = C_2 - xC_1
\end{align*}
```

```python
M = C2 + (- x) * C1
```

$M$から、$X$座標の値$m_x$を取得します。
$m_x$を$100$で割った整数部分がメッセージとなります。

```math
m = \left\lfloor \frac{m_x}{100} \right\rfloor
```

```python
m = M.x // 100
print(m.to_bytes((m.bit_length() + 7) // 8, 'big').decode('utf-8'))
```

## デモ

[Google Colaboratory](https://colab.research.google.com/gist/tnakagawa/85518832a5fdb9769068c42b9513083e/elgamalcryptosystemonellipticcurves.ipynb)でデモを実装してみたので、興味のある方は利用してみてください。

# さいごに

調べてて、疑問に思った事とは、楕円曲線を利用した場合のElGamal暗号で、メッセージをどう格納するのか？、でした
結果としては、$X$座標として設定するというものでした。
この辺りの、安全性とか完全生なんかについての論文を読んではいませんが、実際どうなんでしょうか・・・
サンプル実装では、問題なく動いているように見えます。

# 参考文献(References)

- [楕円 ElGamal 暗号の実装](http://www3.jeed.or.jp/chiba/college/data/kiyou/h28/H28-02.pdf)
- [ELLIPTIC CURVESNUMBER THEORYAND CRYPTOGRAPHY SECOND EDITION](https://people.cs.nctu.edu.tw/~rjchen/ECC2012S/Elliptic%20Curves%20Number%20Theory%20And%20Cryptography%202n.pdf)
- [クラウドを支えるこれからの暗号技術](https://github.com/herumi/ango/raw/master/ango.pdf)