ElGamal 数字签名算法：从 DLP 到可证明安全的先驱
概述
1985 年，Taher ElGamal 在 *IEEE Transactions on Information Theory* 发表论文 *\"A Public-Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm Problem\"*，首次将公钥密码学的核心思想应用于数字签名。这是历史上第一个被证明存在性安全（Existential Unforgeability, EUF-CMA）的数字签名方案。
与 RSA 签名（基于大整数分解）不同，ElGamal 签名基于离散对数问题（Discrete Logarithm Problem, DLP）。这种构造思路启发了后续的 DSA（数字签名算法）和 ECDSA（椭圆曲线 DSA），并最终催生了国密 SM2 签名标准（GM/T 0003.2-2012）。
| 对比维度 | ElGamal 签名 | DSA | ECDSA | SM2 签名 |
|---|---|---|---|---|
| 提出年份 | 1985 | 1991 (NIST) | 1992 | 2010 (GM/T) |
| 数学基础 | DLP in $\mathbb{Z}_p^*$ | DLP in $\mathbb{Z}_p^*$ | ECDLP | ECDLP |
| 安全性证明 | EUF-CMA | EUF-CMA | EUF-CMA | EUF-CMA |
| 签名长度 | 2×$q$ 位 | $2 \times 160$ 位 | $2 \times n$ 位 | 64 字节 |
注意：ElGamal 既有加密方案，也有签名方案，二者共享相同的数学基础（DLP），但构造思路不同。加密方案（elgamal-encryption-scheme）侧重于加密通信，签名方案侧重于身份认证与消息完整性。
数学基础：离散对数问题
形式化定义
设 $p$ 为大素数，$g$ 为 $\mathbb{Z}_p^*$ 的生成元（或阶为素数 $q | (p-1)$ 的元素），离散对数问题定义为：
$$\text{给定 } p, g, h = g^x \bmod p, \text{ 求 } x \in [0, q-1]$$
该问题的计算困难性是 ElGamal 签名的安全基础。对于 2048 位素数 $p$，已知最有效的通用算法是数域筛法（Number Field Sieve, NFS），其复杂度为：
$$L_p\left[\frac{1}{3}, \sqrt[3]{\frac{64}{9}}\right] = \exp\left(\left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln p)^{1/3}(\ln \ln p)^{2/3}\right)$$
要达到 128 位安全强度，$p$ 至少需要 3072 位（NIST SP 800-57 Part 1 Rev. 5 推荐）。
参数选择
根据 RFC 2447 和 RFC 5114，推荐参数如下：
| 安全级别 | $p$ 位数 | $q$ 位数 | 建议使用场景 |
|---|---|---|---|
| 80 位 | 1024 | 160 | 已不建议使用 |
| 112 位 | 2048 | 224 | 过渡期可用 |
| 128 位 | 3072 | 256 | 当前推荐 |
| 192 位 | 7680 | 384 | 长期安全需求 |
签名方案构造
密钥生成
参数：
- 大素数 $p$（如 3072 位）
- 素数 $q | (p-1)$（如 256 位）
- 生成元 $g \in \mathbb{Z}_p^*$，满足 $g^q \equiv 1 \pmod{p}$
- 随机选取私钥 $x \in_R [1, q-1]$
- 计算公钥 $y = g^x \bmod p$
签名生成
对消息 $M$ 进行签名：
- 计算消息哈希 $e = H(M)$，其中 $H$ 为密码学哈希函数（如 SHA-256）
- 随机选取 ephemeral key $k \in_R [1, q-1]$，满足 $\gcd(k, q) = 1$
- 计算 $r = g^k \bmod p$
- 计算 $s = k^{-1}(e - xr) \bmod q$
约束条件：
- $r \neq 0$ 且 $r \neq 1$（否则签名无效）
- $s \neq 0$（否则签名无效）
- $k$ 必须每次随机选取，重复使用会导致私钥泄露
签名验证
给定消息 $M$ 和签名 $(r, s)$：
- 验证 $0 < r < p$ 且 $0 < s < q$
- 计算 $e = H(M)$
- 计算 $w = s^{-1} \bmod q$
- 计算 $u_1 = ew \bmod q$
- 计算 $u_2 = rw \bmod q$
- 计算 $v = (g^{u_1} \cdot y^{u_2} \bmod p) \bmod q$
- 若 $v = r$，则签名有效；否则无效
正确性证明
验证过程的正确性基于模运算的代数性质：
$$g^{u_1} \cdot y^{u_2} \equiv g^{ew} \cdot (g^x)^{rw} \pmod{p}$$
$$\equiv g^{w(e + xr)} \pmod{p}$$
由于 $s = k^{-1}(e - xr) \bmod q$，则 $w = s^{-1}$，代入得：
$$e + xr = sk \bmod q$$
因此：
$$g^{w(e+xr)} = g^{sk} = g^{k \cdot k^{-1}(e-xr) \cdot k} = g^e \pmod{p}$$
最终得到 $v = r$，验证通过。
安全性分析
EUF-CMA 安全性证明
ElGamal 签名方案在随机预言模型（Random Oracle Model, ROM）下被证明具有 EUF-CMA（Existential Unforgeability under Chosen Message Attack）安全性：
定理（Shoup, 2000）：若离散对数问题在群 $\mathbb{Z}_p^*$ 中是困难的，且 $H$ 可理想化为随机预言机，则 ElGamal 签名方案在自适应选择消息攻击下存在性不可伪造。
证明思路：
- 假设攻击者能在 CMA 下伪造签名，则可通过归约算法求解 DLP
- 归约过程利用"forking lemma"技术，通过两次查询同一消息的不同随机 $k$ 值来提取离散对数
关键安全缺陷
#### 1. 随机数重用攻击
若签名过程中 $k$ 值被重复使用，攻击者可通过两个签名恢复私钥：
已知：
- 签名 $(r, s_1)$ 对应消息 $M_1$，使用相同 $k$
- 签名 $(r, s_2)$ 对应消息 $M_2$，使用相同 $k$（$r$ 值相同）
相减得： $$s_1 - s_2 = k^{-1}(e_1 - e_2) \bmod q$$ $$k = (e_1 - e_2)(s_1 - s_2)^{-1} \bmod q$$
一旦获取 $k$，即可计算私钥： $$x = (e_1 - sk)r^{-1} \bmod q$$
历史案例：2010 年 Sony PS3 破解事件即因 HMAC-SHA1 签名中重用随机数导致私钥泄露。
#### 2. 小群攻击（Small Subgroup Attack）
若参数选择不当（$q$ 过小或存在小因子），攻击者可利用 Pohlig-Hellman 算法降低 DLP 难度。应确保 $q$ 为大素数，且 $p = 2q + 1$（安全素数）。
#### 3. 确定性变体：DSA 的改进
ElGamal 签名的随机数依赖问题导致 DSA（FIPS 186-1）采用确定性构造：$k$ 由消息哈希和私钥派生，而非随机选取。但这引入了新的安全考虑（如 NIST 推荐的 $k$ 生成机制）。
与国密 SM2 签名的关系
技术演进路径
ElGamal 签名 (1985)
↓ DLP 基础，EUF-CMA 可证明安全
↓ RFC 2409 (IKE) 采用
↓ DSA (1991) 标准化
↓ 椭圆曲线扩展
↓ ECDSA (1992)
↓ 国密适配
↓ SM2 签名 (GM/T 0003.2-2012)SM2 签名对 ElGamal 的改进
| 特性 | ElGamal 签名 | SM2 签名 |
|---|---|---|
| 数学群 | $\mathbb{Z}_p^*$ | 椭圆曲线群 $E(\mathbb{F}_p)$ |
| 私钥长度 | 与 $p$ 同长 | 256 位（$n$ 为曲线阶） |
| 随机数要求 | 必须保密 | 必须保密（RFC 6979 确定性派生） |
| ZA 预处理 | 无 | 有（身份标识预处理） |
| 签名长度 | 2 × 256 位 | 64 字节（r, s 各 32 字节） |
ElGamal 签名： $$s = k^{-1}(H(M) - xr) \bmod q$$
SM2 签名： $$s = \frac{(1 + d_A)^{-1}(k - r \cdot d_A) \bmod n}{\bmod n}$$
其中 $d_A$ 为私钥，$(1 + d_A)^{-1}$ 项是 SM2 的独特设计，用于增强安全性。
工程实践要点
参数生成示例（Python）
from gmssl import sm3, func
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
# 安全参数：使用 P-256 曲线等价于 SM2
# ElGamal 签名在有限域 Z_p* 上，此处用椭圆曲线类比
def generate_elgamal_params(bits=2048):
"""生成 ElGamal 签名参数"""
import random
# 生成大素数 p
p = generate_safe_prime(bits)
q = (p - 1) // 2 # 安全素数，q 也是素数
# 生成生成元 g，阶为 q
h = random.randrange(2, p - 1)
g = pow(h, 2, p) # g = h^2 mod p，阶为 q
while g <= 1:
h = random.randrange(2, p - 1)
g = pow(h, 2, p)
return p, q, g
def generate_safe_prime(bits):
"""生成安全素数 p = 2q + 1"""
import Crypto.Util.number as cun
while True:
q = cun.getPrime(bits)
p = 2 * q + 1
if cun.isPrime(p):
return p, q常见实现陷阱
- 使用
pow(g, k, p)而非pow(g, k, p)：需确保 $k < q$，避免溢出 - 忽略 $r = 1$ 的无效情况：某些实现未检查 $r \neq 1$
- 哈希函数选择不当：应使用带安全属性的哈希（如 SHA-256），而非 MD5
- 随机数熵不足：$k$ 必须密码学安全随机，不得使用
random.randint()
性能特征
签名与验证速度
| 操作 | 时间复杂度 | 典型延迟（3072 位） |
|---|---|---|
| 密钥生成 | $O(\log^3 p)$ | ~50ms |
| 签名生成 | $O(\log^3 p)$ | ~100ms |
| 签名验证 | $O(\log^3 p)$ | ~150ms |
| 哈希计算 | $O(n)$ | ~1μs |
注：以上数据基于 Intel Xeon Gold 6248R @ 3.0GHz，OpenSSL 3.0。实际性能因实现优化而异。
与国密算法对比
| 算法 | 密钥长度 | 签名长度 | 签名速度 | 验证速度 |
|---|---|---|---|---|
| ElGamal (3072位) | 3072 位 | 512 位 | ~100ms | ~150ms |
| SM2 | 256 位 | 64 字节 | ~0.5ms | ~1ms |
| RSA-3072 | 3072 位 | 384 字节 | ~50ms | ~5ms |
应用场景与局限
适用场景
- 理论教学：第一个可证明安全的签名方案，适合讲解 EUF-CMA 概念
- 历史分析：理解 DSA/ECDSA/SM2 的技术渊源
- 学术研究：签名安全证明方法学（forking lemma、ROM 归约）
不推荐使用场景
- 生产系统：已被 DSA/ECDSA/EdDSA 等更高效的方案取代
- 资源受限设备：3072 位参数导致签名冗长（512 位），带宽开销大
- 高并发场景：有限域运算比椭圆曲线运算慢一个数量级
现代替代方案
| 场景 | 推荐方案 | 理由 |
|---|---|---|
| 通用签名 | Ed25519 | 确定性签名，无随机数依赖，速度快 |
| 国密合规 | SM2 签名 | GM/T 0003.2-2012 标准，密评通过 |
| 后量子安全 | SLH-DSA / Dilithium | 抵御量子计算机攻击 |
相关标准与参考
标准引用
- RFC 2409：Internet Key Exchange (IKE) 协议中采用 ElGamal 签名
- GM/T 0003.2-2012：SM2 数字签名算法规范（国密标准）
- FIPS 186-5：Digital Signature Standard（DSA）
理论参考
- ElGamal, T. (1985). "A Public-Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm Problem." *IEEE Trans. Info. Theory*, 31(4): 469-472.
- Shoup, V. (2000). "On Formal Models for Secure Signature Schemes." *Crypto '91*.
- RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA).
相关实践链接
- SM2 签名编码指南：SM2 签名 DER/ASN.1 编码格式详解
- ElGamal 加密方案：同源的加密方案对比
延伸阅读：
- Diffie-Hellman 密钥交换与 ECDH：离散对数问题的密钥交换应用
- 数字签名算法 DSA：从 ElGamal 到 DSA 的标准化演进