前言
话不多说,然后前一期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
![](/images/780-200-2.jpg)