ElGamal暗号

ElGamal暗号

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

手順

準備

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

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

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

暗号化

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

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

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

復号

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

$$m = c_2 (c_1 ^ s) ^{-1} \bmod p$$

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

評価

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

安全性

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

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

健全性

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

まとめ

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

各パラメータ

$s$：秘密鍵

$r$：乱数

$p$：法（公開鍵）

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

$y = g^s \bmod p$：公開鍵

$c_1 = g^r \bmod p$：暗号文

$c_2 = my^r \bmod p$：暗号文