最近正在学习Merkle（不是默克尔Merkel） Signature Scheme（Merkle签名体制，MSS）。 这一体制的核心是一种基于散列的一次签名算法（One Time Signature，OTS）。 原始算法是Lamport提出的，Merkle在提出时提到了一个改进 （来自Winternitz这个人的改进，因此称为Winternitz一次签名算法）。
MSS签名体制相比当下流行的RSA、DSA等算法相比，具有在量子计算机研制成功之后仍然安全的潜力。 其当前也当然很容易做到超越RSA、DSA等的安全性。在性能方面，改进的MSS算法可以在几十毫秒内进行签名和验证， 其结果长度大约在几个kByte的数量级，是有竞争力的。MSS公钥和私钥都非常短，只有数百字节。 缺点是目前产生一次MSS公钥需要的时间可能长达数分钟。尽管如此，MSS签名体制仍然是十分吸引人的。
本文只是对作者的学习进行一个小结，希望可供分享对OTS算法的理解。 关于MSS签名体制，将另文介绍。密码学方面作者不是专家，大概不是砖家， 只能给出大概的理解，如有错误，欢迎指正。
第一部分：OTS算法
OTS算法可以基于已有的散列函数构建。这类散列函数的输出应该具有良好的伪随机性。 作者认为，类似SHA-256之类的函数，具有这类特性。在对MSS算法研究的论文中，也一般以此为例。
Merkle在提出MSS算法时，对OTS算法给出了一个很好理解的描述。 比如我们有一个代理人，我们要求他在确定我发出了命令这一条件下出售我们的股票。 为此我们这样约定：首先我产生一个随机的字符串，32字节（256比特）长。 然后我对之进行SHA256，这样我得到了一个输出，32字节长。我把这个结果给代理人， 告诉他或者在合同上写好，当他知道用SHA256产生这个字符串的那个字符串时， 他就可以用这个作为我发出了指令的证明，出售我的股票。
对于代理人或者任何看到合同的人来说，从这个散列结果，推出我的命令，是很困难的。 可以说，只有我才能发出这类指令——通过公开我那个随机的字符串。 另一方面，代理人无论通过哪种渠道，直接或者间接地得到了这个字符串， 那么一定是因为我在某个时刻发表过。
因此，我们就签署了一个比特“1”——通过这种方式：产生私钥SK，公开SHA256(SK)的结果。 当我日后某天公开SK时，我就进行了对我的这个“是或否”的指令的签署。
当然，代理人也可以选择永远不出售我的股票。 当我询问时，只说，他从来没有收到过这个字符串，或者我给出了一个错误的指令， 验证不通过。
为此，在假设代理人必须请求我的指令的情况下（比如，24小时之后给我打电话），
我们可以用以上方法，进行另一种形式的签署：产生私钥SK1和SK2，
然后同时给代理人PK1=SHA256(SK1)和PK2=SHA256(SK2)。这样，我若日后给出SK1，
就表示要卖出股票，若给出SK2，就表示不许卖出我的股票。这样，我就唯一地签署了一个比特，0或者是1.
OTS签名，是对以上情况下的256个比特一起进行的签署。例如我们要签署一段信息， 就先将之散列，得到256比特的摘要。为了签署这个摘要，我们需要256对的私钥， 然后在签署之前将这256对私钥算出256对公钥公布出去。当我们签署时， 根据散列值结果的每个比特（0或者1），选择公布256对私钥里面的第一或者第二号结果。
用个具体的例子作为解释，为了节约空间我们用md5代替sha256。 假设我们要签署一段8个比特的消息。首先，我们产生8 x 2 x 16 字节的私钥，如下：
d3d9446802a44259755d38e6d163e820, 98f13708210194c475687be6106a3b84
6512bd43d9caa6e02c990b0a82652dca, 3c59dc048e8850243be8079a5c74d079
c20ad4d76fe97759aa27a0c99bff6710, b6d767d2f8ed5d21a44b0e5886680cb9
c51ce410c124a10e0db5e4b97fc2af39, 37693cfc748049e45d87b8c7d8b9aacd
aab3238922bcc25a6f606eb525ffdc56, 1ff1de774005f8da13f42943881c655f
9bf31c7ff062936a96d3c8bd1f8f2ff3, 8e296a067a37563370ded05f5a3bf3ec
c74d97b01eae257e44aa9d5bade97baf, 4e732ced3463d06de0ca9a15b6153677
70efdf2ec9b086079795c442636b55fb, 02e74f10e0327ad868d138f2b4fdd6f0
然后，我们对上面的每个部分进行散列，结果如下，作为公钥公布出去。
8d8e353b98d5191d5ceea1aa3eb05d43, 74d8ce91d143cad52fad9d3661dded18
7bfc85c0d74ff05806e0b5a0fa0c1df1, e39a411b54c3ce46fd382fef7f632157
c8b2f17833a4c73bb20f88876219ddcd, 4a0f84dd91471107bf6a1dfce1d62fc0
7e51746feafa7f2621f71943da8f603c, 6f181f206b8555c5dc619bc206ab35ad
f93b8bbbac89ea22bac0bf188ba49a61, 83a5a282f092aa7baf6982b54227bb54
ad8b68a55505a09ac7578f32418904b3, c81fb13777b701cb8ce6cdb7f0661f1b
93b6deed95aca08ab22dae75e28592b1, 683529bb1b0fedc340f2ebce47468395
27a989a1aeab2b96cedd2b6c4a7cba2f, 80ecd7abc0579af356a6ca6fb24ec486
现在，如果我们要签署一个8比特的数据，比如10100101， 那么我们就在上面的私钥里面选取对应的结果，（假设左边代表0，右边代表1）
--------------------------------, 98f13708210194c475687be6106a3b84
6512bd43d9caa6e02c990b0a82652dca, --------------------------------
--------------------------------, b6d767d2f8ed5d21a44b0e5886680cb9
c51ce410c124a10e0db5e4b97fc2af39, --------------------------------
aab3238922bcc25a6f606eb525ffdc56, --------------------------------
--------------------------------, 8e296a067a37563370ded05f5a3bf3ec
c74d97b01eae257e44aa9d5bade97baf, --------------------------------
--------------------------------, 02e74f10e0327ad868d138f2b4fdd6f0
然后公布即可：
98f13708210194c475687be6106a3b84
6512bd43d9caa6e02c990b0a82652dca
b6d767d2f8ed5d21a44b0e5886680cb9
c51ce410c124a10e0db5e4b97fc2af39
aab3238922bcc25a6f606eb525ffdc56
8e296a067a37563370ded05f5a3bf3ec
c74d97b01eae257e44aa9d5bade97baf
02e74f10e0327ad868d138f2b4fdd6f0
收到被签署的数据和签署结果的人，只需要对签署的结果进行散列， 然后在公钥列表中查找，看对应的0和1是否符合被签署的数据，即可认证。
第二部分：对长度的讨论
我们计算下这种签署方案的长度。先都按照比特来计算。
对于一个合乎未来几十年安全性要求的设计，我们应该选取输出256或者512比特的散列函数， 例如SHA256, SHA512, Whirlpool等。在对实际使用中的任意长度的消息的散列中， 也应当使用这一长度的散列函数。记这个长度为N。则我们要签署这N个比特。 为了签署每个比特，我们要准备N对私钥（2N个字符串），公布2N个公钥字符串。 在签名结果中，我们需要公布N个长度为N的字符串。
于是，公钥和私钥长度都是2N^2，签署结果长度是N^2。由于OTS签署的私钥只能使用一次， 所以在MSS方案中每次签署都把公钥和签署结果放在一起。 这样，对于一次签署，在OTS算法上我们需要3N^2的结果。代入N=256，结果长度是196608比特， 或者24576字节，24kByte。如果用N=512，则为4倍，96kByte。
需要指出，为了减少私钥在保存起来的不便（虽然12kByte或者48kByte不算大， 但是在MSS算法——以后会另文叙述——中，一个MSS私钥大概能签署2的几十次方次。 全部保存的话就是上G的数据了——还都是随机数据，熵很大的，压缩也很困难）， 应当采用伪随机数发生器随时构建私钥。这样，我们任何时候只要保存伪随机数发生器的种子即可。 伪随机数发生器是这样一类函数，给定种子，和序列号，就能由此给出一定长度的貌似随机的结果。 这一结果在不知道种子和序列号之类的输入参数时如果的确和真随机数发生器的结果一般随机， 就是很理想的设计。当今的AES算法和散列函数，都可以用作这一用途。例如：
X(序列号)=SHA256(‘NeoAtlantis‘, 种子[序列号], 序列号)
由于种子的空间是有限的，所以能产生的良好的伪随机数长度也是有限的，但是一般都远远足够了。
第三部分：Winternitz-OTS改进方案
我们利用伪随机数发生器搞定了私钥的生成和保存问题，但是由于公钥是对私钥的分别散列， 因此不能这样乱搞。然而我们需要尽量缩小公钥和签名结果的长度，使得这个算法更加实用。 数学家Winternitz给出了这个方案。
首先我们回顾下，是什么导致了这么大的结果。我们的签名结果，是对N个比特的签署。 用作签署的证明的是长度为N个比特的字符串。字符串的长度是不能缩短的。那么从对N个比特的签署入手。
我们每次用一个字符串签署一个比特，能否签署多个比特呢？ 如果我们用一个私钥能签署2个比特，那么表示签署结果的字符串的数量就是N/2， 这样就大大缩小了结果的尺寸。
Winternitz设计的方案如此。我们将示例中的8个比特10100101改成4进制：2211 然后我们的公钥不是私钥的1次散列的结果，而是4次散列。我们考虑， 这时，假如我公布了我的私钥的3次散列后的结果，那么再经过1次散列，就和公钥结果吻合。 这样我就签署了一个3：
- 私钥
- SHA256(私钥)
- SHA256(SHA256(私钥))
- SHA256(SHA256(SHA256(私钥))) 【签署结果公布这个】
- SHA256(SHA256(SHA256(SHA256(私钥)))) 公钥
然而这样是有个伪造问题的。 比如，我用Winternitz的方法，公布了私钥2次散列后的结果A。那么我签署了一个2. 可是任何人都可以拿着A，再散列一次，替换掉公布的签署结果，说我签署的实际是3. 不过，如果我签署的是2，则不能有人由这个2次散列结果逆推，说我只签署了一个1. 因为散列函数是单向的，不能求逆。
根据以上观察，我还需要在签署的同时，保证这个问题， 即我的公布结果和公钥结果之间的“距离”是确定的。根据Merkle的描述，是这样解决的：
我们首先将这些距离加起来得到一个校验值。比如在对数据（10100101）2=（2211）4的签署中， 我对2个2和2个1进行了签署。那么和公钥的3333结果比起来，验证者需要验证（3-2）+（3-2）+（3-1）+（3-1）=6次。 这个6就是上面说的签署结果和公约的“距离”。 这个距离，根据前述的伪造方法，只能变小，不能变大。
我们将这个距离也进行4进制表示。将表示结果（12）4附加在被签署的数据的尾部， 即我们签署了一个（2211 12）4的数据。虽然是6位，亦即我们要准备一个6对的公钥， 但是还是比8小。
在这时，如果还有人希望伪造数据，那么经过伪造的数据， 这个校验值一定是比我们附加的原始值偏小才行。比如是（2212 11）4. 然而，校验值减小，意味着校验值在经过4进制之后，也总会有一位的数值被减小。 而我们签署了校验值在4进制下的每个数位，且根据前面的分析， 这类对各个位的签署结果的伪造只能让被签署的数位偏大。这样就发生了矛盾。 所以伪造就被避免了。
可以看出，Winternitz-OTS算法，实际上是用牺牲更多时间进行散列的代价， 换取了空间。上文介绍的4进制，也可以进一步扩展，例如选取2^4=16, 或者2^5=32， 就可以将公钥或者签名缩短到1/4或者1/5的长度。
至此，关于OTS和Winternitz-OTS签名算法就叙述完了。这类一次性的签名算法， 缺点是明显的，只能一次使用，否则可以以极大的概率恢复出密钥。 为此，使用MSS算法构建二叉树，允许使用一种方式，在只保留一个二叉树的根的很少数据的情况下， 验证一个给定的OTS公钥是否为这个树的树叶。这种方式，就允许了构建一个可以多次进行签名的体系。 虽然这样的签名次数也是有限的，但是诸如2^20（>1000000）次的使用限制（这是XMSS算法的论文参数）， 仍然允许这个算法在一些不频繁的环节应用。而且，GMSS算法构建的树，允许进行2^80次签名， 对于服务器的频繁应用也是可行的。关于MSS算法的相关介绍，将在以后的其他文章中进行。