1
文章首发在合天智汇
前言
话不多说,接着前一期,继续探讨RSA的相关问题,上一期,我们讨论了,如果泄露了1
(n,e,dp,c)
可以导致密文被解密的危害。
这一次,我们探讨如果泄露1
(dp,dq,q,p,c)
会带来什么严重影响?
题干
1 | dp= 90494486973243104756298311175705002887155440121025946664275790548694955799661434870163629541771658812502682012435200659355928618529521731475360236486362525996535354732687624609637012830178545914960485330748345108757203508531117591067570383564779625954776907685968592668868046507450242047759226407026094726359 |
题目很清晰,我们没有公钥和私钥,却要从密文推出明文,我们下面来尝试公式推导
公式推导之万事俱备
还是先摆出已知条件
我们的目标很简单,如何从这些式子得到答案
首先根据
因为
利用中国剩余定理,我们可以得到
这里肯定有很多人不理解,我简单证明一下
可以得到式子
因为
所以可以得到
上述式子,同时取余q和p,可以分别得到
为什么kpq
没了,因为这是p或者q的倍数呀~
然后我们继续
由式1可以得到
我们把这个带入式2
可以得到
等式两边同时减去m1,可以得到
这里因为
所以可以求p的逆元,得到
所以这里得到如下两个式子
我们上下两个式子合并,得到
最后可以有
公式推导之只欠东风
现在只剩最后一步了,即
这里的m1和m2怎么求?
这时候我们有
那么分别带入,有
这里肯定有人又不理解为什么可以直接带入了,我们再证明一下,这里用到了费马小定理
即假如p是质数,且gcd(a,p)=1
,
所以如果我们有等式
我们直接带入,有
这里的指数,我们拆开,为
这里的
注:因为p是大素数,显然和c互素
所以可以直接得到
那么m1根据对称性也可以同理得到
故此,我们现在拥有了所有条件,下面归纳一下为
payload
万事俱备,那我们开始写脚本吧~
脚本如下1
2
3
4
5
6
7
8
9
10
11
12
13def 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= 39019112110614280252241495036646034807151213716557526376274345944263453299622818575225245299195523420254672088668617876062998490653404750105272510633841394184860866942704080992475543547501372565259180366123356119418623253283732615682878021900318153700726522250094020806743598752556541454865233668070931534349
p= 114461439704891616590422134857421869878753559940962522699708885701308630438427731936479777010552391068812199529467348873013239528376604282404207321401876195560830474695517139918118078685078197948576662138382523308600480733574419071424466292785993331731881271557573094521160051353184489095799816579282742140953
q= 173407999660109485520889209734134041910836523881475540116955713891631837403964097088089751678165465931150331234455699896350201315926126639981461748491240790317968076899655657331112140939100897570439934688992874242416328330344836429844042122956843979375681077968897817612357468397424082494911472122421034561779
c= 13156088528156801357013836665002509320288819562687150049688430847488062217199478847649128772442129783962344653461951822569890099822350753026372449754819799394899656016487248023042927376134885257136511477879900672582593964626335310995748816166750941755394630154620318544805488209700324391789948495807096701620546557726907853315159542234979480907794659188799145765761654813882682456135251746607111274015475601810166327843158879230660349983897375641623569327757258851636029354634714133778666281729500815659100876558161468140039778498553902396380237570072543395294246750182054410091138654202418836971487515663618000662737
decrypt(dp,dq,p,q,c)
最后我们愉快的得到了flag1
flag{dp_dq_is_very_dangerous!_47325684736584}
反思
这一题告诉我们,如果dp,dq,p,q泄露,就算e,d都保密,也可以被解密
而这种方法也存在于实际中,是用于RSA的加快解密的,专业称为RSA_CRT leaks
今天推导一遍,感觉又复习了不少东西XD