密码学竞赛SM2题目wp

admin
admin
admin
102523
文章
87
评论
2022年3月7日23:50:51评论346 views字数 3488阅读11分37秒阅读模式

                                                                     

背景


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

                                                                     

题目


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

1. 开始对用户 1 进行身份鉴别2. 服务端获取用户 1 发送的公钥值 P1：04E83E542C594496D1F75A7C07841F2DE773DB59CA8A277CC77BAB2FD1BA90B8585F7CC3C9863D129D4DDFACD1B529A31CCB81463AF8A8BB5AB480A3F8BB7DA7373. 产生挑战的杂凑值 e1：875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D48773224. 收到签名值(r1, s1)：1260185C3D7437E6A63F1E18FD810A314A5E27D67884A83F1283D72F1009F6990E9F423B578A8707C83C1A0A3982F52D0FF718C2B481966E4D839CD566EE72095. 验签成功！身份鉴别完成。6. 收到用户 1 发送的文件杂凑值 e2：8FB2B63B9CF9ED7842CC0E0A204B36A3ED5C45936B6148646A26915120F6C7D2和对应 签名值(r2, s2)：1ABAB698181BF3B65DA2C2C0AA1D53ECE519609BFAA9D75C18277CDB5C794B49EBB541CA42C5CCA5FA1324DDC32D3F352546FE4EECE8034E1D64A2848E2A93B97. 验签成功！文件与签名匹配。

                                                                     

解答


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

从日志1-7中获得

e1=0x875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D4877322r1=0x1260185C3D7437E6A63F1E18FD810A314A5E27D67884A83F1283D72F1009F699s1=0x0E9F423B578A8707C83C1A0A3982F52D0FF718C2B481966E4D839CD566EE7209e2=0x8FB2B63B9CF9ED7842CC0E0A204B36A3ED5C45936B6148646A26915120F6C7D2 r2=0x1ABAB698181BF3B65DA2C2C0AA1D53ECE519609BFAA9D75C18277CDB5C794B49 s2=0xEBB541CA42C5CCA5FA1324DDC32D3F352546FE4EECE8034E1D64A2848E2A93B9


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

密码学竞赛SM2题目wp


由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=0x875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D4877322r1=0x1260185C3D7437E6A63F1E18FD810A314A5E27D67884A83F1283D72F1009F699e2=0x8FB2B63B9CF9ED7842CC0E0A204B36A3ED5C45936B6148646A26915120F6C7D2 r2=0x1ABAB698181BF3B65DA2C2C0AA1D53ECE519609BFAA9D75C18277CDB5C794B49


代入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):         if b == 0:                 return 1, 0, a         else:                 x, y, q = ext_euclid(b, a % b)                x, y = y, (x - (a // b) * y)                 return x, y, q

稍加修改，我们仅需要返回值中的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算法中找到了这些默认值：

密码学竞赛SM2题目wp

即

n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123


 

完整python代码：

 

e1=0x875817FFC25231A88B68696273AEECE852A10CCDE93C19476482EBA4D4877322r1=0x1260185C3D7437E6A63F1E18FD810A314A5E27D67884A83F1283D72F1009F699s1=0x0E9F423B578A8707C83C1A0A3982F52D0FF718C2B481966E4D839CD566EE7209e2=0x8FB2B63B9CF9ED7842CC0E0A204B36A3ED5C45936B6148646A26915120F6C7D2 r2=0x1ABAB698181BF3B65DA2C2C0AA1D53ECE519609BFAA9D75C18277CDB5C794B49 s2=0xEBB541CA42C5CCA5FA1324DDC32D3F352546FE4EECE8034E1D64A2848E2A93B9n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123def ext_euclid(a, b):         if b == 0:                 return 1, 0, a         else:                 x, y, q = ext_euclid(b, a % b)                x, y = y, (x - (a // b) * y)                 return x, y, q
d=((r2-r1)*ext_euclid(r2-r1-(s1-s2),n)[0]-1) % nprint(hex(d))


解出私钥d为：

0x3b90f86f263049adbae06cbb1e2f8efef2142f2cc4979050a3d3109df7d83714


密码学竞赛SM2题目wp

 

                                                                     

总结


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



本文始发于微信公众号（InBug实验室）：密码学竞赛SM2题目wp

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年3月7日23:50:51
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   密码学竞赛SM2题目wphttps://cn-sec.com/archives/490756.html

发表评论

匿名网友 填写信息