2024LitCTF

发表于 分类于 阅读次数： Waline： 本文字数： 3.2k 阅读时长 ≈ 12 分钟

2024LitCTF——Crypto题解

第一篇博客从LitCTF开始，时隔一年，再次发表一篇LitCTF的题解

今年题目感觉还不错。几道plus起到了巩固基础的作用，不过也有几道题目做的有点莫名其妙，比如真EasyRSA，莫名其妙出现了个hint。

common_primes_plus这题也有点瑕疵，应该在题目中声明n1,n2有公因数的。

尤其点赞暗号这题，考点是Paillier，是个比较冷门的考点，现学也能做，提示给的也很到位。着实是学到东西了

small_e

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3
c_list = []

for m in flag:
    c_list.append(pow(ord(m),e,n))

print(f"n = {n}")
print(f"c_list = {c_list}")

'''
n = 19041138093915757361446596917618836424321232810490087445558083446664894622882726613154205435993358657711781275735559409274819618824173042980556986038895407758062549819608054613307399838408867855623647751322414190174111523595370113664729594420259754806834656490417292174994337683676504327493103018506242963063671315605427867054873507720342850038307517016687659435974562024973531717274759193577450556292821410388268243304996720337394829726453680432751092955575512372582624694709289019402908986429709116441544332327738968785428501665254894444651547623008530708343210644814773933974042816703834571427534684321229977525229
c_list = [438976, 1157625, 1560896, 300763, 592704, 343000, 1860867, 1771561, 1367631, 1601613, 857375, 1225043, 1331000, 1367631, 1685159, 857375, 1295029, 857375, 1030301, 1442897, 1601613, 140608, 1259712, 857375, 970299, 1601613, 941192, 132651, 857375, 1481544, 1367631, 1367631, 1560896, 857375, 110592, 1061208, 857375, 1331000, 1953125]
'''

根据c_list，对每个字符进行爆破即可

exp.py

1
2
3
4
5
6
7
8
9
10
11
n = 
c_list = 

l = len(c_list)
flag = ""
for i in range(l):
    for j in range(33,128):
        if pow(j,3,n) == c_list[i]:
            flag += chr(j)
print(flag)
# LitCTF{you_know_m_equ4l_cub3_root_0f_n}

small_e_plus

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import random
from secret import flag

e = random.randint(1000,2000)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c_list = []

for m in flag:
    c_list.append(pow(ord(m),e,n))

print(f"n = {n}")
print(f"c_list = {c_list}")

'''
n = 
c_list = 
'''

需要用pow(ord('L'),e,n[0]) == c[0]来确定e

