低加密指数广播攻击

介绍 #

向一个群体，使用了相同的加密指数，对同一个消息进行加密发送，即 n，c 不同，m，e 相同，可以使用中国剩余定理求解

题目 #

flag = 'flag{******}'
e = 13
n[0] = 125555486791884560550086293758712483294510553604123519820907020215034995204390948081864439539909169296492177365235090384993072772138361359041765927316343490532738831918870696932710694270916806965315587461692983744021352859105991836739783213149047996149309892957265100172211808806855993047183329176918476277943
c[0] = 47985569888451044875834999419693114861280107318544860754113780012532140642673053441707087040282426588992596723953200758593209986877560329799805308131470882809965962453230745638224460112819244548496592643359269646263150981650722710403348583341824538859229153500953920166092770596758267149672456076095705688676
n[1] = 112883266462445425802434919418873471090248803163688234621801401415102456833761636004089567693154693499526779404083395825758197457394510713501221716047101003306739104992510287961020463484275341827406714393355960313608298578691669591088847249751781402136271752915097598418731653272218245292196912328247036851531
c[1] = 46936678784825428013905083837174505377012515764570128419415678190582232833261987416426758984350908316097335085597164285720546198677295231015076773949878880531028398636102852522367567059524890358991293212414090037991613098577614012870049308493226860998087642998605167577262856491838885313581336598650389383698
n[2] = 141891435774484135253511040721977018354351862998913169440118302699252537213981567646087964573241310102453274932048075979968352040320740148813228798031283100948477567349375966058780737436321276511283869440655442974624195780417975458458216902203018955858756824439727628043859418703644560387224538015692863377441
c[2] = 30319416754155381786393273784558838748605102476110732553896390422331423008056170393289663632073894997311764704968248364641795159787530087623808642702359859579892482398013892706721435644985530357751013038996746838520539774047599915465689212212505739233428198721612660545819402246874358724906859780647555029076
n[3] = 141317275786967099118542015277041196217188680521986966466508435934476693997288152751129086261469948905525476866366039861705536278828084284078392086948582779261396025576743303042453843528085686087907607370299535322822936337945188187326861089109467095954514186370284149230185424519163694478794525801944003578189
c[3] = 105181475292346726733036498428815453788683853491512459229097908320044584572903359994502866246149103775202863978346711216048869827311033131243018044824858737992075077934965099924950777144650896422762676106846892545313103560801720862361244603560139169052564653670237081726232991337801130794953501225040539640090
n[4] = 154573474384962240035047976381058996392353118375867886715307375788266986784203900163875932804802696271642077242296813812769960796059732225429555976731213011318783567454920370043493629259763484347274852953527788384400305084480690803023575032106591477086913360746534962846302890690214188327604713600734360952343
c[4] = 109593969556984351842620118572315298033420938047374461051453149475406201310207678225379542217626076252306567208006153514081458047612743320062710856486199549114571707486140605839412348792664469193905188596391215294425137377815284687633404218786555343578490365493535988882305923447144114851835047505321433754615
n[5] = 141868209896583481644438896377575235782325347583451906249705924736692551303303330136636427543850825881248606426778414988800788214400042998635979082207429559923014906988949420387851157976903350105064751496036382885130411424952083235845740295404762083228786900200610139445787134627623585931615544503097123111127
c[5] = 68412839850036388547704077738465408846304295926494397797830509868276768727296453864892495409182044283915755962560042656432301401002639949469912633619260824917634088948361533826181901533174694487097266815236120251863358079110301232306430079540017828592004431768106587207890107777450972075786513119426723782793
n[6] = 131962494917764778496012283189503013226635436798020622332024982884859913900595471642568631185708361970072636304088622803559869546249273314661090353617795219913102433369307391428622317321829132615326610197287558941772755012371434895252005218033806411346526124179859436604512822449481303632635058103149463328733
c[6] = 107382230607815539153054561533944551741393661795304903588564340109395814668893871143054931011435980884739608826669167798067504098654243917639791202646471416796617695579526070997409324229440529897831434906126323510278305445951276506412672248585491384087094030683715120519801662432257911356845996674339833558344
n[7] = 168354327623343637509464988139733705126691323150440059423973046485867854620292430303242749907653188313076916690802044847801061852804141022724523010541256081035760143817365344638570547216627509013355038232767842841914274692026787497094356285310019672547751105319324003212263824064644522434404826868928141649937
c[7] = 87312041667167879938644978553255389969861034888702618958126674691301644883609383042457794162172845551994604628966053868419836495333520997539366345596272542275943972638233820513142088353490560812999165809482473636473735371967431269964444045076864441555247313901513446392359385947061406334455913758230610313379
n[8] = 112505382706826100948865870136508406813591439834964471850595747058146612900374112289748301292904623920891395528812660872404400181693496383798011319064451601662124876579532042712469171633051363393884464990856719487149851571837405748451113858260707448448834019697930740061824971134930237920695727669670057756343
c[8] = 27026836341384400752477829514398995059065216828477308362436179009713720854890107915855854011508891147788688830475245731024687073350439109511564633992820140999386430738401654394758030041961934903937498525894610734110118464359999763831284549228234520284159792502027620940425089686670849818512355789390698860725
n[9] = 134803300873444115285551658371041993653859511462236710928524237114466007394967358533248484641612876621298959586473135047997191990242794617765145338002677372422807177049620773214005105309892899242644557063099403473326259622351347190697391800015454386557557505090875814084283051931987026667230183319194373776843
c[9] = 87908911254659252200138393296025901300613844177700832422208536887886634094000727023092781134821774617084398012377589777799051270993705505929161947245999525817644738986397892405298044971042612242103678025801557240724611548947081914702262016033612827534525596059524942376474035301638102357547372998067909576155
n[10] = 135003685107553613484440333357724358049336421471894331224713204893408096655257854571639259933509156503800076616777921439985354621857930875758615726686573523823868827516393421013775032219919603522955615479164339781749451079548041357613801233979170028123816393936688658019972278626072167306617977353239540808439
c[10] = 47749231170929223098536641527116759130616321402723589292012483416622985539678686997190425715886241990155937320850958212070112948881665222779112313010441280954856893386672047249882218601029707177013337424735423117891683102068276780958796911579677205463567257946047276649478555742285991469192869042220796664340
n[11] = 143842122021226602598402348604722013159913905048093528969239895117462881577099433633398546162669165932678977618203657664514070842362733464025257687580619781892584579524306810038271872404249818378209765262934712913754871901959719138614103557995406036019956879085986403366995886878175104752928022429312455071261
c[11] = 40188944062758207789374764497229013486027845991197846276680534377154607161336890858282175507374739900596900448305893469849740240079660894040193732483705430387058183852203712454129091275544214794526593559116536100264569948756809174125350537188477043699378536990153267720824041937166729050752778812258644593783
n[12] = 151876421561086041766058272155488539361648665633305003745959449032546495049159583975217808514614373163582580024268523011793131622189336234658095852135675474511819799997749205054832576450000518037088593161090984148860671276682657782103191741557105531662557083243191308312358122543540701245578777624830519913407
c[12] = 61715481793179434386204123545434472455167488202643735827987774706694119799011592891052732712639476515596322238800544940973507687712739826693430950989456133858000916201776575965490887692270588136126043577889158945382871312620702232836775227078809520696414770841498652623478396278505564849751130064926018053684
n[13] = 135016017018948889892048077249861491427352902732332516945637226790898648225663837569282687534364366720233352891460740377822386643847103327572343806660476560232499273717295242461153887132846279800653763024858720608921581505544729802871411203869802569242521343789275867774497637036110200640123645725979190183839
c[13] = 68565704227733669950636398347662221636657372004548730227084295963458161495355972469434823892237128525015532669862457389948907388480271637497428680042093643646043299691344439877484774299326019688577752189931461410692252412628771116225934663408435090805821074043516578571069931431644167754579448079451350700371
n[14] = 113617407069768718815568962087960271189063680447715859867460683191555851040807389458227997123072019644417236586676984950862411795377024992433100418870908970649855403566857611231431431938666855318046141236903014237486725116950814567032217850474391145519548123511512152874525317839149559675140909304158309368249
c[14] = 22420067924577024371212816540053263625334466227156509518088868639627017202370946558909539519132862931889664835464953788170309406828810581854594900970162730882544579983361507946160161827121700109721709458936368787493714016904757193455561247606914263673762059209294384255106246945972387596118582294356346152090
n[15] = 142964256697842595875726567523655036262719517971688933644150057302331972969009499317404642176995816605575245035431843384954943500580505844169834763702905511413461076111098342691213799048457893917322364457662739680843566249304110991689706932146469604618447377431130459013761433613394766792797269374487657274263
c[15] = 29296328371708756614952060672336699915653877998161762759300006889694985600479897782631944509031428641239305565320135675495502103290482334232859799321140440910761400830595823312071796468217334802230008314008727836228061620500354484233024143148813015984403480953520854808313238808795398635692172533655746386394
n[16] = 142512510657073273778974294710511553063187223481953597629101021239354784652123873737019870881002085066507828639267359636234516890750919418616517458479021334808058572707196658887914111480601364376793894020789271696715384378180886645830785938849363190151918033826415737484868530078421282705813412286419554086159
c[16] = 36258067373877105825055087493773088880305319143163425991802501933592307634380565282211792536203349189146260447850666488075593005988144091839363944118216422232321032023187550701341956217683120682286236821157044056789207847505973325335487617141876394158040170302511026147698140117870936078053149940693809742344
n[17] = 102533335494389392218090303604786825301160249511835750951539887595950113542294097548480828631584449025777895886056739168311356354112944193554125469014191460217511098299228148720240631680208416303682061231842176710265170164701926774972275949411579750112583283495239062063864399525977165271427381589747953436631
c[17] = 3860830094490961085752930884310966690918909746779021840910765828272134765906916258416361041880241208337797182124709475409638427184157760682062239499378258139634870508832957715200906725559847289585974782965946274822184675941355910172994426277285817711407659299873774679529467353447340574476173095090997270887
n[18] = 93097135723163336847586617493687161480054327293298516195605188721713074772196301777516304975195728152915409458804701511060816216467740400187574307448990662189172679995988813287442315109673935739807537289999442702392212067453489314621577211533367402111172994889702662484284368528960831716715092315215045825889
c[18] = 58174930659603530051481089696633182639458958436222609892129088639113327368911105551511748550690912984592653380933017502134980761460623474839151362671442618757892193516120069483995146320454008624814011679255342019163335555032690250948599813711603812851179611383594880308670070294772541300929900936407942446206
n[19] = 144433370570770095167735345888539043699876517597114505863411096023274087944757777877426454857528133446258009694532035411730285329907095877944735687824248690700545076260122879413162485910119218187406100726941124563382230343790472703035275965860068538362112460159627364967177261108925146517058656137775109299597
c[19] = 44079089028711152982021028496891544027497861560917278801060597134507130629029590138353932484080222751995776415833575786219736764105345566270091010823997065161186675184474098872736189906830945504257759361652735423910178644048032275677684693137034101100555989481630131431167092816069402540842828905339322687933

