RSA的常见攻击

本文参考自文章【从0到1：CTFer成长之路-第7章】

上文我们介绍了RSA算法原理，只要我们设置得当，我们有足够多的理由相信我们的RSA系统是安全的，但是粗心的我们，能否禁得住黑客的攻城掠池？下面介绍一些RSA的常见攻击。

1.因式分解

产生公钥和私钥的时候，我们用到了p，q，e，我们对外公布的是p和q的乘积以及e。如果我们选用的p和q太小，很容易就被很多工具将二者的乘积进行因式分解，从而获得了p和q。

有很多在线工具可以将大数进行因式分解，也有一些开源工具，这里以Yafu为例,对于阿珍的公钥<n,e>=<16422644908304291,65537>

D:\HackTools\yafu-1.34>yafu-x64.exe
factor(16422644908304291)


fac: factoring 16422644908304291
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.0058 seconds


***factors found***

P9 = 134235139
P9 = 122342369

ans = 1

继续使用python的Gmpy2库可以很容易求逆元：

import gmpy2
p, q, e = 134235139, 122342369, 65537
phi = (p - 1) * (q - 1)
# 求 e mod phi 的逆元
d = gmpy2.invert(e, phi)
print(d)
# 8237257961022977

此外，如果p和q的差距较小，根据下面的式子： $$ (\frac{p+q}{2} )^2-pq=(\frac{p-q}{2} )^2 $$ 直接暴力枚举p和q的差值，寻找p和q

2.低加密指数小明文攻击

如果阿强想要发送的数据很短，很简单，即明文m编码后，对应数学上，其数值很小，加上其公钥中的e很小，计算m^e的值并没有超过n，那么我们想要得到明文，直接将密文开e次方即可。

此外，如果密文c虽然大于n，但是并不是太大，由于： $$ c\equiv m^e \pmod{n} $$ 即存在整数k，使得： $$ c+kn=m^e $$ 我们可以直接暴力枚举k，然后将其开e次方，如果可以开得尽，则说明找到了明文m。

3.共模攻击

如果阿珍使用了相同的n，不同的指数e1，e2,同时这两个指数互素，并且得到了对同一组明文加密后的密文c1和c2，在不获取私钥的情况下也能将明文解来，原理如下：

设： $$ c_1=m^{e_1}\pmod{n} $$ 和 $$ c_2=m^{e_2}\pmod{n} $$ 由于e1和e2互素，存在整数x和y，使得： $$ xe_1+ye_2=1 $$ x和y可以通过扩展欧几里得算法求解出来。

进一步有： $$ c_{1}^{x}c_{2}^{y} \pmod{n}=m^{xe_1}m^{ye_2}\pmod{n}=m^1\pmod{n}=m $$ 即可获得明文。

4.广播攻击

对于相同的明文，如果阿强使用了相同的明文m，相同的指数e，但是不同的n1,n2,n3...nh(h>=e)，同时暴露了对应的每个密文，可以使用中国剩余定理解出明文m。

