RSA相关题目解题方法与python脚本总结（网上的，做了解）

RSA作为一种非常经典的非对称公开密钥加密体制，属于是CTF密码学题目中的常客。对刚接触密码学的新手来说，一上来看到各种几百上千位的数字难免感到头大，但实际上了解了RSA的原理和常见解题技巧后也没有那么复杂，常规的RSA题目我觉得算是密码学中比较好拿分的部分了。下面就来介绍一下RSA相关算法原理和各种各样的解题思路。

以下文章内容不会涉及到很多数学相关知识或算法具体原理，仅以最直白简略的语言来阐述解基本题目的方法思路，要想进一步加深对RSA密码体制的理解还请自行翻阅相关资料。

RSA算法概述
RSA是一种非对称加密体制，所谓非对称就是加密钥和解密钥不一样，要解决加解密相关问题，我们首先要弄清楚RSA加密解密流程中用到了哪些东西：

明文 m：就是待加密的文本啦，一般也就是我们的flag。

密文 C：加密完成后的密文，一般题目会给你，我们要做的就是根据密文解密出明文。

公钥 e（加密钥）：用来加密的密钥，是一个整数，是公开的。

两个大素数 p,q：RSA加密的关键部分，一般不会告诉你。我们选取两个大素数并计算它们的乘积，得到n=p*q。后面会用p,q,n来加密解密。由于p,q非常大，想要对n进行因式分解得到p，q非常困难，这也确保了RSA的安全性。

私钥 d（解密钥）：用来解密，一般不会告诉你，d满足e*d mod (p-1)(q-1)=1，所以我们只要知道e和p,q就可以把d算出来。

加密过程：

解密过程：

以上就是一个常规RSA算法的组成部分。通过上面的内容我们可以知道要想解密一段密文，我们需要c,d,n三个值。其中c我们是知道的，而n和d都可以通过p,q,e算出来，e我们一般也是知道的，也就是说常规的rsa题目我们的解题思路就是想想怎样把p和q求出来。并以此进行解密。

思路一、分解n得到p,q
适用情况：n已知且可因式分解

既然n = p*q，那么最常规的想法就是把n因式分解得到p,q，上面说n很难分解，但对于一些不太大的n，我们可以借助工具去分解它。下面介绍两种常规因式分解方法：

第一种：在线因式分解网站，例如factordb.com，我们可以利用在线网站快速分解出p,q

第二种：yafu大数分解工具，windows下载地址：yafu download | SourceForge.net使用相关命令分解n:

1
2
3

yafu-x64 factor(n)                               //常规分解n

yafu-x64 "factor(@)" -batchfile 1.txt   //把n复制到txt文件中再分解，用于n过长的情况

例题：BUUCTF：[WUSTCTF2020]babyrsa

附件给出了c,n,e：

n不太大，可以对其进行因式分解得到p,q。以yafu为例：

得到p，q后按解密方法算出明文即可，python脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes
 
 
q = 189239861511125143212536989589123569301
p = 386123125371923651191219869811293586459
 
e = 65537
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
# n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
n = q*p
# print(n)
d = gmpy2.invert(e, (p - 1) * (q - 1))
print("d=",d)
m = pow(c, d, n)
print(m)
print(long_to_bytes(m))

运行即可得到flag，这也是最常规的解密RSA的脚本结构。

思路二、低加密指数攻击（e很小）

适用情况：n很大但是e很小，一般e=3

n很大时我们就不能因式分解了，当然还有其他思路，例如当e很小时，比如e=3，有 $c=m^e+kn$ ，我们可以对k进行爆破，直到 $c-kn$ 可以开根，借此得到m。

例题：BUUCTF DangrousRSA

题目的n很大，但e仅仅是3，此时我们就可以进行低加密指数攻击，python脚本如下：

import gmpy2
from Crypto.Util.number import *
 
def de(c, e, n):
    k = 0
    while True:
        m = c + n*k
        result, flag = gmpy2.iroot(m, e)
        if True == flag:
            return result
        k += 1
e= 3
n= 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c= 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
 
m=de(c,e,n)
print(m)
print(long_to_bytes(m))

思路三、低指数加密广播攻击（e很小;多组n,c）

适用情况：很多组不同的n和c，但用的是同一个e且很小。

此时我们可以使用中国剩余定理来求出 $m^{e}$ ，什么是中国剩余定理自己去了解，这里只讲怎么用python解题，见例题：

例题：BUUCTF RSA4

题目给了很多组n和c

当n很大时我们就可以考虑e=3的低指数情况，把n和c放到数组里，像n=[n1,n2,n3]，c=[c1,c2,c3].然后最方便的是调用sympy库里的中国剩余定理，也就是crt(c,n)方法直接可以求出m的e次，然后开方得到m就行了。其中sympy也是第三方库，可以pip或者pycharm里导入的时候顺手装上去就行了。

这道题还有一点要注意的是给出的n和c是五进制，注意先转换成10进制。python解题脚本如下：

import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
 
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)
 
N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)
 
N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)
 
