【基于哈希的密码体系】One-time key-pair generation using an PRNG

之前呢，我们介绍了不少的基于哈希的签名方案，我们之前密钥都是随机生成的，因此，我们的私钥都是随机生成的，因此，这里，我们需要存储巨大的私钥，那么，我们是否有可能采用PRNG算法，只通过一个种子，就可以生成完整的私钥呢，答案是肯定的，那么我们就来看一下，这个方法。

知识回顾

我们，先来回顾一下PRNG的相关知识。伪随机数生成器（PRNG）是一个算法系统，设计用于从给定的初始种子值生成一个确定性但表现为随机的数值序列。PRNG的输出具有统计上的随机性，尽管其生成过程是完全确定的。这种生成器在计算复杂性、周期长度及分布均匀性上进行优化，以满足各种非加密和加密应用需求。

我们，来看一个稍微详细一点的定义，假设种子是初始种子，PRNG定义为一个递归序列生成函数f, 满足

其中，是第n个状态，是生成的下一个状态的值，序列是可以通过一个输出函数g计算得到

其中，是第n个伪随机数。接下来，我们来看一下，PRNG的一些特性

PRNG关键特性

• 「确定性」: 给定相同的种子，可以得到相同的序列。
• 「均匀分布」: 在理想情况下，生成的数值应在所需范围内均匀分布。
• 「不可预测性」：对于加密应用，需要具有不可预测性，即使知道部分序列，也不能预测下一数值。

对于最后一个特性，针对于我们是非常需要的，因为，根据我们之前的算法，我们会公开部分私钥的值，因此，我们即使得到了，部分私钥的值，我们也不能推断出来，对应的私钥，因此，最后一个特性，是非常有必要的。

MSS 密钥生成

接下来，我们就来介绍一下PRNG如何应用到MSS当中，首先，我们选择一个初始的n比特的种子，然后，我们通过这个种子，派生出来个OTS的私钥，，这里，具体规则如下

到这里，我们就完成了，对于OTS私钥的种子的生成。

接下来，我们就可以生成，具体的每一个私钥了，我们还是采用WOTS的方案，至于为啥呢，因为，我之前写过实现。我们需要生成t个私钥，具体为，具体的规则如下

代码实现

这里，还是采用Python来实现这个吧。

import hashlib

from Cryptodome.Util.number import long_to_bytes

from wots import do_hash
from mss import hash_data, build_merkle_tree, get_merkle_root, sign, verify


def prng(seed, size=16):
    return hashlib.shake_128(seed).digest(size)


def w_ots_key_gen_with_seed(seed):
    omega, t1, t2 = 8, 16, 2
    keys = prng(seed, (t1 + t2) * omega * 2)
    sk = [int.from_bytes(keys[i * omega: (i + 1) * omega], 'big') for i in range(t1 + t2)]
    pk = [do_hash(long_to_bytes(sk[i]), 255) for i in range(t1 + t2)]
    return sk, pk


def key_gen(seed, H=3):
    seeds = []
    for i in range(2 ** H):
        seed = prng(seed)
        seeds.append(seed)
    key_items = [w_ots_key_gen_with_seed(seed) for seed in seeds]
    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


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

总结

通过PRNG呢，我们减小了私钥的大小，从非常大的私钥，减小到了只需要种子的大小，这个思路呢，其实在其他的密码学设计当中也有见到，比如我们之前聊过的基于格的密码体系，Kyber以及Dilithium，他们生成错误分布以及矩阵A, 都采用了种子的方案，以减少传输的体积，这里，采用伪随机数生成器，还有另一个好处，只要PRNG是前向安全的，MSS就是前向安全的。好了，本篇文章，到这里就结束了，文章比较短，我这又双叒叕水了一篇文章，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

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