【基于哈希的密码体系】减少私钥的大小(BC)

本篇文章，我们接着来看一下，基于哈希的签名算法，在上一篇文章中，我们描述了Lamport提出的算法，对于这个算法呢，我们其实有两个问题需要解决，

• 公钥和私钥过大的问题
• 公钥和私钥不能重复使用的问题，也就是每个公钥和私钥，只能对消息签名一次

接下来呢，为了能让这个算法真正的有效，我们来看一下，大佬们是如何解决这两个问题的，解决完成这两个问题，后面，我们就能来聊SLH-DSA的具体过程了。

首先，我们先来看一下，如何来减少私钥的大小，这里介绍Jurien N.E. Bos 和  David Chaum提出的算法。

前置知识

要理解这个算法呢，首先，我们需要用到一点点组合学的知识，说白了，也就是我们在中学学过的计数原理。

排列

从n个元素取出k个元素，k个元素的排列数量为：

举一个例子，假设一个饭店的菜单上面有3个菜(酸辣土豆丝、西红柿炒鸡蛋、红烧肉)，然后，要去点餐，这里，我们要点两个菜，点菜不能重复，我们考虑我们点菜的上菜的顺序，那么我们可能的上菜情况是。

酸辣土豆丝 西红柿炒鸡蛋
酸辣土豆丝 红烧肉
西红柿炒鸡蛋 酸辣土豆丝
西红柿炒鸡蛋 红烧肉
红烧肉 酸辣土豆丝
红烧肉 西红柿炒鸡蛋

这一共，6中情况，我们按照公式来计算一下，那就是

符合，我们上面的计数。

组合

从n个元素中，取出k个元素，不考虑取出的顺序，k个元素的组合数量为

这里，我们还是用上面的例子，我们一共吃菜的可能，那么其实和顺序就没关系了，所有可能情况为

酸辣土豆丝 西红柿炒鸡蛋
酸辣土豆丝 红烧肉
西红柿炒鸡蛋 红烧肉

这一共，3中情况，还是按照公式来计算一下，

也是符合的。

私钥的优化[1]

我们知道，根据Lamport的算法，如果我们要加密n比特的消息，那么我们所需要的私钥的数量是2n，我们考虑刚才提到的计数原理，可以知道，如果我们从2n个元素中取出n个元素，那么我们可以得到的组合的数量为

至于，为什么要这么近似呢，因为这样，我们可以得到一个有关于消息长度和组合数的一个近似关系，也就是我们有一个k个元素的子集，可以签名的消息长度近似为

这里n是比特长度，这里的私钥长度，大约可以达到n，比起最原始的算法，减少了一半。

然后，接下来，就有一个重要的问题，也就是我们怎么把我们的消息，和这个子集给对应起来，也就是我们需要找到一个映射，使得

这里，直接给出参考资料[1]当中的算法，这里原始的论文当中用到的集合下标是从1开始的，但是吧，这么来的话，开始执行一次t - 1, 因此会少一个元素，这块，我不确定是我理解不到位，还是作者笔误，不过不影响整个算法，本文后续代码，我们默认下标从0开始，如果看原始paper的读者需要注意下。

• 输入m是消息，是一个在的数字
• 首先，令t = 2k, e = k
• 当t > 0时，进入循环
• 令t = t - 1
• 判断，如果成立，那么令, e = e - 1, 然后这个t在子集里面
• 否则，这个不在这个子集当中

样例

这里，看起来，是比较复杂的，我们来看一个例子，假设m = 5，然后，我们进行处理，这里，我们还是令k = 3, 和资料[1]中的一样，那么对应集合，接下来，我们来实际的看一个例子

首先，这里t = 6, e = 3, 第一次，进入循环，判断不成立，说明不在里面，接下来t = 4, 我们来计算, 成立，因此在对应的集合里面，这里，t = 3, m = 1, e = 2, 接下来计算不成立，说明不在里面，t = 2, 接下来计算成立，说明在里面，这里m = 0, e = 1, t = 1, 可以判断不在里面，那么最后集合当中的元素是。

最后，给大家，展示一下，0-15的值，可以观察到，是没有重复的。

代码实现

这里，简单的写一个代码吧，因为我不想自己实现组合函数，所以这里直接采用Python来实现。

from scipy.special import comb


def s(m, n):
    t, e = 2 * n, n
    result = []
    while t > 0:
        t -= 1
        tmp = comb(t, e)
        if m >= tmp:
            result.append(t)
            m -= tmp
            e -= 1
        else:
            continue
    return result

总结

通过，这个方案呢，我们将密钥的体积缩小了一半，但是呢，这个算法，求解s是比较复杂的过程，那么接下来呢，后面的文章，我们就来看一下，如何针对于这一点进行一些优化，咱们下次再见。

参考资料

1. https://link.springer.com/content/pdf/10.1007/3-540-48071-4_1.pdf
2. https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas
3. https://eprint.iacr.org/2002/014.pdf