RSA常见攻击方法

1
2
3
4
5
6
7
8
9
10
#判断是否质数
>>> Crypto.Util.number.isPrime(20) 
>>> primefac.isprime(113)
>>> gmpy2.is_prime(13)
#分解质数
factors = primefac.primefac(n)
list = map(str, factors)
#The first 10000 primes
from Crypto.Util import number
for p in number.sieve_base:

明文m相关攻击

m长度很短,直接爆破生成表

分段加密m,每段长度为4字节,遍历所有4字节字符串,预先进行加密生成表

1
2
3
4
5
6
from Crypto.Util import number
dec = {}
for i in range(0x10000): #hexencoded = binascii.hexlify(data)明文是16进制格式的4字节
    x = b'%.4x' % i
    v = number.bytes_to_long(x)
    dec[pow(v, e, n)] = x

模数N相关攻击

1
2
>>> math.log(1024, 2) #计算N的比特位数
10.0

直接分解N

  • RSATool2v17:N比特位数小于256
  • msieve:SIQS and GNFS algorithms
  • yafu:p,q差值太大或者太小,适用Fermat或Pollard rho法分解
  • factordb网站:N比特位数768或更高,在线网站会存储一些已分解成功的N
  • primefac:p+1/p-1光滑

任意两个N不互素

通过欧几里德算法求N1和N2的最大公约数gmpy2.gcd(n1, n2),即求得N的任意一个因子p

相同N,不同私钥e加密相同明文m

通过扩展欧几里德算法求出满足se1+te2=1 mod N的s和t,再结合对应的密文c1和c2求得明文m

1
2
gcd, s, t = gmpy2.gcdext(e1, e2)
m = gmpy2.powmod(c1, s, N) * gmpy2.powmod(c2, t, N) % N

公钥指数e相关攻击

e很小且明文m比较小

以e=3为例

m较小的情况下,从小到大枚举k,依次开e次方根,直到开出整数为止。

e与模数N的一个或多个素数因子的欧拉函数不互素

N可以直接分解,但由于e与一个或多个素数因子的欧拉函数不互素,而e * d - k * phi(N) = 1有解的充要条件是gcd(e, phi(N)) = 1,因此无法直接通过扩展欧几里德算法求模反元素d。

e=2,Rabin加密解密算法
e=prime * 2^k,Rsabin(hitcon-2015)
1
2
3
4
5
6
7
partially_decoded_ct = [ct]
for i in range(5):
    new_partially_decoded_ct = []
    for ct_p in partially_decoded_ct:
        new_ct_p = rabin.decrypt(ct_p)
        new_partially_decoded_ct.extend(list(new_ct_p))
    partially_decoded_ct = set(new_partially_decoded_ct)
素数因子较小,RSA?(0ctf-2016)

通过以下工具计算:x^e=c mod p可能的根x,即为明文m对素数因子p的余数,依次求出m对所有素数因子的余数,再利用中国剩余定理CRT即可求得明文m。

  • wolframalpha

  • Pari/GP

    1
    2
    gp > sqrtnall(x,n)={my(V,r,z,r2);r=sqrtn(x,n,&z);if(!z,error("Impossible case in sqrtn"));if(type(x)=="t_INTMOD"||type(x)=="t_PADIC",r2 = r*z;n=1;while(r2!=r,r2*=z;n++));V=vector(n);V[1]=r;for(i=2,n,V[i]=V[i-1]*z);V}
    gp > Vec(liftall(sqrtnall(Mod(2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524, 32581479300404876772405716877547), 3)))
    
两组e与各自的N的欧拉函数均不互素,AzureRSA(高校运维赛eis-2018)

已知:两组N不互素,通过gcd可以求得共同素数因子p,进而求得q1,q2。由于:gmpy2.gcd(e1, (p-1))=14 gmpy2.gcd(e1, (q1-1)) = 2 gmpy2.gcd(e2, (p-1)) = 14 gmpy2.gcd(e2, (q2-1)) = 2,因此,可以利用q1,q2,求得:m^2对于q1,q2的模,进而通过中国剩余定理CRT求得m^2对于q1*q2的模,由于所求的值刚好可以开平方,否则需要通过Rabin解密法求明文m:

