低加密指数攻击

攻击原理

小明文攻击。

当RSA加密时所用e较小时。可以通过RSA加密公式直接求出m，不需要分解n，求d。

情况一 当e=3时

因为RSA加密公式：

c = m**e (mod n)
所以若 m**e < n ，就有c = m**e ; 这里直接对c开方就可以得到m
若 m**e > n, 假设 m**e / n 的商为k 余数为c，则有m**e=kn+c；这样可以对k进行爆破，只要k满足原式就可以直接开e次方得到m。

关键代码：

i = 0
while 1:if iroot(c + i * n, 3)[1] == 1:  print(long_to_bytes(iroot(c + i * n, 3)[0]))breaki = i + 1

iroot(s,n)是对s开n次方。这里用if判断爆破 i 的大小，如果可以开方（即满足原式）那么就可以打印出来。可以对while做一定的限制，不然程序爆破不到 i 可能一直执行下去。

例题 [SWPUCTF 2021 新生赛]crypto5

题目也只给了 flag 和 n，flag应该是加密过后的c；所以先判断出这是RSA加密，接着判断是小明文攻击（低加密指数攻击）；小明文攻击的情况就三种，e = 3，e = 2，e = 1；从3开始考虑。运用上面的关键代码：

EXP：

from gmpy2 import * 
from Crypto.Util.number import *c = 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
n = 134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419i = 0
while 1:if iroot(c + i * n, 3)[1] == 1:print(long_to_bytes(iroot(c + i * n, 3)[0]))breaki = i + 1# b'NSSCTF{because_i_like}'

得到flag。这里打印了一下 i = 0；实际上是俩种情况中的第一种 m**e < n ，就有c = m**e 相等于直接对c开3。

情况二 当 e = 2时

直接对 c 开平方就好了。

from Crypto.Util.number import *
from gmpy2 import*    c=......              #C的值
m=isqrt(c)            #开平方根print(long_to_bytes(m))

情况三当 e = 1时

如果 e = 1；那么加密公式就会变成 c = m mod n

那么直接爆破 m = c + k * n

from libnum import*n=....
c=....
max_num = 7   #设置遍历上限for k in range(max_num):m = c + n*kprint(n2s(m))    
x_num = 7   #设置遍历上限for k in range(max_num):m = c + n*kprint(n2s(m))