e = 3
n = [N1,N2,N3]
c = [c1,c2,c3]
resultant, mod = crt(n, c)
value, is_perfect = gmpy2.iroot(resultant, e)
print(long_to_bytes(value))

思路三、公因数攻击（多组n,c）
适用情况：很多组n和c

和上面的广播攻击类似，题目会给你很多组n和c。我们知道n=p*q，而p、q是两个大素数。所以说当有很多组n的时候，很有可能出现两个n之间存在公因数。而这个公因数就是p和q其中的一个，当然知道其中一个另一个也就知道了，我们就可以求出d进而根据对应密文求出m。

例题：BUUCTF RSA5
题目中e = 65537，然后给了多达20组的n和c

此时我们就可以尝试公因数攻击，对所有n进行两两对比看看有没有公因数，如果发现公因数就可以顺势解出明文，python脚本如下

import  gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
 
n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320
 
#...此处省略20组n和c
 
e = 65537
n=[]
c=[]
p=[]
for i in range(1,20):
	n.append(eval('n'+str(i)))
	c.append(eval('c'+str(i)))
data=list(zip(n,c))
for i in range(len(n)):
	for j in range(i+1,len(n)):
		if gmpy2.gcd(n[i],n[j])!=1:
			print(i,j)#i=4,j=17
			print(gmpy2.gcd(n[i],n[j]))
p=gmpy2.gcd(n5,n18)
q=n5//p
d = gmpy2.invert(e, (p-1)*(q-1))
print(d)
m = pow(c5,d,n5)
print(long_to_bytes(m))

思路四、低解密指数攻击（e很大）
适用情况：e很大

和低加密指数攻击相反，当e很大的时候我们怎么办呢，这里就要用到低解密指数攻击。当e很大时，相对的d就会很小。这里我们用到github上一个wienerHacker脚本pablocelayes/rsa-wiener-attack: A Python implementation of the Wiener attack on RSA public-key encryption scheme. (github.com)

下载之后把里面RSAwienerHacker.py改一改输入题目给你的e和n就可以帮你解出d。

例题：BUUCTF RSA2
题目给的e非常大，我们放到脚本里解出d：

有了d后续进行一些转换就很简单了，解密脚本如下：

#低解密指数攻击，使用 RSAwienerHacker脚本解出d
#注意python2和python3在hex转换时数据结尾相差差一个L字符，会导致hash值不一样
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
 
d = 8920758995414587152829426558580025657357328745839747693739591820283538307445
dd = hex(d)
dd = dd+"L"
print(dd)
import hashlib
flag = "flag{" + hashlib.md5(dd.encode("utf-8")).hexdigest() + "}"
print(flag)

思路五、共模攻击
适用情况，多组c,e但模数n相同，且e之间最好互质。

当题目给我们很多组c和e，但它们加密使用的模数n相同时，我们可以考虑共模攻击，当e1，e2互质，有gcd(e1,e2)=1，根据扩展欧几里得算法，一定存在整数x,y使得e1x+e2y=1。我们可以调用gmpy2.gcdext()来使用扩展欧几里得算法，以此求出x和y。

又根据加密过程，,。所以

(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)modn

又经过一堆化简之后就可以得到：m = (c1^x*c2^y)modn,得到明文。

例题：BUUCTF [BJDCTF2020]rsa_output
题目给了c1,c2;e1,e2以及一个共同的n，尝试共模攻击，脚本如下。

import gmpy2
from Crypto.Util.number import getPrime,long_to_bytes
 
e1 = 2767
e2 = 3659
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
 
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
 
_,s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(long_to_bytes(m))

思路六、dp泄露

适用情况：题目提供dp\dq

有时候除了e,n,c之外题目还会给你像dp,dq这样的值，这是为了方便计算产生的，同时也给了我们另一种解题思路。首先，了解dp,dq是什么东西：

1	dp=d%(p-1)

然后就可以进行推导，简单过程如下

d = dp + k1 * (p-1) 

d * e = 1 + k2(p-1)(q-1) 

把第二个式子的d代换掉：

e * (dp + k1(p-1)) = 1 + k2(p-1)(q-1)

两边同时对(p-1)取模，消去k

e * dp % (p - 1) = 1

e * dp = 1 + k(p - 1)

得到这个式子之后我们就可以通过爆破k的方式来求出p，进而求出d。

例题：BUUCTF RSA2

题目提供了dp,e,n,c

python脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes
 
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
 
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
 
for i in range(1, e):
    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)
            d = gmpy2.invert(e, (p-1)*(q-1))
            m = pow(c, d, n)
 
print(m)
print(long_to_bytes(m))

思路七、dp,dq泄露

适用情况：dp,dq同时泄露

有的时候题目把dpdq都给我们了，这个时候我们不用知道e也可以解密。

此时有：

m1 = c^dpmodp

m2 = c^dqmodq

m = (((m1-m2)*I)%p)*q+m2

其中I为对pq求逆元

例题：BUUCTF RSA1

题目给出p,q,dp,dq,c没有e。

此时可以用上述公式求解，python脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
I = gmpy2.invert(q,p)
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = (((m1-m2)*I)%p)*q+m2
print(long_to_bytes(m))