WMCTF 2020 | Sum

bkz subset_sum_problem

BKZ

Subset Sum Problem

from json import dump
from random import SystemRandom

random = SystemRandom()

k, n, d = 160, 180, 0.8

B = 2**(n/d)
A = [random.randint(1, B) for _ in range(n)]
s = sum(A[index] for index in random.sample(range(n), k))

dump((s, A), open("data", "w"))

from json import load

k, n, d = 160, 180, 0.8
s, A = load(open("data", "r"))

while True:
    inp = input("Please input the solution (seperated by comma): ") # <- 0, 1, 0, 1, ...
    sol = [int(i) for i in inp.split(',')]

    assert len(sol) == n
    assert all(i == 0 or i == 1 for i in sol)
    assert sum(i == 1 for i in sol) == k
    if sum(x*a for x, a in zip(sol, A)) == s:
        m = int(''.join(str(i) for i in  sol), 2)
        print(f"TQL!!! flag is {str(m).join(['WMCTF{', '}'])}")
        break

[4230171014057309934708763067565512367872507288535799098841231073316859, [24778752966005371563119203996314882265692637735581286369318531512236, 44187589872698849915596365415308356101488103982691565764593376457792, 11976523474345967493593189237806497369767991383683271191730243057410, 20769247130728963754780530253652022055468793963453404771977162734793, 17534665747936178359909537742894957753830821921428171961776195956535, 35808929458283244057273418166613899120009855608686406869488839154283, 30447165276450975133820202818484328000647625887615012210957945267945, 42286029677791925963231649304116564603939637991627766303133018182225, 39103754118663742704724461921337620537339831929466799932796141162506, 33812788322939666237394259632903545280356860904185112338040553250903, 51145028928066548273256497364336045182797212588622413173023310998936, 20771412933076598589049230108315691359449474639533593888189450052644, 13049042572955204295232461211081760798100014932885813167299244498172, 6607107832831133391294571237902018533803024946448481128590862633663, 21561696778859552656255942587669943563483176487522622550079128001675, 12142298889527803493968349776272027677838394785637844312094277095942, 9260171554002553267536605751815993773628631177642078572542241460114, 5121824374614346728627023148710212341671685427528842901188795811187, 1700559301829909809774771143762502311776042241946456807419845851857, 12961431581743756145133308859899485392840306449838397154527950274453, 3726979934030594671138169420133511920516494178221452222759378606454, 28332765610622204652349047835413205865462532538524345654738967799803, 30290645010190918828043517521155964315364973499393756049324277241586, 34389750076295734419206515741310894999501176852839010777827995043466, 42668246197915122942676802776027374687233473013344349836993820188530, 52019081111451208713188056403215605584227456192780570541343488439321, 53004092596916518018350534229337511905829140439461055802872903990976, 53438089499343861961831079561415378341145612615315352030190698896398, 41505790794592680728143635414417543559364924673072943303720366936825, 29353659501739026540184438380687902798725863236534671790415714321511, 22662248043732475036212993442653133957255975620848756651173113897321, 27702357821633061858415611602705252302536138743932622487932662470332, 31061469097915352749260842790294902726660296135660932860164230852578, 18112823424638142012898633772818994891765259973541007777942885508713, 35618709896446356818418519878363765888616807305818009975109034166430, 7440094363818073948463663992794803672651880237738331273874689705284, 9458756544211864841855549219814049399105193850038584500824097073820, 21717024947188123147299841473601646986489023858692870324106187607118, 24183175666270996185414437632788372199322186182949612932627278241401, 10442630235547112185580724281298096981917352239303666220631384513369, 52474596173057636985457050107003870381163635422355288558952579938260, 51978160383839118004023291388769103901353260946250948860575392949399, 825254136578116326570703262182324175322456143823425583610323688539, 33291344279781023553095511362950494901462477385034370331721641841925, 11998482548749909276570840643927193578890464957839506055509227813469, 6983946688031940534845484325922697015808100219121156810167822089528, 26730462514361607348413641364941996085413957246753342008260114567620, 33878222399271823050532081340869998735821526116422989298065189890976, 14284849852507988427521303605557028238838966194937387553424381567949, 42932647084389402477922447943825954901316415567060629874924216891387, 975399250871151149496415408548081082349866179386038220390650741084, 10878824345807654553174850587972646658268417057806782312589080022768, 39846041790668200447282525450528176279495995455913755422478450713047, 26959668347705841204286291732882848866383695268972052371725366433188, 5254285200335051774508161630115937675709836151545615726763573356421, 15999732470611976705242446718141307103540101065408895116130365806493, 31181215445485857016182260921882719791749093667426247079303262154638, 3114986307089377591792607104789398071207933112822519771345794337552, 34367693371984688501626755200645532735359832150070463213713980779604, 48946178757902234052076100213695854139961440828703071274900447087778, 12105322418197199129073018380177931305688139457676108846896877869573, 52032600253629387368588141462834408791920948835700552287403409189767, 18522629149739240154939973912122829379176915658721261446744860625525, 38191815395120181866232870271367211522478946227259477422311402980266, 34904675391549284552347049888525850342285503205865042458463454259884, 8112589669281607179028501301521644251879735453802605873797291373904, 15641830488455901783359643171136147853689587820404037409913882538436, 35653672120360139216401740699354722063341760644948434820326132665906, 24565830614128573411936775428123718815730130818454525907088809840079, 668541412506144676104707637133320508272875902505485238298006319925, 28581773278061375271967565074396198192904600586645217803730204618478, 38397951349944026818839428330708342975630384090623898077341347584474, 37314875091326700449638016730108943552639757507460670214282444795367, 53659512253762319776252557011225221997956600544232812364574382405696, 42874847578149222659375148248281733788565006843994851554347490052592, 30871054036685885694090648763369378279471726036296978123363423694533, 15532071927908737839975786964312128079451619335511367469977935842114, 16698905504169839929353165202114976956717189265886762387390584194609, 20839359759066466110329628141711969938544272977083977469996006394770, 30522952500895578781593627880907403083915016512740026551391156851066, 18122468900669750170422442029442572150389467540945365119033506140329, 25697089272648903669729059516990684352438012910786753176830579583838, 9906590790864868437846718426221587874335163620351107080200336105405, 6666290930630788336172453236574420588208733265408067413598306983793, 19107285295369528322211559835471925635656326551735196101468743239334, 29059057858698293536295126055024286077754746666938825958762700288402, 15901395879743222372078367232932536441438953280177439573677250460360, 44605877182316832041221507999349334657128576620901863599759283003990, 10292148125445482783102336724207109515859616627343485283593664940010, 14084663423027822267786540552843402521290886189918185805718159845201, 21725163532445638839555383152375515587839040341147491501945356563998, 13313690132195283275289515089334717042320835257089554198530871939397, 33033004644988608283712110596770192874435798854302988178015726766880, 50715207169978498451956364999108245136006147415078215754240971475401, 51218255362748630708507430590654277411650025631482912906215572154590, 26467333980436686468119618296110280702701727006881293602852309851541, 47683159431673413820886773556206152129434173396225902774435790557643, 31491832109672937683495134011545371560591526893846616383157002262635, 16352388179020616000743837252707895095269322669369708035612891489672, 3479738497956146058221885731405599699611662338935852037365898379975, 27066252500037036894060121206580764461493191687282667868241232951911, 37382079839366889390645568577792339330341306226937486732241664114911, 29424328686154721591693583922302262060895420081264686560706740211376, 44609440246851492654681706330335809105201283190062723888086382078668, 38098386741225321263050265618020638555863387824139464462756024200672, 42688931365530213243621181704238955525995977651770646740772001651088, 10432502036254084048127361190794180107559600954211924698164507657505, 32197796401137052898367073640527926021427084361666114358205745000622, 7103033831592709390461287958045737590810976666986548632956494995691, 26033121801224860698936535131894728333742674323765130179344304657654, 41087834650352162412454927389775709535616836883383333975243340828618, 17382983942684846005401852397212233665131105001328965821833075179233, 26686557997926582813073182312067717389951486932414701253418059729146, 23846943955892216968103525472038138414005261734177249302878868315720, 50507833865601600101829096463684793415204655859470425159784423714586, 35663878418876495916145334830039634613959515206783112315881994737464, 42236128919626278816529935501836997192498589369584965636728955412360, 42742347612633827985137875897837462793697975528336002575121574220169, 52846387000820749363302360043665818495810039883344455785823359110744, 29132377542153260294240720525318410506567596292565127327928138428513, 50912206998843544838945781609293774984969363599363860761683329157483, 2941693328608834212975838206891661415054145728740273493627942221727, 13254860448943126200401861597288999221505452651017363830954277314314, 28585373662116363610945339722112903787363944989358203150599397026278, 28082779455433222697509267464049129054979689216194757478208944059360, 9007902642746062619571684853626118251084138211686666122030869129120, 25734695688826459799663050775681314549595331576948848828409717700917, 6904309903256000590431499982641575902633008022495489068722274331853, 49963832433198144145614878348341086419598448813827460877053096257753, 32601296229447408404266517159774617993569163897775737742241199430119, 13801773962549111338919224097934669840598453844036062299344173539256, 52865303730812862654699927035591074928115460990293510183654114394946, 38443744763719639308286793728067611493755437993021425496093358126721, 2242394994250523884400993800787975657967933932029856984370423438126, 35356936322637530093267882987384538995440153469920981510955119275230, 40086935947848821763169172406975524015023291739764399620593853435386, 40014474200501282026014529427037915409287016386105196352823061206814, 11769819445116512615902032399644339036633524949848668278491568059367, 34346781529626672168548042857706397775581944621929854049897995447862, 22757362408905149782921181664832393073157149744940565666543824912807, 28537676386461170366634603174190199299067572449142673935560449656676, 140990439171026742142602116885412193159150745310266788347517286466, 32223938706905043871428726233874488745115721021416081573203017105700, 4600351052539234668663778803762941537767220701601174639327726696612, 21506955065330632972299577096928902385855188003829001428976340869405, 36867004398209581736057685524583946712398955836806277620659218958088, 16080356333497431398293544340872552817292459270100692039484023719660, 10604110653316973581486721790871210695531286039184872627952020318871, 18982031930607070980021897144182995688483509290606195554944474521436, 50663297905311002845826798006275669718595762536300876320902470758204, 2923203768218734513437589726643394158166977801869455906348651078365, 16932524937182001863062510802449279448707810622604443887062610605226, 19921834052767223043742056660394368633670327799368197458272663888716, 16087664750489833355421291259011096918452782676522246635774350285788, 39644014768325683091842953614206371673767912925634483196148201180181, 48016243331582905312942479741551007234744000838641660224362359205446, 6024213916176608581160135438090533372473755837727678998115246360237, 29029699671641978199129287345867675883473094389416246555125624777443, 24010789086758821500564368564260650071712063600676297450364518974640, 30072551158431922928323460776694873253453727156420279668731150086797, 47274736286242582865480389404669508892702249996690914639975036447581, 32401914864349812381319663521830989583696826557340714550196647335986, 20579701816229866928568379478302808743429001448559898106846418268083, 50306134704391733008283559676063597581596624754133556679894458766883, 9134114249871400185427201757419267010838883991442760249425552707796, 15958548148693178544371828289308065506106918700650317369390670083894, 49951465319082857768318260331159746430848812603121087941592798184594, 53893884761446518835560648582020670708159495209048681696823648633670, 35588304729905860926842717728382870575986190125921932429256427836185, 49790547949549501779173884554927591446627151117080410044454908830838, 3023606767579945355895088330804384466633454919824921881995313180574, 53147916805131722305983959537550958696172877712860002762121728596383, 38629965035437029262336798286788383658865612194291772259024272976235, 36187606333453806635764514626848754273689432207987390449572907942276, 19733986447777608092431186096438237954777563516644764651292085829519, 2142269097093237119548074755512493918030319379407139889576867438580, 22151507675157518563811391437601258132107145549583214897708358821642, 26852643062947646569010517724255891951776307344221277891940760474821, 9634705436567917380545800280413989180131740447907470960320602006711, 6753431150207674736052973301802304841104777229526159666635889875827]]