RSA dp，dq泄露

以例题为导向，深入剖析RSA中dp和dq泄露会造成的对RSA的攻击。

ephemeral-fever

4550人浏览 · 2022-01-11 20:31:49

ephemeral-fever · 2022-01-11 20:31:49 发布

例题

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

攻击条件

已知dp，dq，p，q，c

其中：

dp=d%(p-1)

dq=d%(q-1)

原理

正常来说，解密用到是这个公式： $\equiv c^{d} \pmod{n}$ 。但是由于 $n = pq$ ，所以刚刚那个式子可以化为 $\left\{\begin{matrix}m_{1} \equiv c^{d} \pmod{p} & (1) \\ m_{2} \equiv c^{d} \pmod{q} & (2) \end{matrix}\right.$ 。证明过程如下：

对于公式 $\equiv c^{d} \pmod{n}$ 我们可以这样理解： $m$ 除以 $n$ 得到某个商 $k$ 和余数 $c^{d}$ 。
于是可以转化成等式： $m=c^{d} +kn$ 。而 $n = p * q$ ，所以可以进一步写成 $m=c^{d} +kn=c^{d} +kpq$ ，其中 $k$ 为假设的商。
然后两边分别同时对 $p$ , $q$ 取余， $k pq$ 那一项就被消去了，就得到 $\left\{\begin{matrix}m_{1} \equiv c^{d} \pmod{p} \\ m_{2} \equiv c^{d} \pmod{q} \end{matrix}\right.$ 。

由于 $\pmod {p-1}$ , $\pmod {q-1}$ ，再结合欧拉定理（或费马小定理），上面的同余式组可以进一步化为 $\left\{\begin{matrix}m_{1} \equiv c^{dp} \pmod{p} & (3) \\ m_{2} \equiv c^{dq} \pmod{q} & (4) \end{matrix}\right.$ .

由式(1)可得 $m_{1}+kp=c^{d}$ （这里的 $k$ 和上面证明中的 $k$ 没有关系），不妨将其记为(5)式，然后代入(2)式可得 $\equiv (m_{2}-m_{1}) \pmod{q}$ 。

又因为 $g c d (p, q) = 1$ ，即 $p$ , $q$ 互素，所以可以在刚刚得到式子两边同时乘上 $p$ 的逆元，得到 $\equiv p'(m_{2}-m_{1}) \pmod{q}$ ，其中 $p^{'}$ 是 $p$ 关于 $q$ 的逆元。

将这个 $k$ 的表达式代入(5)式，得到 $c^{d}=m_{1} +\left [ p'(m_{2}-m_{1}) \pmod {q}\right ]*p$ 。其中的 $m_{1}$ 和 $m_{2}$ 可以通过上面的式(3)(4)计算得到。最后就可以得到 $c^{d}$ 的值从而解出明文 $m$ 。

脚本

from gmpy2 import *
from Crypto.Util.number import *

# dp+dq+p+q+c => m

def rsa(dp,dq,p,q,c):
    m1=pow(c,dp,p)
    m2=pow(c,dq,q)
    p_q=invert(p,q)
    m=m1+p_q*((m2-m1)%q)*p
    print(long_to_bytes(m))



if __name__ == "__main__":
    p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
    q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
    dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
    dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
    c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

    rsa(dp,dq,p,q,c)