然后再对每个字符爆破

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = 26287684934288536371438030224508784042871268975402791015134838900290249602701092702492594931306572692868654436714501196060619149020850402317982203575250568283872182497606239389480186694649979877566740647822434500023605871516831662099415987589808614777313595453727243531121031390104059097782466650186291076316486240197369759537327997880644540629964227584070506981319936888159712058406052247256554081989035415864476278146328967410452695134756792942103209740186339835071828587981271027235499355298543650516643100665039796305276163706693873611519506528344413021878980171629732211592839945004800782325172828561339662590291
c_list = [2206795524649235905421691489826312664535869158473992241382107452229902627430789178221234450699214518235612692491501082306158268745610575202210170312762929300421312081998256557805289595256913161318967687803957784191522197708618872099119883772100567610799038030170491575261415069363292331223848994909959222662307903914818692008641789258455591462146141825906954662346647872459477376830019604449386735009274664469596162731339288162705222622464022019805917855614180415135305122287341306358535204977475464107550060171378721195970927993762052901722822033817371589592984818877687488499315074761849162622037910992107211284008, 5772355660578786193365289788142204471140300880779240030922539554921206850801450259027942229717816557629121843824901435845363716561820657469786680232585256790197665053482436914240306106895783671092825614792775018452789907242936725194811142759000550943111242261233418906869936542409260521957109457093880078265172230140113023756025958760162033801341277275818552619176398362323345440943751030254826411167403369778520042425875280132329006784704419423985932863729258308660619215866531848636409929423223281439774682034891288220844217705947244646337813999934326056219959633197870528867256797102445018262011480153115939973120, 1207753724090260852409848530096938494041869666191344850580616117902540004602216282128000198616910613629758228599152405146528856830526069167686468063404160733191610918533887137790198044549066176847699828584104335658872479915611835658770230456040566481519133420435691429577114944632254145293686212844875236028065213764327990843553209848826790721557229795796629116716323389485143635207391322758673224679570474982769025868784848121296090448593104527159728316178638031965733210974157123951201010132807247490252051791615388655934783546925682929869630639426022317978556708362738999927581494799492081969707506643799602026519, 23349127335265499093449067069020992112353295858939476460071138364566485897994252926437380788575729410533824920877221793075557803246884503318707565286465780619451837755333889863647223503631040527885884507188543322662521167319750343131600891690509665461069767205371629056201897374077580748284228605137071513643680112231720015635177198512671008206911131037246521082139072649111758853436401697265407050360284081221903913252963538698624243925508340434415847360772868692706825954252596535393923195017520961377182762938864807222401006410940590209478399415565644283710492027537832649211992078485373823473694670510027091811150, 10226019140134038624377317848115153109426202728030240919051914421470768415604166541259309040981729429302658204608838639560323294519400489855382683083386777345356043308705897287912341523315760693349431629528606884165134456829229982105748229536220053836967234793460400007088552230829556977946642054006994624346182400713981635617380105674142096166299590924644975504927529440869894823989816288037184537810548374154159131078285611810236360387224739364737369218239938401877019353452254541733135847328578198473654682547864026753170978019586975399474768379227943763421295905943744276512487256848753432567851910082922927470490, 23740354509167079065405461731971916754037420716194453557110579966491604804762436810357240604414289616234875179623546843181969909941655688193848922121025497722570206788206574369953117810580405098086613804927789389379000011120646581696237263731340862157598831413772589626428552355215317461446703978266643741459189148155110184955643416482312525932611502239696070143649593393180531208682271982848368078201739398938285094875058820959849311021066738043111703290623367049523633339597166603017770974672021851132978175318897057265294143015585933755643775222343716729295329665381969705644856166297065958733244549838186512052385, 449014525939717636067736015209424784219819246781576119976763479723069921555975991244061404426209241205491628463587064147168107292515973015167075933513053376730612977909688147192509972914228546673914859512456020534607548288441547681099206879988569397951304088877152364775649300942230940480095891405872756559515878791481146087187792174110744462062133353030045674834570611547897985227875674282106272664164460098105513231986703990634100117091825872525928884988567006942035220750862383326774903397508340077320163638705664083267751275414767422570459999305221215356075828860083175263731374754412655619766335149006888723996, 16724794744491727600425925395927244417134995504796613762545001848691858676855371900138882794396073589851705829977971925497098298081053830365847044742295241579270222074264270766160828536659842604404241318349399345391073018854800119637771843569778469196738774691245194283589151708822054754891860887285845079956055960799325451486703248118285066709862851457478898785928241590593187351807366412037409877885725182051826065860998104380663508501993855389845296242673609538795480745163836240239734138130049347272635936034792561725248889899428632572191869130319297765786132841511245497565771732921602763273993266122615935214603, 8335009241673468873253675068463589266426701056401774737990647304778993560605655347351631416630769577522424783603153098182609522990968188535194397812386924076809847791156568504352196579970447867606517135531565802449373639411293098029825159629692422202058452950834073234658264013415977347155192720165418683784735863643368164054960138519912292186928345518922656777075501616408802833213759105274620228201695472893761054437789976692657170111413189445894590722931833376629118468092175170858255694444972297979072766528207056455924414294930988285253186403605383727454401973318032223978796412991222953728595468797201373820622, 1717028738196915227260339129573501065417757436024070728399837662683474643676720266190852688571851260086024584528234004503770202991702828738603236485267929860326697228640681326889845794391744206929580676537615769150484083242039924741303807364343064097449659558370778499818290907827480001580408520014110979083082316647497828342236619136282585160822630608240519352654269080203964531142386474415714079196749108940162898716817139452352062000261548631825989143362746715121123292436275957550673873937398160148303975715603319819731258894296533494152025775404106195174909015831441339509280028585399046169513149752204461930349, 6253489839553538192995294139816446969824750751774728963617638345595670445770677500921617837218605680169746240573789832579137206230177143500699620111070145585461358354523003959756713830108697398762585026303196668650471722612722372863973566811324151291707208671745892059398682725808801715988328719567890446420981480784833951835550433358928430667547317456646990287369723084794020241264506154652275756123282486762023979426752588250225435784747977075518696454125522814567504866613306081720330538332436897331017796420408357014130003339073229042803329670944110125353218213811432346818713964878168764790792105206633440354005, 1207753724090260852409848530096938494041869666191344850580616117902540004602216282128000198616910613629758228599152405146528856830526069167686468063404160733191610918533887137790198044549066176847699828584104335658872479915611835658770230456040566481519133420435691429577114944632254145293686212844875236028065213764327990843553209848826790721557229795796629116716323389485143635207391322758673224679570474982769025868784848121296090448593104527159728316178638031965733210974157123951201010132807247490252051791615388655934783546925682929869630639426022317978556708362738999927581494799492081969707506643799602026519, 5772355660578786193365289788142204471140300880779240030922539554921206850801450259027942229717816557629121843824901435845363716561820657469786680232585256790197665053482436914240306106895783671092825614792775018452789907242936725194811142759000550943111242261233418906869936542409260521957109457093880078265172230140113023756025958760162033801341277275818552619176398362323345440943751030254826411167403369778520042425875280132329006784704419423985932863729258308660619215866531848636409929423223281439774682034891288220844217705947244646337813999934326056219959633197870528867256797102445018262011480153115939973120, 1717028738196915227260339129573501065417757436024070728399837662683474643676720266190852688571851260086024584528234004503770202991702828738603236485267929860326697228640681326889845794391744206929580676537615769150484083242039924741303807364343064097449659558370778499818290907827480001580408520014110979083082316647497828342236619136282585160822630608240519352654269080203964531142386474415714079196749108940162898716817139452352062000261548631825989143362746715121123292436275957550673873937398160148303975715603319819731258894296533494152025775404106195174909015831441339509280028585399046169513149752204461930349, 16954257214609715453949449319699339161494232855569310228933510507504171504126469206091874371244790265592761015613256403517471291015511338346765442554575984841436537843152588028133877350821930031082920487532579036233128796943768462075658517963544351576867080570835108123172127678561307490005618742426940555485915573421790050723171701483141269800431262504278004147886695150170337842904413809555649193394856219267444671017423976317095448634183238063104910602376968654113825856753568856181455666796555652402905808458114516561773417952991326953537750434218624122318995368477991659040481704212571743288062208854477599259233, 16724794744491727600425925395927244417134995504796613762545001848691858676855371900138882794396073589851705829977971925497098298081053830365847044742295241579270222074264270766160828536659842604404241318349399345391073018854800119637771843569778469196738774691245194283589151708822054754891860887285845079956055960799325451486703248118285066709862851457478898785928241590593187351807366412037409877885725182051826065860998104380663508501993855389845296242673609538795480745163836240239734138130049347272635936034792561725248889899428632572191869130319297765786132841511245497565771732921602763273993266122615935214603, 5185490165247175755074805103840625687511977590976733896967715184223982955725681935365096951517529730737911572507779959945930556296503873230438433692310842981978848881986205067999307067785730415524359447947414935770806603135319166013408164683315806218163318125978230966989985398051513033616788512784230934142137906332152151059584574222941527730647262944250765844919176013002939308197949589859844618414360065768222159786067710805154244111569645546199262226746460081578671653615283375596665960708242700241780342523448742861815380568359092813225600016747957517992666799497302478221946509254852979437130583539850985247422, 1748234508408435343229319253644625402817707176509451594647354284826288727338735967235360246609210161049023834307132290872525340273117113455850690260255921823613621383639409134488848519959372177408937889998552431530493839856756914185531673290249084408278489645057787655359507244021027375565961471003583528932265312366403288884176948556324167675395562225956088863571715251876674710333918813480215719798596428736037441464450389735436535142133977551778467378533427938402690627170065561491269748888688911598444983102702261665208037447965537895418969759387684448834920453303484908559802952752182953165141625674023904414158, 11012890581084315425095922547777050020962029248110211263311188736825161568336991045243917700829742195694068118244042803336244383422040087972310576680130493039066637029837297205028290343840934744140990838248421706520572790950203052596858612764294640351774272157943334862976359969574219205290501939867352064476895317015572786888474774760071718201404856802312145427767679849647981118814029138127523521157700904020659839293447586228220702194369342121785362851205183676546931393764208787501487430625010774845511515509394872334800320955439381971987176625826068199951062429360895302585774691509075464492623725384467268825285, 5976772453334984518311442738240004799220403662435440872185530863193424233037367952925902243175234771035939695813307154967530503941081645934538688267920825967077726208002575899575371222695901346361307413004351281869655229087644917183767240951265807406293078230174759543645470570834782744332808979716142354429389228605592485271438778026468985249730030159932637979600514791593524263931036554765213297195922837236962842381131840868115187459577702023810124989825582700575011520568245435377833934768593346195065831458857440454704013911127816011037625063876159283174160162690848395114549568308205531592017492613772445173774, 5185490165247175755074805103840625687511977590976733896967715184223982955725681935365096951517529730737911572507779959945930556296503873230438433692310842981978848881986205067999307067785730415524359447947414935770806603135319166013408164683315806218163318125978230966989985398051513033616788512784230934142137906332152151059584574222941527730647262944250765844919176013002939308197949589859844618414360065768222159786067710805154244111569645546199262226746460081578671653615283375596665960708242700241780342523448742861815380568359092813225600016747957517992666799497302478221946509254852979437130583539850985247422, 6452875340997852295275020218749378916760411126851936571996259386760459856313309845592392640856504175949234216794963908475913037761993360407125952607943943083700382006783091443756617877566422165299422992987336811474980284131306966940424642139162441283769172531199959298540627795873212152702317440453079566096174835647147665695679094943137671532124636863128457006714211465119286776747310503452130041649279123753848522079886216732719572247000481047269505214596261386534160935834909921155351371984109147724730932926711831690752003577272018655013647352055561080857579522667684581123594159788011149227192380455462896729962, 6253489839553538192995294139816446969824750751774728963617638345595670445770677500921617837218605680169746240573789832579137206230177143500699620111070145585461358354523003959756713830108697398762585026303196668650471722612722372863973566811324151291707208671745892059398682725808801715988328719567890446420981480784833951835550433358928430667547317456646990287369723084794020241264506154652275756123282486762023979426752588250225435784747977075518696454125522814567504866613306081720330538332436897331017796420408357014130003339073229042803329670944110125353218213811432346818713964878168764790792105206633440354005, 6253489839553538192995294139816446969824750751774728963617638345595670445770677500921617837218605680169746240573789832579137206230177143500699620111070145585461358354523003959756713830108697398762585026303196668650471722612722372863973566811324151291707208671745892059398682725808801715988328719567890446420981480784833951835550433358928430667547317456646990287369723084794020241264506154652275756123282486762023979426752588250225435784747977075518696454125522814567504866613306081720330538332436897331017796420408357014130003339073229042803329670944110125353218213811432346818713964878168764790792105206633440354005, 20897947836932076779964827384680266669444872541242595584853544810847660781809255811902379402727265984145972717558208216627868351476262475424181241317707734298108218231636329375895362429626917095073694210812814494087830535014117884013936787285440467171742761631884901929078488856204289738449061959822388725333274257861099169377435400465998662612618115681519773625182456433449001773543437767201553703283209697249003117284877232666946456539017194397166088957330100388776645543342462188483091150441369824235427061443229429025534194618806460187812446633057673388068141804189503074739767911838028579099128625845793341901127, 5185490165247175755074805103840625687511977590976733896967715184223982955725681935365096951517529730737911572507779959945930556296503873230438433692310842981978848881986205067999307067785730415524359447947414935770806603135319166013408164683315806218163318125978230966989985398051513033616788512784230934142137906332152151059584574222941527730647262944250765844919176013002939308197949589859844618414360065768222159786067710805154244111569645546199262226746460081578671653615283375596665960708242700241780342523448742861815380568359092813225600016747957517992666799497302478221946509254852979437130583539850985247422, 1207753724090260852409848530096938494041869666191344850580616117902540004602216282128000198616910613629758228599152405146528856830526069167686468063404160733191610918533887137790198044549066176847699828584104335658872479915611835658770230456040566481519133420435691429577114944632254145293686212844875236028065213764327990843553209848826790721557229795796629116716323389485143635207391322758673224679570474982769025868784848121296090448593104527159728316178638031965733210974157123951201010132807247490252051791615388655934783546925682929869630639426022317978556708362738999927581494799492081969707506643799602026519, 8335009241673468873253675068463589266426701056401774737990647304778993560605655347351631416630769577522424783603153098182609522990968188535194397812386924076809847791156568504352196579970447867606517135531565802449373639411293098029825159629692422202058452950834073234658264013415977347155192720165418683784735863643368164054960138519912292186928345518922656777075501616408802833213759105274620228201695472893761054437789976692657170111413189445894590722931833376629118468092175170858255694444972297979072766528207056455924414294930988285253186403605383727454401973318032223978796412991222953728595468797201373820622, 5185490165247175755074805103840625687511977590976733896967715184223982955725681935365096951517529730737911572507779959945930556296503873230438433692310842981978848881986205067999307067785730415524359447947414935770806603135319166013408164683315806218163318125978230966989985398051513033616788512784230934142137906332152151059584574222941527730647262944250765844919176013002939308197949589859844618414360065768222159786067710805154244111569645546199262226746460081578671653615283375596665960708242700241780342523448742861815380568359092813225600016747957517992666799497302478221946509254852979437130583539850985247422, 25920961707523393202281300218444176129734572566815781137488940145677301500180714145402663962373623882683655757546713176923316428191765157386415468883815905581966232659296756935108128028157735278704173240867754374892767863985119564774915890766313799183822643494869775607043330683224121234927784433937849569120283272329925062133702698267726766476110289877776286080853490841837897993369872640809289989540435112046742658888426704252633322563361442888492873827942589957261396606340845665522400646771232316872444568013520651608356878655632725425106340256031308528158877727958784150436116095788759918507442721063497464001672, 6253489839553538192995294139816446969824750751774728963617638345595670445770677500921617837218605680169746240573789832579137206230177143500699620111070145585461358354523003959756713830108697398762585026303196668650471722612722372863973566811324151291707208671745892059398682725808801715988328719567890446420981480784833951835550433358928430667547317456646990287369723084794020241264506154652275756123282486762023979426752588250225435784747977075518696454125522814567504866613306081720330538332436897331017796420408357014130003339073229042803329670944110125353218213811432346818713964878168764790792105206633440354005, 25663191423484921175412364224530127146643925340004154726702279647143356157592854508759921404410754752035271117262826349048515204905598320781277358442584209773238813165864338686191131303650343111109522647292342262318312191154828123703005048694144581658454332596649591143235675787721964930836353194643708891591880016775053451232129740204331045326847472524157097116402350309528683224670236144960836423799755065339099128269152330465141709080678776263364496603148723855163217962603724059472220503607467867433663538613289855157923304803789694579660594681244121347757234971567712156039920653800971260669403951884026752686998, 6253489839553538192995294139816446969824750751774728963617638345595670445770677500921617837218605680169746240573789832579137206230177143500699620111070145585461358354523003959756713830108697398762585026303196668650471722612722372863973566811324151291707208671745892059398682725808801715988328719567890446420981480784833951835550433358928430667547317456646990287369723084794020241264506154652275756123282486762023979426752588250225435784747977075518696454125522814567504866613306081720330538332436897331017796420408357014130003339073229042803329670944110125353218213811432346818713964878168764790792105206633440354005, 25920961707523393202281300218444176129734572566815781137488940145677301500180714145402663962373623882683655757546713176923316428191765157386415468883815905581966232659296756935108128028157735278704173240867754374892767863985119564774915890766313799183822643494869775607043330683224121234927784433937849569120283272329925062133702698267726766476110289877776286080853490841837897993369872640809289989540435112046742658888426704252633322563361442888492873827942589957261396606340845665522400646771232316872444568013520651608356878655632725425106340256031308528158877727958784150436116095788759918507442721063497464001672, 13263786466446190163016008769836220535269357696454674792666135258902640846903309780108315355392508130227345512883180524670260067683978830659316889987124447343297390324463103766540103214985414999778290407008190424180154779235834484101584174703692738403343419550940166812669376385233441159764013001794070232476009158915966454070958519878855933028785291151945528736387913371707135653596226023268592330842008453104190134667308270525900634583278545983101946869551676698088147890541479096323734726116488316329827416755818060204664181280485697259466218350842103872751987842240867163996948996727825810630964777385967911053901, 6253489839553538192995294139816446969824750751774728963617638345595670445770677500921617837218605680169746240573789832579137206230177143500699620111070145585461358354523003959756713830108697398762585026303196668650471722612722372863973566811324151291707208671745892059398682725808801715988328719567890446420981480784833951835550433358928430667547317456646990287369723084794020241264506154652275756123282486762023979426752588250225435784747977075518696454125522814567504866613306081720330538332436897331017796420408357014130003339073229042803329670944110125353218213811432346818713964878168764790792105206633440354005, 5185490165247175755074805103840625687511977590976733896967715184223982955725681935365096951517529730737911572507779959945930556296503873230438433692310842981978848881986205067999307067785730415524359447947414935770806603135319166013408164683315806218163318125978230966989985398051513033616788512784230934142137906332152151059584574222941527730647262944250765844919176013002939308197949589859844618414360065768222159786067710805154244111569645546199262226746460081578671653615283375596665960708242700241780342523448742861815380568359092813225600016747957517992666799497302478221946509254852979437130583539850985247422, 1748234508408435343229319253644625402817707176509451594647354284826288727338735967235360246609210161049023834307132290872525340273117113455850690260255921823613621383639409134488848519959372177408937889998552431530493839856756914185531673290249084408278489645057787655359507244021027375565961471003583528932265312366403288884176948556324167675395562225956088863571715251876674710333918813480215719798596428736037441464450389735436535142133977551778467378533427938402690627170065561491269748888688911598444983102702261665208037447965537895418969759387684448834920453303484908559802952752182953165141625674023904414158, 8335009241673468873253675068463589266426701056401774737990647304778993560605655347351631416630769577522424783603153098182609522990968188535194397812386924076809847791156568504352196579970447867606517135531565802449373639411293098029825159629692422202058452950834073234658264013415977347155192720165418683784735863643368164054960138519912292186928345518922656777075501616408802833213759105274620228201695472893761054437789976692657170111413189445894590722931833376629118468092175170858255694444972297979072766528207056455924414294930988285253186403605383727454401973318032223978796412991222953728595468797201373820622, 5976772453334984518311442738240004799220403662435440872185530863193424233037367952925902243175234771035939695813307154967530503941081645934538688267920825967077726208002575899575371222695901346361307413004351281869655229087644917183767240951265807406293078230174759543645470570834782744332808979716142354429389228605592485271438778026468985249730030159932637979600514791593524263931036554765213297195922837236962842381131840868115187459577702023810124989825582700575011520568245435377833934768593346195065831458857440454704013911127816011037625063876159283174160162690848395114549568308205531592017492613772445173774, 25920961707523393202281300218444176129734572566815781137488940145677301500180714145402663962373623882683655757546713176923316428191765157386415468883815905581966232659296756935108128028157735278704173240867754374892767863985119564774915890766313799183822643494869775607043330683224121234927784433937849569120283272329925062133702698267726766476110289877776286080853490841837897993369872640809289989540435112046742658888426704252633322563361442888492873827942589957261396606340845665522400646771232316872444568013520651608356878655632725425106340256031308528158877727958784150436116095788759918507442721063497464001672, 5185490165247175755074805103840625687511977590976733896967715184223982955725681935365096951517529730737911572507779959945930556296503873230438433692310842981978848881986205067999307067785730415524359447947414935770806603135319166013408164683315806218163318125978230966989985398051513033616788512784230934142137906332152151059584574222941527730647262944250765844919176013002939308197949589859844618414360065768222159786067710805154244111569645546199262226746460081578671653615283375596665960708242700241780342523448742861815380568359092813225600016747957517992666799497302478221946509254852979437130583539850985247422, 1717028738196915227260339129573501065417757436024070728399837662683474643676720266190852688571851260086024584528234004503770202991702828738603236485267929860326697228640681326889845794391744206929580676537615769150484083242039924741303807364343064097449659558370778499818290907827480001580408520014110979083082316647497828342236619136282585160822630608240519352654269080203964531142386474415714079196749108940162898716817139452352062000261548631825989143362746715121123292436275957550673873937398160148303975715603319819731258894296533494152025775404106195174909015831441339509280028585399046169513149752204461930349, 25139940794218635348197118071301083238188918027193611763525774422502805824030159181810808048312828586310375271390658874846166941305171889519472685469675087274773157307133820213186080599249106104274031234797703970573904818411381605617364965926619916397551349237481884885723093798237875561681274880161116978250140685000915537069110074814807782361116104719639226963741990834724296742064451257526339309855861251778350642631845345431897638639307184086434344778694684043943923041302280417162444914203825532942834207262516015206535412006876830590028421616204643350943277314562927607754616803756985741638210493640875844891960, 6452875340997852295275020218749378916760411126851936571996259386760459856313309845592392640856504175949234216794963908475913037761993360407125952607943943083700382006783091443756617877566422165299422992987336811474980284131306966940424642139162441283769172531199959298540627795873212152702317440453079566096174835647147665695679094943137671532124636863128457006714211465119286776747310503452130041649279123753848522079886216732719572247000481047269505214596261386534160935834909921155351371984109147724730932926711831690752003577272018655013647352055561080857579522667684581123594159788011149227192380455462896729962, 20897947836932076779964827384680266669444872541242595584853544810847660781809255811902379402727265984145972717558208216627868351476262475424181241317707734298108218231636329375895362429626917095073694210812814494087830535014117884013936787285440467171742761631884901929078488856204289738449061959822388725333274257861099169377435400465998662612618115681519773625182456433449001773543437767201553703283209697249003117284877232666946456539017194397166088957330100388776645543342462188483091150441369824235427061443229429025534194618806460187812446633057673388068141804189503074739767911838028579099128625845793341901127, 11585318389310082289634538436928729260761907754954731989483654384251165000197213645281370351397028539366128403662173911562239143321895246754339672995138654604980948825905276968754585440593530502031072587489418651687027546522269634035791996102885960686969316226732356317109881863779734224468395519503131972389118986368190443032576070941428487054450651328773394985517568216579647364967614926730248841713741600286001390136757473284393174512577204042060290369663604703262495330209924328523120390710228628984130500686686583318088441875055416917520119056403841430529851364998090755804939747123419334984081027473820456086396]

