一种基于随机数未知的SM2签名算法安全性验证方法

摘要

本发明公开了一种基于随机数未知的SM2签名算法安全性验证方法。本方法为：1)采用SM2签名算法分别对N+1个消息M进行签名，并在每次SM2签名中注入错误，使每次签名时所用随机数k的相同设定比特部分的签名结果s出现相同的错误；2)以第一次签名的错误签名结果s的等式为参照，将其他N次签名中的错误签名结果s分别与其进行相减，得到一方程组，即格攻击模型；3)对该格攻击模型进行求解，恢复出每一次签名所用随机数k的所有比特，将其代入计算对应签名结果s的等式，得到一私钥dA，如果该私钥dA为正确私钥，则判断该SM2签名算法不安全。本发明能够更有效、全面分析SM2签名算法抵抗攻击的安全能力。

说明书

技术领域

本发明具体涉及一种基于随机数未知的SM2签名算法安全性验证方法，属于信息安全技 术领域。

背景技术

自从20世纪80年代，Miller和Koblitz将椭圆曲线引入密码学，以及Lenstra提出了利 用椭圆曲线进行因数分解算法以来，椭圆曲线在密码学中的作用越来越大。ECC是基于有限 域椭圆曲线离散对数问题(ECDLP)：在一个循环加法群中，G为生成元，且G的阶为n，已 知Q＝kG和G,求k的值，其中Q＝kG为有限域上的标量乘运算，具体为有限域上的代数运算。

若F为有限域，则至少含有两个元素，并存在一个加法+和一个乘法·运算，满足如下条 件：

1)(F，+)是一个交换群；

2)(F/{0}，·)是一个交换群；

3)满足结合律：(a·b)·c＝a·(b·c)加法和乘法满足分配律，即对任何 a,b,c∈R,a·(b+c)＝a·b+a·c,(b+c)·a＝a·b+a·c。

密码应用中最常用的有限域包括：素数域和特征为2的扩张域(二元扩域)，这里主要介 绍素数域。若p是素数，F＝{0,1,2,…,p-1}是关于modp的+和·构成的一个有限域，记为F_p， 称为素数域(Galois域)，F_p^*＝F_P/{0}是F_p由中所有非零元构成的乘法群，由于F_p^*是循环 群，所以在F_p中至少存在一个元素g，使得F_p中任一非零元都可以由g的一个方幂表示，称 g为F_p^*的生成元(或本原元)，即F_p^*＝＜g＞，阶为p-1。

若在素数域F_p(p是大于3的素数)上的椭圆曲线方程为：

y²＝x³+ax+bmodp,a、b∈F_p，且(4a³+27b²)modp≠0

则有限域F_p上椭圆曲线点集E(F_p)定义为：

E(F_p)＝{(x,y)|x,y∈F_p,y²＝x³+ax+bmodp}∪{O}，其中，O为无穷远点。

若点G∈E(F_p)，且G的阶n为素数，则由G生成的循环群 ＜G＞＝{O,G,2G,3G,…,(n-1)G}为E(F_p)的循环子群。椭圆曲线点集E(F_p)的元素数目用 #E(F_p)表示，称为椭圆曲线E(F_p)的阶。在ECC密码系统中，素数p、域F_p的椭圆曲线方 程、基点G及其阶n均为公开的域参数，任选私钥d∈[1,n-1]，则相应的公钥P＝dG。

椭圆曲线上定义的点与点加法运算使用了弦切线法则，则E(F_p)为加法交换群，无穷远 点O为单位元，P(x,y)+P(x,-y)＝O。对E(F_p)上两点P、Q之和P+Q，若P≠Q，连接P、 Q的直线交E于点R'，则R'关于x轴的对称点R即为P+Q之和，称为点加运算(A)。如图1 所示。

若P＝Q，做P点的切线交E于点R'，则R'关于x轴的对称点R即为则2P，称为点倍运 算(D)。如图2所示。

由椭圆曲线上的点加和点倍的几何意义，可以推断出E(Fp)在仿射坐标下运算法则，具 体如下：

点加:令P＝(x₁,y₁)∈E(F_p)，Q＝(x₂,y₂)∈E(F_p)，且P≠Q，则R(x₃,y₃)＝P+Q，其中， $x_3={\left(\frac{y_2-y_1}{x_2-x_1}\right)}^2-x_2-x_1,y_3=\left(\frac{y_2-y_1}{x_2-x_1}\right)(x_1-x_3)-y_1.$

点倍:令P＝(x₁,y₁)∈E(F_p)，P≠-P,则R(x₃,y₃)＝2P，其中，$y_3=\left(\frac{3x_1^2+a}{2y_1}\right)(x_1-x_3)-y_1.$

