RSA之拒绝套路（2）

前言

话不多说，然后前一期RSA拒绝套路(1)继续讨论RSA的相关问题。上一期我们讨论过，如果泄露了

(n,e,dp,c)

它会导致密文被解密的危害。这一次，我们讨论如果泄露

(dp,dq,q,p,c)

会带来什么严重影响？

题干

dp= 90494486973243104756298311175705002887155440121025946664275790548694955799661434870163629541771658812502682012435200659355928618529521731475360236486362525996535354732687624609637012830178545914960485330748345108757203508531117591067570383564779625954776907685968592668868046507450242047759226407026094726359

dq= 92386717102324384872139253931247976320472847834037799716676564640678692924258053130751618730959510913784801723023536527134208843358920592320351399005428347188639433875570867152865970587272904695272790831679276818402117343413503376057524788386479263579869430615501089905630519162146030369086836183772975252551

p= 121869669684596731118740111360803257498670698122183387353481580136405322481841982461820301261370579505460038281590785837096967719889404913176714663774999789266522508163678949469953184327222227297952119212490499582581953510522212981687122483764873187827531047946130999532741388680549345732675732040579796067001

q= 128363031923139297392077349407719417788135630403499671848196425800900870531452570499668481104884553795224784931947824885511134525485570129640119439950191944938407656926280993408854767711557863016197167505998324659906146937423415404059310560359693643987781862684489401368519777953281060013045590132161625607377

c= 4176193749773450562408160796325873473193702511560805285554329767573726211097194419198463203488792792756598428753745425419950423161673497255820731183746106463781291156892140581651301528184812357534808298071893380519977926677138246941946185699346532140641376461516107672722425971178865758049759985915001009787241295292157744353554548314911531918044654676691927347018033509499136103964942830581407087547565204232556314726045307279963709599952745342811947421707024572981812906869557834491207590418553244020621858083633564878305733114484857827620268881100166090837841224767358579366482347136224695333980041913268394994302

这个话题很清楚。我们没有公钥和私钥，但我们必须从密文中推出明文。让我们尝试公式推导

公式推导的一切都准备好了

或者先摆出已知条件

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≡cdmodnm≡cdmodn

因为

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

利用中国的剩余定理，我们可以得到它

{m1≡cdmodpm2≡cdmodq{m1≡cdmodpm2≡cdmodq

这里一定有很多人不明白。让我简单证明一下

m≡cdmodnm≡cdmodn

你可以得到公式

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

因为

n=p∗qn=p∗q

所以可以得到

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

上述公式，同时取余q和p，可分别获得

m1≡cdmodqm2≡cdmodpm1≡cdmodqm2≡cdmodp

为什么kpq不见了，因为这是p或q的倍数~然后我们可以继续从公式1中得到它

cd=kp+m1cd=kp+m1

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

m2≡(kp+m1)modqm2≡(kp+m1)modq

等式两侧同时减去m1，可获得

(m2−m1)≡kpmodq(m2−m1)≡kpmodq

这里因为

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

因此，可以要求p的逆元，得到

(m2−m1)∗p−1≡kmodq(m2−m1)∗p−1≡kmodq

所以这里有以下两个公式

k≡(m2−m1)∗p−1modqcd=kp+m1m≡cdmodnk≡(m2−m1)∗p−1modqcd=kp+m1m≡cdmodn

我们合并了上下两个公式，得到了它们

cd=((m2−m1)∗p−1modq)p+m1m≡cdmodncd=((m2−m1)∗p−1modq)p+m1m≡cdmodn

最后可以有

m≡(((m2−m1)∗p−1modq)p+m1)modnm≡(((m2−m1)∗p−1modq)p+m1)modn

公式推导只欠东风

现在只剩下最后一步了，那就是

m1≡cdmodqm2≡cdmodpm1≡cdmodqm2≡cdmodp

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

{d≡dpmod(p−1)d≡dqmod(q−1){d≡dpmod(p−1)d≡dqmod(q−1)

然后分别带入，有

{m1≡cdqmod(q−1)modqm2≡cdpmod(p−1)modp{m1≡cdqmod(q−1)modqm2≡cdpmod(p−1)modp

这里肯定有人不明白为什么可以直接带进去。让我们再次证明，这里使用费马小定理是假的如果p是质数，gcd(a,p)=1，

a(p−1)≡1modpa(p−1)≡1modp

所以如果我们有等式的话

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

我们直接带进去，是的

m2≡cdp+k∗(p−1)modpm2≡cdp+k∗(p−1)modp

为了这里的指数，我们打开它

m2≡cdp∗ck∗(p−1)modpm2≡cdp∗ck∗(p−1)modp

这里的

ck∗(p−1)≡1modpck∗(p−1)≡1modp

注：由于p是大素数，显然与c互素，因此可以直接获得

m2≡cdpmodpm2≡cdpmodp

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

m1≡cdqmodqm1≡cdqmodq

因此，我们现在有了所有的条件，下面总结一下

⎧⎩⎨m1≡cdqmodqm2≡cdpmodpm≡(((m2−m1)∗p−1modq)p+m1)modn{m1≡cdqmodqm2≡cdpmodpm≡(((m2−m1)∗p−1modq)p+m1)modn

payload

一切都准备好了，那我们就开始写脚本吧~脚本如下

defdecrypt(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

printlibnum.n2s(m)

dp=193473626362736263626362736263626263626362636263626362676263626362636263626362626267626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262626262627262626272626262627262727262727272727272727272627272727272727272727272727272727272727272727262727272727272727272727272727272727272727272727272727272727272727272627272727272727272727272727272727272727272727272726272727272727272727272727272727272727272727272727272727272727272727262627272727272727272727272727272727272727272727272727272727272(dp,dq,p,q,c)

最后，我们愉快地得到了flag

flag{dp_dq_is_very_dangerous!_47325684736584}

反思

如果dp，这个问题告诉我们，dq,p,q泄漏，即使e，d是保密的，也可以解密，这种方法也存在于实践中，用于RSA加速解密，推导，感觉复习了很多东西XD