【基于哈希的密码体系】MSS(默克尔签名模式)

本篇文章，我们接着来聊基于哈希的签名，这次，我们首先开始介绍一个结构，那就是「默克尔树」(Merkle Tree)，这个结构，其实之前文章当中，我们再来回顾一下，因为，后面介绍的其他的签名方案，也是要基于默克尔树[1]的。

背景知识

首先，简单回顾一下默克尔树的概念，默克尔树，是一种二叉树结构，其中每个叶子节点存储数据块的哈希值，非叶子节点存储其子节点哈希值的组合。其主要目的是高效验证数据的完整性和一致性。

结构细节

对于默克尔树，其中结构分为三个部分，分别是

1. 叶子节点: 叶子结点位于树的最底层，包含着实际的数据
2. 非叶子节点: 存储两个字节点的哈希值的组合
3. 根节点: 树的根，代表整个数据集的哈希值

计算方式

1. 首先，得到多个数据块，我们考虑二叉树，因此，分块数目要是，其中H是树的高度，否则的话，可以考虑执行一下Padding，补到满足数目要求。
2. 计算叶子节点的哈希，对于每个数据块，计算其哈希值。
3. 构建哈希树，逐步组合相邻节点的哈希，构建非叶子节点，直到只剩下一个节点。

好了，到这里，我们就简单的回顾了一下默克尔树的结构的知识，本身，这个结构还是相对比较好理解一点的。

通过，这一个图，大家应该好理解，具体默克尔树的结构，简单的解释一下这里用到的符号

• 表示数据，然后, ，其中g是一个哈希函数
• , 表示拼接相邻数据块，然后计算对应的哈希值

有了前面的知识，我们就可以来介绍默克尔签名算法了。

MSS(默克尔签名方案)

和之前的文章一样，这里也分为密钥生成，签名，和验签的过程，那么接下来，我们分别来看一下这个过程。

密钥生成

首先，签名者选择一个数的层级H, 这里，对于这个签名算法来说，可以签名或者验签个数据，这里，实际上，也一定程度的解决了，同一个密钥不能签署多个文档的问题，然后，签名者生成个OTS签名公私钥对其中，，其中是私钥，是公钥，然后，对于默克尔树的叶子节点为。然后，我们就可以来构建我们在上文提到过的默克尔树了。

这里，对于任意的, 其中， 是对应节点的高度，我们有

上图，是H=3情况的一个例子，我们可以发现，我们需要计算个OTS的密钥对以及次的哈希运算。

签名

MSS底层，需要采用OTS的方案，对于OTS, 我们之前介绍了很多了，可以采用任意一个，本文的例子当中呢，我们用上一篇文章讲过的WOTS吧，这里，实际上，我们在代码实现过程中才能用到，这里我们假设是对应OTS签名的结果，我们用第个私钥，其中，这里，对于消息内容，我们需要发送对应的。

之后，验证者要想要恢复根节点，我们实际上是不需要传输完整的默克尔树的，我们只需要传输一部分节点就可以了，我们传输的节点为。

首先，我们来看一张图，假设，我们s=3, 我们还是用上面的H=3的情况。

可以发现，这里的红色节点，我们是可以根据直接计算出来的，然后，我们只需要获得这三个蓝色的节点，实际上，我们就可以恢复出来整个默克尔树的根，我们可以总结出来，我们需要传输的节点

到这里，我们最终传输的数据为

好了，到这里，签名的过程，就描述完了，接下来，我们来看一下验签的算法

验签

实际上，验证过程，我们先拿到来验证的正确性，然后，我们需要根据来恢复，整个默克尔树，来验证根节点是否成立，具体的验证路径为

这里，，，然后我们判断是否和我们公布的默克尔根相等就可以了。

代码实现

这里，我们采用我们之前讲过的WOTS的方案，对于WOTS的代码[3]，大家翻一下我的上一篇文章，这里不重复贴出来了，这里，我们还是用MD5做例子吧，本身这个代码，大家也不要用于生产环境，如果要采用基于哈希的签名，可以采用SLH-DSA。

import hashlib
import wots


def hash_data(data):
    return hashlib.md5(data).digest()


def build_merkle_tree(data_blocks):
    if not data_blocks:
        return []

    hashes = [hash_data(data) for data in data_blocks]

    tree = [hashes]

    while len(hashes) > 1:
        new_level = []
        for i in range(0, len(hashes), 2):
            if i + 1 < len(hashes):
                combined_hash = hash_data(hashes[i] + hashes[i + 1])
            else:
                combined_hash = hash_data(hashes[i] + hashes[i])
            new_level.append(combined_hash)
        hashes = new_level
        tree.append(hashes)

    return tree


def get_merkle_root(tree):
    return tree[-1][0] if tree else None


def get_merkle_proof(tree, index):
    proof = []
    for level in range(len(tree) - 1):
        level_len = len(tree[level])        
        sibling_index = index ^ 1  
        if sibling_index < level_len:
            proof.append(tree[level][sibling_index])
        index //= 2

    return proof


def verify_proof(leaf, proof, root, index):
    current_hash = hash_data(leaf)
    for sibling_hash in proof:
        if index % 2 == 0:
            current_hash = hash_data(current_hash + sibling_hash)
        else:
            current_hash = hash_data(sibling_hash + current_hash)
        index //= 2
    return current_hash == root


def key_gen(H=3):
    key_items = [wots.key_gen() for _ in range(2 ** H)]
    data_blocks = [hash_data(b"".join(item[1])) for item in key_items]
    tree = build_merkle_tree(data_blocks)
    pk = get_merkle_root(tree)
    return key_items, pk, tree


def sign(m, s, sk, tree):
    x, y = sk
展开收缩

    sigma = wots.sign(m, x)
    return s, sigma, y, get_merkle_proof(tree, s)


def verify(m, sigma, pk):
    s, sigma, y, proof = sigma
    return wots.verify(m, sigma, y) and verify_proof(hash_data(b"".join(y)), proof, pk, s)


if __name__ == '__main__':
    sk, pk, tree = key_gen()
    sigma = sign(b"LittleQ", 3, sk, tree)
    print(verify(b"LittleQ", sigma, pk))

总结

本文呢，我们主要是讲解了MSS的签名方案，这里的公钥，实际上，我们压缩到了一个节点，并且，我们是可以对于多个文档进行签名的，后续介绍的签名方案，也是基于此，因此这个结构还是要提前讲一下，这里的问题是，我们的私钥，就会变得非常的大，解决这个问题的方法也不难，实际上，我们可以采用PRNG来生成Key-Pair, 对于这个方案呢，我们后面再聊，由于本人水平有限，难免会出现有哪里理解的不太到位的地方，欢迎读者和我交流，哪里有看不懂的地方，也可以留言，或者私信，好了快乐的时光总过得特别快，又到了说再见的时候了，我们下次再见。

参考资料

1. Merkle, R.C.: A Digital Signature Based on a Conventional Encryption Function. Proceedings of Crypto ’87, pp. 369–378.
2. https://www.e-reading-lib.com/bookreader.php/135832/Post_Quantum_Cryptography.pdf
3. https://mp.weixin.qq.com/s/9ik2fPXH3OP1q7SrH-wLZw