因此，对于ECC中的标量乘运算Q＝kG，实际上就是为k个相同点G之和，由多个点倍 和点加运算组合，kG是ECC中与密钥相关的基本运算，错误攻击和侧信道分析通常针对kG 进行。kG具有多种实现算法，其中最基本的是二进制算法。

ECC作为公钥算法，相对较传统的RSA公钥算法，在相同的安全性下，ECC算法密钥 长度短、计算数据量小、运算速度快、灵活性好，在没有协处理器的情况下，易于在芯片中 实现。另外，目前还没有找到求解ECDLP问题的有效算法，因此在算法安全性上要高于RSA 算法。ECC密码算法基于其自身特点，在许多应用中正逐渐取代了传统的RSA算法，广被使 用。

ECC数字签名算法是ECC公钥算法中应用中最广泛的算法之一，主要用于身份验证，由 一个签名者对数据产生数字签名，并由一个验证者验证签名的可靠性。每个签名者有一个公 钥和一个私钥，其中私钥用于产生签名，验证者用签名者的公钥验证签名。

SM2签名算法是一种ECC的数字签名算法，由国家密码管理局在2010年发布的标准， 共包括签名和验签两部分。

在签名过程(如图3所示)中，设待签名的消息为M，为了获取消息M的数字签名(r,s)， 签名者A的公私钥分别为P_A、d_A，算法中采用的杂凑算法同样由国家密码管理局发布的SM3 杂凑算法，则签名者A应实现以下运算步骤：

1.令其中，Z_A＝H_v(ENTL_A||ID_A),ID_A为签名者A的可辨别标识，ENTL_A为ID_A的比特长度，由两个字节表示，H_v(.)为SM3算法的哈希函数；

2.计算$e=H_v\left(\bar{M}\right);$

3.用随机数发生器产生随机数k∈[1,n-1]；

4.计算椭圆曲线点(x₁,y₁)＝kG；

5.计算r＝(e+x₁)modn，若r＝0或r+k＝n则返回3；

6.计算s＝(1+d_A)^-1(k-rd_A)modn，若s＝0则返回3；

7.输出消息M的签名(r,s)。

签名者将签名结果(r,s)和消息M发送给验签者B，已知签名者A的可辨别标识ID_A， 经过杂凑运算B可得Z_A＝H_v(ENTL_A||ID_A)，且采用A的公钥P_A进行验签(如图4所示)，具 体如下：

1.检验r∈[1,n-1]、s∈[1,n-1]是否成立，若不成立则验签失败；

2.令$\bar{M}=Z_A\left|\right|M;$

3.计算.$e=H_v\left(\bar{M}\right).;$

4.计算t＝(r+s)modn，若t＝0，验签失败；

5.计算椭圆曲线点(x₁,y₁)＝sG+tP_A；

6.计算R＝(e+x₁)modn，若R≠r则验签失败，否则验签成功。

鉴于SM2签名算法的应用重要性，有必要分析其安全性，一般通过攻击的方法检验其 是否安全。由上可知，由于私钥d_A仅在签名中被使用，因此，一般对SM2的攻击和防护都是 分析签名过程中私钥d_A的安全性。大多数对其他ECC签名算法的攻击方法均可用于SM2签 名算法，如对标量乘、ECDSA等的侧信道和错误攻击方法。目前，已有文献提出了对SM2签 名算法的错误攻击方法，主要包括弱曲线、对私钥的错误攻击和基于格的错误攻击。弱曲线 错误攻击是在标量乘kG运算中对基点G注入若干比特错误变成点G'，标量乘结果Q＝kG则 变为Q'＝kG'，G'不在原曲线上，而在一个新的弱曲线上，且G'在新曲线上的阶n'相对原来 的阶n要小得多，若n'的最大素因子q的计算是可行的，则通过解Q'＝kG'可获得k的 值，进而可推导出私钥d_A。对私钥的错误攻击是利用签名中rd_Amodn的模乘运算，对该运算 中的私钥注入错误，使其出现一个字节的错误，通过猜测确定私钥d_A的值。基于格的错误攻 击方法一般是在标量乘运算中注入错误，通过分析获取随机数k的部分比特，进行N次错误 签名，代入签名结果s＝(1+d_A)^-1(k-rd_A)modn中，可生成一个方程组，采用格攻击可确定 私钥的d_A值。

格是m维实数空间R^m的离散子群L，其元素β∈L为N个线性无关的向量 α_i∈L(i∈{0,1,…,N-1})的线性组合，a_i∈Z，Z为整数域， 则α₀,…,α_N-1为格L的一组基，B＝[α₀,…,α_N-1]^T为基矩阵。