# for e in range(1000,2000):
#     if pow(ord('L'),e,n) == c_list[0]:
#         print(e)
#         break

e = 1924
flag = ""
for i in range(len(c_list)):
    for j in range(33,128):
        if pow(j,e,n) == c_list[i]:
            flag += chr(j)
            
print(flag)
# LitCTF{sometim3s_y0u_need_to_rever5e_your_m1nd}

真·签到

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from enc import flag
from Crypto.Util.number import *
import gmpy2
import random

p = getPrime(512)
q = getPrime(512)
e = random.randint(2,10**8)
n = p*q
c = [pow(ord(m),e,n) for m in flag]

print(f"n = {n}")
print(f"c = {c}")
'''
n = 
c = 
'''

和上题一模一样的思路，爆破时间长了点

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from tqdm import *

n = 53779688736203933047434881701980151653423802317221115318252054349550528639605402386823698507644560099402835048990108944258111185574422278737617624691459404487383205558495742477348096557609903091073482529108655721238870718736876917084894146112572318162754496404262394399247602930119945411919174294508800616891
c = [4124398080749553074619843072966405052653858760437326718059791703345965920503569739252697039258403095781261373084359291436131778873009458422798167842256401087702314540530419434366776728534830888673974354635857270349385440098865230210094489169761588857916363734220665484295067349289289937219722492065728599463, 15481644643922585500945090000695562756282558733694376113993997188985665803568510535190119480845091520658885447822873846242168965970319826752836201669345271783173616567609933032017344851978404496594310266471195858958401298265505190354107704046599872108795281982693695588930911349202457222578310220886622884416, 40974022330897595185593668062654482156370823359835540803640174599026663839070218063991563668507393666219642637135525638990455137020424754595250945054931120081475828089632764945575780326199183117119567719177117261011813697975685625263935820428233393538013872760001414320682062909650622706212810667501741354873, 33981786848660496333961506517187714554193615584845878232210394944336780137112027320577548034903832074752598242250089070169817297717880683657379700922708752551349470039462849959879736868560539774248532790598446587204581950938279079907176227710483120279719588731010982317536907131989435797059221285174093962908, 1285910717903203084975787538616625852434321550159180500468441407891029771447865370135113417284148880935400895099397662772912500923680415544536692392496640999237766173745842517211118889788913178800742948591271387743915400252547483363390245549270543581643322229638652142265779266726517677852583628198266108421, 23789203781845502389604138554793333517773526003503743390692470103394090787030629083975882919256262588645554701048271917571850719220017173479370286653555316337255808129285505861937546032314431989480012931420093894536654994001056137216516437854011401289717520452295524972795366753274063468895803833424426506331, 20940208240413900181251095272480030757105866339312310157480925947687648156412725814283553668029566232713480333831122495321031459080649522184580652548367762322620272746907156287431288132170924230190580437501883293037927765862049006329498758245604100845556492302312391684439016854521845339622400243037514523867, 41340655699032850811922590703534124397137469314819785476566566093858629648044627482514797174972386035722096563024583525376236045453451526570126890987183821072119586387364708099135124115856050119661380924186837677285512927400295146789034172166107474252827192261267643468495553148849468493009241668471083048430, 22966360367971968504676737450654736559784526278126249100481690257360113645735823869174095070763996461165850039977914727245980242307319409983699793511352248209423007808171107239738771728438094641440444300596228692729277266556257088686585351869961921410859567001968798590921194402863219621666507877820378827092, 41340655699032850811922590703534124397137469314819785476566566093858629648044627482514797174972386035722096563024583525376236045453451526570126890987183821072119586387364708099135124115856050119661380924186837677285512927400295146789034172166107474252827192261267643468495553148849468493009241668471083048430, 52202475140977838262155766391763349770007617219731559882124842701306589259283233719727463105485402530682922793511867820592726412692298060420804847173813733441078903812811823520344962843237246635665635279928926476628971734748164894875272506105775963532397945641093931037074645811860105881221105902306255621181, 43686732822375527268166781780704145014463398236959129237259540820318050928142217382482854923592727143517945840145245021402367171624497223470640246895897992745217804594441620139099576901221773322604374681094586004810027213343123533228000473640015954168594863999625384697827658129618656763377267113765657637761, 14880134921930262144875287284818967110251827510945998306349834095556559727134453367023956672529927521400098332845397865476485851088348289863395304436600667602897364946074198944367059280853856523321854848231173098875824362694147164421785094924944589659224105370845089374193840009119763660625714201229551202464, 38013516229906731040770728995532120131491416592495253746823605701526767788760134027460299370090486775327164899231056232048607749748639052414737842983659937901990208411978548025212907210373477389757182408450834322391767748006090559771843058148102090701817180898022507797050605846546948706282805015074193093273, 20524906300041996892262239459527462404196257551590250259857365607007677670540302221668693379920161363521285920275466639018409401155313360025405024607708054080526222596947953326605977964045680445269338000371617360892920017917084671528868044975804331654166128752309192614142872384593861258628748764936855953220, 20524906300041996892262239459527462404196257551590250259857365607007677670540302221668693379920161363521285920275466639018409401155313360025405024607708054080526222596947953326605977964045680445269338000371617360892920017917084671528868044975804331654166128752309192614142872384593861258628748764936855953220, 20524906300041996892262239459527462404196257551590250259857365607007677670540302221668693379920161363521285920275466639018409401155313360025405024607708054080526222596947953326605977964045680445269338000371617360892920017917084671528868044975804331654166128752309192614142872384593861258628748764936855953220, 38013516229906731040770728995532120131491416592495253746823605701526767788760134027460299370090486775327164899231056232048607749748639052414737842983659937901990208411978548025212907210373477389757182408450834322391767748006090559771843058148102090701817180898022507797050605846546948706282805015074193093273, 16822859827241912092903301050602204948222809037868347721306013629185546078070142612905867911365364682095817701589155688149474870521437581822944710801232554186762524645518382246152771387652373860849924256464746937608068511622557828364043958392814895625329426982855829366086732912276996321034036018819408951193, 34150153608686108981107806839997156875358767651869050480811448846242725270615327530663889984779854553092120823194108656627949475159285700946138204912775266363022036292515155178325852957375486496328282381365286611916449049601323101141237331480034977207188953388238873934117345088291003788988627587000440491067, 1080077289768974224514697428506714010850637431783677450886962480094680409598510781459495187524547891405762403065728309492525472661717864381505770334364496408759066160232404275108402127205833678508044742271255268139834900230068167627203821637533356900402299478531941413138234500208157822130575455493383047567, 1080077289768974224514697428506714010850637431783677450886962480094680409598510781459495187524547891405762403065728309492525472661717864381505770334364496408759066160232404275108402127205833678508044742271255268139834900230068167627203821637533356900402299478531941413138234500208157822130575455493383047567, 43686732822375527268166781780704145014463398236959129237259540820318050928142217382482854923592727143517945840145245021402367171624497223470640246895897992745217804594441620139099576901221773322604374681094586004810027213343123533228000473640015954168594863999625384697827658129618656763377267113765657637761, 1080077289768974224514697428506714010850637431783677450886962480094680409598510781459495187524547891405762403065728309492525472661717864381505770334364496408759066160232404275108402127205833678508044742271255268139834900230068167627203821637533356900402299478531941413138234500208157822130575455493383047567, 2261213433462723419446068536636649771187144868712624195878985258332075459437123191546644392841202030016957753759317962427017329871785225346154355535823733243490439256337121075737014302820285880854932463336983215343814901470468271086180806826828758278636642722717746069806141466423669570629896086040252059811, 2261213433462723419446068536636649771187144868712624195878985258332075459437123191546644392841202030016957753759317962427017329871785225346154355535823733243490439256337121075737014302820285880854932463336983215343814901470468271086180806826828758278636642722717746069806141466423669570629896086040252059811, 20524906300041996892262239459527462404196257551590250259857365607007677670540302221668693379920161363521285920275466639018409401155313360025405024607708054080526222596947953326605977964045680445269338000371617360892920017917084671528868044975804331654166128752309192614142872384593861258628748764936855953220, 1080077289768974224514697428506714010850637431783677450886962480094680409598510781459495187524547891405762403065728309492525472661717864381505770334364496408759066160232404275108402127205833678508044742271255268139834900230068167627203821637533356900402299478531941413138234500208157822130575455493383047567, 34150153608686108981107806839997156875358767651869050480811448846242725270615327530663889984779854553092120823194108656627949475159285700946138204912775266363022036292515155178325852957375486496328282381365286611916449049601323101141237331480034977207188953388238873934117345088291003788988627587000440491067, 22966360367971968504676737450654736559784526278126249100481690257360113645735823869174095070763996461165850039977914727245980242307319409983699793511352248209423007808171107239738771728438094641440444300596228692729277266556257088686585351869961921410859567001968798590921194402863219621666507877820378827092, 16264894348259769136675550067824857283471919750028043029657185995447205515644739721442713128709898468504029150415861841382906641476195752925950909219618894837821015850329001463680764039265007095540240515692665160125015606879662459432975652875535648068534926380848491577719631224890161757880802939228883185592, 1080077289768974224514697428506714010850637431783677450886962480094680409598510781459495187524547891405762403065728309492525472661717864381505770334364496408759066160232404275108402127205833678508044742271255268139834900230068167627203821637533356900402299478531941413138234500208157822130575455493383047567, 48082751893707411443030173186335305790867819509239136633531599952276619514671134605545456992422479102909480454270136006149473478156585782252929384235054442854349205489546634520955838888639404324251978615664175676633161271815457282615312198983401493084973690137353747061078161134872098033066383487860152411239, 21327622441108572162106669889096334171915319598231314927862632695081879818457106233577588661109578343720589743198154707810708496736138963401446774648179328773413409171869828838434037907816132436438314483017142493175451372700989061258496056410836951234155583628787251073520843683698565432474522538486905480145, 2261213433462723419446068536636649771187144868712624195878985258332075459437123191546644392841202030016957753759317962427017329871785225346154355535823733243490439256337121075737014302820285880854932463336983215343814901470468271086180806826828758278636642722717746069806141466423669570629896086040252059811, 21327622441108572162106669889096334171915319598231314927862632695081879818457106233577588661109578343720589743198154707810708496736138963401446774648179328773413409171869828838434037907816132436438314483017142493175451372700989061258496056410836951234155583628787251073520843683698565432474522538486905480145, 16264894348259769136675550067824857283471919750028043029657185995447205515644739721442713128709898468504029150415861841382906641476195752925950909219618894837821015850329001463680764039265007095540240515692665160125015606879662459432975652875535648068534926380848491577719631224890161757880802939228883185592, 43686732822375527268166781780704145014463398236959129237259540820318050928142217382482854923592727143517945840145245021402367171624497223470640246895897992745217804594441620139099576901221773322604374681094586004810027213343123533228000473640015954168594863999625384697827658129618656763377267113765657637761, 52202475140977838262155766391763349770007617219731559882124842701306589259283233719727463105485402530682922793511867820592726412692298060420804847173813733441078903812811823520344962843237246635665635279928926476628971734748164894875272506105775963532397945641093931037074645811860105881221105902306255621181, 6095619509559019908019352298785640301209234881314970774184941172547625244370412202107112133779358742353812823865176363562807708451451147505179327450732451736668872375390442553984797239930526165727742801338607942940231944774202087146668342653834800543503935286187760190753179319613671205950833349955049912928]

