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

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

表 4 过程参数与签名验证 (部分省略) (续)

哈希链 摘要值中的信息 对应值 index 验证公钥块
42 A 98 98 H 255−98 (σ 42 )
43 B 46 46 H 255−46 (σ 43 )
… … … … …
47 F 100 100 H 255−100 (σ 47 )
′
pk = H 255−10 (σ 0 ),...,H 255−130 (σ 31 ),H 255−15 (σ 32 ),...,H 255−123 (σ 41 ),H 255−98 (σ 42 ),...,H 255−100 (σ 47 )
5 安全性证明

在证明 SM3-OTS 自适应选择消息攻击 (chosen-message attack, CMA) 下存在不可伪造性时, 首先需要理解
哈希函数的单向性和抗碰撞性对签名方案安全性的影响. 哈希函数的单向性保证了给定的哈希值无法有效反
推出原始输入, 而抗碰撞性确保不同输入不会产生相同的哈希值. 本文将 SM3-OTS 的安全性归约到这些哈希
函数特性上, 即如果攻击者能够在 CMA 下成功伪造签名, 那么攻击者可以利用这个伪造过程破解哈希函数
的单向性或抗碰撞性. 例如, 如果攻击者能够伪造签名, 攻击者可能通过逆向工程签名生成过程来找到哈希函
数的碰撞或逆向输入, 这违反了哈希函数的基本特性. 通过这种归约过程, 可以证明 SM3-OTS 的安全性确实
依赖于哈希函数的单向性和抗碰撞性, 因此选择一个安全的哈希函数对确保签名方案的整体安全性至关
重要.
在第一原像攻击的挑战中, 对手 ADV 的挑战是在给定输出计算出对应的输入.

′
′
Pr[y = f h (x); x ←− ADV(y) : x = x ] ⩽ ε pre-image .
,
在第二原像攻击的挑战中, 对手 ADV 知道输入-输出对 (x,y) ADV 的挑战是需要找到另一个与输入 x 不同的
′ y.
输入 x , 但输出为

Pr[y = f h (x); x ←− ADV(x,y) : x , x ∧y = f h (x )] ⩽ ε second-pre-image .
′
′
′
SM3-OTS 密码方案对不同类型攻击的抵抗能力通常被称为该协议提供的安全级别. 哈希函数提供的经典和
量子安全级别取决于哈希函数的摘要长度. 由于 Grover 搜索算法的影响, 哈希函数的后量子安全级别相对小于传
统攻击模式下的安全级别. d 位输出长度的哈希函数能够提供第一和第二抗原像攻击提供 d 位经典安全级别以及
d/2 位的后量子安全性. 但是, 抗碰撞攻击相对是一个复杂的安全要求, 一般 d 位输出长度的哈希函数可以供 d/2
d/3 位后量子安全级别对抗碰撞攻击.
位经典安全级别以及
抗第一原像攻击要求攻击者无法从已知的哈希输出 y 推导出相应的输入 x, 即 f(x) = y. 假设攻击者 ADV 能够
伪造 SM3-OTS ′ ′ f 255−step ′ i (σ ) = pk i step 是攻击
′
,
′
pk i 对应的有效签名块
σ , 即
σ , 那么
签名
ADV 必须找到与公钥块
i i i
′
者对消息的伪造哈希值. 这意味着攻击者需要从公钥块 pk i 反推出签名值中的某个签名块 σ . 如果攻击者能够找
i
′
到这一点, 如果攻击者能够找到这样的 σ , 那么攻击者实际上就破解了哈希函数的抗第一原像性.
i
σ i , σ , 但他们早经过一定次数的哈希操
′
假设攻击者成功替换签名元素, 攻击者需要找到两个不同的签名块
i
′
作后得到了相同的公钥块 pk i , 即 f 255−step i (σ i ) = f 255−step ′ i (σ ), 这相当于破解了哈希函数的二次预映射抗性, 因为攻击
i
′ ′ pk i .
者找到了两个不同的输入 σ i 和 σ , 并且 σ i 和 σ 经相同的哈希函数运算得到了相同的输出
i i
攻击者成功伪造签名的概率可以通过哈希函数的抗第一原像攻击和抗第二原像攻击特性的安全性计算:

P success ⩽ ε pre-image +ε second-pre-image ,
其中, ε pre-image 为哈希函数抗第一原像攻击的失败概率, ε second-pre-image 为哈希函数抗第二原像攻击的失败概率. 若攻
击者 ADV 对签名方案所使用的哈希函数的攻击的成功概率 P success 可忽略, 则说明 SM3-OTS 方案所使用的哈希函
数是一个安全的哈希函数, 即说明 SM3-OTS 方案是安全的数字签名方案.