1
2
3
4
5
6
7
8
dq1 = gmpy2.invert(e1/2, q1 - 1)
dq2 = gmpy2.invert(e2/2, q2 - 1)
cq1 = gmpy2.powmod(c1, dq1, q1)
cq2 = gmpy2.powmod(c2, dq2, q2)
m2 = libnum.solve_crt([cq1, cq2], [q1, q2])
m = gmpy2.iroot(m2, 2)
if m[1]: # if not True, need to use Rabin to cal m
  print libnum.n2s(m[0])

e=3,模数N相同,且明文存在线性关系m1=a*m2+b mod N

Related Message Attack

e不为3时,利用Coppersmith’s short-pad attack。

e很大,Wiener_attack

rsa-wiener-attack,通过n,e即可以求得d

e很大,Boneh and Durfee attack

优先使用wiener-attack,如果无法解出时,尝试Boneh and Durfee attack

相同e(一般较小),e组不同模数N加密相同明文m(m小于所有N),低加密指数广播攻击(中国剩余定理CRT)

以e=3为例,3组不同的模数N1,N2,N3互素(如果不互素,可以通过欧几里德算法求最大公约数直接得到p),则有:

Coppersmith相关攻击

Coppersmith定理指出在一个e阶的mod n多项式f(x)中,如果有一个根小于n^1/e,就可以运用一个O(log n)的算法求出这些根。

明文padding长度太短,Coppersmith’s short-pad attack

当padding长度小于:floor(nBitSize/(e^2))

相同e,e组不同模数N加密明文m的线性关系,Hastad’s Broadcast Attack with Linear Padding

cArray[i] = pow(aArray[i]*msg + bArray[i],e,nArray[i])

当aArray[i]=1,bArray[i]=0时,即为低加密指数广播攻击。

至少已知明文m的ceil(nBitSize*(1-1.0/e))位,LLL attack

如:N.bit_length()=2048,e=3,则至少需要已知:ceil(2048*(1-1.0/3))=1366位明文

pol = ((message + ZmodN((pow(2,unknownEndBitIndex)))*x)^e) - c

当unknownEndBitIndex=0时,即为明文最后字符未知的情况。

已知密钥d低位d0位数大于nBitSize/4,Partial Key Exposure Attack

已知密钥d低位d0位数大于nBitSize/2,Partial Key Recovery Attack

其他条件相关攻击

已知p,q其他等式,如:p+q或p-q的值,联立p*q=N解方程

Twin-Primes(TokyoWesterns-2016)

已知p+q=s,根据一元二次方程:a=1,b=-s,c=N,可解得:

1
p = long((-b + gmpy2.isqrt(b ** 2 - 4*a*c))/2L)

已知dp = d mod (p-1)

已知:N,e,dp,cequation(0ctf-2016)

因此,遍历(0,e)之间的x,必找到能整除dp*e-1的x,求得对应的(p-1),若该p能被N整除,即为所求的p

1
2
3
4
5
for x in range(1,e):
  if (dp*e-1)%x == 0:
    p = (dp*e-1)/x + 1
    if n%p==0: #if n is unknown, could check gmpy2.is_prime(p) instead
      # found p
已知:dp,dq,q,p,cRSA_CRT leaksChop-Suey(noxCTF-2018)

多素数因子(Multi-prime RSA)

The-Best-RSA(Hack-the-vote-2016)

模数N=3^1545 * 5^1650 * … * 251^1493,如果使用常规RSA解法:先求N的欧拉函数,再求e对N的欧拉函数模逆得到d,由于N极大,得到的d也会极大,直接求pow(c,d,N)会耗时很长。因此需要用上一节的RSA_CRT方式进行加速。

