DSA 数字签名算法原理详解：从 ElGamal 到 FIPS 186-5 的演进与退役
概述
Digital Signature Algorithm (DSA) 是美国国家标准与技术研究院 (NIST) 于 1994 年发布的数字签名标准 (FIPS 186) 的核心算法，至今已有近三十年历史。DSA 基于 ElGamal 签名方案的变体，利用离散对数问题 (DLP) 的安全性构造签名机制。作为美国联邦信息处理标准，DSA 在数字证书、代码签名、政府文档等场景中长期承担关键角色。
然而，随着椭圆曲线密码学 (ECC) 的成熟和 EdDSA 等新一代签名方案的标准化，NIST 在 2023 年发布的 FIPS 186-5 中正式将 DSA 标记为"遗留算法"，禁止用于新应用。本文将从数学原理、协议设计、安全性分析和历史演进四个维度，完整解析 DSA 的一生。
数学基础
离散对数问题
DSA 的安全性建立在有限域上离散对数问题的困难性之上。给定素数 $p$、生成元 $g \in \mathbb{Z}_p^*$ 和公钥 $y = g^x \bmod p$，计算私钥 $x$ 在计算上不可行（当 $p$ 足够大时）。
ElGamal 签名方案的缺陷
DSA 的设计直接受 ElGamal 签名方案 (1985) 启发，但改进了以下缺陷：
- 签名长度过长：ElGamal 签名长度为 $2 \times |p|$，DSA 将其缩短为 $2 \times |q|$（其中 $q$ 是 $p-1$ 的 160/256 位素因子）
- 计算效率低：通过引入子群结构减少模幂运算的域大小
- 安全问题：原始 ElGamal 方案存在 existential forgery 漏洞
核心参数体系
DSA 定义在以下全局公共参数之上：
| 参数 | 含义 | FIPS 186-4 推荐 |
|---|---|---|
| $p$ | $L$ 位素数，定义有限域 $\mathbb{Z}_p$ | 2048 / 3072 位 |
| $q$ | $p-1$ 的 $N$ 位素因子，定义子群阶 | 224 / 256 位 |
| $g$ | 子群生成元，满足 $g^q \equiv 1 \pmod{p}$ | $g = h^{(p-1)/q} \bmod p$ |
算法设计
密钥生成
1. 选择全局参数 (p, q, g)
2. 随机选择私钥 x ∈ [1, q-1]
3. 计算公钥 y = g^x mod p签名生成
对消息 $m$ 的签名过程：
1. 计算消息摘要 H = SHA-256(m) （或其他 SHA 变体）
2. 随机选择临时密钥 k ∈ [1, q-1]（每签名不同，必须密码学安全随机）
3. 计算 r = (g^k mod p) mod q
4. 计算 s = k^(-1) * (H + x*r) mod q
5. 输出签名 (r, s)注意：
- 若 $r = 0$ 或 $s = 0$，需重新选择 $k$
- $k$ 必须是密码学安全的随机数，$k$ 的泄露直接导致私钥泄露
- 从 $(r, s)$ 和 $m$ 可恢复 $k$：$k = s^{-1} \cdot (H + x \cdot r) \bmod q$，进而恢复 $x$
签名验证
验证者无需知道私钥 $x$：
1. 计算消息摘要 H = SHA-256(m)
2. 计算 w = s^(-1) mod q
3. 计算 u1 = H * w mod q
4. 计算 u2 = r * w mod q
5. 计算 v = (g^u1 * y^u2 mod p) mod q
6. 验证 v == r数学原理推导
验证等式的正确性证明（基于生成元的子群性质）：
由 $y = g^x \bmod p$，将 $w = s^{-1}$ 代入：
$$v = g^{H \cdot s^{-1}} \cdot y^{r \cdot s^{-1}} \bmod p$$
$$= g^{H \cdot s^{-1}} \cdot g^{x \cdot r \cdot s^{-1}} \bmod p$$
$$= g^{(H + xr) \cdot s^{-1}} \bmod p$$
由于 $s = k^{-1} \cdot (H + xr)$，有 $s^{-1} = (H + xr)^{-1} \cdot k$：
$$= g^{(H + xr) \cdot (H + xr)^{-1} \cdot k} \bmod p = g^k \bmod p$$
取模 $q$ 后等于 $r$，验证通过。
安全性分析
已知攻击
#### 1. 临时密钥 $k$ 的重用攻击
这是 DSA 最致命的安全风险。如果两个不同的消息 $m_1, m_2$ 使用相同的 $k$ 签名：
$$s_1 = k^{-1}(H_1 + xr) \bmod q$$ $$s_2 = k^{-1}(H_2 + xr) \bmod q$$
两式相减：
$$s_1 - s_2 = k^{-1}(H_1 - H_2) \bmod q$$
$$k = (H_1 - H_2)(s_1 - s_2)^{-1} \bmod q$$
求得 $k$ 后，私钥 $x = r^{-1}(s \cdot k - H) \bmod q$ 立即泄露。
真实案例：2010 年索尼 PS3 的 ECDSA 签名实现因 $k$ 固定导致私钥被恢复（虽为 ECDSA，但 DSA 面临同样风险）。
#### 2. 弱 $k$ 值攻击
- $k$ 可预测：若伪随机数生成器 (PRNG) 有缺陷，$k$ 可被推断
- 有偏 $k$：若 $k$ 不完全随机但统计分布有偏，可通过 lattice attack 恢复私钥
- RFC 6979：确定性 $k$ 生成方案，使用 HMAC-DRBG 从 $(m, x)$ 派生 $k$，消除随机源问题
若参数 $(p, q, g)$ 选择不当（例如 $q$ 非素数或 $g$ 阶不正确），可能导致签名泄漏部分私钥信息。FIPS 186-4 明确要求参数生成算法必须可验证。
#### 4. 量子计算威胁
Shor 算法可在多项式时间内求解离散对数，量子计算机上的 DSA（以及 ECDSA、SM2 等基于 DLP/ECDLP 的方案）均不安全。NIST FIPS 203 (ML-KEM)、FIPS 204 (ML-DSA)、FIPS 205 (SLH-DSA) 为后量子替代方案。
FIPS 186-5 退役原因
2023 年 2 月，NIST 发布 FIPS 186-5 最终版，对 DSA 做出以下定性：
- 不再推荐用于新应用：仅允许验证历史签名，禁止生成新签名
- 密钥长度劣势：DSA-2048 提供约 112 位安全强度，等效安全性的 ECDSA 仅需 224 位密钥
- 签名效率低：DSA 签名需要模逆运算（$k^{-1} \bmod q$），ECDSA 虽然也需要但可通过 Jacobian 投影坐标优化，EdDSA 则完全避免了模逆
- 实现复杂性：$k$ 的随机生成要求高，实现者容易出错（如索尼 PS3 事件）
- 功能受限：DSA 仅支持签名，不支持密钥交换（对比 ECDH）或加密（对比 ECIES）
历史演进
| 标准版本 | 发布时间 | 关键变化 |
|---|---|---|
| FIPS 186-1 | 1998 | 仅允许 SHA-1，DSA-512/1024 |
| FIPS 186-2 | 2000 | 引入 SHA-256，扩展密钥长度 |
| FIPS 186-3 | 2009 | SHA-2 系列，SHA-384/512 |
| FIPS 186-4 | 2013 | 增加曲线参数生成要求 |
| FIPS 186-5 | 2023 | DSA 退役，新增 EdDSA (Ed25519/Ed448) |
与其他签名算法对比
| 特性 | DSA | ECDSA | EdDSA (Ed25519) | SM2 |
|---|---|---|---|---|
| 数学问题 | DLP (mod p) | ECDLP (短 Weierstrass) | ECDLP (Edwards) | ECDLP (素数域) |
| 签名唯一性 | 非唯一（$k$ 随机） | 非唯一（$k$ 随机） | 唯一（确定性签名） | 唯一（确定性） |
| 伪随机输出 | 否 | 否 | 理论保证 | 否 |
| 模逆运算 | 是（每签名） | 是 | 否 | 否 |
| 签名长度 | 2q (~64 字节) | 2×坐标 (~64 字节) | 64 字节 (Ed25519) | 2×坐标 (~64 字节) |
| 验签速度 | 慢（双模幂） | 中 | 快（单标量乘） | 中 |
| 标准状态 | 遗留 (FIPS 186-5) | 活跃 (FIPS 186-5) | 活跃 (FIPS 186-5) | 活跃 (GB/T 32905) |
DSA vs ECDSA
ECDSA 本质上是 DSA 的椭圆曲线版本，将有限域上的运算迁移到椭圆曲线上：
- DSA: $r = (g^k \bmod p) \bmod q$ → ECDSA: $r = x\text{-coord}(k \cdot G) \bmod n$
- ECDSA 使用更短的密钥（256 位 vs 2048 位）获得等效安全性
- 但 ECDSA 同样面临 $k$ 重用攻击（Sony PS3 事件）
DSA vs EdDSA
EdDSA (Edwards-curve Digital Signature Algorithm) 由 Daniel J. Bernstein 等人设计：
- 确定性 $k$：$k = H(h_b, M)$ 从私钥和消息派生，消除随机源风险
- 签名唯一性：对同一消息和私钥，签名结果唯一
- 侧信道安全：统一的倍点公式，无分支和内存访问模式差异
- 更快：比 ECDSA 验签快约 4 倍
DSA vs SM2
SM2 是中国国家标准 (GB/T 32918 / GM/T 0003) 定义的椭圆曲线签名算法：
- SM2 使用国密 SM3 哈希算法，DSA 使用 SHA-2
- SM2 的签名输入包含用户 ID 和曲线参数哈希，提供身份绑定
- SM2 验签仅需一次标量乘（对比 ECDSA 的两次），效率更高
- FIPS 186-5 明确将 Ed25519 和 Ed448 列为推荐算法，而 SM2 不在美国联邦推荐范围内
实现注意事项
参数验证
使用任何 DSA 实例前，必须验证：
- $p$ 是素数，长度为 2048 或 3072 位
- $q$ 是素数，整除 $(p-1)$
- $g \in [2, p-2]$ 且 $g^q \equiv 1 \pmod{p}$
- $y \in [1, p-1]$ 且 $y^q \equiv 1 \pmod{p}$（公钥在正确子群中）
恒定时间实现
签名中的模幂和模逆运算必须恒定时间执行，防止侧信道泄露 $k$ 或 $x$。
确定性 $k$ 生成
遵循 RFC 6979 使用 HMAC-DRBG 生成 $k$：
k = drabg(H, x, 迭代次数)确保即使同一消息多次签名也产生相同签名（消除 $k$ 重用风险）。
退役影响
FIPS 186-5 对 DSA 的退役政策分为三个阶段：
- 即时生效 (2023-02)：禁止生成新的 DSA 签名
- 过渡期：允许验证历史 DSA 签名（已签名的文档、证书在有效期内的仍有效）
- 最终淘汰：具体日期取决于使用领域的合规要求，预计 2026-2028 年间
DSA 的替代方案
| 场景 | 替代方案 | 标准 |
|---|---|---|
| 通用数字签名 | Ed25519 / Ed448 | FIPS 186-5, RFC 8032 |
| 传统有限域场景 | RSA-PSS | FIPS 186-5 |
| 国密合规 | SM2 | GB/T 32918, GM/T 0003 |
| 后量子 | ML-DSA (Dilithium) | FIPS 204 |
总结
DSA 作为最早的标准化数字签名算法之一，在公钥基础设施 (PKI) 发展中发挥了重要作用。其基于离散对数问题的简洁设计和与 ElGamal 的紧密联系，使其成为理解签名算法的良好起点。
然而，DSA 的固有缺陷——非唯一签名、$k$ 管理困难、密钥/签名长度过大——使其难以满足现代应用的安全和效率需求。FIPS 186-5 的退役决定是密码学社区向更高效、更安全签名方案（EdDSA、后量子签名）的自然演进。
理解 DSA 仍有其教育价值：它是理解 ECDSA、Schnorr 签名、EdDSA 的共同基础，也是理解"为何确定性签名优于随机签名"的经典案例。
参考来源
- FIPS 186-5 Digital Signature Standard (DSS) — NIST 正式标准
- RFC 6979: Deterministic Usage of DSA and ECDSA — 确定性 $k$ 生成
- NIST SP 800-57 Recommendation for Key Management — 密钥管理建议
- FIPS 186-4 (Historical) — DSA 最后活跃版本
- Wikipedia: Digital Signature Algorithm — 历史与实现细节
相关实践
- DSA 签名在 OpenSSL 中的实现与限制 — Python 密码学实战
- 数字签名方案深度对比：SM2 vs ECDSA vs EdDSA — 签名算法横向对比
- 后量子密码学：从量子威胁到 NIST 标准化的新密码体系 — 了解 ML-DSA 等替代方案
- Schnorr 签名算法原理：数学基础、协议设计与门限签名 — 理解签名算法的演进方向