エルガマル暗号
エルガマル暗号とは、位数が大きい離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つです。
送信者は受信者の公開鍵（暗号化鍵）で平文から暗号文を作成し、受信者は自分の秘密鍵（複合化鍵）で暗号文を平文に戻します。平文と暗号文、及び、暗号化鍵と複合化鍵の関係は以下で表されます。
| 送信者（暗号化） | 受信者（複合化） |
| 平文（$M$）→ 暗号文（$C_1,C_2$） | 暗号文（$C_1,C_2$）→ 平文（$M$） |
| 暗号化鍵（$y,g,n$） | 複合化鍵（$x,n$） |
| $C_1=g^r\pmod{n}$ -③ $C_2=y^rM\pmod{n}$ -④ |
$z=n-1-x$ $M=C_1^zC_2\pmod{n} -⑤$ |
公開鍵の作成
公開鍵（暗号化鍵）$y$ は、素数 $n$ と秘密鍵（複合化鍵）$x$ により以下で求めます。$g$ は除数 $n$ に対する原始根を選びます。
$$y=g^x\pmod{n} -①$$
尚、$g$ が除数 $n$ の原始根とは、以下に関係にある場合を指します。
$$g^{n-1}\pmod{n}=1 -②$$
これら（$y,g,n$）を公開鍵として配布します。
暗号化
送信者は、任意の数 $r\in\{0,1,\cdots,n-2\}$ を選び、平文 $M$ を以下の手順で暗号化します。
$$C_1=g^r\pmod{n} -③$$$$C_2=y^rM\pmod{n} -④$$
これら（$C_1,C_2$）を暗号文として送付します。
複合化
受信者は、自分の秘密鍵 $x$ により指数 $z$ を計算し、
$$z=n-1-x$$
暗号文を複合化して平文を得ます。
$$M=C_1^zC_2\pmod{n} -⑤$$
複合化と安全性
複合化の確認
⑤の右辺に③と④を代入し、①と②を使うことで確認することができます。
$$C_1^zC_2\pmod{n}=g^{r(n-1-x)}y^rM\pmod{n}$$$$=(g^{n-1})^r(g^x)^{-r}y^rM\pmod{n}$$
ここで①と②を使うと、複合化されることが分かります。
$$=y^{-r}y^rM\pmod{n}=M$$
安全性
秘密鍵から公開鍵を求める①について、（$g,n$）が既知とした場合、秘密鍵 $x$ から公開鍵 $y$ を求めるのは容易ですが、公開鍵から秘密鍵を知るのは容易ではありません。①の $x$ を求めることは離散対数問題と呼ばれ、これがエルガマル暗号の安全性の根拠となっています。
例えば、次の計算は容易にできますが、
$$y=7^5\pmod{13}=16807\pmod{13}=11$$
逆に、次の式を満たす $x$ を求めることは容易ではありません。
$$11=7^x\pmod{13}$$
$1\le x\le13$ 程度であれば総当たりで求めることもできますが、$n$ が大きくなると途端に困難になります。