思路 #

使用中国剩余定理求解以下同余方程组，同时对m^e进行爆破 ci = m^e mod ni

答案

from libnum import invmod, gcd, n2s
import gmpy2

def CRT(residues, moduli):
    # Compute the product of the moduli
    M = 1
    for m in moduli:
        M *= m

    # Compute the solution using the CRT
    solution = 0
    for i in range(len(moduli)):
        mi = M // moduli[i]
        mi_inv = invmod(mi, moduli[i])
        solution += residues[i] * mi * mi_inv

    # Reduce the solution modulo M
    solution %= M
    
    return solution, M

# Define the moduli and residues
moduli = [
    125555486791884560550086293758712483294510553604123519820907020215034995204390948081864439539909169296492177365235090384993072772138361359041765927316343490532738831918870696932710694270916806965315587461692983744021352859105991836739783213149047996149309892957265100172211808806855993047183329176918476277943, 
    112883266462445425802434919418873471090248803163688234621801401415102456833761636004089567693154693499526779404083395825758197457394510713501221716047101003306739104992510287961020463484275341827406714393355960313608298578691669591088847249751781402136271752915097598418731653272218245292196912328247036851531, 
    141891435774484135253511040721977018354351862998913169440118302699252537213981567646087964573241310102453274932048075979968352040320740148813228798031283100948477567349375966058780737436321276511283869440655442974624195780417975458458216902203018955858756824439727628043859418703644560387224538015692863377441,
    141317275786967099118542015277041196217188680521986966466508435934476693997288152751129086261469948905525476866366039861705536278828084284078392086948582779261396025576743303042453843528085686087907607370299535322822936337945188187326861089109467095954514186370284149230185424519163694478794525801944003578189,
    154573474384962240035047976381058996392353118375867886715307375788266986784203900163875932804802696271642077242296813812769960796059732225429555976731213011318783567454920370043493629259763484347274852953527788384400305084480690803023575032106591477086913360746534962846302890690214188327604713600734360952343,
    141868209896583481644438896377575235782325347583451906249705924736692551303303330136636427543850825881248606426778414988800788214400042998635979082207429559923014906988949420387851157976903350105064751496036382885130411424952083235845740295404762083228786900200610139445787134627623585931615544503097123111127,
    131962494917764778496012283189503013226635436798020622332024982884859913900595471642568631185708361970072636304088622803559869546249273314661090353617795219913102433369307391428622317321829132615326610197287558941772755012371434895252005218033806411346526124179859436604512822449481303632635058103149463328733,
    168354327623343637509464988139733705126691323150440059423973046485867854620292430303242749907653188313076916690802044847801061852804141022724523010541256081035760143817365344638570547216627509013355038232767842841914274692026787497094356285310019672547751105319324003212263824064644522434404826868928141649937,
    112505382706826100948865870136508406813591439834964471850595747058146612900374112289748301292904623920891395528812660872404400181693496383798011319064451601662124876579532042712469171633051363393884464990856719487149851571837405748451113858260707448448834019697930740061824971134930237920695727669670057756343,
    134803300873444115285551658371041993653859511462236710928524237114466007394967358533248484641612876621298959586473135047997191990242794617765145338002677372422807177049620773214005105309892899242644557063099403473326259622351347190697391800015454386557557505090875814084283051931987026667230183319194373776843,
    135003685107553613484440333357724358049336421471894331224713204893408096655257854571639259933509156503800076616777921439985354621857930875758615726686573523823868827516393421013775032219919603522955615479164339781749451079548041357613801233979170028123816393936688658019972278626072167306617977353239540808439,
    143842122021226602598402348604722013159913905048093528969239895117462881577099433633398546162669165932678977618203657664514070842362733464025257687580619781892584579524306810038271872404249818378209765262934712913754871901959719138614103557995406036019956879085986403366995886878175104752928022429312455071261,
    151876421561086041766058272155488539361648665633305003745959449032546495049159583975217808514614373163582580024268523011793131622189336234658095852135675474511819799997749205054832576450000518037088593161090984148860671276682657782103191741557105531662557083243191308312358122543540701245578777624830519913407,
    135016017018948889892048077249861491427352902732332516945637226790898648225663837569282687534364366720233352891460740377822386643847103327572343806660476560232499273717295242461153887132846279800653763024858720608921581505544729802871411203869802569242521343789275867774497637036110200640123645725979190183839,
    113617407069768718815568962087960271189063680447715859867460683191555851040807389458227997123072019644417236586676984950862411795377024992433100418870908970649855403566857611231431431938666855318046141236903014237486725116950814567032217850474391145519548123511512152874525317839149559675140909304158309368249,
    142964256697842595875726567523655036262719517971688933644150057302331972969009499317404642176995816605575245035431843384954943500580505844169834763702905511413461076111098342691213799048457893917322364457662739680843566249304110991689706932146469604618447377431130459013761433613394766792797269374487657274263,
    142512510657073273778974294710511553063187223481953597629101021239354784652123873737019870881002085066507828639267359636234516890750919418616517458479021334808058572707196658887914111480601364376793894020789271696715384378180886645830785938849363190151918033826415737484868530078421282705813412286419554086159,
    102533335494389392218090303604786825301160249511835750951539887595950113542294097548480828631584449025777895886056739168311356354112944193554125469014191460217511098299228148720240631680208416303682061231842176710265170164701926774972275949411579750112583283495239062063864399525977165271427381589747953436631,
    93097135723163336847586617493687161480054327293298516195605188721713074772196301777516304975195728152915409458804701511060816216467740400187574307448990662189172679995988813287442315109673935739807537289999442702392212067453489314621577211533367402111172994889702662484284368528960831716715092315215045825889,
    144433370570770095167735345888539043699876517597114505863411096023274087944757777877426454857528133446258009694532035411730285329907095877944735687824248690700545076260122879413162485910119218187406100726941124563382230343790472703035275965860068538362112460159627364967177261108925146517058656137775109299597,
    ]

