RSA之拒绝套路(2)

crypto

字数统计: 688阅读时长: 3 min

 2018/08/25  Share

文章首发在合天智汇

前言

话不多说，接着前一期，继续探讨RSA的相关问题，上一期，我们讨论了，如果泄露了

1	(n,e,dp,c)

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

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

会带来什么严重影响？

题干

dp= 90494486973243104756298311175705002887155440121025946664275790548694955799661434870163629541771658812502682012435200659355928618529521731475360236486362525996535354732687624609637012830178545914960485330748345108757203508531117591067570383564779625954776907685968592668868046507450242047759226407026094726359
dq= 92386717102324384872139253931247976320472847834037799716676564640678692924258053130751618730959510913784801723023536527134208843358920592320351399005428347188639433875570867152865970587272904695272790831679276818402117343413503376057524788386479263579869430615501089905630519162146030369086836183772975252551
p= 121869669684596731118740111360803257498670698122183387353481580136405322481841982461820301261370579505460038281590785837096967719889404913176714663774999789266522508163678949469953184327222227297952119212490499582581953510522212981687122483764873187827531047946130999532741388680549345732675732040579796067001
q= 128363031923139297392077349407719417788135630403499671848196425800900870531452570499668481104884553795224784931947824885511134525485570129640119439950191944938407656926280993408854767711557863016197167505998324659906146937423415404059310560359693643987781862684489401368519777953281060013045590132161625607377
c= 4176193749773450562408160796325873473193702511560805285554329767573726211097194419198463203488792792756598428753745425419950423161673497255820731183746106463781291156892140581651301528184812357534808298071893380519977926677138246941946185699346532140641376461516107672722425971178865758049759985915001009787241295292157744353554548314911531918044654676691927347018033509499136103964942830581407087547565204232556314726045307279963709599952745342811947421707024572981812906869557834491207590418553244020621858083633564878305733114484857827620268881100166090837841224767358579366482347136224695333980041913268394994302

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

公式推导之万事俱备

还是先摆出已知条件

$c \equiv m^{e} \text{ } mod \text{ } n \\ m \equiv c^{d} \text{ } mod \text{ } n \\ \phi (n) = (p-1)*(q-1) \\ d*e \equiv 1 \text{ } mod \text{ } \phi (n) \\ dp \equiv d \text{ } mod \text{ } (p-1) \\ dq \equiv d \text{ } mod \text{ } (q-1)$

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

$c^{d}$

首先根据

$m \equiv c^{d} \text{ } mod \text{ } n$

因为

$gcd(p,q)=1 \\ n=p*q$

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

$\begin{cases} m_1 \equiv c^{d} \text{ } mod \text{ } p \\ m_2 \equiv c^{d} \text{ } mod \text{ } q \\ \end{cases}$

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

$m \equiv c^{d} \text{ } mod \text{ } n$

可以得到式子

$m = c^{d}+k*n$

因为

$n = p*q$

所以可以得到

$m = c^{d}+p*q*k$

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

$m_1 \equiv c^{d} \text{ } mod \text{ } q \\ m_2 \equiv c^{d} \text{ } mod \text{ } p$

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

$c^{d}=kp+m1$

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

$m_2 \equiv (kp+m1) \text{ } mod \text{ } q$

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

$(m2-m1) \equiv kp \text{ } mod \text{ } q$

这里因为

$gcd(p,q)=1$

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

$(m2-m1)*p^{-1} \equiv k \text{ } mod \text{ } q$

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

$k \equiv (m2-m1)*p^{-1} \text{ } mod \text{ } q \\ c^{d}=kp+m1 \\ m \equiv c^{d} \text{ } mod \text{ } n$

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

$c^{d}=((m2-m1)*p^{-1} \text{ } mod \text{ } q)p+m1 \\ m \equiv c^{d} \text{ } mod \text{ } n$

最后可以有

$m \equiv (((m2-m1)*p^{-1} \text{ } mod \text{ } q)p+m1) \text{ } mod \text{ } n$

公式推导之只欠东风

现在只剩最后一步了，即

$m_1 \equiv c^{d} \text{ } mod \text{ } q \\ m_2 \equiv c^{d} \text{ } mod \text{ } p$

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

$\begin{cases} d \equiv dp \text{ } mod \text{ } (p-1) \\ d \equiv dq \text{ } mod \text{ } (q-1) \end{cases}$

那么分别带入，有

$\begin{cases} m_1 \equiv c^{dq \text{ } mod \text{ } (q-1)} \text{ } mod \text{ } q \\ m_2 \equiv c^{dp \text{ } mod \text{ } (p-1)} \text{ } mod \text{ } p \end{cases}$

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

$a^{(p-1)} \equiv 1 \text{ } mod \text{ } p \\$

所以如果我们有等式

$d = dp+k*(p-1)$

我们直接带入，有

$m_2 \equiv c^{dp+k*(p-1)} \text{ } mod \text{ } p$

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

$m_2 \equiv c^{dp}*c^{k*(p-1)} \text{ } mod \text{ } p$

这里的

$c^{k*(p-1)} \equiv 1 \text{ } mod \text{ } p$

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

$m_2 \equiv c^{dp} \text{ } mod \text{ } p$

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

$m_1 \equiv c^{dq} \text{ } mod \text{ } q$

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

$\begin{cases} m_1 \equiv c^{dq} \text{ } mod \text{ } q \\ m_2 \equiv c^{dp} \text{ } mod \text{ } p \\ m \equiv (((m2-m1)*p^{-1} \text{ } mod \text{ } q)p+m1) \text{ } mod \text{ } n \end{cases}$

payload

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

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= 39019112110614280252241495036646034807151213716557526376274345944263453299622818575225245299195523420254672088668617876062998490653404750105272510633841394184860866942704080992475543547501372565259180366123356119418623253283732615682878021900318153700726522250094020806743598752556541454865233668070931534349
p= 114461439704891616590422134857421869878753559940962522699708885701308630438427731936479777010552391068812199529467348873013239528376604282404207321401876195560830474695517139918118078685078197948576662138382523308600480733574419071424466292785993331731881271557573094521160051353184489095799816579282742140953
q= 173407999660109485520889209734134041910836523881475540116955713891631837403964097088089751678165465931150331234455699896350201315926126639981461748491240790317968076899655657331112140939100897570439934688992874242416328330344836429844042122956843979375681077968897817612357468397424082494911472122421034561779
c= 13156088528156801357013836665002509320288819562687150049688430847488062217199478847649128772442129783962344653461951822569890099822350753026372449754819799394899656016487248023042927376134885257136511477879900672582593964626335310995748816166750941755394630154620318544805488209700324391789948495807096701620546557726907853315159542234979480907794659188799145765761654813882682456135251746607111274015475601810166327843158879230660349983897375641623569327757258851636029354634714133778666281729500815659100876558161468140039778498553902396380237570072543395294246750182054410091138654202418836971487515663618000662737
decrypt(dp,dq,p,q,c)

最后我们愉快的得到了flag

1	flag{dp_dq_is_very_dangerous!_47325684736584}

反思

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

点击赞赏二维码，您的支持将鼓励我继续创作！

Next Post

2018 安恒8月赛 Writeup
Previous Post

Crypto之击破多层加密

CATALOG

1. 前言
2. 题干
3. 公式推导之万事俱备
4. 公式推导之只欠东风
5. payload
6. 反思

