【密码学】 确定DSA签名方案(RFC 6979)

有读者问，可不可以讲解一下RFC 6979的签名方案，具体和原始的DSA差异在哪里，具体的过程是什么，因为DSA我之前已经简单的描述过具体的过程了，因此，这个看起来比较好水（写），也发现，我好久没写过类似的知识了，捎带着回顾一下吧，所以就来水了这一篇文章。

背景知识

我们首先来回顾一下，DSA签名的结构，这里的DSA我们指的是原始的DSA, 而不是后续出现的基于椭圆曲线的签名(ECDSA)，或者基于M-LWE的ML-DSA，以及基于无状态哈希的SHL-DSA，有关于ECDSA，确定性算法来自于一个RFC[1]，但是本篇文章，我们不做过多讨论，然后对于后面两个，目前是没有相关的RFC的，也有可能是我没找到。

对于签名算法呢，还是老的三个部分，密钥生成，签名算法，以及验签算法。

密钥生成

• p: 一个素数，满足，其中，并且L是64的倍数
• q: q是p-1的素因子，其中要求
• g: 其中h满足，并且
• x: x是一个随机的整数，满足，这个作为用户的私钥
• y: 作为用户的公钥

签名过程

接下来，我们来看一下DSA签名算法的过程，整体过程并不复杂，具体过程如下

• k: 首先选择一个随机值，满足

这样就完成了，签名的过程。

验签过程

接下来我们一起来看一下签名验证的过程，具体过程如下

• 验证

RFC6979

接下来，我们来看一下RFC当中的签名方案，这里和上面签名的不同点在于k不再是随机生成，而是根据某种特定的算法，确定性生成，在保持参数，私钥不变的前提下，最终生成的签名也是确定的。

K生成初始化

这里，我们来简单描述一下吧，首先计算m的哈希值

• h1 = H(m)

然后，令初始的V的长度为8 * ceil(hlen/8)，初始化的值为

初始化K为全0，其中长度也为8 * ceil(hlen/8)，然后，计算

• K = HMAC_K(V || 0x00 || x || h1)

之后，令

• V = HMAC_K(V)

后面，再次更新K，注意这里中间拼接的为0x01，也就是

• K = HMAC_K(V || 0x01 || x || h1)

再次，计算V，可以得到

• V = HMAC_K(V)

因为，我们的K是要满足一定的条件的，也就是k要在模q的时候存在逆元，因此，我们需要执行某个算法，直到找到k为止，具体算法如下。

K生成

令T初始化为空串，然后计算

• V = HMAC_K(V)
• T = T || V
• k = bits2int(T)

这里，判断k是否合理(也就是满足存在逆元)，如果合理，输出k, 如果不合理，计算

• K = HMAC_K(V || 0x00)
• V = HMAC_K(V)

重复上面的操作，得到新的T，再次来验证k的合法性，好了，到这里，就描述完成了。

代码实现

这里，简单的用Python来实现一下吧。

import hmac
import hashlib
from typing import Union, Optional


def bits2int(data: bytes, qlen: Optional[int] = None) -> int:
    x = int.from_bytes(data, byteorder='big')
    if qlen is not None:
        x &= (1 << qlen) - 1
    return x


def int2octets(x: int, rlen: int) -> bytes:
    return x.to_bytes(rlen, byteorder='big')


def bits2octets(v: bytes, q: int, qlen: int, rlen: int) -> bytes:
    z1 = bits2int(v, qlen)
    z2 = z1 % q
    return int2octets(z2, rlen)


def generate_k(msg_hash: Union[str, bytes],
               private_key: int,
               q: int,
               hash_func=hashlib.sha1) -> int:
    if isinstance(msg_hash, str):
        msg_hash = bytes.fromhex(msg_hash)

    holen = hash_func().digest_size
    rolen = (q.bit_length() + 7) // 8
    qlen = q.bit_length()

    x = int2octets(private_key, rolen)

    h1 = bits2octets(msg_hash, q, qlen, rolen)

    V = b'x01' * holen
    K = b'x00' * holen

    K = hmac.new(K, V + b'x00' + x + h1, hash_func).digest()
    V = hmac.new(K, V, hash_func).digest()
    K = hmac.new(K, V + b'x01' + x + h1, hash_func).digest()
    V = hmac.new(K, V, hash_func).digest()

    # 生成 k 值
    while True:
        T = b''
        while len(T) < rolen:
            V = hmac.new(K, V, hash_func).digest()
            T = T + V

        k = bits2int(T, qlen)
        if k >= 1 and k < q:
            return k

        K = hmac.new(K, V + b'x00', hash_func).digest()
        V = hmac.new(K, V, hash_func).digest()


def test_vec_from_rfc6979():
    q = 0x996F967F6C8E388D9E28D01E205FBA957A5698B1

    private_key = 0x411602CB19A6CCC34494D79D98EF1E7ED5AF25F7
    msg_hash = "8151325dcdbae9e0ff95f9f9658432dbedfdb209"

    k = generate_k(msg_hash, private_key, q)
    print(f"Generated k: {hex(k)}")


if __name__ == "__main__":
    test_vec_from_rfc6979()

可以发现，这里和RFC的输出是一样的，好了，实现没毛病。

总结

RFC 6979 提供了一个优秀的解决方案，用于改进 DSA/ECDSA 签名的安全性和可靠性。通过确定性生成 k 值，它有效防止了因随机数生成缺陷导致的私钥泄露风险，同时保持了签名系统的其他安全属性。对于需要实现数字签名的系统，采用 RFC 6979 是一个值得推荐的选择，本文主要是针对于DSA进行的描述，当然RFC里面是支持ECDSA的，因为他们两个原理非常的相似，只不过一个是基于一个乘法的循环群，一个是基于椭圆曲线的加法群，其他的没太大差别，好了，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://datatracker.ietf.org/doc/html/rfc6979