注:不能只是求明文对3,5,…251的余数,否则通过中国剩余定理求得的值只是明文m对于3*5*…*251的余数。

已知d其他等式,以2为明文,构造p的倍数,使之与N共模

原理:根据费马小定理

Rsababy(CodeGate-2018)

已知:g=d*(p-0xdeadbeef),设const=0xdeadbeef,构造如下等式:

shenyue2(网鼎杯2018第四场)

已知:k=(p-r)*d,构造如下等式:

next_prime

原理:根据素数定理,素数的平均间隔为:x/π(x)≈lnx,因此常见的下一个素数比当前素数大一点,一般不会超过1500。

LHY(Pwnhub-2018)

已知:p = gmpy.next_prime(x ** 3 + y ** 3),q = gmpy.next_prime(x ** 2 * y + y ** 2 * x),x=2 * y

因此:p=next_prime(9 * y ** 3) = 9 * y *3 + a,q=next_prime(6 * y ** 3) = 6 * y *3 + b,根据素数定理,a,b很小,因此n ≈ 54 * y ** 6。可以通过以下方法求得p:

  • 得知y的上界,而y的下界也不会离上界太远,可以利用二分查找法来寻找满足条件的y,p和q
  • 由于a,b很小,y如果改变,y**3改变的值将远大于a,b的影响,因此可以认为y=iroot(y/54, 6),进而爆破a(从1到1500)求得:p=next_prime(9 * y ** 3)=(9 * y **3 + a) %n = 0,比直接求next_prime速度快些
  • p=9 * y **3 + a,由于a,b很小,可以认为p高位大部分bit已知,通过Coppersmith攻击可恢复不确定的低位
已知nextprime(p)*nexprime(q)的值(nextrsa,强网杯2018)

npnq=nextprime(p) * nextprime(q) = (p + x) * (q + y),联立p*q=N,得:y * p ** 2 + (n + x * y - npnq) * p + x * n = 0,爆破x和y(从1到1500)解一元二次方程。

任意给定密文,系统返回明文,选择密文攻击

Decryptor(noxCTF-2018)

任意给定密文,系统返回明文的最低位(奇偶性),LSB Oracle Attack

LSBOracle(sharif-ctf-2016)

任意给定密文,系统可能返回计算错误明文(数字签名:从c签名得到m,m验证签名得到c)

RSA-CRT计算错误
私钥指数d错误

给定公钥和部分缺失私钥,最优非对称加密填充 (OAEP)

God Like RSA(JarvisOJ)
  • given a candidate for (p mod 16**(t - 1)), generate all possible candidates for (p mod 16**t) (check against mask for prime1)
  • calculate q = n * invmod(p, 16**t) (and check against mask for prime2)
  • calculate d = invmod(e, 16**t) * (1 + k * (N - p - q + 1)) (and check against mask for private exponent)
  • calculate d_p = invmod(e, 16**t) * (1 + k_p * (p - 1)) (and check against mask for exponent1)
  • calculate d_q = invmod(e, 16**t) * (1 + k_q * (q - 1)) (and check against mask for exponent2)
  • if any of checks failed - check next candidate

附:RSA private key pem文件格式

1
2
3
4
5
6
7
8
9
10
11
12
RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

对pem文件中内容先base64解码,然后以hex方式输出:

1
str.decode('base64').encode('hex')

得到格式为:

1
2
3
4
5
6
7
8
9
10
3082 025d	表示后接0x025d=605byte
02   01		后接0x1byte的version(00双素数,01多素数)
0281 81		后接0x81byte的n
02   03		后接0x3byte的e(默认为-f4:e=0x10001,-3:e=3)
0281 80		后接0x80byte的d
02   41		后接0x41byte的p
02   41		后接0x41byte的q
02   40		后接0x40byte的d mod (p-1)
02   40		后接0x40byte的d mod (q-1)
02   41		后接0x41byte的(inverse of q) mod p