# for e in trange(2,10**8):
#     if pow(ord('L'),e,n) == c[0]:
#         print(e)
#         break
e = 9897777
flag = ""
for i in range(len(c)):
    for j in range(33,128):
        if pow(j,e,n) == c[i]:
            flag += chr(j)
            
print(flag)
# LitCTF{f9fab7522253e44b48824e914d0801ba}

little_fermat

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
from sympy import *
from secret import flag,gen_x

m = bytes_to_long(flag)

e = 65537
p = getPrime(512)
q = nextprime(p)
n = p * q

x = gen_x(p)

assert pow(666666, x, p) == 1

m = m ^ x
c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')

'''
n = 122719648746679660211272134136414102389555796575857405114496972248651220892565781331814993584484991300852578490929023084395318478514528533234617759712503439058334479192297581245539902950267201362675602085964421659147977335779128546965068649265419736053467523009673037723382969371523663674759921589944204926693
c = 109215817118156917306151535199288935588358410885541150319309172366532983941498151858496142368333375769194040807735053625645757204569614999883828047720427480384683375435683833780686557341909400842874816853528007258975117265789241663068590445878241153205106444357554372566670436865722966668420239234530554168928
'''

用费马分解法，求出来p,q，然后x很有可能是p-1，注意p是小于q的就好了

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from gmpy2 import *
from Crypto.Util.number import *

