4、DSA签名算法：DSA算法原理、DSA签名与验签实现、DSA参数生成

聊完RSA，咱们来看看另一个经典——DSA。说实话，我在刚接触密码学时，总觉得DSA和RSA差不多，都是非对称签名嘛。但实际用下来，你会发现它俩的“脾气”完全不同。DSA是美国国家标准与技术研究院（NIST）在1991年提出的数字签名标准，它的核心思想不是基于大整数分解，而是基于离散对数难题。

嗯，这里要注意：DSA只能做签名，不能做加密。这一点和RSA不一样。你想想看，如果只需要签名验签，DSA其实是个很纯粹的选择。

4.1 DSA算法核心原理

DSA的数学基础是有限域上的离散对数问题。说白了，就是给定一个大素数p和一个生成元g，已知g^x mod p的值，想反推出x，在计算上是不可行的。这个“单向性”就是DSA安全的根基。

DSA的签名过程会生成两个值：r和s。验签时，验签方用公钥和签名(r, s)来验证签名是否由对应的私钥生成。整个流程涉及三个关键参数：

• p：一个大素数，长度通常在1024位以上
• q：p-1的一个素因子，长度160位或256位
• g：一个生成元，满足g^q ≡ 1 mod p

我个人习惯把DSA的签名过程想象成“用私钥在随机数上盖章”。每次签名都会引入一个随机数k，所以同一个消息每次签名得到的(r, s)都不一样。这不是bug，是特性——它天然抗重放攻击。

4.2 DSA参数生成

参数生成是DSA的第一步，也是最容易被忽视的一步。很多开发者直接拿现成的参数用，但理解生成过程能帮你避免不少坑。

标准的DSA参数生成流程如下：

1. 选择一个哈希函数H，比如SHA-256
2. 选择一个合适的密钥长度L和N（L是p的位数，N是q的位数）
3. 生成一个N位的素数q
4. 生成一个L位的素数p，满足p-1能被q整除
5. 计算生成元g = h^(p-1)/q mod p，其中h是随机数

下面是一个简化的参数生成代码示例：

// 伪代码：DSA参数生成
function generateDSAParams(L, N):
    // 1. 生成素数q（N位）
    q = generatePrime(N)
    
    // 2. 生成素数p（L位），满足 p ≡ 1 mod q
    while true:
        p = generatePrime(L)
        if (p - 1) % q == 0:
            break
    
    // 3. 计算生成元g
    h = random(2, p - 2)
    g = pow(h, (p - 1) / q, p)
    if g == 1:
        // 重新选h
        h = random(2, p - 2)
        g = pow(h, (p - 1) / q, p)
    
    return (p, q, g)

实际项目中，我建议直接用标准化的参数集，比如NIST推荐的P-256、P-384等。自己生成参数容易出问题，尤其是素数检测不够严格时。

4.3 DSA签名与验签实现

好了，参数有了，咱们来看看签名和验签到底怎么做的。我尽量用最直白的方式讲清楚。

4.3.1 签名过程

签名需要私钥x和消息m。流程如下：

1. 生成一个随机数k，范围在[1, q-1]
2. 计算 r = (g^k mod p) mod q
3. 计算 s = k^-1 * (H(m) + x * r) mod q
4. 签名结果就是(r, s)

这里有个关键点：如果r或s等于0，必须重新选k再算一遍。虽然概率极低，但规范里明确写了，不能跳过。

// 伪代码：DSA签名
function dsaSign(message, privateKeyX, params):
    (p, q, g) = params
    hash = SHA256(message)
    
    while true:
        k = random(1, q - 1)
        r = pow(g, k, p) % q
        if r == 0:
            continue
        
        k_inv = modInverse(k, q)
        s = (k_inv * (hash + privateKeyX * r)) % q
        if s == 0:
            continue
        
        break
    
    return (r, s)

4.3.2 验签过程

验签用公钥y（y = g^x mod p）和签名(r, s)。流程是：

1. 检查r和s是否在[1, q-1]范围内，不在直接拒绝
2. 计算 w = s^-1 mod q
3. 计算 u1 = (H(m) * w) mod q
4. 计算 u2 = (r * w) mod q
5. 计算 v = (g^u1 * y^u2 mod p) mod q
6. 如果v等于r，验签通过；否则失败

// 伪代码：DSA验签
function dsaVerify(message, signature, publicKeyY, params):
    (p, q, g) = params
    (r, s) = signature
    
    // 范围检查
    if r < 1 or r > q - 1:
        return false
    if s < 1 or s > q - 1:
        return false
    
    hash = SHA256(message)
    w = modInverse(s, q)
    u1 = (hash * w) % q
    u2 = (r * w) % q
    
    v = (pow(g, u1, p) * pow(publicKeyY, u2, p)) % p % q
    
    return v == r

4.4 DSA与RSA签名对比

很多同学会问：DSA和RSA到底选哪个？我个人的经验是，看场景。下面这张表可以帮你快速决策：

对比维度	DSA	RSA
数学基础	离散对数	大整数分解
签名长度	固定（320位或512位）	与密钥长度相同
签名速度	较慢（需模幂运算）	较快
验签速度	较快	较慢
随机数要求	高（k必须随机）	低（填充方案可控）
能否加密	不能	能

你看，DSA验签比RSA快，但签名比RSA慢。如果你的场景是“一次签名，多次验签”（比如软件分发），DSA更合适。反过来，如果是“多次签名，偶尔验签”（比如即时通讯），RSA可能更好。

4.5 DSA知识体系总览

为了让你对整个DSA有个全局印象，我画了张图：

4.6 实战中的避坑指南

最后，我把自己这些年踩过的坑总结一下，希望能帮你少走弯路：

• 随机数k不能复用：这是DSA最大的坑。两个签名用了同一个k，私钥直接暴露。我曾经在审计一个区块链项目时，发现他们的签名库在并发场景下会复用k值，吓得我当场让他们停服修复。
• 参数长度要跟上时代：NIST在2016年就建议弃用1024位DSA。现在至少用2048位p和256位q。别为了省那点计算资源牺牲安全性。
• 哈希函数要匹配：DSA的哈希输出长度不能超过q的位数。用SHA-512配160位的q，哈希值会被截断，虽然不影响功能，但会降低安全性。
• 不要自己实现：除非你是密码学专家，否则永远用成熟的密码库（OpenSSL、Bouncy Castle等）。自己实现DSA，十有八九会出问题。