设： $$ \left{\begin{matrix} c_1=m^e\pmod{n_1} \ c_2=m^e\pmod{n_2} \ ... \ c_h=m^e\pmod{n_h} \end{matrix}\right. $$ 借助中国剩余定理,假设ni两两互素，令： $$ N=\prod_{i=1}^{h} n_i $$

$$ N_i=\frac{N}{n_i} $$

则上述同余方程组有唯一解： $$ X=m^e\equiv\sum_{i=1}^{h} c_iN_iy_i \pmod{N} $$ 其中： $$ N_iy_i\equiv1\pmod{n_i} $$

例如，假设张三想要发送消息给甲乙丙三个人，张三手上也有对应的三个公钥<205,3><187,3><667,3>，他想发送的消息m=10，加密后的密文分别是180，65，333

这三组公钥和密文在传输过程中被李四截取，他立马写下脚本进行窃取：

# 中国剩余定理的代码来自rosettacode Wiki
import gmpy2
from functools import reduce
def CRT(c,n):
    sum = 0
    # ni 的乘积,N=n1*n2*n3
    N = reduce(lambda x,y:x*y,n)
    # zip()将对象打包成元组
    for n_i, c_i in zip(n,c):
        # Ni=N/ni
        N_i = N // n_i
        # Ni y == 1 % ni 求逆元
        y = gmpy2.invert(N_i,n_i)
        sum += c_i * N_i * y
    return sum % N
n1, n2, n3 = 205, 187, 667
c1, c2, c3 = 180, 65, 333
e = 3
n = [n1, n2, n3]
c = [c1, c2, c3]

x = CRT(c,n)
# 将x开e次方
m = gmpy2.iroot(x,e)[0]
print(m)

5.低解密指数攻击

1989年，Michael J.Wiener发表了Cryptanalysis of Short RSA Secret Exponents文章，提出了一种针对解密指数d较低时对于RSA的攻击方法，该方法基于连分数,设： $$ ed=1+k \varphi(n) $$ 当q<p<2q时，若满足： $$ d<\frac{1}{3} n ^{\frac{1}{4}} $$ 则通过搜索连分数e/N的收敛，可以有效率地找到k/d，从而恢复正确的d。

目前，对于此种攻击已有完备的实现，在GitHub可以找到完整可用的攻击代码

6.dp泄露

dp = d % (p-1)并非字面上d和p相乘

如果已知dp,e,n,c，则可以解出明文m。证明如下,已知： $$ c \equiv m^e \pmod{n} \tag{1} $$

$$ m \equiv c^d \pmod{n} \tag{2} $$

$$ DP = d \bmod(p-1) \tag{3} $$

对式子（3）两边同乘e，有 $$ DP e\equiv de \pmod{p-1} $$ 则存在整数k1，使得： $$ de=k_1(p-1)+DPe \tag{4} $$ 而 $$ de\equiv1 \pmod{\varphi(n)} $$ 即 $$ de\equiv1\pmod{(p-1)(q-1)} $$ 故存在一个整数k2，使得： $$ de=k_2(p-1)(q-1)+1 $$ 带入到式子（4）并整理，得到 $$ DPe=(p-1)(k_2(q-1)-k_1) + 1 $$ 再令 $$ x=k_2(q-1) $$ 即 $$ DPe=(p-1)x+1 $$ 解得 $$ x=\frac{DPe}{p-1}-\frac{1}{p-1} $$ 根据定义，DP<(p-1)，因此1<x<e。

如果e不大，我们可以直接暴力枚举x,当其能够整除DPe-1时候，则p就可以找到了，找到以后进一步解得q，进一步得到d，从而恢复原文。

代码如下：

import gmpy2

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
# 在范围(1,e)之间进行遍历
for x in range(1, e):
    # 若存在 x ，使得 de*e - 1 能被 x 整除
    if (dp * e - 1) % x == 0:
        pp = ((dp * e - 1) // x) + 1
        # 确保 p 能够整除 n
        if n % pp == 0:
            p = pp
            q = n // (((dp * e - 1) // x) + 1)
            phi = (q - 1) * (p - 1)
            # 求模逆
            d = gmpy2.invert(e, phi)
            m = gmpy2.powmod(c, d, n)
            print(m)
            break

7. dp,dq泄露

dp = d % (p-1), dq = d % (q-1),并非字面上d和p相乘

如果已知dp,dq,p,q,c，则可以解出明文m。证明如下,已知 $$ c \equiv m^e \pmod{n} \tag{1} $$

$$ m \equiv c^d \pmod{n} \tag{2} $$

$$ DP = d \bmod(p-1) \tag{3} $$

$$ DQ = d \bmod(q-1) \tag{4} $$

由式子（2）可得： $$ m=c^d+kn=c^d+kpq $$ 对上式子分别对p和q取模,有： $$ m_1 \equiv c^d \pmod{p} \tag{5} $$

$$ m_2 \equiv c^d \pmod{q} \tag{6} $$

对式子（5），话句话说，有： $$ m_1 + kp = c^d \tag{7} $$ 即： $$ m_1+kp \equiv c^d \pmod{q} $$ 将上式子带入式子（6），有： $$ kp \equiv (m_2-m_1) \pmod{q} $$ 因为p和q互素，二者最大公约数为1,有： $$ k \equiv p'(m_2-m_1) \pmod{q} \tag{8} $$ p'是p关于q的逆元,即： $$ pp' \equiv1 \pmod{q} $$ 联立（7）和（8），有： $$ c^d=m_1+((p'(m_2-m_1) )\bmod{q} )p $$ 再带入式子（2），有： $$ m \equiv (m_1+((p'(m_2-m_1) )\bmod{q} )p )\pmod{n} \tag{9} $$ 下面我们来求m1和m2.

由式子（3），得： $$ d=DP+k(p-1) $$ 将上式子（5），有： $$ m_1 \equiv c^{DP+k(p-1)} \pmod{p} $$ 即： $$ m_1 \equiv c^{DP}c^{k(p-1)} \pmod{p} $$ 根据费马小定理，若p是素数,且gcd(c,p)=1，则c^(p-1)=1 mod p。

即 $$ c^{k(p-1)} \pmod{p} \equiv (c^{p-1}\pmod{p})^{k}\pmod{p}\equiv1 $$ 故： $$ m_1=c^{DP} \pmod{p} $$ 同理 $$ m_2=c^{DQ} \pmod{q} $$ 将这两个式子回代到式子（9）即可求出明文。

使用python脚本如下：

import gmpy2
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
n = p * q
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
I = gmpy2.invert(p,q)
m = (m1 + I * ((m2 - m1) % q) * p) % n
print(m)