ElGamal 加密方案：从 Diffie-Hellman 到公钥加密的数学构造

背景与动机

1976 年 Diffie 和 Hellman 提出了第一个实用的公钥密钥交换协议，但当时他们并未给出完整的公钥加密方案。两年后，Taher ElGamal 在 1985 年的论文 *"A Public-Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm Problem"* 中，将 Diffie-Hellman 的思想扩展为完整的加密方案——这就是 ElGamal 加密。

ElGamal 加密的历史意义在于：

• 第一个实用的公钥加密方案，早于 RSA 的应用普及
• 基于离散对数难题（DLP），与 RSA 基于大整数分解形成对比
• 概率加密，同一明文多次加密产生不同密文，提供了语义安全性
• 是现代密码学许多方案的基础构件，如 Paillier 同态加密、Cramer-Shoup 加密等

数学构造

参数设置

ElGamal 加密基于一个循环群 $G$，其阶为素数 $q$，生成元为 $g$。实际应用中通常取：

• $G = \mathbb{Z}_p^*$，其中 $p$ 是大素数，$q = (p-1)/2$ 也是素数（安全素数）
• 或 $G$ 为椭圆曲线群 $E(\mathbb{F}_p)$

密钥生成

1. 选择随机私钥 $x \in_R [1, q-1]$
2. 计算公钥 $h = g^x \bmod p$
3. 公钥 $(p, q, g, h)$，私钥 $x$

加密过程

假设发送方要加密消息 $m$（需映射到群元素，通常 $m \in \mathbb{Z}_q^*$）：

1. 选择随机数 $k \in_R [1, q-1]$
2. 计算共享密钥 $s = h^k \bmod p$
3. 计算密文对：
   - $c_1 = g^k \bmod p$
   - $c_2 = m \cdot s \bmod p = m \cdot h^k \bmod p$
4. 输出密文 $(c_1, c_2)$

直观理解：ElGamal 加密本质上是" Diffie-Hellman 密钥交换 + 一次性 XOR"。接收方用私钥 $x$ 计算 $s = c_1^x = g^{kx}$，这与发送方计算的共享密钥相同，从而可以解密 $m = c_2 \cdot s^{-1} \bmod p$。

解密过程

1. 计算共享密钥 $s = c_1^x \bmod p$
2. 计算 $s$ 的模逆 $s^{-1} \bmod p$
3. 恢复明文 $m = c_2 \cdot s^{-1} \bmod p$

正确性证明：

$$s = c_1^x = (g^k)^x = g^{kx} \pmod{p}$$

$$m = c_2 \cdot s^{-1} = m \cdot h^k \cdot (g^{kx})^{-1} = m \cdot g^{xk} \cdot g^{-xk} = m \pmod{p}$$

安全性分析

基于 DDH 假设的安全性

ElGamal 加密的语义安全性（IND-CPA）依赖于 Decisional Diffie-Hellman (DDH) 假设：

给定 $(g, g^a, g^b, g^c)$，判断 $c = ab \bmod q$ 是否成立是计算上不可行的。

• 攻击者看到密文 $(c_1, c_2) = (g^k, m \cdot h^k)$
• 若 DDH 成立，则 $(g, g^k, h, h^k)$ 与随机四元组不可区分
• 因此 $h^k$ 对攻击者是随机的，$c_2 = m \cdot h^k$ 遮蔽了 $m$

与 RSA 的安全性对比

已知攻击

#### 1. 小消息攻击

若 $m$ 较小（如 $m < p^{1/3}$），可通过 Coppersmith 方法恢复 $m$。缓解：对消息进行随机填充。

#### 2. 选择明文攻击下的密文篡改

攻击者可修改 $c_2$ 而不改变密文结构。这是 ElGamal 缺乏认证性的体现。缓解：结合数字签名或 MAC。

#### 3. 共模攻击

若多个用户共享相同 $p, g$ 但使用不同公钥，且加密相同消息，可通过中国剩余定理恢复明文。缓解：每个用户独立生成参数或添加随机盐。

工程实现与变体

ElGamal 签名方案

ElGamal 同时提出了签名方案，其安全性基于 DLP：

签名：s = k^(-1) * (H(m) - x*r) mod (p-1)
验证：g^H(m) ≡ y^r * r^s (mod p)

注：ElGamal 签名与 DSA 同源，DSA 是其变体（将模数从 $p-1$ 改为 $q$）。

Cramer-Shoup 加密

Cramer-Shoup（1998）是对 ElGamal 的改进，提供 IND-CCA2 安全性（抗选择密文攻击）：

• 引入双哈希校验，检测密文篡改
• 安全性可归约到 DDH 假设
• 是第一个被证明达到 IND-CCA2 的公钥加密方案

Paillier 同态加密

Paillier（1999）基于 Decisional Composite Residuosity 假设，扩展了 ElGamal 的思想：

• 加法同态：$E(m_1) \cdot E(m_2) = E(m_1 + m_2)$
• 应用于隐私计算、电子投票、安全多方计算

椭圆曲线 ElGamal

将 $\mathbb{Z}_p^*$ 替换为椭圆曲线群 $E(\mathbb{F}_p)$：

• 相同安全强度下密钥长度更短（256 位 vs 2048 位）
• SM2 加密方案本质上是椭圆曲线 ElGamal 的变体

国密对照：SM2 加密与 ElGamal 的关系

SM2 公钥加密（GB/T 32918.4-2016 / GM/T 0003.4-2012）的数学结构与 ElGamal 加密高度相似，关键差异在于：

加密：
1. 随机选择 k ∈ [1, n-1]
2. C1 = [k]G（曲线上的点）
3. t = KDF([k]PB, klen)  # PB 为对方公钥
4. C2 = M ⊕ t
5. C3 = Hash([k]G + [t]PB)  # 哈希校验
密文: (C1, C2, C3)

SM2 比原始 ElGamal 增加了：

• KDF 密钥派生：将共享点转换为字节串
• 哈希校验：提供认证性，抵御选择密文攻击

应用与局限

适用场景

• 混合加密系统：ElGamal 常用于密钥封装机制（KEM），如 TLS 1.3 的 ECDHE 密钥交换
• 同态加密基础：Paillier、Boneh-Goh-Nissim 等均基于 ElGamal 思想
• 阈值密码学：Shamir 阈值方案与 ElGamal 结合实现分布式签名/加密
• 混环技术：Ring Signature、Group Signature 的构造基础

局限性

• 密文扩展 2 倍：加密 $m$ 产生 $(c_1, c_2)$，长度约为明文 2 倍
• 无原生认证：需额外结合签名或 MAC
• 计算开销：每次加密需 2 次模幂运算
• 参数选择敏感：需确保 $p$ 为安全素数，$g$ 的阶为大素数

现代替代方案

相关实践

• Diffie-Hellman 密钥交换与 ECDH 原理
• SM2 椭圆曲线公钥密码算法
• 密码学安全模型：从 IND-CPA 到 IND-CCA2
• 国密 SSL/TLS 双证书自适应方案
• 密钥封装机制（KEM）

*参考标准：RFC 2631 (Diffie-Hellman Key Agreement), GB/T 32918.4-2016 (SM2 第 4 部分：公钥加密算法), FIPS 186-5 (Digital Signature Standard)*