CTF-CRYPTO-RSA #共模攻击

2019-04-13 14:41发布

巅峰极客——flag{4b0b4c8a-82f3-4d80-902b-8e7a5706f8fe}

描述

有两个公钥,两个密文

分析

  1. 用RsaCtfTool.py分析公钥信息,发现n相同,e不同
root@ben-PC:/mnt/d/security/misc-tool/RSA/rsatools# python RsaCtfTool.py --pkey pubkey1.pem --v "n" is:17362520124149736059291605717839814089431261833972408175766504894876091272021197374480215582589878198406028065354454242540322618614670160317701698407729515781811530180885334265851364490357884909336085410775168953942120359215038925025305363480538685487988827339463890539279008285241711326041868183805848503077373967082910932422798165242481154593794712639251157856102009630894845049984346776659339380886766804814959778048440996937820138560802077375885700500737699904011032451007341777160586467318264288370080315519305800247682611802774996999330812534723806925426052547128371180683265963525581842037399869323246530085399 ************************************************************ "e" is:2333 ************************************************************ Try weak key attack Try Wiener's attack root@ben-PC:/mnt/d/security/misc-tool/RSA/rsatools# python RsaCtfTool.py --pkey pubkey2.pem --v "n" is:17362520124149736059291605717839814089431261833972408175766504894876091272021197374480215582589878198406028065354454242540322618614670160317701698407729515781811530180885334265851364490357884909336085410775168953942120359215038925025305363480538685487988827339463890539279008285241711326041868183805848503077373967082910932422798165242481154593794712639251157856102009630894845049984346776659339380886766804814959778048440996937820138560802077375885700500737699904011032451007341777160586467318264288370080315519305800247682611802774996999330812534723806925426052547128371180683265963525581842037399869323246530085399 ************************************************************ "e" is:23333 ************************************************************ Try weak key attack Try Wiener's attack 密文内容如下: [root RsaCtfTool]$ cat flag1.enc XSKBJ2biS6brC5iGwU0GZitHdVM3HXAiwtFnVf2+HTaUqFahxL+BxBi2QDcx7gLxcjEWCMwFP6DS92nMAU4r0gPWSEUIoY57sgNZsjDIDAukiYeLNDUgYz+1P+nF4fk7gwPdozrIvAXGDBvMBjuviqsC8vmVP3I6eLLkt9C46HFt0SBw5ycfAjVoDF2r7/4B1UDs4G0dpIDUCk4khezzgqspn6tqtwOGB27vrKegoL/FlwmutFYIuRKKCBKx3yc/qfWXZ84Oo8nPqgaxgDlxWeLtGM9ZouwFKnagmjbnH+58Pescw4XYafXKqFjQz3XrK/uUESE8jIEIPeL1+8yUpw== [root RsaCtfTool]$ cat flag2.enc EruzwVAXSVLC3rldjcsx6HO0UUICdR9xxgr9eWNhIW0T8l2O3yT/LlFLK2+YU0HB97xr5HaiZesk4T6IuJ9+iOzB8YSkWMfYvOSDKn7Jng/1Q3wQuoldm+UurmZkiEs9kFi+EhsCNAbVAnLzLXLwzYm3emamueDqru4Doo/lSMz8p0+jqz24HscJN9shU85WX4JngW92REHHV8rPHaisCdxeAs+uPyTNzO4IbwDaJvw3ZR/Lo4m1K2Qw8PbYnOcgVr9CWR7mVyxofoWk6qWpQf3d0fX6wbbPcQkXxnnqLWy5S3PZcNQa1wkfRTJJO03QmNVsOivXGb3GzmeZbxmVhQ== [root RsaCtfTool]$
  1. 对于同一明文使用同样的N不同的E分别进行加密,满足共模攻击条件
    解密代码如下:
