RSA刷题
Normal_RSA(详细)
文件下载下来是这样的
查阅信息发现：带有PEM文件扩展名的文件是用于私密传输电子邮件的隐私增强型邮件证书文件。 PEM格式使用base64对二进制进行编码，以便它以ASCII字符串形式存在。
PEM文件是Base64编码的证书。PEM证书通常用于web服务器，因为他们可以通过一个简单的文本编辑器，很容易地转换成可读的数据。通常当一个PEM编码在文本编辑器中打开文件,它会包含不同的页眉和页脚。
-----BEGIN CERTIFICATE REQUEST----- and -----END CERTIFICATEREQUEST-----
CSR(证书签名请求)
-----BEGIN RSA PRIVATE KEY----- and -----END RSA PRIVATEKEY-----
私钥
-----BEGIN CERTIFICATE----- and -----END CERTIFICATE-----
1、使用openssl从pubkey.pem中提取出e和modulus（即大素数）的值
通过搜索可以发现可以用openSSL解密.pem的参数
kali自带openssl
用命令openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem对其中参数进行解密
得到Exponent、modulus
Exponent是公钥 e=65537
modulus 是 模数 转为十进制数据是：87924348264132406875276140514499937145050893665602592992418171647042491658461
分解得到 p , q
p=319576316814478949870590164193048041239
q=275127860351348928173285174381581152299
或者
使用python的RSA模块
from Crypto.PublicKey import RSA
import rsa
f = open("pubkey.pem","rb").read()
pub = RSA.importKey(f)
n = pub.n
e = pub.e
或者
2、使用rsatool工具生成私钥
命令：
python rsatool.py -o prikey.pem -e 65537 -p 275127860351348928173285174381581152299 -q 319576316814478949870590164193048041239
3、使用私钥解密flag
命令：
openssl rsautl -decrypt -in flag.enc -inkey prikey.pem
wtc_rsa_bbq
打开压缩包获得文件 cipher.bin 和 key.pem
使用 RSACTFTOOL
python3 RsaCtfTool.py --publickey /key.pem --uncipherfile /cipher.bin
或者
import gmpy2
from Crypto.Util.number import bytes_to_long, long_to_bytes
n = 0x62D3D61C92452630147E89670FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
e = 65537
p = (2**4244)*699549860111847+1
q = (2**4244)*699549860111847-1
Phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, Phi)
with open('cipher.bin', 'rb') as file:
data = bytes_to_long(file.read())
res = long_to_bytes(pow(data, d, n)).decode()
print(res)
或者
轩禹CTF_RSA工具
就在其中
key.txt：密文 psa.key：私钥文件
openssl rsautl -decrypt -in key.txt -inkey psa.key -out flag.txt
babyRSA(详细)
题目：
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from flag import FLAG
p=getPrime(64)
q=getPrime(64)
N=q**8 * p**8
e=65537
c=pow(bytes_to_long(pad(FLAG,120)),e,N)
print(N)
print(c)
'''
195869853761605418565912426575165155310138169878437113242420866794581458121010172175123773271172966494737601637192319031324980923234574024717004578493417782613794332361852436053080758357356796975886814896748127864437682733874594209237175890215554823802759715050092541290013484514244379930939120479013336321
97005606970821804403994763488668565541380119944415342813038679665968492985759461541273864242512555285439143004622121856190251008775641399317706165715818778134144273158588994292880105800607038946430945921187911592583778698219033437461671853884487810872315564812232169491576154432524236217382798380345144152
'''
原理：
\[当n=p^k时，\phi(n)=n\cdot(1-\frac{1}{p})=p^k\cdot(1-\frac{1}{p})=p^k-p^{k-1} \]\[当n=p*q时,\phi(n)=(p-1)*(q-1) \]\[当m,n互素时，\phi(N)=\phi(m)\cdot\phi(n) \]大数分解得
p=11795576488031432147
q=12296365925077812421
payload:
import gmpy2
from Crypto.Util.number import *
p=11795576488031432147
q=12296365925077812421
e=65537
N = 195869853761605418565912426575165155310138169878437113242420866794581458121010172175123773271172966494737601637192319031324980923234574024717004578493417782613794332361852436053080758357356796975886814896748127864437682733874594209237175890215554823802759715050092541290013484514244379930939120479013336321
c = 97005606970821804403994763488668565541380119944415342813038679665968492985759461541273864242512555285439143004622121856190251008775641399317706165715818778134144273158588994292880105800607038946430945921187911592583778698219033437461671853884487810872315564812232169491576154432524236217382798380345144152
l=(q**8-q**7)*(p**8-p**7)
d=gmpy2.invert(e,l)
m=gmpy2.powmod(c,d,N)
print(long_to_bytes(m))
2023 SICTF BabyRSA
题目：
from flag import flag
import libnum
from Crypto.Util.number import getPrime
m=libnum.s2n(flag)
n=getPrime(16)
for i in range(233):
n*=getPrime(16)
e=65537
c=pow(m,e,n)
print(c)
print(n)
'''
44457399775772165283580795763046604956432217865936749114390645714446263790235445725770165521476841968764175721036280702731933849090719866149354613431301887740671003826556620460836983488011711209908075106260857650574672356032244606425941095128801765463716482316101398637519304864271794460829068714740938719022156283319142938782439784724450045931039355442034325311037568791297455084676548879770834712506552233840348850684727096270392080049993135041218143811167688449496243036317450681348089315258831745988434134987055263393540923865029931594717328162951158311497514418799360413513590684301435386737514918075848373373755748782672860711406169316940293554209702288482064854840802876490202123903888235028119047988176327629542924415737212649237787748145773301112682790682933658516724691338727523894513267588035437093188599375494920656327919129240066252636130803666175859640361767805549884909317548802917210333235914904622641997249853362378711924024129399688535136879208010081166848163897114124726692078532337827810846421365846926064892472698603597461932481745017020417072013702099809833423003201003030492
157077292656328898849823499976497003976795705913326943955927601882559735301000546878663484930436631929909115065166613744548816622146802007640124796249330573411377703969505934904150600987843325674764620305047603408490558134670867673308099650843329640744997672015466571290660161290811275435569339606335117906571999000341133024698424364682800683662193063661214736762852739324479859236963365531207752799197178993887860855078852702337761399225640575281412171035871278933493943575572155382899938265639764715616686123949482372238288859715465115400317136714757882965887595246507450491169518000205087415380208167764110920711042584766805992237919576823121108078407699912757901788925718859790257450499775129521327827653298451904392241906547672843110356658889638496906522290674659574024024440113632175010053065452660076447040937842478007881589334096496073556056726805396937630799201696246079227214272205462258357482722478243481697053301054600954126539848778226175296162997813416634702496577009409960503948474494741296663849482119365434792563324547643352816519125305335959420429699475765642610737903235960423173
'''
n为多个素数积，可以直接分解得出，用sagemath可以节约很多时间
euler_phi(n) 可以直接得到 \(\phi(n)\)
# sagemath9.3
import gmpy2
import libnum
n = 157077292656328898849823499976497003976795705913326943955927601882559735301000546878663484930436631929909115065166613744548816622146802007640124796249330573411377703969505934904150600987843325674764620305047603408490558134670867673308099650843329640744997672015466571290660161290811275435569339606335117906571999000341133024698424364682800683662193063661214736762852739324479859236963365531207752799197178993887860855078852702337761399225640575281412171035871278933493943575572155382899938265639764715616686123949482372238288859715465115400317136714757882965887595246507450491169518000205087415380208167764110920711042584766805992237919576823121108078407699912757901788925718859790257450499775129521327827653298451904392241906547672843110356658889638496906522290674659574024024440113632175010053065452660076447040937842478007881589334096496073556056726805396937630799201696246079227214272205462258357482722478243481697053301054600954126539848778226175296162997813416634702496577009409960503948474494741296663849482119365434792563324547643352816519125305335959420429699475765642610737903235960423173
c = 44457399775772165283580795763046604956432217865936749114390645714446263790235445725770165521476841968764175721036280702731933849090719866149354613431301887740671003826556620460836983488011711209908075106260857650574672356032244606425941095128801765463716482316101398637519304864271794460829068714740938719022156283319142938782439784724450045931039355442034325311037568791297455084676548879770834712506552233840348850684727096270392080049993135041218143811167688449496243036317450681348089315258831745988434134987055263393540923865029931594717328162951158311497514418799360413513590684301435386737514918075848373373755748782672860711406169316940293554209702288482064854840802876490202123903888235028119047988176327629542924415737212649237787748145773301112682790682933658516724691338727523894513267588035437093188599375494920656327919129240066252636130803666175859640361767805549884909317548802917210333235914904622641997249853362378711924024129399688535136879208010081166848163897114124726692078532337827810846421365846926064892472698603597461932481745017020417072013702099809833423003201003030492
e = 65537
phi = euler_phi(n)
d = gmpy2.invert(e, phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))
2023 SICTF RRRSSSAAA(详细)
题目：
from Crypto.Util.number import *
import gmpy2
import libnum
from secret import flag,hint,alpha
def gen_num(x):
while True:
x+=1
if isPrime(x):
break
return x
p = getPrime(512)
q = gen_num(p*alpha)
r = gen_num(q*alpha*2)
s = gen_num(r*alpha*4)
n = p**alpha * q**(alpha*2) * r**(alpha*4) * s**2
e = getPrime(2048)
c = pow(libnum.s2n(flag), e, n)
print('n =', n)
print('c =', c)
print('e =', e)
n = 510598540378970007468346322989879190780475356832709189528874695730531468123747091318830966440138615736420891392158097533731041150162690662471483619765171875053776526546923686545162088172326434280369545887080098691661618888498451216122577703462656147845476260802989936275927468143618457014875124540773380472942489037761179303561650189545290190421786318533073909424735517884608967725919128200358535113829753453601297612782921831305721998858231417374167746154206561475003022801732102170674160043866579234096945753255309604584663823273990392197858273029361669185072049422597132579136784027822968387907216366150999438414498332890674564920800382005582891491049365978733797356415518435343495821039314228388769356638637099572998812062355774848959446125701462950655806332002764535951282449862140062574418031213788534096501985200284615865248974807525604893147298611402252296159828500266098282909607218395957805357667923653409828275804406466185333491486073920384298557332939701611488655278812282652143513835104674009767479927241052662403578967182673338296967573503287747778401579267126898937724971226916836862238412923209155792382534204896050548824028658237640251964366961727999178646613907934616655737902329568420682808750546571786374023614255135110482419627491157502417864563832543812083026753673687664854910877686333766643694031564516722983669199704788291656757271915091399977189663329054202997146978631991467923388119989473941572476162990901960011968892272676827771256008656450296183884491251752111424531449198118292179798490440493223653950102915889401116251591885909790869073018774674246846164536910633015902964911907187085243240032540938841961345835517368130042501382327926289017383981908729734129193302049155793436988510517701765733605569135643208447952662352778482137713239592896997102366230279153456455232519301534222340901671138239539845240151878610363390683459663471954623868659324304077587611084188341121303918876492043578883059738615210439439368338460631574255417822627815523601923537626576677004085017875860928802762176477815284840936951142176532768517728636562256240668409525184886142801802825451465440993457022771077957094228957592122319682216294509338262739872163482972508991702525289361105971574659126127296233247905505496525683817711366704746617027744889413904684867577081667137187623825349410229389484199608739864221035985277681307389939848405790294473878622092200837753161101695539947514614727699952200114544362051873938505591469240465379091377837297561323297393518152524513948294475770774872596601345526469590486037386767964812631618224527233850818909346007449756779707319609915127618828551910681421647307180399632857248867655836894968134457622987954781685664833951774981383914013420724637676787907498490619865488706542422141338754933476190313653530739822029700217857534243473680585150263523947891501341441371965435851479670882202992955935279933652356336270251591324623898094984119190752775236005057405257945038031382867511822173122001309505728526596893926445291712035117553637589190292816001770554129840326832888707541999454791653742647879694585329112697382151447923691770809327807665376014114552626285289291808032845544905356380497227622738746307685611140483875177839511922977657045680353723672792411661489242162646272105649970359134277499907207906149573299990033858943215801954126448693460102775418225293255402758159431943811872373682053160944887775375465971432320964554947377318554518275854303099420999992690990916801757184853847474379621177976926681977371922191722085164910430032177320954341986984523594583172470609743970245810969858512632597943721628165724329447516823159387734220282510185959768239630017162115072758419177056571781075148374822721899683720488356041096248563880547752710289151512607087038310649235610688255059182467964379544134070766646863815775576049106337955345150055151813028534690066771104188418296440067303355417210829440978858599306487361626723932883675404705319649877631289465547597225908934420304867048341698308940436377375588905463549199568800788130324653074398891097223958392703515180958466771395566567923630440881986781120062769327993137151783189811570714391264155060840731029466593405853721833971303821804104382800673631786729744779165371433211267361024896576031556979771007693215198547296582235167582106419779580693225211695215406540025468141235241168387527901851774993867055740692835931115312659500713701652905802357951993290979099170159167009106534001226859533836082801229997337966972579186548771169099646656172882424089451273021293821026173210665095782802709874946641962115525841325300318524665386511421662860490620819561338110623774842340380068922415609137358448899126553279894950604871889208579886778999174405582160576479554324208876082033912031737086248121899303730781498156597249803927142235444644481388064486155431912003641095674949903404176810866307571531389637794147871012904134653569388493652441432759092336752228939764110397029831387803943394811558386122839568158928461007578259968765727092577006588264867960486472014493774664081407186721351852883527145790575242285664659303948842228766554243966691396492391152581830022133814454196259968655735361775914705332258892954614272244452518449260489348504449204461418971768011384340273291232094176572232837038670467853897665877851434992557429017504229337778470080893449423405491607587635438331476572996201482633587271479001915768182336813417460145272910780420062773057289352127058606048428315185624554551172152106354445240590380140756355226376829443068190672329776832112173322011137862590548721676059398379694994522794474774534579546109677615257696703950497332824299576069196330271666459758430542051969093680846765661685489556479825015505460585577388300005030240514448617715276600874290664416888184557142542207029827016362686924883704397874129412267949416733492080843315519912943048041880665442664534980370689081266908497051077237188221752059058912835617635691061804481035908317765279937217591432632832678806430381325340000898958680468694182993189208039459712391492410123386884340504648296815916980264240229859574883155040793388439699245314010536014311134726579595932201351264754211113984594974123575279085420654342347792446273359397655783349850267895960713020361459104930811498666622216299579774939159380045958811891996366190154624989040001455252320159516822116133341010157165599727635333348456688307169980804760876207246783116588952529877373514768545007418968307885769960168050996962066803264260375707466369627458024513973771207018864983698407016663019106354023164759250846073414341438963394719456500998324900154652118420207057668806120330181700845296117532235012372135050553397046174401449323031309344766628888675704109715329046692002106076405553528413866402862565543443907259825033515101841485790388106868972724754988229771779715569516295419556055234476868558577442887306482605945053829666543946452255290321024138948999088611233226734197091325915223296133751626031378197131875533631358612215053149934608672729194446883476706267066475008836864936670808320239466055935088929279252129128009704233352664523535820092988950793050907265677092793104426094212209504897403359406325045852228354350509453013015487815230129380079713113632363881496974185547766115624580099624722897692297760495094913178120692467666707678647081180656345151015995338390986674404981831649353833607305738823436744297628382797810952028446046016233612873716789383675779820186248250486000672269630344269347652027789034023080859790238772676504723029078903218723114249502157501775936110552413022658586833869562215506206204712447588632398550497708640229614956652263449460598992811393334042395804931240940416629178335447861485028284981615219874331354750385150254017244750993573994159458909546341067039268159319391512934162794663414200907868505060542602841564239761181077333990423542820064315891665379550720216448942932714180923613869070005330476506812100063599659432570925437054287120906048730323556681557905787470647037629769660028387819741611799183349496549168370221978146678987457271259655273299546276899538032070218474555442304430064164467753804089753466882786069297036926063093020795423414152340563079346797084488827259011515774643776620378827875819192074121522712821147817374988804339999134520633699074448564057555026364304855373068414955699295158212425760345481057281658337956841137897162198027254556350868502178340964817530029135654659162400076087528650997151875596189190736466304722028587441680622878918057024286243448077104494316372739218635221411755498456912672491099154558604384574583302548226057069534004474532514444674565766058970748694657151540644416463532338966570743112669782840065402131461088637463019996192189423665651801811614499041923273110971446683450048861113332787126098622974613883291506736280588039145040361795192519576202306796277888696719887642051327259799873478040156450250036778305950744573270786882726162630115640020293415918210448873867037875790399234972055537649774407094382744621251926131880807765203843946682834221238903263352845265134368550124026502981782369374484091775137498831749984649699756860976525160646445060537001
c = 25311588269686177955448734593829241225577179988164713941852977611031657483354358211703127234256857543045931490595235462694154500286504335321863566904591526587164297277540588019404183750093303030110155964308233155625979213391426577001127732161793532171930032372311485789800839135378584125843945003217786635500780784536181313697728354510921343049319891609423580951127082479154042124088536642353812516362473763243425336498681024731131013712158320926550826023277898283823992258572884077276506953901984370413493389421701244517177275694290580595883324705204426546600360091062972293159479880268240701929584137714053692704173792703744319619320692061092061615202753943135058204637610994232168818081462863915909261100211958674543647005416235222620606212841753586419836448681445654681389951211124603287962397164672343026391101395393442103086256726266031275710666309840451443110824175976964355109239201609721120961810198879456321855222352235065257082872600438604687617267718725588993464084147695037610145634237788526691386358596867368523164061114195245860062033244276270480267737617206612775486335779851309426638789250166900931784751600508190450785806340839297468432626354823268011108399699249876358363866293469899572158837757748629586492339783888456600259136387616777593894789302431752391447333278000811521062096467397501227651566498970779080811188805992370970942403208432494393387894197176720244315639559895616799551357601688597541585709039366190088117378880414928532937085490713336140523926983900188378021593225550131993528275166272215028510435690944582596557549068715312515919059333916941744937308255671959764859162487792658274812322891679161915480098864709106347357292015949882243095564999283630289876842913558415205967734452657944991350268108202225952952066459093168792825684626405271617613362070897142103054139806566495183172335794957308822648116537830567396971238329939142829563169355194093529211071160078683833491919940022871862059981346961003867620542620578917684687869682550269127226291011607064545739386850054846167307744022708831833252517778607796258598290908139274345221343651583618249287308738279011682960787460189183445095638164116734700624496711487227176740828397696295620232796356005136058517828311139839381424066302086111930635998143063033446131859852797958765199173807715541045956108285596958780742834805533223538366354327087736088500599094358107164689423572964793385788194218918919596478862097292477628426360333874314260108133339375942666508606311391805252966277961758108821946154428477616100004321457604879220523742427633323872953699931521980332026241531049474031438142792394628576016121322036294740176980189940853036679375845577017978783071015970829136676221389585848058189544793760570196797629432282672371000290840492119720433350192833648839794730598188620374416865232426658538841900897108162173580739323675324880778494924038982358349531848197090990541020708295116156624389135273650491811601011636903928586011504526431498652011548693157985029456398851189821020778958527809174433156243544030624341915713810661287037659586018768085470670240790942171506843637271442721823608266490364627429331023698199955218456371716269004979764982383921294842864121196124699402037204598504310969390789092001114319822852242500941141355281693725110460506548426263105213498404197519606615831672853931646583757742145492562101250546593997874586076926641241047317510838024042147508770595175718146175716833867781581245298658392175502069483979736336330731124942036757071709086638075284655589787868565023763734664219353940143820183318534640360506287779208468427268377183973501528333749816003855834863565394122448191029578528511650194632623989208637401008114422451686312319644054514944700566430912835340518601698767128195833704182657730566589247891277627101027106635732998136735398078858899384713118593668984773592904704131402905145754570091966901120411201405256435232063295790833161132002246279663161388421997242226907126829858922174709653627696146355472690262198127338971112610753839661677080463775112411884196230185877234066728564716929551607129141735155379529048300204700285511666205204686244751557147684338591300111406075976759988295937870045743031816067994768915303111125253664865369863586807234945352445045026501495849671447691502253489642657652848949102823407762108943161789244134119866441040670840037015617307056821150285453994199024947457774647253618512995677313792036106100497936654142008173389260345411854520383366800831542339243757421033121103167943520915885043698882609693007629591093225819727653240183003450339802857059736870645197609170799838610316307123146927966669912638227587517396282910946355194781275415343491170583392480153599086125374051844306869510079152461763122622668280249192047024784624692776244265874153473114993619019113474166958126841368545758693832786756946298833891033171752534079387364641021835311861509609494125593285947444939996542402774020507531158198766149282993994638607458820211163623309687149807339960007614766879688676462400606899851539023671152038536934433128973358637812907001112093086713949701646964777013925616637956114825918525229968119306607256312727518429074253193934915609865400118400124334806320033990630595454381780378123232633134565408152216410478497582716891919477755736223636583493709691482948793995974775520709337409910573358960632077245564017495103173982250506224927848890977671698731337737945862469303397352291579706358090437359126171980555387033997507170208063868788685780633727495158542911276981383764698030088894904043298340184342818716278091407356551940358010532738356144600648671870141201656260882560550096111259047730234565173017875969390130055742832375612379167064701421263006004472414998830886590121784525812803198481744263349186310137594023961272959521982892804372412802448375074058059953851751721276448647238818757245128139844126234490887064897176175605991477364838775902549049484485649550475857257115219540606931472558004890564503134870490140656624241401747198540715275804941032074573356860460172868340373583692584902872979221114982298050586685719887060873413850621645519128954022253850929825608263273096476942591333367968509790925478388960974334157155990587259664085903377635645971389261554405014491809856113962072321115329323751880850245450855429733690986687462514539793256111238991830404264833945950057548041347552265351912075406068254301589527368376552057750656888595867048015012255350060023438752477068307445956245683183096512267217891149812719686622381240260466772552889788641876064057960173837664029586196731436456574414559972320705400861271592462379875676277251086312872195716024719468847393778892154498344296554136868868732950910162390521996660833516010868267341539744299603050842530651780425947531816479566426165422123252285427076862067553260240357395991463485011778125635347076641337205162163658915958257879189951068432591492287483129944125287963913713736174143726754563437013760958618334477377727596918588685928884428267449422751775309153821164066157157127578931430789782791432466972743083256930846560916380022935439074194208587413499830348721004306047843916090382879427208653946874404416581482497419737465638158237340330822703573665318917667360471294611610224794247546701801044290825387969994925735165223021550294577211312086169077389985367351707099712483698243658870007261177946508698830792080087400145468466457013023648585707831661968993789151545051681008263293021078693138432668411562842904645661356499891588207831214182852485507569391094080770281546830762172075737108196782354642073491890672014845707320966391491467609280627047834838773416130380735074488364271149543425149101272213833983451690912775914099688310078028317868139895586469648241691434390559738020665790535748911667198341478329818172050103593169144077713081858968945277802911631514524770516773987691162846774892828407010262766598402873965272708201519043339930474621748065360132998861911090097210247744181877811558047691563490093112810880988416880859363631693862441291401344868362517958157134815632633152101164792211199872770004214575342556751954753067436057216989105115974894826691301734658752554796336087163153087013755182247902851847839867807219615044427616326518986674768302109569955218389569458769985874451273117138435546665024826358058600551523916808015505037962468350942106702503883112975634757971636535249998962164886704286732345711210362931312187319836001555348202695806282730945501510756659164231139623277954192087899140537284122009070763979073048837471984618684020674370221463294306239424220412900401460550783283591789801735401367473630854684306273273881688896021682911944793729874921181848098382943970467341811398482121657330781393699096796050290808604481724879698091852697163383826854575487201365106673196811573729247280577781500366763330567122007588833805912087009446499739562463428568952248234506507069953596589309728265145195922268165106056450388840269349409588020300011340940321969965833519126936472969929255823540027083032424724503173052044192907375974391257436211908641463947719594493311129179150043015816776680636855703407557636501711566215605658114055289137679940955
e = 19458216662993202562182929756256684791318810848802754020883513588583377528821730559897870095442161189229950925325157413999927847684731484753811988111830295294129447423655650029218971567158117911790213848402209470536199246476182240248742771389082526603384625792117047996128232952372477895218147279573573322975526303267821446640338606290250958710008158544852602338088244940388562828263436457418528981476220691508040085291576643321726669065360399003917048894093458055139757991688086912143763420958307099065105543361779847689716282373299487102518794317683805758527645283956734672229827240143254092779918701447288342107763
#************************************hint**************************************
M = libnum.s2n(hint)
P = getPrime(512)
Q = getPrime(512)
N = P * Q
print("N=" , N)
E = 65537
dp = (gmpy2.invert(E,(P-1)*(Q-1)))%(P-1)
print("dp=" , dp)
ct = pow(M, E, N)
print("ct=" , ct)
#N= 154243858720978602820118866455277758287334223654318945323956633685668127012462551649034724900534326698546179107853501584676890290935304784613676008667655919749627682648852472398117930471389759979432279103098572267738634433626627146280660185675121614094399255782089060202532182667463993275434746386786808729553
#dp= 414447829724187823397808703878958757693775250832414113550357728233230359464880433113636330432984183165483109337095394192757735932571515450285102727598243
#ct= 107353143319003715532284973064969905174389167949274067058206046773012002421251301189097709121034091973243342582216724329271495555062882075119176838856174054763892910473175610614629226628025470613930226188506099489500606701109022668507012376482339056160636468427364776216626364765166621843217027512464383836160
hint里给了dp，很明显是dp泄露
import gmpy2
import libnum
e= 65537
n= 154243858720978602820118866455277758287334223654318945323956633685668127012462551649034724900534326698546179107853501584676890290935304784613676008667655919749627682648852472398117930471389759979432279103098572267738634433626627146280660185675121614094399255782089060202532182667463993275434746386786808729553
dp= 414447829724187823397808703878958757693775250832414113550357728233230359464880433113636330432984183165483109337095394192757735932571515450285102727598243
c= 107353143319003715532284973064969905174389167949274067058206046773012002421251301189097709121034091973243342582216724329271495555062882075119176838856174054763892910473175610614629226628025470613930226188506099489500606701109022668507012376482339056160636468427364776216626364765166621843217027512464383836160
p=gmpy2.gcd(pow(2,e*dp,n)-2,n)
print(p)
for i in range(1, e):
p = (dp * e - 1) // i + 1
if n % p == 0:
q = n // p
print(p)
break
phi_n = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)
hint = libnum.n2s(int(m))
print(hint)
得到hint: Alpha == 8，这样的话就可以化简以下部分
p = getPrime(512)
q = gen_num(p*alpha)
r = gen_num(q*alpha*2)
s = gen_num(r*alpha*4)
n = p**alpha * q**(alpha*2) * r**(alpha*4) * s**2
得到n的近似的值
q=8*p
r=q*8*2=128*p
s=r*8*4=4096*p
n=(p**8) * [(8*p)**16] * [(128*p)**32] * [(4096*p)**2] = (8**16)*(128**32)*(4096**2)*p**58
将n系数整除然后开58次方可以得到一个在p附近的数，最后在这个数的前面爆破一下即可得到p。由于p的长度为512bit大于flag(PS:SICTF{uuid值})的长度，所以模p即可得到flag
from Crypto.Util.number import *
import gmpy2
from sympy import *
alpha = 8
n = 510598540378970007468346322989879190780475356832709189528874695730531468123747091318830966440138615736420891392158097533731041150162690662471483619765171875053776526546923686545162088172326434280369545887080098691661618888498451216122577703462656147845476260802989936275927468143618457014875124540773380472942489037761179303561650189545290190421786318533073909424735517884608967725919128200358535113829753453601297612782921831305721998858231417374167746154206561475003022801732102170674160043866579234096945753255309604584663823273990392197858273029361669185072049422597132579136784027822968387907216366150999438414498332890674564920800382005582891491049365978733797356415518435343495821039314228388769356638637099572998812062355774848959446125701462950655806332002764535951282449862140062574418031213788534096501985200284615865248974807525604893147298611402252296159828500266098282909607218395957805357667923653409828275804406466185333491486073920384298557332939701611488655278812282652143513835104674009767479927241052662403578967182673338296967573503287747778401579267126898937724971226916836862238412923209155792382534204896050548824028658237640251964366961727999178646613907934616655737902329568420682808750546571786374023614255135110482419627491157502417864563832543812083026753673687664854910877686333766643694031564516722983669199704788291656757271915091399977189663329054202997146978631991467923388119989473941572476162990901960011968892272676827771256008656450296183884491251752111424531449198118292179798490440493223653950102915889401116251591885909790869073018774674246846164536910633015902964911907187085243240032540938841961345835517368130042501382327926289017383981908729734129193302049155793436988510517701765733605569135643208447952662352778482137713239592896997102366230279153456455232519301534222340901671138239539845240151878610363390683459663471954623868659324304077587611084188341121303918876492043578883059738615210439439368338460631574255417822627815523601923537626576677004085017875860928802762176477815284840936951142176532768517728636562256240668409525184886142801802825451465440993457022771077957094228957592122319682216294509338262739872163482972508991702525289361105971574659126127296233247905505496525683817711366704746617027744889413904684867577081667137187623825349410229389484199608739864221035985277681307389939848405790294473878622092200837753161101695539947514614727699952200114544362051873938505591469240465379091377837297561323297393518152524513948294475770774872596601345526469590486037386767964812631618224527233850818909346007449756779707319609915127618828551910681421647307180399632857248867655836894968134457622987954781685664833951774981383914013420724637676787907498490619865488706542422141338754933476190313653530739822029700217857534243473680585150263523947891501341441371965435851479670882202992955935279933652356336270251591324623898094984119190752775236005057405257945038031382867511822173122001309505728526596893926445291712035117553637589190292816001770554129840326832888707541999454791653742647879694585329112697382151447923691770809327807665376014114552626285289291808032845544905356380497227622738746307685611140483875177839511922977657045680353723672792411661489242162646272105649970359134277499907207906149573299990033858943215801954126448693460102775418225293255402758159431943811872373682053160944887775375465971432320964554947377318554518275854303099420999992690990916801757184853847474379621177976926681977371922191722085164910430032177320954341986984523594583172470609743970245810969858512632597943721628165724329447516823159387734220282510185959768239630017162115072758419177056571781075148374822721899683720488356041096248563880547752710289151512607087038310649235610688255059182467964379544134070766646863815775576049106337955345150055151813028534690066771104188418296440067303355417210829440978858599306487361626723932883675404705319649877631289465547597225908934420304867048341698308940436377375588905463549199568800788130324653074398891097223958392703515180958466771395566567923630440881986781120062769327993137151783189811570714391264155060840731029466593405853721833971303821804104382800673631786729744779165371433211267361024896576031556979771007693215198547296582235167582106419779580693225211695215406540025468141235241168387527901851774993867055740692835931115312659500713701652905802357951993290979099170159167009106534001226859533836082801229997337966972579186548771169099646656172882424089451273021293821026173210665095782802709874946641962115525841325300318524665386511421662860490620819561338110623774842340380068922415609137358448899126553279894950604871889208579886778999174405582160576479554324208876082033912031737086248121899303730781498156597249803927142235444644481388064486155431912003641095674949903404176810866307571531389637794147871012904134653569388493652441432759092336752228939764110397029831387803943394811558386122839568158928461007578259968765727092577006588264867960486472014493774664081407186721351852883527145790575242285664659303948842228766554243966691396492391152581830022133814454196259968655735361775914705332258892954614272244452518449260489348504449204461418971768011384340273291232094176572232837038670467853897665877851434992557429017504229337778470080893449423405491607587635438331476572996201482633587271479001915768182336813417460145272910780420062773057289352127058606048428315185624554551172152106354445240590380140756355226376829443068190672329776832112173322011137862590548721676059398379694994522794474774534579546109677615257696703950497332824299576069196330271666459758430542051969093680846765661685489556479825015505460585577388300005030240514448617715276600874290664416888184557142542207029827016362686924883704397874129412267949416733492080843315519912943048041880665442664534980370689081266908497051077237188221752059058912835617635691061804481035908317765279937217591432632832678806430381325340000898958680468694182993189208039459712391492410123386884340504648296815916980264240229859574883155040793388439699245314010536014311134726579595932201351264754211113984594974123575279085420654342347792446273359397655783349850267895960713020361459104930811498666622216299579774939159380045958811891996366190154624989040001455252320159516822116133341010157165599727635333348456688307169980804760876207246783116588952529877373514768545007418968307885769960168050996962066803264260375707466369627458024513973771207018864983698407016663019106354023164759250846073414341438963394719456500998324900154652118420207057668806120330181700845296117532235012372135050553397046174401449323031309344766628888675704109715329046692002106076405553528413866402862565543443907259825033515101841485790388106868972724754988229771779715569516295419556055234476868558577442887306482605945053829666543946452255290321024138948999088611233226734197091325915223296133751626031378197131875533631358612215053149934608672729194446883476706267066475008836864936670808320239466055935088929279252129128009704233352664523535820092988950793050907265677092793104426094212209504897403359406325045852228354350509453013015487815230129380079713113632363881496974185547766115624580099624722897692297760495094913178120692467666707678647081180656345151015995338390986674404981831649353833607305738823436744297628382797810952028446046016233612873716789383675779820186248250486000672269630344269347652027789034023080859790238772676504723029078903218723114249502157501775936110552413022658586833869562215506206204712447588632398550497708640229614956652263449460598992811393334042395804931240940416629178335447861485028284981615219874331354750385150254017244750993573994159458909546341067039268159319391512934162794663414200907868505060542602841564239761181077333990423542820064315891665379550720216448942932714180923613869070005330476506812100063599659432570925437054287120906048730323556681557905787470647037629769660028387819741611799183349496549168370221978146678987457271259655273299546276899538032070218474555442304430064164467753804089753466882786069297036926063093020795423414152340563079346797084488827259011515774643776620378827875819192074121522712821147817374988804339999134520633699074448564057555026364304855373068414955699295158212425760345481057281658337956841137897162198027254556350868502178340964817530029135654659162400076087528650997151875596189190736466304722028587441680622878918057024286243448077104494316372739218635221411755498456912672491099154558604384574583302548226057069534004474532514444674565766058970748694657151540644416463532338966570743112669782840065402131461088637463019996192189423665651801811614499041923273110971446683450048861113332787126098622974613883291506736280588039145040361795192519576202306796277888696719887642051327259799873478040156450250036778305950744573270786882726162630115640020293415918210448873867037875790399234972055537649774407094382744621251926131880807765203843946682834221238903263352845265134368550124026502981782369374484091775137498831749984649699756860976525160646445060537001
c = 25311588269686177955448734593829241225577179988164713941852977611031657483354358211703127234256857543045931490595235462694154500286504335321863566904591526587164297277540588019404183750093303030110155964308233155625979213391426577001127732161793532171930032372311485789800839135378584125843945003217786635500780784536181313697728354510921343049319891609423580951127082479154042124088536642353812516362473763243425336498681024731131013712158320926550826023277898283823992258572884077276506953901984370413493389421701244517177275694290580595883324705204426546600360091062972293159479880268240701929584137714053692704173792703744319619320692061092061615202753943135058204637610994232168818081462863915909261100211958674543647005416235222620606212841753586419836448681445654681389951211124603287962397164672343026391101395393442103086256726266031275710666309840451443110824175976964355109239201609721120961810198879456321855222352235065257082872600438604687617267718725588993464084147695037610145634237788526691386358596867368523164061114195245860062033244276270480267737617206612775486335779851309426638789250166900931784751600508190450785806340839297468432626354823268011108399699249876358363866293469899572158837757748629586492339783888456600259136387616777593894789302431752391447333278000811521062096467397501227651566498970779080811188805992370970942403208432494393387894197176720244315639559895616799551357601688597541585709039366190088117378880414928532937085490713336140523926983900188378021593225550131993528275166272215028510435690944582596557549068715312515919059333916941744937308255671959764859162487792658274812322891679161915480098864709106347357292015949882243095564999283630289876842913558415205967734452657944991350268108202225952952066459093168792825684626405271617613362070897142103054139806566495183172335794957308822648116537830567396971238329939142829563169355194093529211071160078683833491919940022871862059981346961003867620542620578917684687869682550269127226291011607064545739386850054846167307744022708831833252517778607796258598290908139274345221343651583618249287308738279011682960787460189183445095638164116734700624496711487227176740828397696295620232796356005136058517828311139839381424066302086111930635998143063033446131859852797958765199173807715541045956108285596958780742834805533223538366354327087736088500599094358107164689423572964793385788194218918919596478862097292477628426360333874314260108133339375942666508606311391805252966277961758108821946154428477616100004321457604879220523742427633323872953699931521980332026241531049474031438142792394628576016121322036294740176980189940853036679375845577017978783071015970829136676221389585848058189544793760570196797629432282672371000290840492119720433350192833648839794730598188620374416865232426658538841900897108162173580739323675324880778494924038982358349531848197090990541020708295116156624389135273650491811601011636903928586011504526431498652011548693157985029456398851189821020778958527809174433156243544030624341915713810661287037659586018768085470670240790942171506843637271442721823608266490364627429331023698199955218456371716269004979764982383921294842864121196124699402037204598504310969390789092001114319822852242500941141355281693725110460506548426263105213498404197519606615831672853931646583757742145492562101250546593997874586076926641241047317510838024042147508770595175718146175716833867781581245298658392175502069483979736336330731124942036757071709086638075284655589787868565023763734664219353940143820183318534640360506287779208468427268377183973501528333749816003855834863565394122448191029578528511650194632623989208637401008114422451686312319644054514944700566430912835340518601698767128195833704182657730566589247891277627101027106635732998136735398078858899384713118593668984773592904704131402905145754570091966901120411201405256435232063295790833161132002246279663161388421997242226907126829858922174709653627696146355472690262198127338971112610753839661677080463775112411884196230185877234066728564716929551607129141735155379529048300204700285511666205204686244751557147684338591300111406075976759988295937870045743031816067994768915303111125253664865369863586807234945352445045026501495849671447691502253489642657652848949102823407762108943161789244134119866441040670840037015617307056821150285453994199024947457774647253618512995677313792036106100497936654142008173389260345411854520383366800831542339243757421033121103167943520915885043698882609693007629591093225819727653240183003450339802857059736870645197609170799838610316307123146927966669912638227587517396282910946355194781275415343491170583392480153599086125374051844306869510079152461763122622668280249192047024784624692776244265874153473114993619019113474166958126841368545758693832786756946298833891033171752534079387364641021835311861509609494125593285947444939996542402774020507531158198766149282993994638607458820211163623309687149807339960007614766879688676462400606899851539023671152038536934433128973358637812907001112093086713949701646964777013925616637956114825918525229968119306607256312727518429074253193934915609865400118400124334806320033990630595454381780378123232633134565408152216410478497582716891919477755736223636583493709691482948793995974775520709337409910573358960632077245564017495103173982250506224927848890977671698731337737945862469303397352291579706358090437359126171980555387033997507170208063868788685780633727495158542911276981383764698030088894904043298340184342818716278091407356551940358010532738356144600648671870141201656260882560550096111259047730234565173017875969390130055742832375612379167064701421263006004472414998830886590121784525812803198481744263349186310137594023961272959521982892804372412802448375074058059953851751721276448647238818757245128139844126234490887064897176175605991477364838775902549049484485649550475857257115219540606931472558004890564503134870490140656624241401747198540715275804941032074573356860460172868340373583692584902872979221114982298050586685719887060873413850621645519128954022253850929825608263273096476942591333367968509790925478388960974334157155990587259664085903377635645971389261554405014491809856113962072321115329323751880850245450855429733690986687462514539793256111238991830404264833945950057548041347552265351912075406068254301589527368376552057750656888595867048015012255350060023438752477068307445956245683183096512267217891149812719686622381240260466772552889788641876064057960173837664029586196731436456574414559972320705400861271592462379875676277251086312872195716024719468847393778892154498344296554136868868732950910162390521996660833516010868267341539744299603050842530651780425947531816479566426165422123252285427076862067553260240357395991463485011778125635347076641337205162163658915958257879189951068432591492287483129944125287963913713736174143726754563437013760958618334477377727596918588685928884428267449422751775309153821164066157157127578931430789782791432466972743083256930846560916380022935439074194208587413499830348721004306047843916090382879427208653946874404416581482497419737465638158237340330822703573665318917667360471294611610224794247546701801044290825387969994925735165223021550294577211312086169077389985367351707099712483698243658870007261177946508698830792080087400145468466457013023648585707831661968993789151545051681008263293021078693138432668411562842904645661356499891588207831214182852485507569391094080770281546830762172075737108196782354642073491890672014845707320966391491467609280627047834838773416130380735074488364271149543425149101272213833983451690912775914099688310078028317868139895586469648241691434390559738020665790535748911667198341478329818172050103593169144077713081858968945277802911631514524770516773987691162846774892828407010262766598402873965272708201519043339930474621748065360132998861911090097210247744181877811558047691563490093112810880988416880859363631693862441291401344868362517958157134815632633152101164792211199872770004214575342556751954753067436057216989105115974894826691301734658752554796336087163153087013755182247902851847839867807219615044427616326518986674768302109569955218389569458769985874451273117138435546665024826358058600551523916808015505037962468350942106702503883112975634757971636535249998962164886704286732345711210362931312187319836001555348202695806282730945501510756659164231139623277954192087899140537284122009070763979073048837471984618684020674370221463294306239424220412900401460550783283591789801735401367473630854684306273273881688896021682911944793729874921181848098382943970467341811398482121657330781393699096796050290808604481724879698091852697163383826854575487201365106673196811573729247280577781500366763330567122007588833805912087009446499739562463428568952248234506507069953596589309728265145195922268165106056450388840269349409588020300011340940321969965833519126936472969929255823540027083032424724503173052044192907375974391257436211908641463947719594493311129179150043015816776680636855703407557636501711566215605658114055289137679940955
e = 19458216662993202562182929756256684791318810848802754020883513588583377528821730559897870095442161189229950925325157413999927847684731484753811988111830295294129447423655650029218971567158117911790213848402209470536199246476182240248742771389082526603384625792117047996128232952372477895218147279573573322975526303267821446640338606290250958710008158544852602338088244940388562828263436457418528981476220691508040085291576643321726669065360399003917048894093458055139757991688086912143763420958307099065105543361779847689716282373299487102518794317683805758527645283956734672229827240143254092779918701447288342107763
np = (8**16)*(128**32)*(4096**2)
p = gmpy2.iroot(n//np,58)[0]
while True:
p = prevprime(p)
d = gmpy2.invert(e,p-1)
m = pow(c,d,p)
flag = long_to_bytes(m)
if b"SICTF{" in flag:
print(flag)
break
else:
continue
p = gmpy2.iroot(n//np,58)[0] 用于计算大整数n除以np的58次方根。最终返回值是一个包含结果的元组，用[0]取出第一个元素，即 p 值
prevprime(p) 用于获得小于p的最大素数
NBCTF RRRRsa
题目：
from Crypto.Util.number import *
def keygen(nbit = 64):
while True:
k = getRandomNBitInteger(nbit)
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
if isPrime(p) and isPrime(q):
return p, q
def encrypt(msg, n, e = 31337):
m = bytes_to_long(msg)
return pow(m, e, n)
p, q = keygen()
n = p * q
enc = encrypt(b'flag', n)
print(f'n = {n}')
print(f'enc = {enc}')
'''
n = 51653537089867000761652011130590746802313520068264673020160580069917561392188519232931390445869515344232532568784331302048237171359690952822722876039493000769452096767081300404931722330216126346532584969886603
enc = 44690536038281122354170266051400960154176714745263193061372060985841720368984427654145880743582670327030379760480586797583160681328701811092906918087869110550886466875288189792583233570726037964802137779457763
'''
从p , q , k的关系入手 设未知数 k ，解方程得到 k 值
# sagemath9.3
from Crypto.Util.number import *
import gmpy2
n = 51653537089867000761652011130590746802313520068264673020160580069917561392188519232931390445869515344232532568784331302048237171359690952822722876039493000769452096767081300404931722330216126346532584969886603
c = 44690536038281122354170266051400960154176714745263193061372060985841720368984427654145880743582670327030379760480586797583160681328701811092906918087869110550886466875288189792583233570726037964802137779457763
e=31337
k = var('k')
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
eq = p*q ==n
rec = solve(eq, k)
print(rec)
'''
[k == 9417121805620516276,
0 == k^10 + 9417121805620516268*k^9 + 88682183101893412656202062363816777994*k^8 + 835130920258871731116520438942626595113656903397155629935*k^7 + 7864529599717749552406969663848876637668288910728619036077093993154700322511*k^6 + 74061233184450009775209292858765016061597604616251504720357102634860917158893194588375524699886*k^5 + 697443653972429974598169121392783285650160287293093434693132091397844106836445436517680058567334665090549278389475*k^4 + 6567911842015420321506819400654101948560509860899536310025238160263722196610521748526085410893269573458248310576235146023099304436799*k^3 + 61850825824836626053205688386572909005580601078239651439074568660561225097383377525811026312027808435982140891818296791583544340402682897669507792911761*k^2 + 582456760570705545876626629762170782238386614997526870381419602700853348633640012410288036959044160515727875282061251282681344280966616673131654652317541008459190122670763*k + 5485066260801479340309566314996911949293470279583920918728786330267656152986451379305670068003086372731757466767785235399139803344832423397523965320400372817316884072889848236182860028802056]
'''
# python 3.10.3
from Crypto.Util.number import *
import gmpy2
n = 51653537089867000761652011130590746802313520068264673020160580069917561392188519232931390445869515344232532568784331302048237171359690952822722876039493000769452096767081300404931722330216126346532584969886603
enc = 44690536038281122354170266051400960154176714745263193061372060985841720368984427654145880743582670327030379760480586797583160681328701811092906918087869110550886466875288189792583233570726037964802137779457763
k = 9417121805620516276
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
n = p*q
phi=(p-1)*(q-1)
e=31337
d=gmpy2.invert(e,phi)
m=pow(enc,d,n)
print(long_to_bytes(m))
next_prime
题目：
from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'
p = getPrime(512)
q = gmpy2.next_prime(p)
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
'''
题目生成了一个512位的素数p，随后使用next_prime函数获取p的下一个素数作为q，显而易见考点是 p,q临近
考虑n的算术平方根 \(sn=\sqrt{n}\) 同时 sn 也是 p 和 q 的几何平均值。此时则有 \(p<sn<q\)
我们又有q,p是相邻的素数，p的下一个素数为q，同理也有sn的下一个素数也应该是q
from Crypto.Util.number import *
import gmpy2
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
sn=gmpy2.isqrt(n)
q=gmpy2.next_prime(sn)
p=n//q
e = 65537
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
fermat_attack
题目：
from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'
p = getPrime(512)
q = gmpy2.next_prime(p - getPrime(256))
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932
'''
因为 r 的值很小，依然可以认为p和q依然是两个比较接近的数。但求解n的算术平方根 \(sn=\sqrt{n}\) 时，q不再是sn相邻的素数
而是查找达到r，也就是说我们可以在r的范围内找到q，这时就要使用费马分解
\[\frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p-q)^2}{4} \]既然 \(p−q\) 比较小，则说明\(\frac{(p-q)^2}{4}\)也比较小，则说明\(\frac{(p+q)^2}{4}\)和n也差不多大，所以\(\frac{p+q}{2}\)应该和n差不多大
解题步骤：
- 遍历大于\(\sqrt{n}\) 的每一个整数 x ，若满足 \(x^2-n\) 为平方数，即\(x^2-n=y^2\)，则有\(x^2=\frac{(p+q)^2}{4}\)，\(y^2=\frac{(p-q)^2}{4}\)
- 解开上述式子即得 p,q
通俗一点来说，当\(\frac{p+q}{2}\)和 sn 接近时，我们便可以用此方法分解n，那么如何判断是否接近呢，其实本质就是两个值的算术平均值和几何平均值，俩个值越接近，其二种平均值也越接近，所以当pp和q比较接近时，我们便可以利用费马分解方法
from Crypto.Util.number import *
import gmpy2
def fermat(n):
a = gmpy2.isqrt(n)
b2 = a*a - n
b = gmpy2.isqrt(n)
count = 0
while b*b != b2:
a = a + 1
b2 = a*a - n
b = gmpy2.isqrt(b2)
count += 1
p = a+b
q = a-b
assert n == p * q
return p, q
n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932
p, q = fermat(n)
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
[BJDCTF 2020]rsa
题目：
from Crypto.Util.number import getPrime,bytes_to_long
flag=open("flag","rb").read()
p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)
p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n
'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''
分析题目，发现 p 值输入了两次，所以前后n对应不同的值，分别为 n1,n2
前后q值相同，于是我们可以用gcd求出q值，进而求出在不同操作中的p1和p2值
欧几里得算法求出最大公约数得到 q 即 gcd函数 q=gmpy2.gcd(n1,n2) 由此得到 p1 , p2
接下来需要对 e 值求解，通过 pow(294,e,n) 对 e 进行暴力求解
for e in range(1,100000):
if c_294==gmpy2.powmod(294,e,n1):
break
#得到e值52361
payload:
from Crypto.Util.number import getPrime,long_to_bytes
import gmpy2
c1=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
c_294=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c2=979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n2=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
q=gmpy2.gcd(n1,n2)
p1=n1//q
phi_n=(q-1)*(p1-1)
for e in range(1,100000):
if c_294==gmpy2.powmod(294,e,n1):
break
d=gmpy2.invert(e,phi_n)
m=gmpy2.powmod(c1,d,n1)
print(long_to_bytes(m))