一、背景

在密码学中，ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔提出。GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。
ElGamal加密算法可以定义在任何循环群G上。它的安全性基于离散对数难题。

• elgama算法可分别用作加解密与数字签名。

二、加解密算法细节

2.1 公私钥产生算法（$KeyGen$）：

• 随机选择一个满足安全要求的大素数$p$（通常1024bits），并生成有限域$Z_p$的一个生成元$g\in Z_p^{\ast }$；
  • 通常$p$产生方法：
  • $p=2^x\ast q+1$，$q$为160bits大素数
• 随机选择一个随机数$x(1<x<p-1)$，计算$y\equiv g^x(modp)$，则公钥为$(y,g,p)$，私钥为$x$。

2.2 加密过程（$Encryption$）

• 对消息$m$进行加密；
• 随机选择整数$r(1<r<p-1)$；
• 计算密文$C=(c,c^{{}^{\prime }})$，其中：$c\equiv g^r(modp),c^{{}^{\prime }}\equiv m{y}^r(modp)$。

2.3 解密过程（$Decryption$）

• 收到密文$C=(c,c^{{}^{\prime }})$；
• 使用密钥$x$对密文$C$解密得到消息$m$，$m=c^{{}^{\prime }}/c^x=(m{y}^r)/(g^x{)}^r=(m{y}^r)/y^r(modp)$。

三、数字签名算法

3.1 公私钥产生算法（$KeyGen$）：

• 随机选择一个满足安全要求的大素数$p$（通常1024bits），并生成有限域$Z_p$的一个生成元$g\in Z_p^{\ast }$；
  • 通常$p$产生方法：
  • $p=2^x\ast q+1$，$q$为160bits大素数
• 随机选择一个随机数$x(1<x<p-1)$，计算$y\equiv g^x(modp)$，则公钥为$(y,g,p)$，私钥为$x$。

3.2 签名算法（$Sign$）

• 对消息m进行签名；
• 随机选择整数$k(1<k<p-1)$；
• 计算$r$，$r\equiv g^k(modp)$；
• 计算$s$，$s\equiv [h(m)-xr]k^{-1}(mod(p-1))$，$h(m)$表示哈希函数；
• 得出数字签名$(r,s)$。

3.3 签名验证（$Verify$）

• 根据公钥$y$，消息$m$验证数字签名$(r,s)$；
• 计算$g^{h(m{)}^{\prime }}$，$g^{h(m{)}^{\prime }}=y^r{r}^s=(g^x{)}^r(g^k{)}^{(h(m)-xr)/k}$；
• 验证等式$g^{h(m{)}^{\prime }}=g^{h(m)}$是否成立，若成立则为真，否则为假。