密码学竞赛SM2题目wp

                                                                     

背景

近期在学习国密系列算法，为巩固刚学习的SM2算法，在网上找到一个竞赛题目，让我们一起来干它！

                                                                     

题目

某信息系统基于 OpenSSL 实现了 SM2 算法，部署在客户端和服务器进行身份鉴别以及用户对数据摘要进行签名。密码分析人员采集到服务器日志，请恢复出用户签名私钥明文。

1. 开始对用户 1 进行身份鉴别

                                                                     

解答

前置知识：了解扩展欧几里得算法、素域、同余、逆元等相关概念

从日志1-7中获得

e1=0x875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D4877322

GM/T0003.2- 2012中描述的签名算法如下:

由A5步骤设两次签名的r、e、x1分别为 r1、e1、x1、r2、e2、x2，

得到等式 r1≡e1+x1(mod n)，r2≡e2+x2(mod n)

两式相减得r1-r2≡e1-e2+x1-x2(mod n)，移项得x1-x2≡(r1-r2)-(e1-e2)

将

e1=0x875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D4877322

代入x1-x2≡(r1-r2)-(e1-e2)得x1-x2=0，即x1=x2，x由A4步骤[k]G得来，两次x得值相等，说明两次使用的k值相等。

由A6步骤设两次签名的s分别为s1、s2，两次使用的k和dA(私钥)相同，均记为k、d，

得到等式 s1≡(1+d)-1·(k-r1·d) (mod n)，s2≡(1+d)-1·(k-r2·d) (mod n)

两式相减得s1-s2≡(1+d)-1·(k-r1·d)-(1+d)-1·(k-r2·d) (mod n)

解出d的表达式为d≡(r2-r1)(r2-r1-(s1-s2))-1-1 (mod n)

d≡(r2-r1)(r2-r1-(s1-s2))-1-1 (mod n)不等价于d≡(r2-r1)/(r2-r1-(s1-s2))-1 (mod n)，

设m=r2-r1-(s1-s2)，

m-1为m在模n的域中的逆元，使用扩展欧几里得算法，以下python代码摘自百度百科，

 def ext_euclid(a, b):     

稍加修改，我们仅需要返回值中的x,将等式d≡(r2-r1)(r2-r1-(s1-s2))-1-1 (mod n)写成python代码如下:

d=((r2-r1)*ext_euclid(r2-r1-(s1-s2),n)[0]-1) % n

r1、r2、s1、s2均已知，模数n未知。实际上sm2在用于签名时并未交换n,a,b,p等参数，但是这些参数双方保持一致才能进行签名和验签，所以n,a,b,p参数应该存在默认值，于是我在python的gmssl库的sm2算法中找到了这些默认值：

即

n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123

完整python代码：

e1=0x875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D4877322

解出私钥d为：

0x3b90f86f263049adbae06cbb1e2f8efef2142f2cc4979050a3d3109df7d83714

                                                                     

总结

此题的关键点在于由r1-r2=e1-e2 (mod n) 推导出两次的倍点x坐标相同，进而推导出两次使用的k值相同，再利用两次签名的r值相减，得到方程解出私钥d。由此看来，使用sm2签名时，必须保证k值的随机性，并且不能重复，一旦重复就可以被计算出私钥。