格中存在两个著名的难解问题，分别为最小向量问题(SVP)和最近向量问题(CVP)。

SVP：已知格L的一组基B，在格中找到其最短非零向量v∈L，使得||v||＝min{||u|||u∈L}， 其中||·||为二范数，该问题可通过LLL算法确定v的近似解。

CVP:已知格L的一组基B、任意向量u∈R^m，在格中找到距u最近的向量v∈L，满足 ||v-u||＝min{||t-u|||t∈L}。CVP可由LLL算法和Babai算法在多项式时间内获得其近似解。

若对SM2签名算法实施格攻击，首先就需要转化成隐藏数问题(HNP)。若t_i∈Z_n是随 机均匀分布的，i∈{1,2，…，N}，u_i∈Z_n，0＜l＜log₂n，找到一个α∈Z_n，使其满足 |αt_i-u_i|_n≤n/2^l，其中|x|_n＝min{|x-bn||x∈Z_n,b∈Z}，上述即为HNP。实际上，上述不等式 等价于|αt_i-u_i+h_in|≤n/2^l，其中h_i是使得上述不等式成立的最小值。

HNP可转化成格中的CVP，构建(N+1)维格L，则基向量矩阵为

令目标向量u＝(u₁,u₂,…,u_N,0)、x＝(h₁,h₂,…,h_N,d_A)，则v＝xM为格L中向量，且 v＝(αt₁+nh₁,…,αt_N+nh_N,α/2^l)，由HNP不等式组可得为CVP问 题，求解CVP可得v，由v可确定α的值。

对于SM2签名算法，假若进行了N次签名运算，通过电磁、激光等错误诱导手段使得 每一次签名运算出现错误，从而分别获取到随机数k_i的最低l位比特值a_i，i∈{1,2，…，N}，并 得到错误的签名结果(r_i,s_i)，可构造相应的HNP。令k_i＝b_i2^l+a_i，其中b_i＜n/2^l为未知值。 将k_i代入签名中的第6步s＝(1+d_A)^-1(k-rd_A)modn可得下式：

2^-l(s_i+r_i)d_A-2^-l(a_i-s_i)＝b_i modn

令t_i＝2^-l(s_i+r_i)modn、u_i＝2^-l(a_i-s_i)modn，从而可得：

|t_id_A+h_in-u_i|＜n/2^l

其中，h_i是使得上述不等式成立的最小值。

上式即为HNP问题，将其转换成CVP，可求解得d_A的值。对于m位的签名算法，目前 已有文献证明若已知k的l比特，需m/l条错误的签名，即可得到正确的d_A。如对于256位 的SM2签名算法，若已知k的8比特，一般约需32条签名即可成功获取私钥，这在实际实验 中是非常可行的。

相比较弱曲线攻击和直接对私钥的错误攻击，基于格的错误攻击运算速度快，模型简单， 对SM2的安全性威胁相对较大，且防护相对较难，不同的错误模型对应的防护也需相应改变， 日益成为检验ECC签名算法安全性的主要攻击手段。目前对签名算法基于格的错误攻击方法 的错误注入方式主要为在标量乘运算中忽略某些点倍和点加运算，该错误注入方法很容易通 过算法级别的验签来防护，因此，亟需一些无法防护或防护困难的基于格攻击的错误攻击方 法来重新评估和定义算法的安全性。

发明内容

为了检验和评估SM2签名算法是否安全，本发明提出了一种基于随机数未知的SM2签 名算法安全性验证方法。该方法采用的错误注入方式进行攻击并没有使得算法中任何的中间 值错误，使得从防护角度很难检验到错误，在更强的防护条件下，并未知随机数的任何比特 值，仍可对算法进行格攻击获取私钥d_A。整个错误攻击方法(如图5所示)共包括三部分， 1)在SM2签名中注入错误使每次签名时随机数k的低/高位部分比特的签名结果s出现相同 的错误；2)以第1次签名中计算s的等式(即等式s＝(1+d_A)^-1(k-rd_A)modn)为参照，将 其他所有错误签名中计算s的等式分别与其进行相减，所得的方程组为HNP，即格攻击模型； 3)采用格攻击解HNP，可恢复随机数k的所有比特，代入计算s的等式，可得到正确的私钥 d_A；如果该私钥d_A为正确私钥，则判断该SM2签名算法不安全。具体如下：

