ElGamal暗号

ElGamal暗号

ElGamal暗号とは離散対数問題を用いた公開鍵暗号方式である。

手順

準備

以下の手順で公開鍵と秘密鍵の生成を行う。

1. 大きな素数である法 $p$ を用意する。
2. $1<g<p-1$ を満たす 原始根 $g$ を選ぶ。
3. $1<s<p-1$ 満たす自然数 $s$をランダムに選ぶ。
4. $y=g^{s}modp$ を計算する。

組$(p,g,y)$ が公開鍵、$s$ が秘密鍵となる。

暗号化

公開鍵 $(p,g,y)$ を用いて、以下の手順により暗号化を行う。

1. 平文 $m$ を用意する。
2. $1<r<p-1$ を満たす 自然数 $r$ をランダムに選ぶ。
3. $c_1=g^{r}modp$ を計算する。
4. $c_2=m{y}^{r}modp$ を計算する。

組 $(c_1,c_2)$が暗号文となる。

復号

以下のように平文$m$を計算する。

$$m=c_2(c_1^s{)}^{-1}modp$$

$c_1^s$ のモジュラ逆数 $(c_1^s{)}^{-1}$は、フェルマーの小定理や拡張ユークリッド互除法を用いて計算できる。

評価

ElGamal 暗号の安全性と健全性について示す。

安全性

$g,p,y(=g^{s}modp)$ を用いて秘密鍵$s$ を求めることは、理論上可能である。

しかし離散対数問題により、現実的な時間で計算するのは難しい。

健全性

以下に復号が成り立つことを示す。

まとめ

離散対数問題に基づく公開鍵暗号である、ElGamal暗号の手順、安全性、健全性についてまとめた。

各パラメータ

$s$：秘密鍵

$r$：乱数

$p$：法（公開鍵）

$g$：原始根（公開鍵）

$y=g^{s}modp$：公開鍵

$c_1=g^{r}modp$：暗号文

$c_2=m{y}^{r}modp$：暗号文