#!/usr/bin/env python # -*- coding: utf-8 -*- import sys,gmpy,base64 def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m def pad_even(x):#重要!凑齐2位,将0x1 变成 0x01 return ('', '0')[len(x)%2] + x def CipherB2n(c):#将base64编码后的密文转成数字 c2 = base64.b64decode(c) temp = '' for i in c2: temp += pad_even(str(hex(ord(i)))[2:]) temp = eval('0x'+temp) return (temp) def CipherN2b(m):#将数字转换成ascii hex_m=hex(m)[2:] if hex_m[-1] == 'L' : hex_m=hex_m[:-1] return hex_m.decode('hex') if __name__ == '__main__': sys.setrecursionlimit(1000000) e1 = 2333 #根据分解结果 e2 = 23333 #根据分解结果 s = egcd(e1, e2) s1 = s[1] s2 = s[2] c1 = 'XSKBJ2biS6brC5iGwU0GZitHdVM3HXAiwtFnVf2+HTaUqFahxL+BxBi2QDcx7gLxcjEWCMwFP6DS92nMAU4r0gPWSEUIoY57sgNZsjDIDAukiYeLNDUgYz+1P+nF4fk7gwPdozrIvAXGDBvMBjuviqsC8vmVP3I6eLLkt9C46HFt0SBw5ycfAjVoDF2r7/4B1UDs4G0dpIDUCk4khezzgqspn6tqtwOGB27vrKegoL/FlwmutFYIuRKKCBKx3yc/qfWXZ84Oo8nPqgaxgDlxWeLtGM9ZouwFKnagmjbnH+58Pescw4XYafXKqFjQz3XrK/uUESE8jIEIPeL1+8yUpw==' c2 ='EruzwVAXSVLC3rldjcsx6HO0UUICdR9xxgr9eWNhIW0T8l2O3yT/LlFLK2+YU0HB97xr5HaiZesk4T6IuJ9+iOzB8YSkWMfYvOSDKn7Jng/1Q3wQuoldm+UurmZkiEs9kFi+EhsCNAbVAnLzLXLwzYm3emamueDqru4Doo/lSMz8p0+jqz24HscJN9shU85WX4JngW92REHHV8rPHaisCdxeAs+uPyTNzO4IbwDaJvw3ZR/Lo4m1K2Qw8PbYnOcgVr9CWR7mVyxofoWk6qWpQf3d0fX6wbbPcQkXxnnqLWy5S3PZcNQa1wkfRTJJO03QmNVsOivXGb3GzmeZbxmVhQ==' c1 = CipherB2n(c1) c2 = CipherB2n(c2) #print hex(c1) n = 17362520124149736059291605717839814089431261833972408175766504894876091272021197374480215582589878198406028065354454242540322618614670160317701698407729515781811530180885334265851364490357884909336085410775168953942120359215038925025305363480538685487988827339463890539279008285241711326041868183805848503077373967082910932422798165242481154593794712639251157856102009630894845049984346776659339380886766804814959778048440996937820138560802077375885700500737699904011032451007341777160586467318264288370080315519305800247682611802774996999330812534723806925426052547128371180683265963525581842037399869323246530085399 #共n if s1<0: s1 = - s1 c1 = modinv(c1, n) elif s2<0: s2 = - s2 c2 = modinv(c2, n) m=(pow(c1,s1,n)*pow(c2,s2,n)) % n print m print CipherN2b(m) 7087928-197f7f52fa419b05.png 运行结果
flag{4b0b4c8a-82f3-4d80-902b-8e7a5706f8fe}

总结

串了一下rsa的明文和密文处理方式。计算过程中明文和密文都作为一个大数字,于是有:
  1. 明文是字符串。
    1.1. 将字符串转hex编码(py3里只能逐字,py2里可以直接转),拼上0x头和L尾,成为大数字。
    hex_m.decode('hex')
    1.2. 将字符串分成每行一个字,ord(i)。(解密时chr(i)再拼接)
  2. 算出密文是大数字。
    2.1. 转成16进制,去掉0x和L后变成一串16进制。此时可能出现:
    2.1.1 将十六进制直接转存为文件。(解密时提取十六进制值)
    2.1.2 将十六进制进行base64编码,变为可见字符。(解密时进行base64解码,由于二位一组,需注意对0x1这种补成0x01)
    def pad_even(x): return ('', '0')[len(x)%2] + x
    for i in c2:temp += pad_even(str(hex(ord(i)))[2:])
    2.2. 直接是10进制数字,无需处理
    m = chr(pow(int(i),d,n))