Lamport单签名方案

兰波特·奥诺·蒂姆佩西格拉姆这是一种用于生成数字签名的方法，通常需要使用加密哈希函数来实现。由于这是一种一次性签名方案，因此只能用来对一条消息进行安全的签名处理。
假设Alice想要为发送给Bob的消息进行数字签名。这个过程可以分为三个步骤来实施：

1. 密钥生成
2. 签名生成
3. 签名验证。

密钥生成： 

• 首先，Alice需要创建一个Lamport密钥对，即一个私钥以及与之对应的公钥。
• 为了生成私钥，需要使用安全的随机数生成器来生成256对随机数字。每对数字都由256位组成。Alice会将这些私钥安全地存储起来。请记住，私钥是不应该与任何人分享的。
• 为了生成公钥，Alice将她的私钥中的每512个数字进行哈希处理。这样就能得到另外512个结果，每个结果由256位组成。这些就是需要分享给所有人的公钥。

在数学表示中：

• 设 k 为一个正整数，那么 P = {\{0,1\}}^k 表示需要被签名的信息集合，而 f: Y → Z 则是一个单向哈希函数。
• 对于 1≤i≤k，且j∈{0,1}，Alice会随机选择一个元素y_{i,j}∈Y，然后应用单向哈希函数来计算z_{i,j}=f(y_{i,j})。
• 私钥和公钥都由2k个值组成，分别表示为y_{i,j}和z_{i,j}。

2. 签名生成：

• Alice使用256位的加密哈希函数来处理她的消息，例如SHA-256算法，从而得到一个256位的摘要。
• 对于每一个比特位，根据该比特位是1还是0，Alice会从她的私钥中对应的数字中选择一个数字。也就是说，如果比特位是0，则选择第一个数字；如果比特位是1，则选择第二个数字。这样，就得到了一串由256个数字组成的序列，这串数字实际上就是Alice的“签名”。
   

• 艾丽斯将这条消息连同她的签名一起发送给鲍勃。

在数学表示法中，

• 设 $M = m_1, m_2, \ldots, m_k \in \{0, 1]^k$ 为Alice想要签署的消息。
• 该签名被表示为：sig(m_1, m_2, …, m_k) = (y_1, m_1, y_2, m_2, …, y_k, mk) = (s_1, s_2, …, s_k)。
• 这个签名会与消息一起发送给Bob。

3. 签名验证：

• Bob使用相同的256位加密哈希函数对消息进行哈希处理，从而得到一个256位的摘要。
• 对于每一个比特位，根据该比特位是1还是0，Bob会从Alice的公钥中选取相应的数字。也就是说，如果消息哈希值的第一个比特位是0，那么Bob就会选择第一对中的第一个哈希值；以此类推。这个过程与上面图示中的步骤相同。最终，会得到一系列共256个数字。
• Bob将Alice签名中的每一个数字进行哈希处理，从而得到一个256位的摘要。如果这个摘要与Bob之前选出的256个数字序列一致，那么这个签名就是有效的。

在数学表示法中，Bob会检查：对于所有的1≤i≤k，是否满足f(s_i) = {z_I}_{mi}，其中{z_I}是由mi个z_I组成的集合。
注意：需要注意的是，由于Alice已经公开了私钥的一半内容作为她的签名，因此她剩余的私钥将无法再次被使用，必须被销毁。