前言
近期在复习数论和密码学的题目，于是先从RSA开始，做一些题目推导与证明希望知其然，知其所以然，而不是一味的跟着套路走
RSA大众套路
这里简单的概述总结一下：
· 1.e较大：Wiener攻击
· 2.e较小：直接开方
· 3.低加密指数广播攻击：相同低指数的e和多个相同的消息m
· 4.Coppersmith定理攻击：只有部分高位的p或q
· 5.共模攻击：相同n，相同m
........话不多说，下面从非套路的题目开始
题干
例如题目
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
注意，其中dp的意思为：
dp≡d mod (p−1)dp≡d mod (p−1)
公式推导
现在我们可以知道的是
c≡me mod nm≡cd mod nϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)dp≡d mod (p−1)c≡me mod nm≡cd mod nϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)dp≡d mod (p−1)
由式5*e可以得到
dp∗e≡d∗e mod (p−1)dp∗e≡d∗e mod (p−1)
因此可以得到
d∗e=k∗(p−1)+dp∗ed∗e≡1 mod ϕ(n)d∗e=k∗(p−1)+dp∗ed∗e≡1 mod ϕ(n)
我们将式1带入式2可以得到
k∗(p−1)+dp∗e≡1 mod (p−1)∗(q−1)k∗(p−1)+dp∗e≡1 mod (p−1)∗(q−1)
故此可以得到
k2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗ek2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗e
变换一下
(p−1)∗[k2∗(q−1)−k1]+1=dp∗e(p−1)∗[k2∗(q−1)−k1]+1=dp∗e
因为
dp<p−1dp
可以得到
e>k2∗(q−1)−k1e>k2∗(q−1)−k1
我们假设
x=k2∗(q−1)−k1x=k2∗(q−1)−k1
可以得到x的范围为
(0,e)(0,e)
因此有
x∗(p−1)+1=dp∗ex∗(p−1)+1=dp∗e
那么我们可以遍历
x∈(0,e)x∈(0,e)
求出p-1，求的方法也很简单，遍历65537种可能，其中肯定有一个p可以被n整除那么求出p和q，即可利用
ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)
推出
d≡1∗e−1 mod ϕ(n)d≡1∗e−1 mod ϕ(n)
注：这里的-1为逆元，不是倒数的那个-1
payload
写下如下脚本：
import gmpy2import libnume = 65537n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1,65538):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)/i)+1)==0:
p=((dp*e-1)/i)+1
q=n/(((dp*e-1)/i)+1)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)%phi
print libnum.n2s(pow(c,d,n))
即可得到flag
flag{wow_leaking_dp_breaks_rsa?_98924743502}
反思
现在不难得出结论，RSA中，如果dp或者dq任意一个泄露都可以导致密文被破解因为上述的证明过程，没有用到任何特例情况。但是如果e较大的话，可能会比较困难一些，但是如果e过大，那就可以使用维纳攻击了XD
文章仅用于普及网络安全知识，提高小伙伴的安全意识的同时介绍常见漏洞的特征等，若读者因此做出危害网络安全的行为后果自负，与合天智汇以及原作者无关，特此声明。
本站以现代、古代情诗为主，情诗网创办于2013年，以原创爱情诗歌、经典情诗、现代情诗、古代情诗、英文情诗、情诗绝句为主并收集古诗、古诗词、诗歌大全、诗词名句的文学门户。方便您下次继续阅读；可以放在浏览器的收藏夹中（快捷键Ctrl+D）;或者看到喜欢或者有趣的诗词可以通过分享按钮给你的好友分享；情诗网是目前最全情诗大全网站之一。并欢迎广大诗歌爱好者阅览投稿！喜欢本站的话请大家把本站告诉给你朋友哦！地址是 www.qingshiwang.com ！