n = 
c = 

def fermat(num):
    x = iroot(num, 2)[0]
    if x * x < num:
        x += 1

    while (True):
        y2 = x * x - num
        y = iroot(y2, 2)[0]
        if y * y == y2:
            break
        x += 1

    result = [int(x + y), int(x - y)]
    return result

p,q = fermat(n)
p,q = q,p
assert p < q
d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(c,d,n)
m = m ^ (p-1)
print(long_to_bytes(m))
# LitCTF{Y0u_know_littl3_ferm4t_th3ory}

little_fermat_plus

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
from sympy import *
from secret import flag,gen_x

m = bytes_to_long(flag)

e = 65537
p = getPrime(512)
q = nextprime(p)
n = p * q

x = gen_x(p)

assert pow(666666, x, p) == 1 ** 1024

m = m ^ x
c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')

'''
n = 169522900072954416356051647146585827691225327527086797334523482640452305793443986277933900273961829438217255938808371865341750200444086653241610669340348513884285892043530862971785487294831341653909852543469963032532560079879299447677636753647721541724969084825510405349373420839032990681851700075554428485967
c = 105943762023156641770119141175498496686312095002592803768522760959533958364969985856505466722378959991757667341747887520146437729810252085791886309974903778546814812093444837674447485802109225767800488527376777153844313243366001288246744190001997192598159277512188417272938455513900277907186067996704043274199
'''

已知
$$
666666^{p-1} \equiv 1 \mod p
$$
两边同时乘方1024即可
$$
666666^{1024(p-1)}
$$

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from gmpy2 import *
from Crypto.Util.number import *

n = 
c = 

def fermat(num):
    x = iroot(num, 2)[0]
    if x * x < num:
        x += 1

    while (True):
        y2 = x * x - num
        y = iroot(y2, 2)[0]
        if y * y == y2:
            break
        x += 1

    result = [int(x + y), int(x - y)]
    return result

p,q = fermat(n)
phi = (p-1)*(q-1)

p,q = q,p
assert p < q

e = 65537
d = invert(e,phi)
m = pow(c,d,n)

x = (p - 1) * 1024
assert pow(666666,x,p) == 1**1024

m = m ^^ x
print(long_to_bytes(int(m)))
# LitCTF{It_i5_little_f3rm4t_the0ry_extends}

Polynomial

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
from secret import *

m = bytes_to_long(flag)

e = 65537
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r

Polynomial1 = p**2 + q
Polynomial2 = q**2 + r
Polynomial3 = r**2 + p

c = pow(m,e,n)

print(f"Polynomial1 = {Polynomial1}")
print(f"Polynomial2 = {Polynomial2}")
print(f"Polynomial3 = {Polynomial3}")
print(f"c = {c}")

'''
Polynomial1 = 58154360680755769340954893572401748667033313354117942223258370092578635555451803701875246040822675770820625484823955325325376503299610647282074512182673844099014723538935840345806279326671621834884174315042653272845859393720044076731894387316020043030549656441366838837625687203481896972821231596403741150142
Polynomial2 = 171692903673150731426296312524549271861303258108708311216496913475394189393793697817800098242049692305164782587880637516028827647505093628717337292578359337044168928317124830023051015272429945829345733688929892412065424786481363731277240073380880692592385413767327833405744609781605297684139130460468105300760
Polynomial3 = 97986346322515909710602796387982657630408165005623501811821116195049269186902123564611531712164389221482586560334051304898550068155631792198375385506099765648724724155022839470830188199666501947166597094066238209936082936786792764398576045555400742489416583987159603174056183635543796238419852007348207068832
c = 690029769225186609779381701643778761457138553080920444396078012690121613426213828722870549564971078807093600149349998980667982840018011505754141625901220546541212773327617562979660059608220851878701195162259632365509731746682263484332327620436394912873346114451271145412882158989824703847237437871480757404551113620810392782422053869083938928788602100916785471462523020232714027448069442708638323048761035121752395570167604059421559260760645061567883338223699900
'''

解这个方程组方程就行
$$
p^2 + q = Polynomial1
$$

$$
q^2+r = Polynomial2
$$

$$
r^2+p = Polynomial3
$$

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from sympy import symbols, solve
from Crypto.Util.number import *

p = symbols('p')
q = symbols('q')
r = symbols('r')

t1 = 
t2 = 
t3 = 
c = 

f1 = p**2 + q - t1
f2 = q**2 + r - t2
f3 = r**2 + p - t3
# res = solve([f1,f2,f3],[p,q,r])
# print(res)

p = 7625900647186256736313352208336189136024613525845451962194744676052072325262646533642163553090015734584960267587813894745414843037111074258730819958397631
q = 13103163880267648221851617296336865295731278851373488569182099549824826973560296247802058712197255433671825570972129891122274435889696663320490806634737981
r = 9898805297737495640281149403465681435952383402115255751446422784763742395898034378399391604085137196351802539935697155137226495010184322468562791581344399

n = p * q * r
phi = (p-1)*(q-1)*(r-1)
d = inverse(65537,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# LitCTF{P0lynomi4l_i5_inter3st1ng}

Polynomial_plus

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)

