dp,dq泄露

例题

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

攻击条件

已知dp，dq，p，q，c

其中：

dp=d%(p-1)

dq=d%(q-1)

原理

加密： $c \equiv m^{e} \pmod{n} $

解密：$m \equiv c^{d} \pmod{n} $

dp=d%(p-1)

dq=d%(q-1)

整理上述条件后有如下式子：

$c \equiv m^{e} \pmod{n} $ ①
$m \equiv c^{d} \pmod{n} $ ②
$dp \equiv d \pmod{(p-1)} $ ③
$dq \equiv d \pmod{(q-1)} $ ④

由②式可以衍生出两个式子：

m1=c^d%p
m2=c^d%q

证明如下:

$m=c^{d}+kn=c^{d}+kpq$

分别同时对q,p取余得：
$m1=(c^{d})%p$⑤
$m2=(c^{d})%q$⑥

由式⑤可得$m1+kp=c^{d}$，代入⑥中可得：
kp≡(m2-m1) (mod q)

又因为gcd(p,q)=1

所以，k≡p’(m2-m1)(mod q)

其中，p’是p关于q的逆元

回代得 c^d=m1+(p’(m2-m1)%q )*p

由⑤及欧几里得定理得：m1=(c^dp)%p
同理由⑥得：m2=(c^dq)%q

最后就可以得到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)