【基于哈希的密码体系】WOTS(Winternitz one-time signature scheme)

本篇文章呢，我们接着来看一个基于哈希的签名算法，这个算法呢，是Robert Winternitz提出的一个改进方案，这里，通过时间来换空间的思路，减少了签名的体积，那么我们就来简单的看一下这个算法的过程。

算法过程

对于这个算法来说，还是包括密钥生成、签名、验签三个算法，首先，来看一下密钥生成。

密钥生成

首先，选取一个参数，这个参数表示要同时签名的位数，为了代码好实现呢，并且要提升下运行的速度，这个我们后面代码实现的过程当中取，至于为什么这么取，先卖一个关子，看完之后，读者应该就明白了。之后，计算

其中n是需要签名的消息的长度，然后，我们可以得到对应的私钥为

这里，是随机均匀获取的比特串。

然后，就可以通过私钥来计算公钥了，对于公钥，我们按照如下的方式进行计算

最终可以得到

看这个式子，可能突然看的时候，会比较突兀，实际上，简单来说，就是我们需要针对每一个私钥的字符串(比特串)执行次的f运算，因此呢，对于上面的那个我们不能取的太大，否则，执行的次数会非常的多，那么为什么取8呢，因为这里，我们只需要计算255次，不是特别多，并且正好是一个字节的大小。

签名算法

假设消息是m, 我们首先，执行一个哈希函数，将消息的长度映射到n，然后，我们对消息进行分组，分组大小为，也就是

之后，需要计算一个校验和，具体计算方式如下

我们，需要将分组的消息，转换成为对应的数字，然后对他们进行求和，因此，前文的实际上就是来存储校验和的长度的，最后，我们将求和之后的数字，转换成为比特串，然后按照和消息同样的分组方式进行分组

最终，我们可以得到签名

这里，最坏的情况下，我们需要执行次的哈希函数的运算。

验签算法

验签算法，其实也比较好理解，注意到，如下的关系，

因此，我们只需要补足计算对应的哈希函数的次数就可以了，因此验签的方式如下

好了，到这里，其实算法就讲完了，接下来，我们来看下具体的代码实现，这里还是用Python吧，懒得写其他的了。

代码实现

import hashlib
import random

from Crypto.Util.number import long_to_bytes


def do_hash(m, count):
    if count == 0:
        return m
    h = hashlib.md5(m).digest()
    for i in range(count - 1):
        h = hashlib.md5(h).digest()
    return h


def key_gen():
    omega, t1, t2 = 8, 16, 2
    sk = [random.randint(0, 2 ** (omega * 16)) for _ in range(t1 + t2)]
    pk = [do_hash(long_to_bytes(sk[i]), 255) for i in range(t1 + t2)]
    return sk, pk


def sign(m, sk):
    h = hashlib.md5(m).digest()
    sigma = []
    for index, item in enumerate(h):
        sigma.append(do_hash(long_to_bytes(sk[index]), item))
    c = long_to_bytes(sum(list(h)))
    for index, item in enumerate(c):
        sigma.append(do_hash(long_to_bytes(sk[index + 16]), item))
    return sigma


def verify(m, sigma, pk):
    h = hashlib.md5(m).digest()
    for index, item in enumerate(h):
        v_prime = do_hash(list(sigma)[index], 255 - item)
        if v_prime != pk[index]:
            return False
    c = long_to_bytes(sum(list(h)))
    for index, item in enumerate(c):
        v_prime = do_hash(list(sigma)[index + 16], 255 - item)
        if v_prime != pk[index + 16]:
            return False
    return True


if __name__ == '__main__':
    x, y = key_gen()
    m = b'LittleQ'
    sigma = sign(m, x)
    print(verify(m, sigma, y))

总结

本篇文章呢，我们简单的讲解了一下WOTS的签名算法的过程，对于后面的GMSS、XMSS里面也用到了这个算法，因此呢，这里，先水一篇文章，来写一下它，这个算法的核心呢，采用了时间换空间的做法，减小了签名的体积，整个原理，还是比较好理解的，没有涉及到太多复杂的结构，比起之前讲的格密码，用到的知识，明显是少了一些，哈哈，好了，快乐的时光过得特别快，又到了和大家说再见的时候了，咱们下次再见。

参考资料

1. https://eprint.iacr.org/2023/850.pdf
2. https://eprint.iacr.org/2011/191.pdf
3. https://www.e-reading-lib.com/bookreader.php/135832/Post_Quantum_Cryptography.pdf
4. https://link.springer.com/content/pdf/10.1007/978-3-540-72738-5_3.pdf
5. [https://theswissbay.ch/pdf/Gentoomen Library/Security/Oded_Goldreich-Foundations_of_Cryptography__Volume_2%2C_Basic_Applications(2009).pdf](https://theswissbay.ch/pdf/Gentoomen Library/Security/Oded_Goldreich-Foundations_of_Cryptography__Volume_2,_Basic_Applications(2009).pdf)