while True:
    k = getRandomNBitInteger(64)
    p = k**10 + 22*k**8 + 53*k**6 - 22*k**4 - 39*k**2 + 114514
    q = k**9 + 10*k**7 - 13*k**6 - 2*k**4 + 111*k**2 + 1919810
    if isPrime(p) and isPrime(q):
        e = 65537
        n = p * q
        c = pow(m,e,n)
        print(f"n = {n}")
        print(f"c = {c}")
        break

'''
n = 343424787688946710828788193478518340184635630498236346907606509763011890082198311173501834898393322176325060349656021994088578448585570427399686920253145504431065451412326430233084073651599248661762036671841142048573051549474182586297565046285161375600990596119448538118327240405957845178956427810835797220204485242640945891970398041508724313442375608608662117158013
c = 300097152084696274516003269451037367405899874736667089358316145472977115856239312841307278390995620995063953407731245808077915106161525019835875978698148238617148929170257141762407514139479267867121064342168993486529889088067645866930029787500052390195406519896658384623575160091828173111087120708969655686251340535134778177193882787257773427670338018428731395437974
'''

根据p,q产生的方式可以知道$n \approx k^{19}$，直接对n开19次方，得到的值t，再小范围爆破即可求得p,q

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
from Crypto.Util.number import *

n = 
c = 

t = gmpy2.iroot(n,19)[0]

for i in range(-1000,1000):
    k = t + i
    p = k**10 + 22*k**8 + 53*k**6 - 22*k**4 - 39*k**2 + 114514
    q = k**9 + 10*k**7 - 13*k**6 - 2*k**4 + 111*k**2 + 1919810
    if isPrime(p) and isPrime(q):
        e = 65537
        n = p * q
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(int(m)))
        # LitCTF{Th1s_i5_a_trick_for_s0lving_polynomi4l}

真·EasyRSA

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from secret import flag
p=getPrime(256)
print(p)
n=p**4
m=bytes_to_long(flag)
e=65537
c=pow(m,e,n)
print(c)

'''
c1= 78995097464505692833175221336110444691706720784642201874318792576886638370795877665241433503242322048462220941850261103929220636367258375223629313880314757819288233877871049903331061261182932603536690216472460424869498053787147893179733302705430645181983825884645791816106080546937178721898460776392249707560
c2= 3784701757181065428915597927276042180461070890549646164035543821266506371502690247347168340234933318004928718562990468281285421981157783991138077081303219
n = 111880903302112599361822243412777826052651261464069603671228695119729911614927471127031113870129416452329155262786735889603893196627646342615137280714187446627292465966881136599942375394018828846001863354234047074224843640145067337664994314496776439054625605421747689126816804916163793264559188427704647589521

'''

先把n开4次方得到p，解c1，得到信息：LitCTF{HeRe_1s_Weak_F1aG}hahahaha_____hint_is_93492332457019255141294502555555489582661562346262162342211605562996217352449

根据c2的数量级为512bit，这个hint的数量级为256bit，并且hint是素数。猜测hint是q

然后用p,q组成一个新的n，再求解c2

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from gmpy2 import *
from Crypto.Util.number import *

c1= 
c2= 
n = 

p = iroot(n,4)[0]
# 102846375519753428570573823986925744957687092615041080268232889119455234034483

phi = p^3*(p-1)
d = invert(65537,phi)
hint = pow(c1,d,n)
print(long_to_bytes(int(hint)))

hint = 93492332457019255141294502555555489582661562346262162342211605562996217352449
d = invert(65537,(p-1)*(hint-1))

m = pow(c2,d,p*hint)
print(long_to_bytes(m))
# LitCTF{R1ght_Answ3r!}

mid

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from enc import flag
from Crypto.Util.number import *
import gmpy2


m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
leak1 = p>>924
leak2 = p%(2**500)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"leak1 = {leak1}")
print(f"leak2 = {leak2}")
'''
n = 10912724749357317040117295175340915836309117326481842971911576002816136982982366412133127436929465794389631046998036509363047557873155846920275327196471118680559431161116535588318645353317739214770132790445807395653916337747136630775427171105596048281228718048314706544665819996610453587925745842345926654572410324847927833437471701176403031302117052425160845583678182335391697596801106017558494065612842298945201720733418994561321697012416704574891516720606917736854915347853341353358814869449590841870866128113400765492223847582506991200050368263722438854522124807397499067048911261448546634778788867555039834459211
e = 65537
c = 6991017300002465473760665517672638980904771950587963320768028786572848880002446111427309844155944419991711131609525886799710433964716773503883581910737560542905952516670539044167012461107915291519628081744473505479068712979401023972013124089857993361492602682730769445826818873805246777789559501477084603991595919524098203387452563401306823917989080019788620521432596833764004972429814705900915782768111621466120683534147560628509733828773006451505153520893053368254310905682981931980175859011116643271531341395883753605992130701423800808678200033639094180802506618083869818685981234182334150817211223363755511509799
leak1 = 749278395841748263310980933893
leak2 = 2675756732628494397256285826768672620995252274010849868485475743575097846941007603037228233621038664628877573057336866559545388148568450491606789423985
'''

很简单的一个p的高位和低位泄露

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

n = 
e = 65537
c = 
leak1 = 749278395841748263310980933893
leak2 = 2675756732628494397256285826768672620995252274010849868485475743575097846941007603037228233621038664628877573057336866559545388148568450491606789423985

phigh = leak1 << 924
plow = leak2

R.<x> = PolynomialRing(Zmod(n))
f = phigh + x*2^500 + plow
f = f.monic()
res = f.small_roots(X=2^424,beta=0.49)
for root in res:
    p = phigh + int(root)*2^500 + plow
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))
    # LitCTF{3b633bcc134c1d0f5c07ea7873f91c26}

你是capper，还是copper？

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
N=getPrime(2048)
p=getPrime(512)
q=getPrime(512)
n=p*q
e=getPrime(1024)
c=pow(m,e,n)
Q=q>>100
P=p<<100
a=pow(Q,5,N)
print ("e=",e)
print ("c=",c)
print ("a=",a)
print ("N=",N)
print ("P=",P)

'''
e = 13072237795424057999129127027979234989717137387957646486113645675299547455876355434346547808746552482965795288244687521108647998478307740108159933821771239011129296482617888480397978257432977308896431711182794340987048211178166823842422554472231405752077101111017727678497340027900077855145324567076470130835
c = 68627543734818005182182738951459640368220444851344171131951942770319683236026987275564911027739185775745844128612642216644533871400591052349794872565933125142881743934565729384895786720059720829738537411808512740621199697348750764033684771791461466523568130279863016302934164238161768481421610386382948741646
a = 29886515512126216731872822863342168524178804819277798137694648187535122007361698348012826864316113462619631404784701713598250504350847404704511275173569527993044728758373465323132649093666827652191127263514969054034178232381536186558882792792658400658805864317969510789325209629970510611697264690242354910697279101097076160734551272655637072457755427702327968248887832201456315670206545608108548532387404598868338062368026986272531243881152161156845992888930282181928184864800163331550035605892120822893818762473564190742360913032722805345122954472060199209651480909308623204782049913146103631197775952155897296727758
N = 30862422297928709181239751692704342665112621784469743119416634932990957784925336225419558020781912482604031494963767628422741140218194125167564890910023973751859762772564509417727807585344663605720306848651674777455957321846686766028032897935430317914513843941842612162856081647345544367930417644089939010942052714956124340450925431546635109101203596120066417771724536199794090338054127436783996371330443765655164007345152020956671886134143225546713511939703191665568669852593956318012200617631356629493372579211049274189611392878353716894836226969536226832390617104216783180964503619839420953622098097344241832069521
P=8770594378518257184819328657308152928029757169205998713929325053727701443407644651726148745366587806353078115048763121275581729457548618046203512855832519694356213899919351220281540608
'''

感觉是非预期了。

我直接把P右移100位恢复p

然后拿p求解

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
from gmpy2 import *
from Crypto.Util.number import *

e = 13072237795424057999129127027979234989717137387957646486113645675299547455876355434346547808746552482965795288244687521108647998478307740108159933821771239011129296482617888480397978257432977308896431711182794340987048211178166823842422554472231405752077101111017727678497340027900077855145324567076470130835
c = 68627543734818005182182738951459640368220444851344171131951942770319683236026987275564911027739185775745844128612642216644533871400591052349794872565933125142881743934565729384895786720059720829738537411808512740621199697348750764033684771791461466523568130279863016302934164238161768481421610386382948741646
P = 8770594378518257184819328657308152928029757169205998713929325053727701443407644651726148745366587806353078115048763121275581729457548618046203512855832519694356213899919351220281540608

p = P >> 100
d = invert(e,p-1)
m = pow(c,d,p)

print(long_to_bytes(int(m)))
# LitCTF{wiener_@nd_c0pp3r}

看flag，可能要用连分数？

男人，什么罐头我说

密文：

