在进行RSA解密之前，我们先要理解RSA的加密原理：

已知明文$a$，公钥对$(n,e)$，加密过程如下:

若要对已知的密文进行解密，我们就需要得到私钥(Private Key)：

设对于上述加密过程所得出的私钥为$d$，则：

很明显：

所以：

一般情况下，$gcd(n,b)=1$，故先对这种情况进行考虑

由欧拉定理：我们知道

很显然：

可以看出：

所以：

已知n,e,c在一般情况下（n可通过软件进行质因数分解）的解密

此时，我们有：

此时，由欧拉函数的性质，我们有：

$\varphi(n)=\varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \varphi(p_3^{\alpha_3}) \cdots \varphi(p_k^{\alpha_k})(p_1,p_2,p_3,\cdots p_k是n的不同质因数，且有p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}=n)$

由欧拉函数的计算公式我们可以知道：

所以对于$n$，有：

特别的，对于质数$p$，有：

若$n$为$k$个不相同质数相乘，即：

有：

在一般情况下$n$只有两个质因数$p$和$q$，例如下题：

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from gmpy2 import gcd,invert
from secret import flag

m=bytes_to_long(flag)
p=274327862430236019688316864082249987313
q=206961224895267889099693426679050192439
n=p*q
phi=(p-1)*(q-1)
e=65537
c=pow(m,e,n)
print("c =",c)
# c = 54831930044859946955044417597501651143196043923856762253170140444376354297816

这题直接给出了$p$和$q$，故我们只需要写出如下代码即可解决：

from Crypto.Util.number import *
import gmpy2
p = 274327862430236019688316864082249987313
q = 206961224895267889099693426679050192439
c = 54831930044859946955044417597501651143196043923856762253170140444376354297816
e = 65537
n = p * q
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)#求e模phi的乘法逆元
m = gmpy2.powmod(c,d,n)#等价于c^d mod n
print(long_to_bytes(m))

运行即可得出flag：

flag{how_excellent_you_are!}

这就是最基本的RSA类型了。

在已知e以及e组(n,c)的广播攻击

此类型攻击属于CRT（Chinese remainder theorem，中国剩余定理，又称孙子定理）类型。

原理不赘述，实质上即为已知$e$组$(n,c)$时利用CRT在不对任何一个$n$进行分解的情况下求解明文

在这里，我们设明文为$m$，有：

再通过CRT求解出$m^e$后对其开$e$次方根即可得到明文$m$

例题
[鹤城杯 2021]Crazy_Rsa_Tech

题目代码：

from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
#n_list= [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
#c_list=[62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]


这里很容易可以知道$e=9$（显而易见，$n$和$c$也有九组），所以很显然，这题要用到$e=9$的广播攻击

将上面给出的n_list和c_list用sagemath利用CRT求解得出：

m9=3678337284039442047026947312380394506988284605153398380909870598085147736828709178219597429308046538374273111663234962853201175297522552444068549756304348183089003998584929250444862897734669616839072634559776823068102560978738392642133409979083241310818961120830565330801827594023873873703163937572703881578432281109467318674533265052430906776650900523035132668203491899352234368836316318216812572637893433384928785981896373747430646617935503364537613820302679656375356094380483213814869276308187497478084540603362678580814022322799191778371368875742773945120383365613028633102737056410926701477700008313642639347163933146129361496566648131161287075292980980083166106192999528561889437021539352391671756010617540361596164032486633114877739259434431765044242037641759566659268290619705700083536966807192023377334915872207418596226819579720241509860110741821630775501873143209229299530346706612248414951753383716954165108266753409813119293227854442685830689203424064786691447734948037502729127922328149002842971722645909768174575776908113523451541199095073733017029558396658874593357205426105429760517295964966905772455366037986657671195106462661190327510507460112791663031458690187525393979689469548319821181450874331998372947479866557921497942728807505035932385939931524294822439633516457845581452433022749099648076725811489217888688273759202726271093237450290814247396662589614216704#m9为m的9次方

再对$m9$开9次方根可得：

m=5364346700993245916083351542951836466599376039702798829478182513243184146028312538778801523615449405915572188751896617305936540801999004614344621214275094

再通过Crypto库中long_to_bytes函数可得：

flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}

gcd类型

这种类型主要考察数学推导的能力，直接上例题。

[GKCTF 2021]RRRRsa 1（部分）

题目代码：

pbits = 512
p, q = getPrime(pbits), getPrime(pbits)
n = p * q
hint1 = pow(2020 * p + q, 202020, n)
hint2 = pow(2121 * p + 212121, q, n)
print(f'{n = }')
print(f'{hint1 = }')
print(f'{hint2 = }')
"""
n =
72480597722768310802103225074022304502987810353239303491995392556828592827312126864102279719480413772239054950810362120660174703790228376146053986053171930937388580526219104498648291397309599209554202670080978901954049943834889894306222459711036629282482760872552358198065124168348275611897584923869319730917
hint1 =
70685159982753618117937078087626553902610663214529331305611406765104333038200912863267956767277081926123480288270862897047313253820275507292683667878994502600957911694615683337770022569861106230373836250952155917286151237134316356851059293688768775787985566372022900108303136666429150678266857778726967849907
hint2 =
59397395285145715354919882069200896861665631746130494855994590508589325004636436593048816842106180115714527211321251497281171549276111388361451000025849056493942252398618018816656979043710894623882099581494083699322411790446784391932055982624616996747139852037848608960801937270797966812928286289985647495610
"""

我们可以知道：

我们要从上面两个方程中求解$p$和$q$，下面进行数学推导：

首先观察hint1，由二项式定理有：

显然的，右式除$(2020p)^{202020}$与$q^{202020}$两项外均能被$n$整除

所以有：

进一步的，有：

现在看到hint2，有：

由费马小定理，可以得到：

所以：

对于hint1：

故：

所以有：

由于$n=pq$

所以$gcd(kq,n)=$

代码如下：

from Crypto.Util.number import *
import gmpy2
n = 72480597722768310802103225074022304502987810353239303491995392556828592827312126864102279719480413772239054950810362120660174703790228376146053986053171930937388580526219104498648291397309599209554202670080978901954049943834889894306222459711036629282482760872552358198065124168348275611897584923869319730917
hint1 = 70685159982753618117937078087626553902610663214529331305611406765104333038200912863267956767277081926123480288270862897047313253820275507292683667878994502600957911694615683337770022569861106230373836250952155917286151237134316356851059293688768775787985566372022900108303136666429150678266857778726967849907
hint2 = 59397395285145715354919882069200896861665631746130494855994590508589325004636436593048816842106180115714527211321251497281171549276111388361451000025849056493942252398618018816656979043710894623882099581494083699322411790446784391932055982624616996747139852037848608960801937270797966812928286289985647495610
kq = gmpy2.powmod(2121,202020,n)*hint1-gmpy2.powmod((hint2-212121)*2020,202020,n)
q = gmpy2.gcd(kq,n)
print(q)

这样就得出了$q$，由此我们就可以顺带求出$p$了。

（还有道题是Geek Challenge 2023的Poly_RSA，但是在写笔记的时候比赛还没结束，就不放出来了，后面写wp的时候再讲推导过程）