一种针对SM2数字签名算法的攻击方案.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(4):823835密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]一种针对 SM2 数字签名算法的攻击方案*白 野1,何德彪1,罗 敏1,杨智超2,彭 聪11.武汉大学 国家网络安全学院 空天信息安全与可信计算教育部重点实验室,武汉 4300722.海军工程大学 信息安全系,武汉 430032通信作者:何德彪,E-mail:摘要:SM2 数字签名算法是我国商用密码体系的重要组成部分,目前已广泛应用于电子签章等领域.研究 SM2 数字签名算法潜在的安全风险及相应的防范技术,对于推动我国商用密码体系的安全应用具有重要意义.SM2 数字签名算法的安全性基于椭圆曲线离散对数问题的困难性,当前已有一些针对不同椭圆曲线类数字签名算法的攻击研究,但攻击 SM2 数字签名算法的方案还存在所需签名数量较多、攻击耗时较长、成功率较低的问题.本文针对 SM2 数字签名算法设计了一组判断函数,基于带判断的格基约减算法,提出了一种针对 SM2 数字签名算法的侧信道攻击方案,并分别就算法中随机数的最高 3 比特、最低3 比特和中间 17 比特已知三种情况进行了侧信道攻击实验.实验结果表明,相比现有攻击 SM2 数字签名算法的方案,本文攻击方案所需签名数量减少了 10%,私钥恢复时间减少了 86%,成功率提高了 2 倍.关键词:SM2 数字签名算法;格基约减算法;侧信道攻击;判断函数中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000631中文引用格式:白野,何德彪,罗敏,杨智超,彭聪.一种针对 SM2 数字签名算法的攻击方案J.密码学报,2023,10(4):823835.DOI:10.13868/ki.jcr.000631英文引用格式:BAI Y,HE D B,LUO M,YANG Z C,PENG C.An attack method on SM2 digital signaturealgorithmJ.Journal of Cryptologic Research,2023,10(4):823835.DOI:10.13868/ki.jcr.000631An Attack Method on SM2 Digital Signature AlgorithmBAI Ye1,HE De-Biao1,LUO Min1,YANG Zhi-Chao2,PENG Cong11.Key Laboratory of Aerospace Information Security and Trusted Computing,Ministry of Education,Schoolof Cyber Science and Engineering,Wuhan University,Wuhan 430072,China2.Department of Information Security,Naval University of Engineering,Wuhan 430032,ChinaCorresponding author:HE De-Biao,E-mail:Abstract:SM2 digital signature algorithm is an important part of Chinese commercial cryptographysystem,which has been widely used in electronic signature and other fields.Studying the potentialsecurity vulnerabilities of SM2 digital signature algorithm and the corresponding prevention methodsare of great significance to promote the application of Chinese commercial cryptosystem.The securityof SM2 digital signature algorithm is based on the hardness of elliptic curve based discrete logarithmproblem.At present,there have been some researches about attacks on different elliptic curve digital*基金项目:山东省重点研发计划(2020CXGC010107);国家自然科学基金(U21A20466,62172307,61972294,61932016)Foundation:Shandong Provincial Key Research and Development Program(2020CXGC010107);National NaturalScience Foundation of China(U21A20466,62172307,61972294,61932016)收稿日期:2022-05-16定稿日期:2022-09-01824Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023signature algorithms,however,the existing attacks on SM2 digital signature algorithm still have someefficiency problems such as large number of signatures required,long attacking time and low successrate.This paper designs a set of judgment functions for SM2 digital signature algorithm,and proposesa side-channel attack on SM2 digital signature algorithm based on lattice basis reduction algorithmwith judgment.Experiments of private key recovery are carried out in three cases of knowing thehighest 3 bits,the lowest 3 bits and the middle 17 bits of the random number.Experimental resultsshow that,compared with the existing attacks on the SM2 digital signature algorithm,in this proposedattack,the number of signatures required is reduced by 10%,the private key recovery time is reducedby 86%,and the success rate is increased by 2 times.Key words:SM2 digital signature algorithm;lattice basis reduction algorithm;side channel attack;predicate function1引言SM2 椭圆曲线公钥密码算法1于 2010 年 12 月 17 日发布,2012 年被批准为密码行业标准(GM/T0003-2012)2,2016 年正式成为中国国家密码标准(GB/T32918-2016)3.SM2 椭圆曲线公钥密码算法包括数字签名算法、密钥交换协议、公钥加密算法三部分.在当前的商用密码体系中,SM2 数字签名算法4提供了电子认证服务系统所需的安全支撑,基于 SM2 数字签名算法的适配器签名5、环签名6等算法丰富了它的应用环境.目前,SM2 数字签名算法已成为我国自主可控商用密码体系的重要组成部分.侧信道攻击又称边信道攻击,是一种利用计算机计算过程中泄漏出的功耗、电磁辐射等信号来进行攻击的方法.对于椭圆曲线类数字签名方案,如果签名者没有妥善保护好执行签名算法的设备,恶意攻击者可以通过观察随机数 k 的功耗泄露情况,对 k 参与的计算过程进行简单功耗分析(simple power analysis,SPA)7,恢复出 k 的部分比特值;当签名者使用相同签名私钥执行多次签名算法使攻击者收集到足够的随机数、签名组后,攻击者能够通过随机数、签名和公钥之间的关系利用格攻击等手段以较高的概率恢复出签名私钥.格基约减算法是密码学中广泛使用的一类算法,主要包括 LLL 算法8、BKZ 算法9等,它们通过对格基矩阵的行向量(或列向量)进行线性组合,使算法的输出为一组范数更小的格基.BKZ 算法可以分为使用枚举(enumeration,enum)子算法10的 BKZ 算法和使用筛选(Sieve)子算法11的 BKZ 算法两类.两种子算法均可用于求解格上最短向量问题(shortest vector problem,SVP),它们的计算复杂度分别为(4/3)n+o(n)和 2(n log n).Chen 和 Nguyen 于 2011 年提出了基于修剪技术的枚举算法 Prun-Enum12,提高了枚举算法的实际运行速度.虽然筛选算法比枚举算法的计算复杂度更小,但在实际应用中,Prun-Enum 算法往往具有更高的运行效率.2018 年,Ducas 提出了一种亚指数级的筛选算法13,令d=(n/logn),算法通过在(n d)维线性空间上调用 Sieve 算法求解 n 维线性空间上的最短向量问题,相比于以往的筛选算法,它的运行速度更快;相比于 Prun-Enum 算法,它的运行速度只慢一个数量级.当攻击者知晓了椭圆曲线数字签名随机数的部分比特并搜集到足够的签名后,构造出一组隐藏数问题(hidden number problem,HNP)14实例.隐藏数问题可被视为一种特殊的有界距离解码(boundeddistance decoding,BDD)问题,攻击者使用格基约减算法对实例进行破解,最终恢复出用户的签名私钥.2001 年,Howgrave-Graham 和 Smart 首次提出了使用格基约减算法攻击 DSA 算法的方案15.2003 年,Nguyen 和 Shparlinski 提出了第一个可证明的多项式时间内基使用格基约减算法攻击 ECDSA 算法的方案16.早期,大多数对椭圆曲线数字签名算法攻击方案的研究都是在随机数最高部分比特或最低部分比特已知下进行的,2006 年,Hlav 和 Rosa 针对随机数中间部分比特已知的椭圆曲线数字签名算法提出了带有两组未知数的隐藏数问题(hidden number problem with two holes,HNP-2H)17,并给出了一种HNP-2H 问题到 HNP 问题的转换方法,使 HNP-2H 问题也可以被格基约减算法攻破.2013 年,Liu 等人提出了第一个利用格基约减算法攻击 SM2 数字签名算法的方案18,可以在 SM2数字签名算法随机数最高 3 比特已知的情况下恢复出签名私钥,但这种方法所需的签名数量较多,运行时间较长.2019 年,Ryan 等人对 ECDSA、DSA 等签名算法中的模约减部分进行分析,提出了一种新的侧白野 等:一种针对 SM2 数字签名算法的攻击方案825信道攻击方式19,在 256 比特安全级别下,ECDSA 算法中随机数最高 4 比特已知时,能以极高的成功率恢复出签名私钥,但无法做到 3 比特已知时的私钥恢复,且攻击方案的时间开销较大.2021 年,Albrecht和 Heninger 提出了一种带判断的 BKZ 算法20,在相同的安全级别下,可以做到随机数最高 3 比特已知时的私钥恢复,且时间开销较小,所需签名数量也较少.目前,大多数研究成果都是针对 ECDSA 算法的攻击方案,只有 Liu 等人18针对 SM2 数字签名算法的攻击方案进行了研究,但他们的攻击成功率较低,所需时间较长.针对这一问题,本文基于带判断的格基约减算法20,分别设计了随机数最高、最低、中间部分比特已知三种情况下的 SM2 数字签名算法攻击方案,并对方案进行了实验和分析.本文的主要贡献如下:(1)基于带判断的格基约减算法20,根据 SM2 数字签名算法的结构,设计了 SM2 数字签名算法中随机数最高、最低、中间部分比特已知三种情况下的判断函数 fmost,least,mid(),用于修剪掉格基约减过程中产生的无效分支,提高约减效率.(2)设计了针对 SM2 数字签名算法中随机数中间部分比特已知时的攻击方案.本文以损失一半已知比特数的代价,将对应的 HNP-2H 问题转换为 HNP 问题,基于所设计的判断函数进行求解以恢复出签名私钥.(3)分别设计了针对 SM2 数字签名算法中随机数最高、最低部分比特已知时的攻击方案.本文基于所设计的判断函数,对两种情况对应的 HNP 问题进行求解以恢复出签名私钥.实验结果表明:相比现有攻击 SM2 数字签名算法的方案,本攻击方案所需的签名数量减少了 10%,私钥恢复的时间减少了 86%,成功率提高了 2 倍.本文结构如下:第2节介绍了 SM2 数字签名算法密钥恢复的预备知识,包括 SM2 数字签名的定义、格的定义、格上困难问题、格基约减算法以及隐藏数问题的定义;第3节就 SM2 数字签名算法中随机数的最高、最低、中间部分比特已知三种情况,分别设计各自的判断函数,并提出相对应的格攻击方案;第4节分析了本文方案攻击 SM2 数字签名算法的效率;最后第5节总结本文的研究成果.2预备知识2.1SM2 数字签名算法SM2 数字签名算法4包括系统参数生成、密钥生成、签名生成、签名验证四部分:系统参数生成:输入一个安全参数,输出椭圆曲线参数六元组 T=p,a,b,G,n,h,其中 p 为一个大于 3 的素数,确定了有限域 Fp中的元素为 0,1,p 1;a,b 为有限域 Fp中的两个元素,与 p 共同确定了椭圆曲线方程 y2 x3+a x+b mod p;G=(xG,yG)为椭圆曲线上一个循环子群的生成元,n 为生成元的阶,它们共同确定了循环子群的内容;h 为 n 的余因子,大小为h=N/n,其中 N 为椭圆曲线的阶(椭圆曲线中点的数量).密钥生成:拥有 entlenA比特长可辨别标识 IDA的签名者 A 生成自己的私钥 dA并将其私密保存,计算并公开公钥 PA=(xA,yA)=dAG.签名生成:给定消息 M,A 首先将 entlenA转换为 2 字节长的比特串 ENTLA,并将身份信息和椭圆曲线相关参数拼接在一起作哈希映射 ZA=H256(ENTLAIDAabxGyGxAyA);其次,令M=ZA|M,计算消息摘要 e=H256(M);然后,随机选取 k Zn,计算(x1,y1)=kG.(1)最后计算r=(e+x1)mod n,(2)s=(1+dA)1(k r dA)mod n,(3)(4)826Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023将签名对(r,s)发送给验证者.签名验证:验证者 B 收到消息 M和签名对(r,s)后,首先,B 判断是否有 r,s Zn,如果条件不成立则验证不通过,否则令M=ZA|M,计算消息摘要 e=H256(M);其次,计算 t=(r+s)mod n;然后,利用 s和 t 计算(x1,y1)=sG+tPA;最后,计算 R=(e+x1)mod n,判断如果 R=r则验证通过,(r,s)是关于消息 M 的有效签名,否则验证不通过.2.2格格 L 是 n 维线性空间中一组线性无关向量的整线性组合,本文用形如 b 的小写粗体字母表示格中的向量,形如 B 的大写粗体字母表示一个格基矩阵,b2表示向量 b 的二范数,bi,bj 表示向量 bi和向量 bj的内积,1(L)表示格 L 中最短向量的长度.格的基(B)定义为 Rn上的 d 个线性无关向量 b0,b1,bd1 Rnd,B=(b0,b1,bd1)是一个 n d 的矩阵,其中 bi为第 i 列向量,整数 d 和 n 表示格 L(B)的秩和维数.若 d=n,则 L(B)是 Rd上的满秩(或满维)格.格可以表示为L(B)=Bv:v Zd=L(b0,b1,bd1)=d1i=0vibi:vi Z,0 i d 1.对于格中的正交映射,其定义如下.定义 1(正交映射)定义 i:Rnd7 span(b0,b1,bi),其中 i=0,1,d 1,特别地,当i=0 时,定义 0为恒等变换.那么给定一组基 B,和其施密特正交(Gram-Schmidt orthogonalization,GSO)基 B=(b0,b1,bd1),其中 b0=b0,对于 i=1,2,d 1 和 j=0,1,i 1,令i,j=bi,bjbj,bj,则有 bi=bii1j=0i,jbj.那么正交映射和施密特函数间存在等式 i(bi)=bi.对于0 i 0 使得向量 t 和格之间的欧氏距离 dist(t,L(B)1(L),找到一个长度为 1(L)的非零向量 v L.并且,对于任何一个多项式边界 1,都存在一个由 BDD1/(2)到 uSVP的规约21.Albrecht 和 Heninger 结合传统的 uSVP 问题,增加了一个判断函数 f(),定义了一种带判断的uSVP 问题20:定义 4(带判断的唯一最短向量问题,unique shortest vector problem with predicate,uSVPf()给定一个格 L 和一个判断函数 f(),找到一个满足 f(v)=1 的向量 v L.2.4格基约减算法格基约减算法的目标是找到尽量短且近似正交的一组格基向量,它是求解近似格困难问题的主要算法,同时也是求解精确格困难问题时对格基进行预处理的重要工具.目前主流的格基约减算法主要有 LLL算法、BKZ 算法等,这种算法能够在一定时间内找到相对较短的向量.LLL 算法8于 1982 年被首次提出,是第一个具有多项式渐进运行时间的算法22.算法的输入是一组格基 B,输出是一组近似正交的 LLL 约减基 B.虽然它并没有解决 uSVP 问题,但它将原有的格基约减为了一组近似正交的格基.BKZ 算法9由 Schnorr 等人首次提出,是一种比较理想的格基约减算法.对于 BKZ 约减,Nguyen等人给出了如下的定义23:白野 等:一种针对 SM2 数字签名算法的攻击方案827定义 5(HKZ 约减和 BKZ 约减,Hermite-Korkine-Zolotarev and Block-Korkine-Zolotarev reduc-tions,HKZ 和 BKZ)在基为 B=(b0,b1,bn1)的格 L 中,如果 i 0,i n,都有 bi=1(Li:max(i+,n),那么就称它是块大小为 的 BKZ 约减(简记为 BKZ-约减)的.BKZ 约减算法常被用来解决 uSVP 和 BDD 问题,Enum(i,k)和 Sieve(i,k)是两种求解最短独立向量的算法,分别代表者枚举算法和筛选算法,它们输入一组基 Bi,j,输出这组基下的最短向量.BKZ 算法通过不断调用 Enum(或 Sieve)子算法和 LLL 算法实现了格基的约减,且使用 BKZ 算法比使用 LLL 算法得到的格基的范数更小.算法 1 BKZ 算法Input:一个 d 维格 L 的基 B=(b0,b1,bd1),块大小 2,3,dOutput:一组约减基 B=(b0,b1,bd1)1B B;2for i from 0 to d 1 do3k min(+i 1,d 1);4b Enum(i,k)(或 Sieve(i,k);5h min(k+1,d 1);6正交化 bi和 b 得到 bi和 b;7if b bi then8(b0,b1,bh)LLL(b0,b1,bi1,b,bi+1,bi+2,bh);9else10(b0,b1,bh)LLL(b0,b1,bh);11end12end特别地,算法1是对列向量组成的格基进行约减的算法,当需要对行向量组成的格基进行约减时,只需将格基矩阵转置并输入,再将输出的矩阵转置即可得到约减基.Albrecht 和 Heninger 结合原本的 Enum 和 Sieve 算法,增加了一个判断函数 f(),提出了两种带判断的算法 Enum-Pred 和 Sieve-Pred,它们在算法运行过程中筛选出一些满足 f(v)=1 的向量 v 以加快算法的运行速度,提高计算效率,可以被用来解决 uSVPf()问题20.2.5隐藏数问题(hidden number problem,HNP)隐藏数问题由 Boneh 和 Venkatesan 首次提出14,定义如下:定义 6(隐藏数问题,hidden number problem,HNP)给定长度 Z,公共模数 n,一些整数0 ti n,0 ui n,满足等式 ui+ki ti mod n,其中 0 i d 1,ki为一些满足 ki 2的未知非负整数,为一个未知的秘密整数,要求根据这些等式求解出秘密值.HNP 的困难性可以规约到比较特殊的 BDD 问题上18,除此之外,Hlav 等人于 2006 年还定义了一种更为复杂的 HNP-2H17如下:定义 7(带有两组未知数的隐藏数问题,hidden number problem with two holes,HNP-2H)给定长度 1,2 Z,公共模数 n,一些整数 0 ti n,0 ui n,0 i,1 n,0 i,2 n,满足等式ui+i,1ki,1+i,2ki,2 ti mod n,其中 0 i d1,ki,1和 ki,2为一些满足 ki,1 21和 ki,2 0,那么一定 Z,使得1 B 且|A|NNB,其中,|A|N表示(A mod N).828Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20233基于格攻击 SM2 数字签名SM2 数字签名算法包含对随机数 k 的选取,如果 k 的最高 know位、最低 know位或中间 know位已知,那么根据情况不同,可以选用3.1节、3.2节或3.3节的方案攻击 SM2 数字签名算法,恢复出签名私钥 dA.为了方便理解,对于 比特长的大整数 k,本文使用(k(2)1,k(2)2,k(2)0)表示它的二进制形式,其中 i 0,1,1,ki 0,1.3.1SM2 数字签名随机数最高 know位已知时的攻击方案如果随机数 k 的最高 know位已知,令 =logn know表示 k 的未知位长度,可以将其表示为k=2a+b,其中 a 已知,b 未知,写作二进制形式如下:(k(2)log n1,k(2)log n2,k(2)0)|zlog n位,未知=2(a(2)know1,a(2)know2,a(2)0)|zknow位,已知+(b(2)1,b(2)2,b(2)0)|z位,未知那么式(3)将变为s (1+dA)1(2a+b r dA)mod n,等式两边进行移项后,有(2a s)+b (s+r)dAmod n.(5)假如签名者使用私钥 dA进行了 d 次签名,恶意攻击者通过简单功耗分析等手段获取到每次签名过程中随机数 ki的最高 know比特 ai,并得到签名结果(ri,si),令 ki=2ai+bi,ui=(2ai si)mod n,ti=(si+ri)mod n,=dA,其中 0 bi 2,i 0,1,d 1,式(5)被转变为了一个 HNP 实例ui+bi ti mod n,i 0,1,d 1.(6)针对式(6)的集合,有t1i(ui+bi)t1d1(ud1+bd1)mod n.重新组合上式,有ui ti t1d1 ud1+bi ti t1d1 bd1mod n.那么令 ui=ui ti t1d1 ud1,ti=ti t1d1,构造出一个新的 HNP 实例ui+bi ti bd1mod n,i 0,1,d 2.(7)不难发现,式(7)比式(6)构成的 HNP 实例具有更小的维度.由于格基约减算法求解 HNP 实例的效率不仅取决于待约减格基的维数,更与格基矩阵中元素大小相关,元素尺寸越小,约减速率越快,求解成功率也越高.因此,令 w=2l1,本文基于 Albrecht 和 Heninger20的约减方法对式(7)做如下恒等变换(ui+w ti w)+(bi w)ti(bd1 w)mod n,i 0,1,d 2.令 ui=ui+w ti w,bi=bi w,bd1=bd1 w,i 0,1,d 2,构造出最终的 HNP 实白野 等:一种针对 SM2 数字签名算法的攻击方案829例ui+bi ti bd1mod n,i 0,1,d 2.(8)SM2 数字签名算法要求 ti=(si+ri)=0 mod n,故 ti=ti t1d1 1 mod n,于是有 ui=ui+w ti w ui;由于 0 bi 2l1且 bi 2l 2l1=2l1.相比于式(7),式(8)中 ui的大小更小,bi的尺寸也更短,构造格基矩阵求解 HNP 实例的效率将更高.本文基于式(8)构造出(d+1)(d+1)的格基矩阵如下:L=n00000n000.00n00t0t1td210u0u1ud20w.那么对于约减矩阵任意一行的向量 v,设计判断函数 fmost(v)为:(1)计算 ki 2knowai+v0+w;(2)计算(x1,y1)kiG mod n;(3)根据式(2)计算 ri x1+eimod n;(4)判断是否有 ri=ri,如果相等,则返回 fmost(v)=1,否则返回 fmost(v)=0.最后,以 vt=(b0,b1,bd2,bd1,w)为目标向量,利用判断函数 fmost(v)对格基 L 使用带判断的 BKZ 算法,得到一组约减基 vt=(v0,v1,vd),然后遍历向量的前 d 个分量,执行以下步骤判断是否成功恢复出了第 i 次签名的随机数 ki:(1)计算 ki 2knowai+vi+w;(2)计算(x1,y1)kiG mod n;(3)根据式(2)计算 x1 ri eimod n;(4)判断是否有 x1=x1,如果相等,则成功恢复出了第 i 次签名的随机数 ki ki.重复以上过程直至成功恢复出一个签名随机数或遍历完所有分量为止,如果成功恢复出了一个签名随机数 ki,那么根据式(3)计算dA=(si+ri)1(ki si)mod n,即可恢复出签名私钥 dA.3.2SM2 数字签名随机数最低 know位已知时的攻击方案如果随机数 k 的最低 know位已知,令 =logn know表示 k 的未知位长度,可以将其表示为k=a+2knowb,其中 a 已知,b 未知,写作二进制形式如下:(k(2)log n1,k(2)log n2,k(2)0)|zlog n位,未知=(a(2)know1,a(2)know2,a(2)0)|zknow位,已知+2know(b(2)1,b(2)2,b(2)0)|z位,未知,那么式(3)将变为s (1+dA)1(a+2knowb r dA)mod n,830Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023等式两边进行移项后,有2know(a s)+b 2know(s+r)dAmod n.(9)假如签名者使用私钥 dA进行了 d 次签名,与3.1节不同,恶意攻击者可以获取到每次签名过程中随机数 ki的最低 know比特 ai,并得到签名结果(ri,si),令 ki=ai+2knowbi,ui=2know(ai si)mod n,ti=2know(si+ri)mod n,=dA,其中 bi 2,i 0,1,d 1,式(9)被转变为了一个与式(6)具有相同形式的 HNP 实例.令 ui=ui ti t1d1 ud1,ti=ti t1d1,ui=ui+w ti w,bi=bi w,bd1=bd1 w,i 0,1,d 2,构造出一个与式(8)具有相同形式的 HNP 实例.利用 Albrecht 和 Heninger20提出的格基构造方法构造出格基矩阵 L,对于矩阵任意一行的向量 v,设计判断函数 fleast(v),函数首先计算 ki ai+2know(v0+w),后续步骤与 ki相同.最后,以 vt=(b0,b1,bd2,bd1,w)为目标向量,利用判断函数 fleast(v)对格基 L 使用带判断的 BKZ 算法,得到一组约减基 vt=(v0,v1,vd),然后遍历向量的前 d 个分量,分别计算 kiai+2know(vi+w),重复执行与3.1节类似的恢复步骤(只有 ki的计算过程不同),直至成功恢复出一个签名随机数或遍历完所有分量为止,如果成功恢复出了一个签名随机数 ki,那么根据式(3)计算dA=(si+ri)1(ki si)mod n即可恢复出签名私钥 dA.3.3SM2 数字签名随机数中间 know位已知时的攻击方案如果随机数 k 的中间 know位已知,那么 k 由低位到高位将被分割成三部分 b1,a 和 b2,令 1表示b1的位长,2=logn know 1表示 b2的位长,可以将其表示为 k=b1+21a+21+knowb2,其中 a,1,2均已知,b1和 b2未知,写作二进制形式如下:(k(2)log n1,k(2)log n2,k(2)0)|zlog n位,未知=(b(2)1,11,b(2)1,12,b(2)1,0)|z1位,未知+21(a(2)know1,a(2)know2,a(2)0)|zknow位,已知+21+know(b(2)2,21,b(2)2,22,b(2)2,0)|z2位,未知.那么式(3)将变为s (1+dA)1(b1+21a+21+knowb2 r dA)mod n,等式两边进行移项后,有(21a s)+b1+21+knowb2(s+r)dAmod n.(10)假如签名者使用私钥 dA进行了 d 次签名,与3.1节和3.2节不同,恶意攻击者可以获取到每次签名过程中随机数 ki的中间 know比特 ai,并得到签名结果(ri,si),令 ki=bi,1+21ai+21+knowbi,2,ui=(21ai si)mod n,ti=(s+r)mod n,=dA,=21+know,其中 bi 2,i 0,1,d 1,那么式(10)被转变为了一个 HNP-2H 实例ui+bi,1+bi2 ti.(11)根据 Hlav 和 Rosa17对 HNP-2H 的求解方案,本文使用如下的方法将 HNP-2H 实例转变为白野 等:一种针对 SM2 数字签名算法的攻击方案831HNP 示例:令 i=bi,1+bi,2,那么同余式可转变为ui+i ti.(12)当前 i的取值范围为 0 i n,为了缩短 i的位长,本文引用了引理1.给定一个实数 Bmin=n1/22(21)/2,对于 0 i d 1,根据引理1可以比较容易地找到一个非零整数 i,Bmin满足|i,Bmin|nBmin且 1 i,Bmin Bmin,于是有i,Bmin imod n=(i,Bminbi,1+i,Bminbi,2)mod n(i,Bminmod n)bi,1+(i,Bmin mod n)bi,2 Bmin 21+nBmin 22=n1/22(1+2)/2.那么令 bi=i,Bminimod n,ui=i,Bminuimod n,timod n,就可以将式(12)转变为一个新的HNP 实例ui+bi ti,i 0,1,d 1.(13)那么将这个 HNP 实例(式(13)代入到3.1节的方案中,令 bi=bi w,i 0,1,d 1,构造出格基矩阵 L,对于矩阵任意一行的向量 v,设计判断函数 fmid(v),函数首先计算 ki 2know+1ai+1i,Bi,min(v0+w)mod n,后续步骤与 ki相同.最后,以 vt=(b0,b1,bd1,w)为目标向量,利用判断函数 fmid(v)对格基 L 使用带判断的 BKZ算法,得到一组约减基 vt=(v0,v1,vd),然后遍历向量的前 d 个分量,分别计算 ki 2know+1ai+1i,Bi,min(vi+w)mod n,重复执行与3.1节类似的恢复步骤(只有 ki的计算过程不同)直至成功恢复出一个签名随机数或遍历完所有分量为止,如果成功恢复出了一个签名随机数 ki,那么根据式(3)计算dA=(si+ri)1(ki si)mod n即可恢复出签名私钥 dA.相比于式(12)中的 i,式(13)中的 bi具有更短的位长,但相比于最初的 HNP-2H 实例(式(10)中的 bi,1和 bi,2,本方案将会损失约(12logn+1+22)(1+2)12(logn (1+2)12know的已知位长,也就是说在同等难度下,用本方案求解 HNP-2H 实例所需的已知位长大约为求解 HNP 实例所需的已知位长的两倍.4实验结果分析4.1实验环境设置本文的实验环境为:Intel(R)Xeon(R)CPU E5-2667 v4 3.2 GHz 处理器,64 GB 内存,Ubuntu20.04 操作系统,Sage v9.1 with fpylll v0.5.4 软件环境.832Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20234.2性能分析本小节分别根据 SM2 数字签名算法中随机数的最高、最低、中间 know比特已知三种情况进行了SM2 私钥恢复实验,实验结果如图1和图2所示.0204060801005560657075808590成功率(%)签名数量已知随机数最高 5 比特已知随机数最高 4 比特已知随机数最高 3 比特 0204060801005560657075808590成功率(%)签名数量已知随机数最低 5 比特已知随机数最低 4 比特已知随机数最低 3 比特(a)随机数最高部分比特已知时密钥恢复的成功率(b)随机数最低部分比特已知时密钥恢复的成功率 0204060801003540455055606570成功率(%)签名数量已知随机数中间 21 比特已知随机数最低 4 比特已知随机数最低 3 比特(c)随机数中间部分比特已知时密钥恢复的成功率图 1 数据集加密阶段所需计算和通信开销Figure 1 Computational and communication costs of dataset encryption stage 051015202530354045556065707580运行时间(s)签名数量已知随机数最高 5 比特已知随机数最低 5 比特已知随机数最高 4 比特已知随机数最低 4 比特 0.000.501.001.502.002.503540455055606570运行时间(s)签名数量已知随机数中间 21 比特已知随机数最低 4 比特已知随机数最低 3 比特(a)随机数最高/低部分比特已知时密钥恢复所需的时间(b)随机数中间部分比特已知时密钥恢复所需的时间图 2 随机数部分比特已知时密钥恢复所需的时间Figure 2 Time required of key recovery when part bits of random number are known当 SM2 数字签名算法中随机数的高位、低位、中间部分比特已知时,随着给定签名数量的增加,