话不多说，接着前一期RSA之拒绝套路（1） ，继续探讨RSA的相关问题，上一期，我们讨论了，如果泄露了

(n,e,dp,c)

可以导致密文被解密的危害。这一次，我们探讨如果泄露

(dp,dq,q,p,c)

会带来什么严重影响？

dp=

9049448697324310475629831117570500288715544012102594666427579054869495579966143487016362954177165881250268201243520065935

5

9286185295217314753602364863625259965353547326876246096370128301785459149604853307483451087572035085311175910675703835647

796

25954776907685968592668868046507450242047759226407026094726359

dq=

9238671710232438487213925393124797632047284783403779971667656464067869292425805313075161873095951091378480172302353652713

4208843358920592320351399005428347188639433875570867152865970587272904695272790831679276818402117343413503376057524788386

4792

63579869430615501089905630519162146030369086836183772975252551

p=

1218696696845967311187401113608032574986706981221833873534815801364053224818419824618203012613705795054600382815907858370

9696771988940491317671466377499978926652250816367894946995318432722222729795211921249049958258195351052221298168712248376

4873

187827531047946130999532741388680549345732675732040579796067001

q=

1283630319231392973920773494077194177881356304034996718481964258009008705314525704996684811048845537952247849319478248855

1113452548557012964011943995019194493840765692628099340885476771155786301619716750599832465990614693742341540405931056035

9693643987781862684489401368519777953281060013045590132161625607377

c=

4176193749773450562408160796325873473193702511560805285554329767573726211097194419198463203488792792756598428753745425419

9504231616734972558207311837461064637812911568921405816513015281848123575348082980718933805199779266771382469419461856993

4653214064137646151610767272242597117886575804975998591500100978724129529215774435355454831491153191804465467669192734701

8033509499136103964942830581407087547565204232556314726045307279963709599952745342811947421707024572981812906869557834491

2075904185532440206218580836335648783057331144848578276202688811001660908378412247673585793664823471362246953339800419132

68394994302

题目很清晰，我们没有公钥和私钥，却要从密文推出明文，我们下面来尝试公式推导

还是先摆出已知条件

c≡me mod nm≡cd mod nϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)dp≡d mod (p−1)dq≡d mod (q−1)c≡me mod nm≡cd mod nϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)

dp≡d mod (p−1)dq≡d mod (q−1)

我们的目标很简单，如何从这些式子得到答案

cdcd

首先根据

m≡cd mod nm≡cd mod n

因为

gcd(p,q)=1n=p∗qgcd(p,q)=1n=p∗q

利用中国剩余定理,我们可以得到