1
00001010 00110000 00110001 00110000 00110001 00110001 00100000 00110000 00110000 00110000 00110000 00110000 00100000 00110000 00110001 00110001 00110000 00110000 00100000 00110001 00110000 00110001 00110000 00110000 00100000 00110000 00110000 00110001 00110001 00110001 00100000 00110000 00110000 00110000 00110000 00110000 00100000 00110001 00110000 00110000 00110001 00110000 00100000 00110000 00110000 00110000 00110001 00110000 00100000 00110000 00110000 00110000 00110000 00110000 00100000 00110000 00110001 00110001 00110000 00110000 00100000 00110000 00110001 00110000 00110001 00110000 00100000 00110001 00110000 00110000 00110000 00110001 00100000 00110000 00110000 00110000 00110000 00110000 00100000 00110001 00110000 00110001 00110001 00110000

8个一组，直接把2进制转ASCII，得到

1
01011 00000 01100 10100 00111 00000 10010 00010 00000 01100 01010 10001 00000 10110

培根密码解密

1
LitCTF{MANWHATCANLSAY}

common_primes

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q1 = getPrime(512)
q2 = getPrime(512)
n1 = p * q1
n2 = p * q2
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

'''
n1 = 63306931765261881888912008095340470978772999620205174857271016152744820165330787864800482852578992473814976781143226630412780924144266471891939661312715157811674817013479316983665960087664430205713509995750877665395721635625035356901765881750073584848176491668327836527294900831898083545883834181689919776769
n2 = 73890412251808619164803968217212494551414786402702497903464017254263780569629065810640215252722102084753519255771619560056118922616964068426636691565703046691711267156442562144139650728482437040380743352597966331370286795249123105338283013032779352474246753386108510685224781299865560425114568893879804036573
c1 = 11273036722994861938281568979042367628277071611591846129102291159440871997302324919023708593105900105417528793646809809850626919594099479505740175853342947734943586940152981298688146019253712344529086852083823837309492466840942593843720630113494974454498664328412122979195932862028821524725158358036734514252
c2 = 42478690444030101869094906005321968598060849172551382502632480617775125215522908666432583017311390935937075283150967678500354031213909256982757457592610576392121713817693171520657833496635639026791597219755461854281419207606460025156812307819350960182028395013278964809309982264879773316952047848608898562420
'''

n1,n2存在公因数

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from gmpy2 import *
from Crypto.Util.number import *

n1 = 
n2 = 
c1 = 
c2 = 

p = gcd(n1,n2)
q = n1 // p
d = invert(65537,(p-1)*(q-1))
m = pow(c1,d,n1)
print(long_to_bytes(int(m)))
# LitCTF{c0mmunity_w1th_two_ciphert3xt}

common_primes_plus

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from secret import flag,a,b,c,d

assert a*c == b*d + 1
m = bytes_to_long(flag)

e = 65537
hint1 = a * n1 + b * n2
hint2 = c * n1 + d * n2
c = pow(m,e,n1)

print(f"n1 = {n1}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")
print(f"c = {c}")

'''
n1 = 72619153900682160072296441595808393095979917106156741746523649725579328293061366133340736822282117284050717527134297532031234706715551253283030119063143935874516054785948327252045453986903379262257406260016876625891582923191913450785482873961282498295762698500898694660964018533698142756095427829906473038053
hint1 = 115150932086321440397498980975794957800400136337062771258224890596200580556053305338941267789684878816176014493153795643655219028833232337281425177163963414534998897852644398384446019097451620742463880027107068960452304016955877225140421899265978792650445328111566277376529454404089066088845864500514742797060500618255170627
hint2 = 166820160267525807953634213157298160399912450930658918773153592459310847514047652216110562360456335336533080444219104489314586122760398361430693763814336759476811490524054588094610387417965626546375189720748660483054863693527537614055954695966458622029711055735399842018236940424665041143785192280089418185085532002136215976
c = 28378912671104261862184597375842174085651209464660064937481961814538145807266472966765374317717522401362019901110151858589886717440587644003368826809403188935808872400614919296641885383025657934630410406898092262104442977722339379234085663757182028529198392480656965957860644395092769333414671609962801212632
'''

本题有点非预期的感觉。

c的数量级为1022bit
$$
ac = bd + 1
$$

$$
hint1 = an_1 + bn_2
$$

$$
hint2 = cn_1+dn_2
$$

假设n2 < n1则：
$$
\frac{hint_1}{n_1} = a
$$

$$
\frac{hint_2}{n_1} = c
$$

这个推导有点问题，要建立在$b,d$都很小的情况。求出a,c之后就可以求n2，然后gcd(n1,n2)可能会有p，没想到真求出来了

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
import gmpy2

n1 = 
hint1 = 
hint2 = 
cipher = 
e = 65537

a = hint1 // n1
c = hint2 // n1

tmp1 = hint1 - a*n1
tmp2 = hint2 - c*n1
n2 = gmpy2.gcd(tmp1,tmp2)

p = gmpy2.gcd(n1,n2)

q = n1 // p
d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(cipher,d,n1)
print(long_to_bytes(m))
# LitCTF{th1s_i5_a_adv4nced_c0mmon_prim3s}

可能的预期

$$
hint1 = an_1 + bn_2
$$

$$
hint2 = cn_1+dn_2
$$

把$n_1,n_2$写成$pq_1,pq_2$的形式，于是得到
$$
hint1 = apq_1+bpq_2
$$

$$
hint2 = cpq_1+dpq_2
$$

简单看成
$$
hint1 = k_1p+k_2p
$$

$$
hint2 = k_3p+k_4p
$$

于是gcd(hint1,hint2) = kp

用divisors去分解，找到512bit的素数，作为p

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
import gmpy2

n1 = 72619153900682160072296441595808393095979917106156741746523649725579328293061366133340736822282117284050717527134297532031234706715551253283030119063143935874516054785948327252045453986903379262257406260016876625891582923191913450785482873961282498295762698500898694660964018533698142756095427829906473038053
hint1 = 115150932086321440397498980975794957800400136337062771258224890596200580556053305338941267789684878816176014493153795643655219028833232337281425177163963414534998897852644398384446019097451620742463880027107068960452304016955877225140421899265978792650445328111566277376529454404089066088845864500514742797060500618255170627
hint2 = 166820160267525807953634213157298160399912450930658918773153592459310847514047652216110562360456335336533080444219104489314586122760398361430693763814336759476811490524054588094610387417965626546375189720748660483054863693527537614055954695966458622029711055735399842018236940424665041143785192280089418185085532002136215976
cipher = 28378912671104261862184597375842174085651209464660064937481961814538145807266472966765374317717522401362019901110151858589886717440587644003368826809403188935808872400614919296641885383025657934630410406898092262104442977722339379234085663757182028529198392480656965957860644395092769333414671609962801212632
e = 65537

kp = gmpy2.gcd(hint1,hint2)
for i in divisors(kp):
    if i.bit_length() == 512 and isPrime(i):
        p = i
        q = n1 // p
        d = gmpy2.invert(65537,(p-1)*(q-1))
        m = pow(cipher,d,n1)
        print(long_to_bytes(m))
        # LitCTF{th1s_i5_a_adv4nced_c0mmon_prim3s}

CRT

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
e = 10

n_list = []
c_list = []
for i in range(10):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(m,e,n)
    n_list.append(n)
    c_list.append(c)

print(f"n_list = {n_list}")
print(f"c_list = {c_list}")

'''
n_list = 
c_list = 
'''

中国剩余定理之后，对C开10次方即可

exp.sage

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2