residues = [
    47985569888451044875834999419693114861280107318544860754113780012532140642673053441707087040282426588992596723953200758593209986877560329799805308131470882809965962453230745638224460112819244548496592643359269646263150981650722710403348583341824538859229153500953920166092770596758267149672456076095705688676,
    46936678784825428013905083837174505377012515764570128419415678190582232833261987416426758984350908316097335085597164285720546198677295231015076773949878880531028398636102852522367567059524890358991293212414090037991613098577614012870049308493226860998087642998605167577262856491838885313581336598650389383698,
    30319416754155381786393273784558838748605102476110732553896390422331423008056170393289663632073894997311764704968248364641795159787530087623808642702359859579892482398013892706721435644985530357751013038996746838520539774047599915465689212212505739233428198721612660545819402246874358724906859780647555029076,
    105181475292346726733036498428815453788683853491512459229097908320044584572903359994502866246149103775202863978346711216048869827311033131243018044824858737992075077934965099924950777144650896422762676106846892545313103560801720862361244603560139169052564653670237081726232991337801130794953501225040539640090,
    109593969556984351842620118572315298033420938047374461051453149475406201310207678225379542217626076252306567208006153514081458047612743320062710856486199549114571707486140605839412348792664469193905188596391215294425137377815284687633404218786555343578490365493535988882305923447144114851835047505321433754615,
    68412839850036388547704077738465408846304295926494397797830509868276768727296453864892495409182044283915755962560042656432301401002639949469912633619260824917634088948361533826181901533174694487097266815236120251863358079110301232306430079540017828592004431768106587207890107777450972075786513119426723782793,
    107382230607815539153054561533944551741393661795304903588564340109395814668893871143054931011435980884739608826669167798067504098654243917639791202646471416796617695579526070997409324229440529897831434906126323510278305445951276506412672248585491384087094030683715120519801662432257911356845996674339833558344,
    87312041667167879938644978553255389969861034888702618958126674691301644883609383042457794162172845551994604628966053868419836495333520997539366345596272542275943972638233820513142088353490560812999165809482473636473735371967431269964444045076864441555247313901513446392359385947061406334455913758230610313379,
    27026836341384400752477829514398995059065216828477308362436179009713720854890107915855854011508891147788688830475245731024687073350439109511564633992820140999386430738401654394758030041961934903937498525894610734110118464359999763831284549228234520284159792502027620940425089686670849818512355789390698860725,
    87908911254659252200138393296025901300613844177700832422208536887886634094000727023092781134821774617084398012377589777799051270993705505929161947245999525817644738986397892405298044971042612242103678025801557240724611548947081914702262016033612827534525596059524942376474035301638102357547372998067909576155,
    47749231170929223098536641527116759130616321402723589292012483416622985539678686997190425715886241990155937320850958212070112948881665222779112313010441280954856893386672047249882218601029707177013337424735423117891683102068276780958796911579677205463567257946047276649478555742285991469192869042220796664340,
    40188944062758207789374764497229013486027845991197846276680534377154607161336890858282175507374739900596900448305893469849740240079660894040193732483705430387058183852203712454129091275544214794526593559116536100264569948756809174125350537188477043699378536990153267720824041937166729050752778812258644593783,
    61715481793179434386204123545434472455167488202643735827987774706694119799011592891052732712639476515596322238800544940973507687712739826693430950989456133858000916201776575965490887692270588136126043577889158945382871312620702232836775227078809520696414770841498652623478396278505564849751130064926018053684,
    68565704227733669950636398347662221636657372004548730227084295963458161495355972469434823892237128525015532669862457389948907388480271637497428680042093643646043299691344439877484774299326019688577752189931461410692252412628771116225934663408435090805821074043516578571069931431644167754579448079451350700371,
    22420067924577024371212816540053263625334466227156509518088868639627017202370946558909539519132862931889664835464953788170309406828810581854594900970162730882544579983361507946160161827121700109721709458936368787493714016904757193455561247606914263673762059209294384255106246945972387596118582294356346152090,
    29296328371708756614952060672336699915653877998161762759300006889694985600479897782631944509031428641239305565320135675495502103290482334232859799321140440910761400830595823312071796468217334802230008314008727836228061620500354484233024143148813015984403480953520854808313238808795398635692172533655746386394,
    36258067373877105825055087493773088880305319143163425991802501933592307634380565282211792536203349189146260447850666488075593005988144091839363944118216422232321032023187550701341956217683120682286236821157044056789207847505973325335487617141876394158040170302511026147698140117870936078053149940693809742344,
    3860830094490961085752930884310966690918909746779021840910765828272134765906916258416361041880241208337797182124709475409638427184157760682062239499378258139634870508832957715200906725559847289585974782965946274822184675941355910172994426277285817711407659299873774679529467353447340574476173095090997270887,
    58174930659603530051481089696633182639458958436222609892129088639113327368911105551511748550690912984592653380933017502134980761460623474839151362671442618757892193516120069483995146320454008624814011679255342019163335555032690250948599813711603812851179611383594880308670070294772541300929900936407942446206,
    44079089028711152982021028496891544027497861560917278801060597134507130629029590138353932484080222751995776415833575786219736764105345566270091010823997065161186675184474098872736189906830945504257759361652735423910178644048032275677684693137034101100555989481630131431167092816069402540842828905339322687933,
    ]

solution, M = CRT(residues, moduli)
print(solution) # 通解是 solution + M*k

e = 13
k = 0
while True and k < 10000:
    me = solution + M*k
    result, flag = gmpy2.iroot(me, e)
    if flag:
        # 0
        # b'flag{Chin3s3_KoNgfu}'
        print(k)
        print(n2s(int(result)))
    k += 1