针对RSA的攻击方法

ligang041

0x00 选择密文攻击所谓“选择密文攻击”，就是密码分析者并不知道解密的密钥，但是给出任意的消息，密码分析者都可以将其加密，再解密。或者说，密码分析者能获得解密服务。

设攻击者为A，密文接受者为T，公钥对为(e, n)，私钥为d，T收到的密文为c，c对应的明文为m。
现在A想知道m = cd mod n，但是他不想分解n。于是T找了一个随机数r，r < n。他进行如下计算：
x = re mod n （对r用T的公钥加密，得到临时密文x）
y = (x * c) mod n （将临时密文x与密文c相乘）
t = r(-1) mod n
A利用了RSA加密和解密过程的特点，即：
如果x = re mod n，那么 r = xd mod n
现在A要做的是使T用d对t签名：u = td mod n。A需要获得u，然后计算
m = (t * u) mod n


xxxxxxxxxx1








1

m = (t * u) mod n











计算结果是这样推导的：
t * u mod n = [r(-1) * yd] mod n= [r(-1) * xd * cd] mod n= cd mod n= m


xxxxxxxxxx4








1

t * u mod n = [r(-1) * yd] mod n
2

= [r(-1) * xd * cd] mod n
3

= cd mod n
4

= m














0x01 过小的加密指数e0x01.00 e=1当e选择为1时，因为1 mod 任意数据等于1，所以e*d=1，从而推出d=1.
0x01.01 e=3当e=3，N非常大。所以可以不断地c+N然后开三次方，直接写代码爆破，不过python单线程有点长，跑了将近30分钟，可以改个多线程……

源码示例：
import binasciifrom gmpy2 import irootn = 0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929e = 3c = open('/root/tmp/flag.enc', 'rb').read()c = int('0x' + binascii.hexlify(c).decode(), 16)i = 0while 1:    res = iroot(c+i*n,3)    if(res[1] == True):        print res        break    print "i="+str(i)    i = i+1#i=118719487m = 440721643740967258786371951429849843897639673893942371730874939742481383302887786063966117819631425015196093856646526738786745933078032806737504580146717737115929461581126895844008044713461807791172016433647699394456368658396746134702627548155069403689581548233891848149612485605022294307233116137509171389596747894529765156771462793389236431942344003532140158865426896855377113878133478689191912682550117563858186print(binascii.unhexlify(hex(m)[2:]))# 结果# Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}


xxxxxxxxxx21








1

import binascii
2

from gmpy2 import iroot
3


4

n = 0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
5

e = 3
6

c = open('/root/tmp/flag.enc', 'rb').read()
7

c = int('0x' + binascii.hexlify(c).decode(), 16)
8


9

i = 0
10

while 1:
11

    res = iroot(c+i*n,3)
12

    if(res[1] == True):
13

        print res
14

        break
15

    print "i="+str(i)
16

    i = i+1
17

#i=118719487
18

m = 440721643740967258786371951429849843897639673893942371730874939742481383302887786063966117819631425015196093856646526738786745933078032806737504580146717737115929461581126895844008044713461807791172016433647699394456368658396746134702627548155069403689581548233891848149612485605022294307233116137509171389596747894529765156771462793389236431942344003532140158865426896855377113878133478689191912682550117563858186
19

print(binascii.unhexlify(hex(m)[2:]))
20

# 结果
21

# Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}












0x02 计时攻击法
0x03 公共模数攻击法参见RSA攻击之共模攻击
0x04 唯密文攻击0x04.00 密文和模数有公因子破解1. 获取最大公约数
如给定n和多个密文e1，e2，e3...等，可以检查n和每个密文是否存在最大公约数，最大公约数可以通过以下两种方法来进行计算

• 通过大数据计算器计算
  

缺点是不能批量计算，一次只能算一个。

• 通过yafu工具计算
  

yafu可以直接命令行实行函数，命令格式如下：
yafu-x64.exe "gcd(6,3)""


x






1

yafu-x64.exe "gcd(6,3)"











可以编写批处理文件实行完命令后再查看结果。

• 通过python脚本计算
  

可以通过以下python函数计算：
n =6e=[2,3,4,5]def isCoPrime(x,y):    ma = 0    mi = 0    ma=max(x,y)    mi=min(x,y)    if x==1 or y==1:        return True    if x % y == 0:        print x        print y        return False    return isCoPrime(mi,ma % mi)for i in range(len(e)):    print i,isCoPrime(n,e)


x






1

n =6
2

e=[2,3,4,5]
3


4

def isCoPrime(x,y):
5

    ma = 0
6

    mi = 0
7

    ma=max(x,y)
8

    mi=min(x,y)
9

    if x==1 or y==1:
10

        return True
11

    if x % y == 0:
12

        print x
13

        print y
14

        return False
15

    return isCoPrime(mi,ma % mi)
16


17

for i in range(len(e)):
18

    print i,isCoPrime(n,e)











然后在计算出的x和y用n进行验证是否能够整除，能整除则为最大公约数，另一个舍弃。

2. 获取p和q
上一步获取到的最大公约数即为p，通过q=n/p得到q。
0x05 已知N,E攻击D已知N,E的情况下有时也可以直接攻击D，参见RSA相关脚本中的脚本。可能需要N,E都是大值的时候才行，也不是100%会成功。