【数字签名】L-OTS：基于哈希的一次性签名及改进

type

status

date

slug

summary

签名

假设我们的目标是对 256 位的消息进行签名。要得到我们需要的密钥，首先需要生成随机的 512 个位字符串，每个位字符串长度为 256 位。为了便于理解，我们将这些字串列为两个独立的表，并以符号代指：

以列表表示用来签名的密钥。

接下来为了生成公钥，我们将随机的位字符串通过 H(.) 进行哈希运算，得到公钥如下表：

现在我们可以将公钥公布给所有人知道。

接着我们使用密钥对 256 位消息 M 进行签名。首先我们得将消息 M 重现为独立的 256 位元（Bit，又称“比特”）：

签名算法的其余部分非常简单。我们从消息 M 的第 1 位至第 256 位，逐一相应在密钥列表中的其中一个密钥上取出字符串。而所选密钥取决于我们要签名的消息每一位（bit）的值。

具体一点地说:

对于，如果第位的消息位元，我们会从表中选择第个字符 () ，作为我们签名的一部分；

如果第位的消息位元，我们则从表进行前述过程，以此类推。对每个消息位元完成此操作后，我们将选中的字符串连接，得到签名。

验签

当某个用户（已经知道公钥 ()）收到消息和签名，她能够轻易地验证这个签名。我们以表示签名中第个组成部分，用户能够检查相应的消息并计算哈希值。如果，则哈希值必须匹配公钥中的元素；如果，则哈希值必须匹配公钥中的元素。

如果签名中的每个元素经过哈希运算后，都能找到对应的正确部分的公钥，我们就会说这个签名是有效的。

这个数字签名方法的弊端是：

签名和密钥的数据太大

每个密钥只能被用来签名一个消息，所以叫做一次性签名。因为假设攻击者从不同的消息得到两个有效的签名，她便能够发起 “混合搭配（mix and match）”攻击，成功伪造签署第三条我从未签名过的信息。以下图示说明这个攻击过程：

相当于私钥泄露。

W-OTS：减小签名和公钥大小

L-OTS是根据每一位生成2个秘钥对，W-OTS对消息进行“压缩”，比如根据8位生成256个秘钥对，但是不是全部是随机生成的秘钥对，而是在同一个随机秘钥对的基础上记性256次哈希运算，得到256个秘钥对。注意：要对字节进行签名，我们只需要 255 个密钥列，而不是 256 个。因为最后一个密钥列等同于公钥。