1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):4660密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于杂凑函数 SM3 的后量子数字签名*孙思维1,刘田雨1,关 志2,何逸飞2,荆继武1,胡 磊3,张振峰4,闫海伦11.中国科学院大学 密码学院,北京 1000492.北京大学 软件工程国家工程研究中心,北京 1008713.中国科学院大学 网络空间安全学院,北京 1000494.中国科学院 软件研究所,北京 100190通信作者:孙思维,E
2、-mail:摘要:基于杂凑函数的数字签名的安全性仅依赖于其所使用的杂凑函数的抗(第二)原像攻击的强度,可以抵抗量子计算攻击,是当前后量子签名研究的热点方向之一,各标准化组织也积极对基于杂凑函数的数字签名方案进行标准化.本文利用国产杂凑函数 SM3 替代 RFC 8554、RFC 8391 和 NIST SP 800-208中给出的 LMS、HSS、XMSS 和 XMSSMT数字签名方案所使用的杂凑函数,并给出了初步的实验结果.实验结果表明,使用 SM3 实例化 LMS 和 HSS 是完全可行的,为后续相关标准化工作的推进提供了支撑.关键词:杂凑函数;数字签名;后量子密码;LMS;HSS;XMS
3、S;XMSSMT;SM3中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000578中文引用格式:孙思维,刘田雨,关志,何逸飞,荆继武,胡磊,张振峰,闫海伦.基于杂凑函数 SM3 的后量子数字签名J.密码学报,2023,10(1):4660.DOI:10.13868/ki.jcr.000578英文引用格式:SUN S W,LIU T Y,GUAN Z,HE Y F,JING J W,HU L,ZHANG Z F,YAN H L.SM3-based post-quantum digital signature schemesJ.Journal of Cryptol
4、ogic Research,2023,10(1):4660.DOI:10.13868/ki.jcr.000578SM3-based Post-quantum Digital Signature SchemesSUN Si-Wei1,LIU Tian-Yu1,GUAN Zhi2,HE Yi-Fei2,JING Ji-Wu1,HU Lei3,ZHANG Zhen-Feng4,YAN Hai-Lun11.School of Cryptology,University of Chinese Academy of Sciences,Beijing 100049,China2.National Engin
5、eering Research Center For Software Engineering,Peking University,Beijing 100871,China3.School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China4.Institute of Software,Chinese Academy of Sciences,Beijing 100190,ChinaCorresponding author:SUN Si-Wei,E-mail:Abstract:The s
6、ecurity of hash-based signatures relies solely on the(second)pre-image resistanceof the underlying hash functions and they are arguably the most conservative signature designs with*基金项目:国家重点研发计划(2022YFB2701900);国家自然科学基金(62032014,62202444);中央高校基本科研业务费专项资金Foundation:National Key Research and Developme
7、nt Program of China(2022YFB2701900);National NaturalScience Foundation of China(62032014,62202444);the Fundamental Research Funds for the Central Universities ofChina收稿日期:2022-10-31定稿日期:2022-11-24孙思维 等:基于杂凑函数 SM3 的后量子数字签名47respect to security.Therefore,hash-based signatures are actively standardized
8、 by the standard bodies.In this article,we instantiate the LMS,HSS,XMSS and XMSSMThash-based signature schemesstandardized in RFC 8554,RFC 8391 and NIST SP 800-208 with SM3 and report on the results ofpreliminary performance tests.Experimental results show that it is feasible to instantiate LMS andH
9、SS with SM3,which provides support for the subsequent standardization work of relevant algorithms.Key words:hash functions;digital signatures;post-quantum cryptography;LMS;HSS;XMSS;XMSSMT;SM31引言由于 Shor 算法可以在量子计算模型下以多项式时间复杂度分解大整数和求解离散对数,一旦大规模通用量子计算机问世,现行的基于大整数分解和离散对数求解困难性的数字签名体制(如 RSA、ECDSA 和 SM2 等)将
10、不再安全1.因此,学术界、产业界和各标准化组织都在积极研究后量子密码算法的设计与迁移.本文主要讨论基于杂凑函数设计的后量子签名体制.基于杂凑函数设计后量子签名体制主要有两类方法.第一类通过暴露某单向函数的原像进行签名24,第二类通过对一单向函数的原像进行零知识证明进行签名.其中后者是一种较新的技术路线,PICNIC5是典型代表,但此类方案还不够成熟稳定.因此,本文只关注第一种技术路线.基于杂凑函数的数字签名体制研究历史悠久,最早可以追溯到 1976 年.在密码学的新方向6这篇里程碑式的工作中,Diffie 和 Hellman 提出了一种利用单向函数对一比特数据进行签名的方法.该方案随机选择(x
11、0,x1)Fn2Fn2作为私钥,(F(x0),F(x1)Fn2Fn2则为相应的公钥,其中 F:Fn2 Fn2为一单向函数.那么,消息 b F2的签名为 F(xb)的原像 xb.经过四十余年的发展,基于杂凑函数的签名体制逐渐成熟.对比其他后量子签名体制的设计方法,基于杂凑函数的设计有很多优势.首先,它是目前所有后量子签名体制中安全性最可靠的方案,这类方案的安全性只依赖于底层杂凑函数的抗(第二)原像攻击的安全性,而不需要依赖其他结构性安全假设(注意,根据目前的研究,即使是被破解了的 MD5 算法也是具备抗原像攻击的性质的).并且,基于杂凑函数的签名体制的底层杂凑函数是可替换的,一但发现当前使用的杂
12、凑函数有安全问题,可以直接替换一个安全的杂凑函数.第二,基于杂凑函数的签名体制的签名和验签性能很好,部分参数设置下性能与 RSA 等传统签名算法相当.第三,基于杂凑函数的签名体制的参数选项丰富,针对具体应用场景有广泛的调整空间710.第四,基于杂凑函数的签名的公私钥尺寸较小.但基于杂凑函数的签名体制仍存在一些缺点.首先,性能和开销比较有优势的基于杂凑函数的签名体制是带状态的,这意味着每次签名后签名私钥都会改变状态.这种改变状态是为了确保同一个一次性签名实例不会进行多于一次签名以确保系统的安全性.2019 年,美国国家标准与技术研究院(NIST)对基于杂凑函数的带状态签名的抗误用进行了专门的讨论
13、11.其次,基于杂凑函数的签名体制的一个实例只能进行有限次签名(但一般都可通过参数调整达到具体应用所需要的签名次数).第三,基于杂凑函数的签名体制生成的签名尺寸较大.但总体来看,在部分应用场景下,上述局限性和开销并没有成为基于杂凑函数的签名体制应用的障碍.1.1应用情况来自 Cisco 和佛罗里达大学的研究人员指出12,签名时间和验签时间分别在 1 s 内和 10 ms 内的后量子签名方案完全可以应用于安全启动(secure boot)的应用场景.而基于杂凑函数的签名体制完全可以达到这个要求.文献 13 分析了在 TPM(trusted platform modules)中利用基于杂凑函数的签
14、名替换 RSA 签名的情况,并指出通过采用合适的 Merkle 树遍历算法,这种替换的开销是完全可以接受的.基于杂凑函数的签名在区块链领域也有所应用,QRL 利用 XMSS 结合 WOTS+实现了一个抗量子攻击分布式账本14.加拿大密码解决方案提供商在其产品 ISARA RadiateTM中实现了 XMSS 方案,该方案克服了基于 HSM 实现基于杂凑函数的签名的多个困难,并在 Utimaco Inc.SecurityServer 中进行了测试15.文献 16 提出了一种可以在无线传感器网络中传感器节点消息认证和广播认证中使用的基于杂凑函数的签名方案.Boneh 等人则考虑了在 SGX 应用基
15、于杂凑函数的签名方案17.最后,英飞凌在48Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023其 TPM 芯片产品 OPTIGATMTPM SLB 9672 中的固件更新功能中使用了基于杂凑函数的签名算法XMSS1.1.2基于杂凑函数的签名体制的标准化工作现状密码学界、工业界和各标准化组织都在积极推动后量子密码算法的标准化工作.因为其可靠的安全性和良好的性能,基于杂凑函数的签名体制成为第一批被标准化的后量子密码算法.早在 2013 年,IETF 就开始了对 Leighton-Micali 签名体制的标准化工作,最终在 2019 年
16、形成了 RFC 855418.对 XMSS 签名体制的标准化工作则开始于 2015 年,最终在 2018 年形成了 RFC 839119.NIST 则将 Leighton-Micali 签名体制(LMS)、XMSS 签名体制以及他们的变种 HSS 和 XMSSMT写入了 NIST SP 800-20820,用以补充 FIPS 186 的不足,并确保在更一般的后量子签名标准形成前有备选的后量子签名算法.当前,ISO 也在积极推动基于杂凑函数的签名体制的标准化工作,形成了 ISO/IEC CD 14888-4 等文件,目前正在讨论与修订中.同时,IETF 也考虑为 LMS 增加更多的参数选择21.
17、我国有关部门对后量子密码的研究、标准化及迁移工作也极为重视.中国密码学会于 2018 年组织了全国密码算法设计竞赛,其中包括后量子公钥密码设计竞赛内容.然而,所提交的算法中并没有基于杂凑函数设计的签名算法.另外,2022 年,基于多变量和基于同源的两个重要后量子密码算法被破解,表明当前后量子密码算法设计的理论与方法在某些方面还不成熟、不可靠.这说明关于后量子密码算法的标准化工作必须谨慎推进.由于可靠的安全性,且国际标准化组织已有相关可借鉴经验,基于杂凑函数的后量子签名体制也许可以成为我国后量子公钥密码算法标准化的起点,并以此为基础形成后量子算法部署、迁移等工作的实践阵地.2预备知识与符号F2=
18、0,1 表示二元域,B=F82表示所有字节(即 8 位二进制数据)的集合.字节和字节序列是本文的基本数据类型,用“0 x”和两个 16 进制数字表示 1 个字节,如 0 xF3.0 xF324EA 则表示一个长度为 3 个字节的字节序列.我们有时会将一个无符号整数 i 转化成一个字节序列,u8str(i)、u16str(i)和 u32str(i)分别为 i 的 1 字节表示、i 的 2 字节表示和 i 的 4 字节表示,例如:u8str(11)=0 x0B,u16str(6214)=0 xF2BC,u32str(305441741)=0 x1234ABCD.有时会将一个 4 字节序列 S 转化
19、成一个无符号整数 int32(S),例如 int32(0 x1234ABCD)=305441741.注意,我们总有 u32str(int32(S)=S.设 S 是字节序列,|S|表示 S 中的字节数.若 0 i|S|,则 byte(S,i)表示 S 的第 i 个字节,byte(S,i,j)表示 S 的第 i 到第 j 个字节.设 A 是一个字节序列数组,数组中的每个元素是一个 n 字节序列,则 Ai Bn表示数组 A 的第 i 个元素.例如,若 S=0 xABCDFF01,则 byte(S,0)=0 xAB,byte(S,3)=0 x01,byte(S,1,3)=0 xCDFF01.若 A=(
20、0 xABCDFF01,0 x00000001,0 xFFFFFFFE),则 A0=0 xABCDFF01,A1=0 x00000001.对一个字节序列 S,我们用 coef(S,i,w)表示它的第 i 个 w 比特串所对应的无符号整数.例如,若 S=0 xABCDFF01,则 coef(S,0,4)=0 xA=10,coef(S,6,4)=0 x0=0,coef(S,3,2)=3.另外,我们总有 coef(S,i,8)=byte(S,i).在本文中,用 w 1,2,4,8 表示所谓的 Winternitz 参数.最后,coef(S,i,w)可以用如下公式计算:coef(S,i,w)=(2w
21、1)AND(byte(S,iw8)(8 w(i%(8/w)+1),其中,j=iw8表示 coef(S,i,w)会出现在 S 的第 j 个字节,=i%(8/w)表示 coef(S,i,w)出现在 S 的第 j 个字节中的第 个 w 比特串上.本文中所涉及到的签名算法都只能进行有限次签名,如果一个签名体制可以进行 N 次签名,当进行了大于 N 次签名后系统的安全性就不能得到保障,则称该签名算法的容量为 N.1https:/ 等:基于杂凑函数 SM3 的后量子数字签名493Leighton-Micali 一次性签名算法(LM-OTS)LM-OTS 是一种一次性签名体制,即一个公私钥对只能进行一次签名
22、,否则该体制安全性会遭到破坏.3.1LM-OTS 系统参数-H():本文中所使用的杂凑函数.-n:本文中所使用的杂凑函数输出杂凑值的字节数.-w:Winternitz 参数,本文中 w 1,2,4,8.-u:杂凑函数的输出中包括 u 个 w 比特串,u=8nw.-v:在使用 LM-OTS 对消息 M 进行签名的过程中,需要计算一个关于 M 的杂凑值的一个校验值,v 为该校验值中 w 比特串的个数,可以按如下公式计算:v=log2(u(2w 1)+1w.-p:在 LM-OTS 的私钥中秘密原像数组中 n 字节序列的个数,p=u+v.-:在签名生成过程中,需要对一个校验值进行向左移位操作,=16
23、vw 表示向左移动的位数.3.2LM-OTS 公私钥对生成方法首先,根据系统所要使用的具体杂凑函数 H()、杂凑函数输出长度 n 和 Winternitz 参数确定 otstype B4值.otstype 的值通常会在相关标准文件中进行规范,例如,在 RFC 8554 中,如果使用的杂凑函数为 SHA256,杂凑函数输出长度为 32 字节且 Winternitz 参数为 4,则 otstype=LMOTS_SHA256_N32_W4=0 x00000003;附录中表5和表6分别给出了 RFC 8554 和一个正在讨论过程中的互联网草案对 otstype 的规范.在本文中,如果使用 SM3,则
24、otstype 的取值见附录中的表7.然后,随机选取 I B16,设置 q=0.接下来,随机生成 x=(x0,x1,xp 1),其中 xj(0 j p)是 n 字节序列.LM-OTS 的私钥为(otstype,I,q,x)B4 B16 B4 Bnp,(otstype,I,q)是可以公开的,而 x=(x0,x1,xp 1)必须保密,称 x 为 LM-OTS 的秘密原像数组.这个秘密原像数组也可通过一个秘密种子 SEED Bn按如下方式生成:对 i 0,1,p 1,令 xj=H(Iu8str(q)u16str(j)0 xFFSEED).这样可以只保存 SEED,在需要 x 时进行在线计算,从而有效
25、降低私钥的存储.通过私钥,可以计算公钥(otstype,I,q,K)B4 B16 B4 Bn.其中,K=H(Iu32str(q)0 x8080y0y1yp 1),而 yi(0 i p)按算法1计算.算法 1 计算(y0,y1,yp 1)1for 0 i p do2tmp xi3for 0 j 2w 1 do4tmp H(I|u32str(q)|u16str(i)|u8str(j)|tmp)5end6yi tmp7end3.3LM-OTS 签名生成过程签名是根据私钥(otstype,I,q,x)和消息 M 生成的,M 可以是任意比特长的串.首先随机生成C Bn,然后计算Q=H(Iu32str(q
26、)0 x8181CM).50Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023接下来需要计算 Q 的一个校验值(Q)=8nw1i=0(2w 1 coef(Q,i,w),(Q)被保存成一个 16 位无符号整型数据.最终 M 的签名为 otstypeCz0z1zp 1,其中(z0,z1,zp 1)按算法2计算.算法 2 计算(z0,z1,zp 1)1S Q|u16str(Q);/*n,w的取值见表1*/2for 0 i p do3a coef(S,i,w)4tmp xi5for 0 j a do6tmp H(Iu32str(q)u16
27、str(i)u8str(j)tmp)7end8zi tmp9end表 1 n,w的取值Table 1Values of n,wnwn,w32172644803.4LM-OTS 签名验证过程对于给定的消息 M 及其签名 otstypeCz0z1zp 1,首先计算Q=H(Iu32str(q)0 x8181CM),然后计算S=Qu16str(Q).接下来用算法3计算(z0,z1,zp 1):算法 3 计算(z0,z1,zp 1)1for 0 i p do2a coef(S,i,w)3tmp zi4for a j 2w 1 do5tmp H(Iu32str(q)u16str(i)u8str(j)tmp
28、)6end7zi tmp8end最后,计算 K=H(Iu32str(q)0 x8080z0z1zp1),若 K=K,则签名验证通过.从签名验证过程可以看出,通过消息和一个正确的签名可以计算出 LM-OTS 的公钥.孙思维 等:基于杂凑函数 SM3 的后量子数字签名514LMS 签名算法LMS 签名体制给出了一种利用高度为 h 的完美二叉树组织 2h个 LM-OTS 公私钥对的方式并规定了这 2h个 LM-OTS 公私钥对的使用顺序.在 LMS 体制中,2h个 LM-OTS 实例对应了一棵如图1所示的高度为 2h的完美二叉树的 2h个叶子节点,从左到右每个叶子节点分别被编号为 0,1,2h1.这
29、个LMS 的整个生命周期会经历 2h个签名,这 2h次签名使用的 LM-OTS 实例的顺序与上述编号一致.T1T2T4T8T9T5T10T11T3T6T12T13T7T14T15图 1 高度为 3 的 LMS 树Figure 1 LMS tree with height 34.1LMS 系统参数-H():使用的杂凑函数.-m:LMS 树中每个节点对应的值的字节数.-h:LMS 树的高度,高度为 h 的 LMS 树对应的 LMS 实例总共可以进行 2h次签名.4.2LMS 公私钥生成方法首先,根据系统所要使用的具体杂凑函数 H()、LMS 树中每个节点对应的值的字节数 m 和 LMS 树的高度
30、h,确定 lmstype B4值.lmstype 的值通常会在相关标准文件中进行规范,例如,在 RFC 8554 中,如果使用的杂凑函数为 SHA256,m=32,且 h=10,则 lmstype=LMS_SHA256_M32_H10=0 x00000006.附录中表5和表6分别给出了 RFC 8554 和一个正在讨论过程中的互联网草案对 lmstype的规范.然后根据使用的 LM-OTS 的参数设置 otstype 的值.在本文中,如果使用 SM3,则 lmstype 的值见附录表10.然后,随机生成 16 字节的 I,设置 q=0.接下来要生成 2h个 LM-OTS 私钥的秘密原像数组x0
31、,x1,x2h1,其中 xj=(xj0,xj1,xjp 1)Bmp.这 2h个 LM-OTS 的秘密原像数组可以通过随机选取 2hp 个 m 字节序列生成,但这需要把x00 x0p 1x10 x1p 1.x2h10 x2h1p 1(1)都存储下来.为了降低存储,也可以使用伪随机数发生器通过一个秘密种子 SEED Bm生成 x=(x0,x1,x2h1).例如,对于 0 q 2h和 0 i p,令xqi=SM3(I|u32str(q)u16str(i)|u8str(0 xFF)SEED).LMS 的私钥为(lmstype,otstype,I,q,x)B4 B4 B16 B4 B2hnp.x=(x0
32、,x1,x2h1)对应了 2h个 LM-OTS 私钥(otstype,I,q,xq),0 q 2h.对于每个 q 0,1,2h 1,可以利用第3.2节中的方法计算 LM-OTS 私钥(type,q,I,xq)所对应的公钥(otstype,I,q,Kq).52Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023利用这 2h个 LM-OTS 公钥可以构造一棵如图1所示的有 2h个叶子节点的完美二叉树,称这棵树为LMS 树.高度为 h 的 LMS 树共有 2h+1 1 个节点,其中有 2h个叶子节点.将这些节点如图1所示按从上到下、从左到
33、右的顺序编号,其中 T1 表示根节点,叶子节点用 T2h,T2h+1,T2h+11 表示.这些节点的值满足如下关系Tr=SM3(I|u32str(r)u16str(0 x8282)Kr2h),r 2hSM3(I|u32str(r)u16str(0 x8383)T2rT2r+1),0 r 2h.(2)LMS 的公钥为(lmstype,otstype,I,T1)B4 B4 B16 Bm.4.3LMS 签名生成过程设消息为 M,LMS 私钥为(lmstype,otstype,I,q,x).首先利用 x=(x0,x1,x2h1)对应的第q 个 LMS-OTS 私钥(type,q,I,xq)对消息 M
34、进行签名,签名生成方法见第3.3节,得到的签名结果记为q(M).若 lmstype 对应的 LMS 的树高为 h,则分别选择高度为 h,h 1,1 的 h 个节点,分别记为path0,path1,pathh1,使得通过 LMS-OTS 私钥(type,q,I,xq)对应的公钥(otstype,I,q,Kq)和(path0,path1,pathh 1)可以计算得到 LMS 树的根节点 T1.则消息 M 的 LMS 签名为(u32str(q),q(M),lmstype,(path0,path1,pathh 1).注意,计算完该签名后,LMS 的私钥变为(lmstype,otstype,I,q+1,
35、x).例如,若 h=3,LMS 的私钥为(lmstype,otstype,I,q=1,x),则 M 的签名结果为(0 x00000001,q(M),lmstype,(T8,T5,T3).如图2所示,实际上是用 LMS 树的第 1 个叶子节点对应的 LM-OTS 私钥对消息 M 进行签名,并提供了第1 个叶子节点的认证路径.T1T2T4T8T9T5T10T11T3T6T12T13T7T14T15M图 2 消息 M 的 LMS 签名Figure 2 LMS signature of M4.4LMS 签名验证过程设消息 M 的签名为(u32str(q),q(M),lmstype,(path0,pat
36、h1,pathh 1).首先,可以利用 q(M)和第3.4节中的 LM-OTS 签名验证方法计算第 q 个叶子节点的假想值 T2h+q.然后,利用T2h+q 和(path0,path1,pathh 1)基于公式(2)计算假想的 LMS 树的根节点 T1.如果T1=T1 则签名验证通过.孙思维 等:基于杂凑函数 SM3 的后量子数字签名535HSS 签名算法与 LMS 一样,HSS 也提供了一种组织和使用大量 LM-OTS 实例的方法.在一些场景中,如果需要较多的签名次数并希望密钥生成的时间较短,则可以使用所谓的分层签名方案(hierarchical signaturescheme,HSS).在
37、 HSS 中有 L 层 LMS 实例,包括第 0 层,第 1 层,第 L 1 层.同一层内的 LMS实例对应的 LMS 树的高度相同.假设第 i 层 LMS 实例的高度都为 hi(0 i L),则第 0 层只有 1 棵LMS 树,当 0 i 1 时,签名可表示为u32str(Nspk)|signed_pub_key0|signed_pub_key1|signed_pub_keyNspk 1sigNspk,其中 Nspk=L1 表示被签名的 LMS 公钥(LMS 树的根节点)的个数(number of signed public keys).上述签名按算法4得到.算法 4 生成消息 M 的签名1
38、d L2while prvd 1.q=2prvd1.hdo3d d 1;/*当前第 d 层正在使用的 LMS 树的叶子节点已全部用完,需要检查上一层的情况*/4if d=0 then5return FAILURE;/*超过了该 HSS 实例可签名的总次数*/6end7end8while d L do9随机独立生成一个 LMS 公私钥对并存入 pubd 和 prvd10sigd 1 使用 prvd 1 对公钥 pubd 签名11d d+112end13sigL 1 使用 prvL 1 对消息 M 进行签名.14for 0 i L 1 do15signed_pub_keyi sigipubi+11
39、6end17return u32str(L 1)signed_pub_key0signed_pub_key1signed_pub_keyL 2sigL 15.3HSS 签名验证过程分别验证 signed_pub_key0,signed_pub_key1,signed_pub_keyL 2 和 sigL 1,HSS签名验证通过当且仅当上述签名全部验证通过.6XMSS 和 XMSSMT签名算法与 LMS 类似,一个容量为 2h的 XMSS 实例对应于一个高度为 h 的完美二叉树.这个二叉树的每个叶子节点对应于一个 WOTS+一次性签名实例,其根节点则用于对其所有叶子节点对应的 WOTS+22实例进
40、行认证.XMSS 每次签名会消耗一个 WOTS+实例,方式与 LMS 签名时消耗 LM-OTS 实例的方式相似.我们称一个 XMSS 实例对应的完美二叉树为一个 XMSS 树,XMSS 树中每个节点的计算方式与LMS 有所不同,具体细节可参考文献 3,19.孙思维 等:基于杂凑函数 SM3 的后量子数字签名55XMSSMT 8是 XMSS 的超树版本(与 HSS 是 LMS 的超树版本类似),它提供另一种组织和使用大量 WOTS+一次性签名实例的方法.在一个容量为 2h的 XMSS-MT 实例中,许多高度为hd的 XMSS树分布在 d 个不同的层中,其中第 0 层是最底层,第 d 1 层是最顶
41、层.位于第 1 层到第 d 2 层中的每一个 XMSS 树的每一个叶子节点,都关联着一个位于其下一层的 XMSS 树.在第 d 1 层(最顶层)有且仅有一个 XMSS 树.在第 i 层中(0 i d),共有 2(d1i)h/d个 XMSS 树.从而,在第 0 层中共有2(d1)h/d个 XMSS 树.由于每个 XMSS 树共有 2h/d个叶子节点,因此,在最底层共有 2h个叶子节点,共对应于 2h个 WOTS+一次性签名实例.在使用 XMSSMT对一个消息 M 进行签名时,首先使用最底层的一个 XMSS 树的叶子节点所对应的 WOTS+实例对其签名.从第 1 层到第 d 1 层,每一层都有且仅
42、有一个 XMSS 树涉及到此次签名.我们用这里的每一个 XMSS 树对其下一层的 XMSS 树的根节点进行签名,其基本原理与 HSS 相似,具体细节可参考文献 8,19.7实现与性能测试本节使用 SM323将之前提到的基于杂凑函数的数字签名机制实例化,并分别命名为 LMS-SM3、HSS-SM3、XMSS-SM3 和 MT-XMSS-SM3.我们通过将 https:/ 中的杂凑函数替换成 SM3 来实现 LMS-SM3 和 HSS-SM3.在一台处理器为 2.9 GHz 的 AMD EPYC-ROME,系统为 Linux ubuntu 18.04 的 32 核服务器上进行了性能测试,具体结果见
43、表2与表3所示.在表2与表3中,“参数”一列显示了 HSS-SM3 实例的层数和每层的树高:一个数字 h 代表一个高度为 h 的 LMS-SM3 实例,h0/h1代表第 0 层树高为 h0、第 1 层树高为 h1的 2 层 HSS-SM3 实例.表 2 HSS-SM3 性能测试(w=4)Table 2Performance test of HSS-SM3(w=4)参数密钥生成时间(s)公钥尺寸(byte)私钥尺寸(byte)签名时间(s)签名尺寸(byte)验签时间(ms)容量50.01160640.005623520.001525100.09860640.007925120.00142101
44、52.9160640.01926720.001821520100.0260640.01928320.00222015/102.9960640.0152360.003422515/153.1860640.0153960.004823020/10107.3560640.01353960.003823020/15118.0660640.01155360.003235表 3 HSS-SM3 性能测试(w=8)Table 3Performance test of HSS-SM3(w=8)参数密钥生成时间(s)公钥尺寸(byte)私钥尺寸(byte)签名时间(s)签名尺寸(byte)验签时间(ms)容量5
45、0.03360640.02412960.003325100.69760640.04214560.00362101521.3560640.0116160.004621520928.2160640.0917760.00522015/1023.9560640.05631240.0122515/1525.6260640.06832840.0123020/10911.4260640.05732840.0123020/15960.4660640.05134440.008723556Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023我们通过将
46、https:/ 中的杂凑函数替换成 SM3 来实现 XMSS-SM3 和 MT-XMSS-SM3.初步的性能测试结果见表4,其中,“参数”一列代表 XMSS-SM3 或 MT-XMSS-SM3 各实例的层数和相应各层 XMSS 树的高度:h/d 代表实例有 d 层,各层中 XMSS 树的高度为 h/d.注意在 XMSS-SM3 和 MT-XMSS-SM3 中 w 参数的意义与 LMS-SM3 和 HSS-SM3 中 w 参数的意义有所不同,具体参见文献 19.表 4 XMSS-SM3 和 MT-XMSS-SM3 性能测试(w=16)Table 4Performance test of XMSS
47、-SM3 and MT-XMSS-SM3(w=16)参数密钥生成时间(s)公钥尺寸(byte)签名时间(s)签名尺寸(byte)验签时间(s)容量109.758708680.01742925020.0062121020/26.730387680.01912849650.0118322020/40.210187680.02931492530.0194922040/80.213399680.037080184710.0334724060/120.21967680.031442276900.042522608结论与讨论本文对 RFC 8554、RFC 8391 和 NIST SP 800-208 中
48、的基于杂凑函数的后量子数字签名 LMS、HSS、XMSS 和 XMSS-MT XMSS-MT 进行了国产杂凑函数 SM3 的替换,并进行了初步的实现和性能测试24,25.这一工作表明了在 LMS 和 HSS 中使用 SM3 的可行性,为后续相关标准化工作的推进提供了支撑.后续还需要在多种平台上对相关算法进行实验和测试.本文给出的全部签名算法本质上都是一种使用有限个一次性签名实例(OTS)进行签名的方法.其所使用的每个 OTS 实例最多只能对一个消息进行签名,否则签名算法的安全性将得不到保障,关于使用 OTS 多次签名带来的安全影响,可参考文献 26.为此,本文给出的签名方案的私钥必须维护一个状
49、态,每次签名都需要对该状态进行更新,以确保其所使用的每个 OTS 实例最多只能进行一次签名.因此,安全可靠的私钥状态管理,是确保安全应用这类签名方案的前提.下面给出一些安全管理私钥状态的建议.首先,私钥通常会被保存在非易失存储(如硬盘)中,在进行签名时私钥被载入内存.在实现中,可以先进行状态更新再进行签名操作以确保完成并输出签名前非易失存储中的私钥状态得到了正确更新.第二,建议将私钥存储在硬件安全模块(HSM)中,以防止对私钥信息的非法访问.最后,不建议在同一私钥可以在多个模块或设备中共同使用的场景中应用这类带状态的签名方案,这样可以避免多个私钥拷贝间不正确的状态同步所带来的安全性问题.上述内
50、容旨在提醒算法实现者安全管理私钥状态的重要性,其提供的相关措施并不能覆盖所有应用场景,具体实现需要根据应用场景做具体分析,更多关于状态管理的技术可参考文献 27.参考文献1 SHOR P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum com-puterJ.SIAM Review,1999,41(2):303332.2 LAMPORT L.Constructing digital signatures from a one way function:CSL-98R