1)在SM2签名中注入错误使每次签名时随机数k高/低位部分比特的签名结果s出现相 同的错误。在一个实现了SM2签名算法的智能卡芯片中，输入不同的消息M_i，共进行了N+1 (N≥log₂n/l，n为基点G的阶，G为SM2签名算法椭圆曲线的基点)次签名运算，每一 次签名运算芯片需生成256比特的随机数k_i(0≤i≤N)，若随机数发生器每次仅产生k_i的l比 特a_i，共需要256/l次才能生成完整的k_i，其中l一般为总线位宽，如8、16、32、64等。每 一次生成的随机数a_i需通过总线写入到芯片的存储区域，该写入操作在能量迹上峰值明显， 很容易能区分出来。因此，若在随机数写入存储区域的时刻t对芯片的CPU注入错误，则该 写入操作的指令未被执行，则在时刻t该存储区的值未被更新，即k_i的l比特a_i与上一次签名 中k_i-1的a_i-1相等(1≤i≤N)，a_i＝a_i-1。采用相同的光强，并在相同的位置，在每一消息M_i签 名所用随机数k的相同比特部分写入存储区时注入错误，可使得k_i中低/高l比特a_i一直保持 相同，即其中b_i为k_i中剩余的未知部分比特， 0＜b_i＜n/2^l，且a＝a₀＝a₁＝…＝a_N，并得到错误的签名结果(r_i,s_i)。

2-1)建立格攻击的模型。已知错误的签名结果(r_i,s_i)，且k_i中低l比特a_i一直保持相同， k_i＝b_i2^l+a(0≤i≤N)，则可得如下方程组：

$\left(\begin{array}{c}{s}_0={(1+d_A)}^{-1}(k_0-r_0{d}_A)\mathrm{mod}n\\ s_1={(1+d_A)}^{-1}(k_1-r_1{d}_A)\mathrm{mod}>\\ .\\ .\\ .\\ s_N={(1+d_A)}^{-1}(k_N-r_N{d}_A)\mathrm{mod}>\end{array}\right)$

将k_i代入上式，转化可得：

$\left(\begin{array}{c}(1+d_A)s_0=(a+b_0{2}^l-r_0{d}_A)\mathrm{mod}n\\ (1+d_A)s_1=(a+b_1{2}^l-r_1{d}_A)\mathrm{mod}n\\ .\\ .\\ .\\ (1+d_A)s_N=(a+b_N{2}^l-r_N{d}_A)\mathrm{mod}n\end{array}\right)$

令第1个方程为参考，将其他方程分别与其相减，约化可得：

$\left(\begin{array}{c}{2}^{-l}(s_1+r_1-s_0-r_0)d_A{-2}^{-l}(s_0-s_1)=b_1-b_0\mathrm{mod}n\\ 2^{-l}(s_2+r_2-s_0-r_0)d_A-2^{-l}(s_0-s_2)=b_2-b_0\mathrm{mod}n\\ .\\ .\\ .\\ 2^{-l}(s_N+r_N-s_0-r_0)d_A-2^{-l}(s_0-s_N)=b_N-b_0\mathrm{mod}n\end{array}\right)$

已知0＜b_i＜n/2^l，则|b₁-b₀|＜n/2^l，对于1≤i≤N，令Δt_i＝2^-l(s_i+r_i-s₀-r₀)mod n， Δu_i＝2^-l(s₀-s_i)mod n，h_i为使得不等式成立的最小整数，可得如下HNP的不等式方程组：

$\left(\begin{array}{c}|\Delta t_1{d}_A-\Delta u_1+n{h}_1|<n/2^l\\ |\Delta t_2{d}_A-\Delta u_2+n{h}_2|<n/2^l\\ .\\ .\\ .\\ |\Delta t_N{d}_A-\Delta u_N+n{h}_N|<n/2^l\end{array}\right)$

2-2)建立格攻击的模型。已知错误的签名结果(r_i,s_i)，且k_i中高l比特a_i一直保持相同， $k_i=a{2}^{{\log }_{2}n-l}+b_i(0\le i\le N),$则可得如下方程组：

$\left(\begin{array}{c}{s}_0={(1+d_A)}^{-1}(k_0-r_0{d}_A)\mathrm{mod}n\\ s_1={(1+d_A)}^{-1}(k_1-r_1{d}_A)\mathrm{mod}n\\ .\\ .\\ .\\ s_N={(1+d_A)}^{-1}(k_N-r_N{d}_A)\mathrm{mod}n\end{array}\right)$

将k_i代入上式，转化可得：

$\left(\begin{array}{c}(1+d_A)s_0=(a{2}^{{\log }_{2}n-l}+b_0-r_0{d}_A)\mathrm{mod}n\\ (1+d_A)s_1=(a{2}^{{\log }_{2}n-l}+b_1-r_1{d}_A)\mathrm{mod}n\\ .\\ .\\ .\\ (1+d_A)s_N=(a{2}^{{\log }_{2}n-l}+b_N-r_N{d}_A)\mathrm{mod}n\end{array}\right)$