n_list = [16284549467215459860410219597024063610473673936290355100056351270928590364613988243842136274404316005691228851657707321037165033870804113001550943722154728825877813376691406849932899693973387282799799300076386870984605589385666352824740622229871992727011987847056429850720207816048044538068625281977059392365698031140268787802886018698622326103590834314940280191560618753408741810842189500991556860816195814550884416201667771827582907240044216817705876129993030771943110090291383205720587816820335839616491257078918258839986942101986011761809815192713499542329037877195448381127272183807358011340669666067708631770629, 18874449316683637715798227591079994715220250787784886038879393543606786017564740000007881151950098752600868917271951840433212429335449734520464340460962870875528399394278620757114832553403790578599857545045548782264680469899469733610229824411943119032419052885845035690046611519195843721184869834557481917675133504256150187042147269721516549831707784660343957497462516302534697915170087780048689613921549811073805796084838801677337285061667687328043565589734203160196445644144798845303226939960633632967262794622796927905511547760465906600293964201276584199569541295613430382495278352554280248372584117917520373403063, 13076908038170870040678205430512292701702182383746502395067907294908791921755288520053025319156015431312084703402938465525746196078114225446604200656116848235842943713613538425047483331236843707852400888407037547782069810250229035895403347555287877301409523248658733500963325361631821388259137561613536275954710848967383282290486421290937700396986650186236373076267188846407623991396459884128392118502565707689494271484411270172764553747426536404781904379621870642658609027074757591034785814602602669666257742808888301912575857074138613714693225934811254682687014167022418837710552784925328161453554291397460324648009, 16378397749449315054623854181248970586445531404081850673625192835136416152712968780451149412408644689393643801969477034418829482292894114547339155149570026460766659623960243723741437212596779580161767297321149670682427000047000712397718946486472118638780090056091542235702825736985864963592363421943353726975184567975451918105247987573044010599149673027905021130138957885113596669923366241161695565837122963976988635649640547443201925034845002113548522307980664206158188711548845245115694530280375848933481227411503982144621846732228815377656607983358898296200251680387871097014543693213877074718748683243193584032307, 16561385664507310659703460597815131331175620854125898893505075859155749890511144622913872488783791188180242785479319865960633526830814389031162024199864660323116594980719331106368397062852472114748955889862650270563487466194545102072373606964935390400328607060427961354290055443710114639781630071832997101380097322119243847190066266823291236828718017385537809056374392924015081117151158033309950857254309859691442649968222489177513517837849318096762149934959873646750864750378500351560253453052870424424427631414365680967482680769587570457938750679258205430151223470761518748987038822469422647137405393267829437115661, 27046459277694602448592524332290812177367631061914086306537115904955610821120392893033090428641088790759783810505225125618182431554899875183961418066959811832057748013953098277804562621152445358481976221983179988257658622392669474721482514871569548645762057681213193026792187879687736985533503283192537252904253565317763028483404018596514523171644666753183517320602643087213777450193062371986178076259168860180486748722567326484282893069173271762518110920685267104269429407229859993484209639764440874444582271870147714648808732931399985199947422716048582921727875237459841962093669408116061538502016560235135864203187, 26656304012303785684433399162699704691814095671158676770279115782799819097401667611247727555104978633884125246262630572285699884039990597392442760154412046297340436752418017863089245998557221143069544231044947583991838381529081774245290065442299808728542273138931461712874414662570197142795674160946728850452526786804787060582942714635903943088540232346797109678405554499677459722287119125623191067780196726820726456507802067342186435679967664032334075189916733352409403602499298544374351405005339596410771187606377781063995755795494682971576602822244457151090982442689870155439418641987576796032975032982289138437523, 15430339362720939092241771692575439580654810089653970198317149114896596238037181680990393763581287618371554846982066535980062263001619707606585504112155505335852802431392213092366756058196440934454810685146101829974548748060332228708229146991380736668433937967747468330692411917426038703359064546899782163287526256750039064809093426968389929333819191207284079703677535201724530391246890003928025687520199553868464322185815354591044585221486768114570373992719977614232251764409893171263639718616620216630797031237033969290978218328767317279717825174597882707772846934097838694418308236053838800414834627456689940059791, 18567217334857361786819913577261265078968886790989901098066320191741355103505838160569648197557648144402318678198622602821398215265062903833980611331991924162821902705417905758829862021425828310098183855605162264362860669298956185657733562472361876121183146316333113433547558152618165933865808900552444816088227098441082165477634812598644531670232452276788291537671779564658425789722419032860803991282640262179618723470437500425645011269733791887608702964571393657348573277992781115199432229176320688981128912052074722348557580462855962547978505669490105804175211061178124988260957275350940324541120102820024607088877, 10779265483116424102513175333888918968735912126282080716409998310381429332303237383487628664073567555863832134055945636657550074126628975203541323090803941066893475056319351674995896497450955897099614503220268400135112031310669044989879413178359759130908036871112663414065113664951350386824618325532532761206110118269005313068956882540007289422776225718534047101012876346009269097785027585782628699252006893938086064139042361425306202870627629615292450559291783382487842611805623198422252868756644595549320868144393828052610953995595915294930701560599016888539448223935199483656756326744914184772404419968728372785709]
c_list = [644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049, 644471004204038587358576160407417490938643306027967868486894032686145771114614076076527690366372762614045209015175209880518279715723521182568975220993976451106760236390912778371250746699463366097164369672789316408520079193370191810477580463635224092686607896863852671881543817329521589324466628227730589108339783619357530316049670209743367574983963078106666377633552745384690084183804939047320711873053569717432670155045869610477526046503868585690544254566603491357805849009447674789480061139157433156989123228768899846183291164697221164452100037658563026884070301188916984245139290761779580443049]
e = 10

C = crt(c_list,n_list)

m = gmpy2.iroot(C,10)[0]
print(long_to_bytes(int(m)))

CRT_plus

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import *
import random
from secret import flag

m = bytes_to_long(flag)

e = 5
A = [random.randint(1, 128) for i in range(e)]
B = [random.randint(1, 1024) for i in range(e)]

C = []
N = []

for i in range(e):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(A[i] * m + B[i], e, n)
    N.append(n)
    C.append(c)

print(f'A = {A}')
print(f'B = {B}')
print(f'C = {C}')
print(f'N = {N}')

'''
A = [126, 48, 16, 72, 118]
B = [1015, 838, 454, 322, 287]
C = 
N = 
'''

Hastad’s Broadcast Attack

而且本题类似2020羊城杯——INVITATIONS

在NSS里找个exp跑就行

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import bytes_to_long,long_to_bytes
import gmpy2

A = [126, 48, 16, 72, 118]
B = [1015, 838, 454, 322, 287]
C = [, , , , ]
N = [, , , , ]
e = 5

# step1
n = prod(N)
# step2
temp = [[1 if k == i else 0 for k in range(5)] for i in range(5)]
T = [CRT_list(temp[i],N) for i in range(5)]
# step3
R.<x> = PolynomialRing(Zmod(n))
# step4
f0 = (A[0] * x + B[0])^e - C[0]
f1 = (A[1] * x + B[1])^e - C[1]
f2 = (A[2] * x + B[2])^e - C[2]
f3 = (A[3] * x + B[3])^e - C[3]
f4 = (A[4] * x + B[4])^e - C[4]
# step5
g = T[0]*f0 + T[1]*f1 + T[2]*f2 + T[3]*f3 + T[4]*f4
# step6
g = g.monic()
# step7
roots = g.small_roots(X=2^432,epsilon=0.05)
for i in roots:
    flag = long_to_bytes(int(i))
    if b"Lit" in flag:
        print(flag)
        # LitCTF{Y0u_know_broadca5t_att4ck}

暗号-paillier

没给源码。根据题目，猜测是Paillier

先了解一下Paillier的流程

首先是密钥生成

  1. 随机选两个大素数$p,q$，满足$gcd(pq,(p-1)(q-1)) = 1$，且$p,q$长度相同（安全性高一点）

  2. 计算$n = pq$，以及$\lambda = lcm(p-1,q-1)$，即$\lambda$是$p-1$和$q-1$的最小公倍数

  3. 随机选择$g \in Z_{n^2}^*$，表示$g$为$(0,n^2)$中的正整数，g还需满足$gcd(L(g^{\lambda} \mod n^2),n) = 1$。后面发现$g = n+1$满足条件，可以直接取$g = n+1$

  4. 定义$L$函数：$L(x) = \frac{x-1}{n}$，计算$\mu = (L(g^{\lambda}\mod n^2))^{-1} \mod n$

  5. 公钥为$(n,g)$，私钥为$(\lambda,\mu

然后是加密

  1. 明文$m$，满足$m \in Z_n$

  2. 选择随机数$r$，满足$r \in Z_n^*$

  3. 计算密文$c = g^mr^n \mod n^2$

然后是解密

$m = L(c^\lambda \mod n^2)×\mu \mod n$即$m = \frac{L(c^\lambda \mod n^2)}{L(g^\lambda \mod n^2)} \mod n$

具体详细的过程可以看网上的文章，比如这篇:应用密码学 | Paillier同态加密算法简介 - 知乎 (zhihu.com)

然后我们关注Paillier一个很重要的性质：Dec(enc(m1)*enc(m2)) = m1 + m2

dec代表解密，enc代表加密

根据这个特性，我们可以先输入00进行加密，此时服务器返回的值记为c0，然后获取encrypted_flag

把两者相乘得到c0 * encrypted_flag % n**2(模$n^2$是根据加密过程来的，这一步对本题没影响)，再让服务器解密，这个时候得到的将是$flag + 0 \mod n$

根据提示说的flag的长度大于32，而n只有256bit，所以交互两次，然后CRT即可得到flag

exp.sage

1
2
3
4
5
6
7
8
9
10
n1,g1 = (81799017563765125514504527052003913366173623814176603242422896521422153967173, 81799017563765125514504527052003913366173623814176603242422896521422153967174)
m1 = 0x7b94db288b117535425513fd7a8cbb5a67e95cc3542387061c4c43a148421d4f
n2,g2 = (89860077733933248166879987690896750588749886442467961686119236675688758633379, 89860077733933248166879987690896750588749886442467961686119236675688758633380)
m2 = 0x18c63c2c4a64416bc265c17f821ab854e4b60ab75b654f9503b7bf8ce3354c17
M = crt([m1,m2],[n1,n2])

from Crypto.Util.number import *

print(long_to_bytes(M))
# Litctf{A235E5DF-0E8B-D361-D1D4-60F7E25345AA_this_is_Paillier!!!}
-------------已经到底啦！-------------