{m1≡cd mod pm2≡cd mod q{m1≡cd mod pm2≡cd mod q

这里肯定有很多人不理解，我简单证明一下

m≡cd mod nm≡cd mod n

可以得到式子

m=cd+k∗nm=cd+k∗n

因为

n=p∗qn=p∗q

所以可以得到

m=cd+p∗q∗km=cd+p∗q∗k

上述式子，同时取余q和p，可以分别得到

m1≡cd mod qm2≡cd mod pm1≡cd mod qm2≡cd mod p

为什么kpq没了,因为这是p或者q的倍数呀~然后我们继续由式1可以得到

cd=kp+m1cd=kp+m1

我们把这个带入式2可以得到

m2≡(kp+m1) mod qm2≡(kp+m1) mod q

等式两边同时减去m1,可以得到

(m2−m1)≡kp mod q(m2−m1)≡kp mod q

这里因为

gcd(p,q)=1gcd(p,q)=1

所以可以求p的逆元，得到

(m2−m1)∗p−1≡k mod q(m2−m1)∗p−1≡k mod q

所以这里得到如下两个式子

k≡(m2−m1)∗p−1 mod qcd=kp+m1m≡cd mod nk≡(m2−m1)∗p−1 mod qcd=kp+m1m≡cd mod n

我们上下两个式子合并，得到

cd=((m2−m1)∗p−1 mod q)p+m1m≡cd mod ncd=((m2−m1)∗p−1 mod q)p+m1m≡cd mod n

最后可以有

m≡(((m2−m1)∗p−1 mod q)p+m1) mod nm≡(((m2−m1)∗p−1 mod q)p+m1) mod n

现在只剩最后一步了，即

m1≡cd mod qm2≡cd mod pm1≡cd mod qm2≡cd mod p

这里的m1和m2怎么求？这时候我们有

{d≡dp mod (p−1)d≡dq mod (q−1){d≡dp mod (p−1)d≡dq mod (q−1)

那么分别带入，有

{m1≡cdq mod (q−1) mod qm2≡cdp mod (p−1) mod p{m1≡cdq mod (q−1) mod qm2≡cdp mod (p−1) mod p

这里肯定有人又不理解为什么可以直接带入了，我们再证明一下，这里用到了费马小定理即假如p是质数，且gcd(a,p)=1，

a(p−1)≡1 mod pa(p−1)≡1 mod p

所以如果我们有等式

d=dp+k∗(p−1)d=dp+k∗(p−1)

我们直接带入，有

m2≡cdp+k∗(p−1) mod pm2≡cdp+k∗(p−1) mod p

这里的指数，我们拆开，为

m2≡cdp∗ck∗(p−1) mod pm2≡cdp∗ck∗(p−1) mod p

这里的

ck∗(p−1)≡1 mod pck∗(p−1)≡1 mod p

注：因为p是大素数，显然和c互素所以可以直接得到

m2≡cdp mod pm2≡cdp mod p

那么m1根据对称性也可以同理得到

m1≡cdq mod qm1≡cdq mod q

故此，我们现在拥有了所有条件，下面归纳一下为

⎧⎩⎨m1≡cdq mod qm2≡cdp mod pm≡(((m2−m1)∗p−1 mod q)p+m1) mod n{m1≡cdq mod qm2≡cdp mod pm≡(((m2−m1)∗p−1 mod q)p+m1) mod n

万事俱备，那我们开始写脚本吧~脚本如下

def decrypt(dp,dq,p,q,c):

    InvQ = gmpy2.invert(q, p)

    mp = pow(c, dp, p)

    mq = pow(c, dq, q)

    m = (((mp-mq)*InvQ) % p)*q+mq

    print libnum.n2s(m)

dp=24417628139330679432551095868116968814142396193102639509841676574931690513464588523684381397207121003439385360929299071710433231196678202942915347185802024747158497456267595000613289619481116892073493417896024118597833611923086327107489774162727006791982668721110819684552525393969199138125692085053266311867

dq=390191121106142802522414950366460348071512137165575263762743459442634532996228185752252452991955234202546720886686178760629984906534047501052725106338413941848608669427040809924755435475013725652591803661233561194186232532837326156828780219003181537007265222500940208067435987525565414548652336680709315343

49p=11446143970489161659042213485742186987875355994096252269970888570130863043842773193647977701055239106881219952946734887301329528376604282404207321401876195560830474695517139918118078685078197948576662138382523308600480733574419071424466292785993331731881271557573094521160051353184489095799816579282742140

953q=7340799966010948552088920973413404191083652388147554011695571389163183740396409708808975167816546593115033123445569989635020131592612663998146174849124079031796807689965565733111214093910089757043993468899287424241632833034483642984404212295684397937568107796889781761235746839742408249491147212242103456

1779c=13156088528156801357013836665002509320288819562687150049688430847488062217199478847649128772442129783962344653461951822569890099822350753026372449754819799394899656016487248023042927376134885257136511477879900672582593964626335310995748816166750941755394630154620318544805488209700324391789948495807096701620546557726907853315159542234979480907794659188799145765761654813882682456135251746607111274015475601810166327843158879230660349983897375641623569327757258851636029354634714133778666281729500815659100876558161468140039778498553902396380237570072543395294246750182054410091138654202418836971487515663618000662737decrypt(dp,dq,p,q,c)

最后我们愉快的得到了flag

flag{dp_dq_is_very_dangerous!_47325684736584}

这一题告诉我们，如果dp,dq,p,q泄露，就算e,d都保密，也可以被解密而这种方法也存在于实际中，是用于RSA的加快解密的，推导一遍，感觉又复习了不少东西XD