【基于哈希的密码体系】Lamport签名方案(1979)

由于NIST最后发布的三个抗量子加密体系，我之前讲过两个了，其中那两个都是基于格来设计的协议，还剩下一个呢，是基于无状态哈希的方案，要想理解这个方案呢，那么我们就先来看一下，他的一个演化过程，首先，我们先来介绍有状态的哈希函数的方案，先来理解这个的原理，然后再来看SLH-DSA[1]的具体过程。

那么，提到基于哈希函数的密码体系，不得不提的那肯定是第一个算法，也就是Lamport的签名方案[2]，因此，本篇文章呢，我们先来看一下，这个方案的具体过程。

前置知识

首先，我们来看一下，什么是One Way Function。

单项函数(One-way Function)

单项函数是一种对于每个输入都容易计算的函数，但在给定一个随机输入的输出时，很难反向求解出输入。

然后，我们发现，密码学安全的哈希函数，实际上是满足这个条件的，也就是，我们计算哈希函数的值是非常容易的，但是，如果我们给定一个和哈希函数输出等长的一个随机的输出，来求解，输入，这显然是比较困难的，举一个例子，比如，

a60636d79a54d4b844a09c3af280a5b0

给定这么一个随机字符串，我们想要求解，满足输出结果是它的md5的输入，有兴趣的读者可以试试，能不能搞出来，或者说，能不能判定，这个值是否存在都不简单，因为这个是我随机生成的，因此，我也不知道，存不存在。

当然，我这个描述呢，实际上是比较通俗的，稍微正式一点的定义如下，

一个函数是一个「One-way function」，满足一下条件：

• 易于计算: 存在多项式算法A，对于任意的输入x，有
• 难以反向计算：对于所有多项式的随机算法B，存在一个可以忽略的函数，使得

Lamport签名方案

好了，理解了，上面的单项函数的知识，接下来，我们就可以来看一下具体的签名方案了，我们假设给定消息m签名，哈希函数H，可以换成任意的安全的哈希函数，假设哈希函数的输出长度为n。

密钥生成

这里，我们需要生成私钥和公钥，首先，来看一下私钥的生成过程。

随机选择2n个整数，这里，整数可以取的稍微大一些，因为这些整数只能用一次，至于为什么，我们看签名过程就理解了。

将生成的2n个整数分成两组，分别记作和，这里，这些整数，构成私钥。

而对于公钥，我们需要计算以及，其中, 由于哈希函数的特性，这里，我们通过计算得到S的概率在计算上是可忽略的，不理解的，可以看下上文当中的那个例子。

签名算法

计算消息的哈希函数，然后，按照如下的关系来生成签名。

• 如果的第位是0，那么签名值的第位是
• 否则，签名值的第位是

从这里，我们可以看到，这个实际上泄露了私钥的一半，因此，如果多次使用重复的密钥的话，显然是不安全的，并且，也不能抵抗选择明文攻击。因为，我们虽然说是，生成完整的哈希函数是的输入是困难的，但是，控制指定的比特，还是相对来说容易的。

这里，还是，给大家来看一个例子吧，比如，我们想要第一位是0，那么，我们可以很轻松的构造一个输入，满足这个条件。

如果，我们想要构造，第一位是1，那么，只需要，稍微改动一下，这就可以实现了。

所以，如果私钥，重复使用的话，我们将可以很轻松的构造一系列输入，来拿到完整的私钥。

验签过程

验签过程，也比较好理解，签名者计算H(m), 然后，使用后H(m)的各位数据的取值来选择对应的公钥，因此，如果第k位是1，则选择，然后将签名中的n个哈希值和公钥选择的n个哈希值进行比较，如果全匹配，则签名验证通过。

总结

本文，简单描述了，Lamport所设计的基于哈希函数的签名方案，当然，这个签名是存在一些问题的，比如，签名的公钥和私钥都非常大，因为我们要计算2n个哈希值，并且，我们的私钥是不能重复使用的，因此，追踪那些私钥被使用过了，也是一个非常困难的问题，至于如何来改进这些问题呢，我们后面再聊，好了，本篇文章，到这里就结束了，感谢读者的观看，因为本人的水平有限，因此，难免会出现哪里理解的不到位的地方，也欢迎读者和我交流。

参考资料

• https://csrc.nist.gov/pubs/fips/205/final
• https://www.microsoft.com/en-us/research/uploads/prod/2016/12/Constructing-Digital-Signatures-from-a-One-Way-Function.pdf
• https://en.wikipedia.org/wiki/One-way_function