1979 年 Ralph C. Merkle 提出了 Winternitz-OTS，其中运用了哈希链(hash chain)的结构，论文见 A Certified Digital Signature ，更加详细的算法描述见 Hash-based Digital Signature Schemes，该算法产生的一对密钥也只能签名一条消息。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先，我们需要确定 $w$ 参数该参数决定哈希私钥多少次构造公钥，此外还需确定哈希之后摘要的长度 $n$ ，或者可以认为是采用的哈希函数族。

Lamport 是第一个 OTS(One Time Signature) 算法，由 Leslie Lamport 于 1979 年提出，论文可见 Constructing Digital Signatures from One Way Function ，一对密钥只能签名一次，不能重复使用。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先我们需要确定安全参数 $k$，不过实际操作中我们一般只需要确定输出的摘要长度 $n$。

通过随机数生成器(PRG, Pseudo Random Generator)，生成 $n$ 对随机数，每一对包含两个随机数，每一个随机数 $n$ bits，总共 $2\times n\times n$ bits，此为私钥。

对每一个随机数进行哈希，生成 $2\times n$ 个摘要，每一个 $n$ bits，也是 $2 \times n \times n$ bits，此为公钥。

形式化表示为：

$$sk = (sk_{0,0}, sk_{0,1}, \dotsm, sk_{n-1, 0}, sk_{n-1, 1}) \\
pk = (pk_{0,0}, pk_{0,1}, \dotsm, pk_{n-1, 0}, pk_{n-1, 1})$$

定义

任意的签名算法都可以用一个三元组表示: ($GEN, SIG, VER$)，可以说是组成签名系统的三个算法。

• $GEN$: 密钥生成算法
• $SIG$: 消息签名算法
• $VER$: 消息校验算法

定义一个接口表示：

1
2
3
4
5
6
7
8

type Signature interface {
	// GenerateKey generates secret key and public key
	GenerateKey() (sk []byte, pk []byte)
	// Sign computes signature of message using secret key
	Sign(message []byte, sk []byte) []byte
	// Verify check if the signature is valid
	Verify(message []byte, pk []byte, signature []byte) bool
}

下面详细说说这三个算法。

概念

什么是哈希函数？

定义其实很简单，哈希函数其实就是一种映射关系，它可以把任意长度的数据映射为固定长度的数据，输出一般称为摘要(digest) ，就比如常见的 md5 算法，可以将输入映射成 128 bits。

$$\{0, 1\}^* \overset{map}{\longrightarrow} \{0,1\}^n$$

同时，也正因为说，哈希函数将任意长度的输入映射成固定长度的输出，因为输入空间远大于输出空间，所以必然会存在冲突，比如下面的这种情景。不过，在实际使用的时候，必须要求哈希函数具备一定的安全性。

前言

每一个技术同学都希望能够拥有一份自己的博客，有时候在上面写写东西，不需要太多，不需要炫彩夺目，简简单单就好，如果自己的文章能够帮助到他人那就更加欢喜不得了。

第一次看到 CSDN 上的写的一篇文章如此受大家的喜欢，甚是喜悦，后来又陆陆续续写了很多文章，不论是写代码时遇到的 bug 解决思路，还是刚学习某门语言时碰到的问题，亦或是学的某些算法等等。

收到 GitHub 上许多同学的点赞之后，也越来越喜欢开源自己写的 Project，同时 GitHub 上有着许许多多的有些仓库值得我们去学习。

在 CSDN 和 掘金 上写了这么些文章，但总是觉点欠缺点什么，前不久看到其他同学的博客，于是想着搭建自己的一份博客，一来可以方便内容的聚集，二来也算是满足自己的一个小小的愿望，谁不想要有自己的博客呢😄