要么改变世界,要么适应世界

RSA的常见攻击

2022-08-15 09:56:47
80
目录

本文参考自文章【从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

继续使用pythonGmpy2库可以很容易求逆元:

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

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

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,不同的指数e1e2,同时这两个指数互素,并且得到了对同一组明文加密后的密文c1c2,在不获取私钥的情况下也能将明文解来,原理如下:

设: $$ c_1=m^{e_1}\pmod{n} $$ 和 $$ c_2=m^{e_2}\pmod{n} $$ 由于e1e2互素,存在整数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 $$ 对上式子分别对pq取模,有: $$ 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} $$ 因为pq互素,二者最大公约数为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} $$ 下面我们来求m1m2.

由式子(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)
历史评论
开始评论