Page 24 - 《软件学报》2025年第10期

杨亚涛 等: SM3-OTS: 基于国密算法 SM3 的紧凑型后量子一次签名方案 4421

的环境中比 WOTS+方案具有更大的应用潜力.
SM3-OTS 方案主要包含 3 个算法: 密钥生成算法 KeyGen( )、签名生成算法 Sign( )、签名验证算法 Verify( ).
密钥生成算法接受一个安全参数 n 作为输入, 经过相应运算输出签名密钥对 (sk, pk), 私钥 sk 为只有签名者拥有,
pk 可以被任何人获得, 用于对消息的签名作有效性验证. 签名生成算法接受待签名的
用于对消息进行签名; 公钥
消息 M、私钥 sk 两个输入, 经过算法后生成消息 M 对应的签名值 σ. 签名验证算法接受消息 M、 M 对应的签名
值 σ 以及公钥 pk 这 3 个输入, 签名验证算法可验证签名值的有效性, 若签名值有效则输出 true, 若签名值无效则
输出 false.
4.1 SM3-OTS 方案密钥生成
Seed 作为伪随机数发生器 PRNG 的种子数据生成 48 个伪随机数:
在 n =256 bits 的安全参数下, 将秘密种子
sk 0 , sk 1 ,..., sk 47 , 每个伪随机数为 32 字节的伪随机十六进制数据称为一个私钥块, SM3-OTS 签名方案私钥 sk 包
含 48 个私钥块, 记为 sk = sk 0 , sk 1 ,..., sk 47 .
SM3-OTS 签名方案公钥由对应的私钥生成, 使用国密算法 SM3 将上述 48 个私钥块 sk i 分别做 255 次哈希运
255
算, 即 pk i = H (sk i ), 生成 48 个公钥块: pk 0 , pk 1 ,..., pk 47 , SM3-OTS 签名方案公钥 pk 包含 48 个公钥块, 记为
pk = pk 0 , pk 1 ,..., pk 47 . 从私钥生成公钥的过程得到 48 条哈希链, 分别为 L 0 ,L 1 ,...,L 47 , 每条哈希链中包含 256 个链
节点, 每条哈希链中相邻两个链节点中后一个节点为前一个节点的哈希值, 每条哈希链的首节点为该哈希链对应
私钥块, 每条哈希链的尾节点为该哈希链对应的公钥块, 密钥生成如算法 1 所示.
算法 1. 密钥生成 KeyGen 算法.

输入: 安全参数 n;
输出: 私钥集合 sk = sk 0 , sk 1 ,..., sk 47 ; 公钥集合 pk = pk 0 , pk 1 ,..., pk 47 .
1. Seed ⇐ PRNG //通过伪随机数发生器 PRNG 生成随机种子
2. for 0 ⩽ i ⩽ 47 //利用种子生成 48 个私钥块
3. sk i = PRNF(Seed,i)
4. end for
5. for 0 ⩽ i ⩽ 47 //利用私钥块生成对应公钥块
pk i = H (sk i ) //对每个私钥块做 255 次哈希运算得到对应公钥块
255
6.
7. end for
;
8. return sk = sk 0 , sk 1 ,..., sk 47 pk = pk 0 , pk 1 ,..., pk 47 //输出密钥对
如算法 1 所示, 在预设的安全参数 n=256 bits 下, 使用秘密种子 Seed 和伪随机数发生器 PRNG 随机生成 48
n 字节的随机数作为私钥, 分别将 48 个私钥块使用国密算法 SM3 做 255 次哈希运算生成 48 n 字节的哈希
个 个
值作为公钥, 密钥生成如图 1 所示, 哈希链结构如图 2 所示.
私钥 公钥

伪 0 0 SM3 运算 链节点
随 私钥 公钥
机 1 1
密钥 数 ...
种子 生 2 2 L 0
成 ... ... L 1 ...
器 ... ...
47 47 L 47 ...
图 1 SM3-OTS 密钥生成 图 2 哈希链结构
4.2 SM3-OTS 签名生成
SM3-OTS 签名生成是将消息摘要的信息映射到哈希链节点的过程. 如图 3 所示, 图 3(a) 为签名方案的哈希