令第1个方程为参考，将其他方程分别与其相减，约化可得：

$\left(\begin{array}{c}(s_1+r_1-s_0-r_0)d_A-(s_0-s_1)=b_1-b_0\mathrm{mod}n\\ (s_2+r_2-s_0-r_0)d_A-(s_0-s_2)=b_2-b_0\mathrm{mod}n\\ .\\ .\\ .\\ (s_N+r_N-s_0-r_0)d_A-(s_0-s_N)=b_N-b_0\mathrm{mod}n\end{array}\right)$

已知则|b₁-b₀|＜n/2^l，对于1≤i≤N，令Δt_i＝(s_i+r_i-s₀-r₀)modn， Δu_i＝(s₀-s_i)modn，h_i为使得不等式成立的最小整数，可得如下HNP的不等式方程组：

$\left(\begin{array}{c}|\Delta t_1{d}_A-\Delta u_1+n{h}_1|<n/2^l\\ |\Delta t_2{d}_A-\Delta u_2+n{h}_2|<n/2^l\\ .\\ .\\ .\\ |\Delta t_N{d}_A-\Delta u_N+n{h}_N|<n/2^l\end{array}\right)$

3)采用格攻击分析出私钥。将HNP转化成CVP，采用LLL和Babai算法求解最近向量 问题CVP，可可恢复随机数k的所有比特，代入计算s的等式，可得到一私钥d_A；根据该私 钥d_A判断该SM2签名算法是否安全，如果得到的私钥正确，则该SM2签名算法存在安全问 题。从算法安全的角度来看，SM2签名算法是无法抵抗该攻击。

和现有技术相比，本发明具有如下优势：

1.本发明创新地提出了一种基于格的错误攻击方法，使用本发明提出的新方法能够更有 效、全面分析SM2签名算法抵抗攻击的安全能力；

2.本发明与以前的错误方法不同，以前的错误攻击方法是错误影响的比特越少，复杂度 越小，但对实验而言是越难实现。而本发明则相反，错误影响的比特数越多，复杂度越小， 这非常有利于错误注入实验；

3.本发明是在标量运算前对随机数k注入的错误，在其后面的运算均无任何的错误中间 值或结果，因此可防护一般的抗错误攻击的校验。如标量运算点是否在椭圆曲线上，签名后 是否可通过验签等。

附图说明

图1是椭圆曲线上点加运算几何表示图；

图2是椭圆曲线上点倍运算几何表示图；

图3是SM2签名生成流程图；

图4是SM2验签流程图；

图5是本发明中对SM2签名算法的攻击流程图；

具体实施方式

下面结合附图和一个范例对本发明做进一步详细的说明，但不以任何方式限制本发明的 范围。在实施例中，通过以本发明的错误攻击方法对SM2签名算法进行格攻击的实验为例说 明本发明的有效性。

1)对随机数k注入错误使得低位部分比特出现相同的错误。在一个32位的SM2签名算法 芯片中，共进行了50次签名，当每次签名运算中产生随的机数写入内存时，对其 EPPROM(存储COS指令)区注入错误，可得k_i＝b_i2^l+a_i(0≤i≤49)中的低32位比特a_i全 部等于a，其中l＝32，如下表所示，所有随机数的低32比特都相同，均为a， a＝0xf5e333d0，并得到错误的签名结果(r_i,s_i)。

2)建立格攻击的模型。根据上述50条数据，共得到50个签名结果(r_i,s_i)，且k_i＝b_i2^l+a， 建立格攻击模型，将求d_A转化成HNP问题进行格攻击。

3)采用格攻击分析密钥。由于已知随机数的32比特，因次需至少选择log₂n/l+1＝9条 签名数据，实验中依次选择连续的10条数据进行格攻击，攻击结果如表2所示，共进 行了41次格攻击，每次均为10条，成功获取私钥的概率为100％，每次格攻击的平均时 间为48ms，因此，该攻击方法可成功分析出正确的私钥。

表1：随机数低32位比特值相同的SM2签名结果

表2：对SM2签名算法格攻击结果

以上详细说明的具体的实施方式仅仅是为了更好了理解本发明使用的，本发明不局限于 此，本领域一般技术人员可以根据本发明的公开内容，采用其他多种实施方式来实施本发明， 凡是采用本发明的设计结构和思路的，在不脱离权利要求范围的变换和替代，都属于本发明 的保护范围。