WOTS介绍

  • WOTS全称为Winternitz one-time signature scheme，翻译过来就被叫做Winternitz 一次性签名方案，该数字签名为Robert Winternitz提出的。
  • WOTS这个数字签名是基于哈希的签名算法，该签名是Lamport签名的改进算法，通过时间换空间的思路，减少了签名的体积。
  • 应用场景：
    • 作为XMSS、SPHINCS等现代化哈希签名体系的核心组件。
    • 适合在抗练字密码学中作为安全的签名方案
    • 由于WOTS是一次性签名，通常配合Merkle树扩展成多次使用的签名体系。

WOTS算法过程

  • 对于这个算法来说，主要包括的还是密钥生成、签名、数字签名的验证三个算法，所以WOTS算法过程主要就是分为密钥生成、签名、数字签名的验证三个过程

密钥生成

签名

验签算法

例题-nepctf2025

  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from gmssl import sm3
from random import SystemRandom
from ast import literal_eval
import os
flag = os.environ["FLAG"]
def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)  # 应该是计算一个hash值
    return h

def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]
# SM3和SM3_n是一块的,实现的就是哈希值计算

class Nepsign():
    def __init__(self): # 构造方法, 初始化n = 256 , hex_symbols = '012....' ,调用keygen函数
        self.n = 256
        self.hex_symbols = '0123456789abcdef'
        self.keygen()

    def keygen(self): # 密钥生成方式类似于WOTS(Winternitz one-time signature scheme)
        rng = SystemRandom()   # 调用随机数的库
        self.sk = [rng.randbytes(32) for _ in range(48)] # 随机生成32byte的数据,生成48组
        self.pk = [SM3_n(self.sk[_], 255, self.n) for _ in range(48)] # 对这些数据计使用SM3算法计算哈希值
        return self.sk, self.pk # 返回数据及其哈希值

    def sign(self, msg, sk=None): # 签名操作
        sk = sk if sk else self.sk  # 获取数据
        m = SM3(msg) # 计算消息msg的哈希值,结果为m
        m_bin = bin(int(m, 16))[2:].zfill(256) # 将哈希值转换为二进制比特填充,填充到256位
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)] # 8位一组,8位一组的取出来
        step = [0] * 48 # 初始化,保存a数组的值
        qq = [0] * 48 # 初始化,保存hash值
        for i in range(32):
            step[i] = a[i]
            qq[i] = SM3_n(sk[i], step[i]) # SM3_n(data, n=1, bits=256)
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]: # 如果消息的哈希值对应索引符合hex_symbols中的某一个
                    sum[i] += j     # sum就会加上索引
            step[i + 32] = sum[i] % 255 #
            qq[i + 32] = SM3_n(sk[i + 32], step[i + 32]) # 之后用step这个列表32个索引之后的数据传入SM3_n计算哈希值
        return [i for i in qq] # 相当于返回qq列表

    def verify(self, msg, qq, pk=None): # 验证过程
        qq = [bytes.fromhex(i) for i in qq] #
        pk = pk if pk else self.pk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48
        pk_ = [0] * 48
        for i in range(32):
            step[i] = a[i]
            pk_[i] = SM3_n(qq[i], 255 - step[i]) # 关键点一共会进行255次哈希,抓住这一点去伪造qq
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            pk_[i + 32] = SM3_n(qq[i + 32], 255 - step[i + 32])
        return True if pk_ == pk else False


print('initializing...')
Sign = Nepsign()
while 1:
    match int(input('> ')): # 提供俩个选项
        case 1: # 选项1是输入消息,消息不等于happy for NepCTF 2025就会对输入的消息进行签名
            msg = bytes.fromhex(input('msg: '))
            if msg != b'happy for NepCTF 2025':
                print(Sign.sign(msg))
            else:
                print("You can't do that")
        case 2:
            qq = literal_eval(input('give me a qq: ')) # 输入qq使得使得qq满足对happy for NepCTF 2025这个消息的签名
            if Sign.verify(b'happy for NepCTF 2025', qq):
                print(flag)