Knapsack / Easy crypto

!README.md

LetoCTF 2019 | Easy crypto (crypto)

Задание с AntiCTF, который проводился в Летней школе CTF летом 2019 года.

flag.txt

CTF{I_will_refactor_this_later}

solver.py

#!/usr/bin/python3


def main():
    key = [431, 709, 1567, 3119, 6029, 12197, 24499, 48907, 97711, 195319, 390671, 781171, 1562833, 3125257, 6250597, 12501283, 25002667, 50005181, 100010353, 200020663, 400041353, 800082559, 1600165379, 3200330807, 6400661387, 12801323081, 25602645767, 51205291831, 102410583739, 204821167169, 409642334251, 819284668679, 1638569337329, 3277138674913, 6554277349651, 13108554699077, 26217109398391, 52434218796887, 104868437593973, 209736875187689, 419473750375369, 838947500750819, 1677895001501281, 3355790003003029, 6711580006006039, 13423160012012099, 26846320024024133, 53692640048048011, 107385280096096271, 214770560192192533, 429541120384385171, 859082240768770261, 1718164481537540273, 3436328963075080577, 6872657926150161253, 13745315852300322439, 27490631704600644739, 54981263409201289777, 109962526818402579253, 219925053636805158611, 439850107273610317553, 879700214547220634899, 1759400429094441269707, 3518800858188882539501, 7037601716377765078829, 14075203432755530157737, 28150406865511060315663, 56300813731022120631403, 112601627462044241263019, 225203254924088482525639, 450406509848176965051091, 900813019696353930102247, 1801626039392707860204547, 3603252078785415720409261, 7206504157570831440818443, 14413008315141662881636727, 28826016630283325763273907, 57652033260566651526547423, 115304066521133303053095077, 230608133042266606106189909, 461216266084533212212380107, 922432532169066424424759809, 1844865064338132848849519789, 3689730128676265697699040017, 7379460257352531395398079401, 14758920514705062790796159167, 29517841029410125581592317977, 59035682058820251163184636459, 118071364117640502326369272693, 236142728235281004652738545277, 472285456470562009305477090443, 944570912941124018610954181247, 1889141825882248037221908362137, 3778283651764496074443816724631, 7556567303528992148887633449091, 15113134607057984297775266897959, 30226269214115968595550533796011, 60452538428231937191101067592221, 120905076856463874382202135184203, 241810153712927748764404270368499, 483620307425855497528808540737291, 967240614851710995057617081474617, 1934481229703421990115234162949189, 3868962459406843980230468325898207, 7737924918813687960460936651796221, 15475849837627375920921873303592759, 30951699675254751841843746607185583, 61903399350509503683687493214370847, 123806798701019007367374986428741537, 247613597402038014734749972857483277, 495227194804076029469499945714966479, 990454389608152058938999891429932943, 1980908779216304117877999782859866237, 3961817558432608235755999565719732433, 7923635116865216471511999131439464899, 15847270233730432943023998262878929459, 31694540467460865886047996525757859077, 63389080934921731772095993051515718039, 126778161869843463544191986103031436297, 253556323739686927088383972206062872313, 507112647479373854176767944412125744723, 1014225294958747708353535888824251489333, 2028450589917495416707071777648502978543, 4056901179834990833414143555297005957481, 8113802359669981666828287110594011914793, 16227604719339963333656574221188023829619, 32455209438679926667313148442376047659337, 64910418877359853334626296884752095318437, 129820837754719706669252593769504190636733, 259641675509439413338505187539008381273729, 519283351018878826677010375078016762547599, 1038566702037757653354020750156033525095213, 2077133404075515306708041500312067050190171, 4154266808151030613416083000624134100380343, 8308533616302061226832166001248268200760969, 16617067232604122453664332002496536401521861, 33234134465208244907328664004993072803043711, 66468268930416489814657328009986145606087567, 132936537860832979629314656019972291212175051, 265873075721665959258629312039944582424350043, 531746151443331918517258624079889164848700221, 1063492302886663837034517248159778329697400469, 2126984605773327674069034496319556659394800467, 4253969211546655348138068992639113318789601057, 8507938423093310696276137985278226637579202297, 17015876846186621392552275970556453275158404699, 34031753692373242785104551941112906550316809191, 68063507384746485570209103882225813100633618913, 136127014769492971140418207764451626201267237109, 272254029538985942280836415528903252402534474259, 544508059077971884561672831057806504805068948463, 1089016118155943769123345662115613009610137897307, 2178032236311887538246691324231226019220275794563, 4356064472623775076493382648462452038440551589201, 8712128945247550152986765296924904076881103178447, 17424257890495100305973530593849808153762206356773, 34848515780990200611947061187699616307524412713309, 69697031561980401223894122375399232615048825426703, 139394063123960802447788244750798465230097650853241, 278788126247921604895576489501596930460195301706893, 557576252495843209791152979003193860920390603413763, 1115152504991686419582305958006387721840781206827487, 2230305009983372839164611916012775443681562413654827, 4460610019966745678329223832025550887363124827309619, 8921220039933491356658447664051101774726249654619491, 17842440079866982713316895328102203549452499309238859, 35684880159733965426633790656204407098904998618477439, 71369760319467930853267581312408814197809997236955121, 142739520638935861706535162624817628395619994473910469, 285479041277871723413070325249635256791239988947820391, 570958082555743446826140650499270513582479977895641367, 1141916165111486893652281300998541027164959955791282591, 2283832330222973787304562601997082054329919911582564999, 4567664660445947574609125203994164108659839823165129889, 9135329320891895149218250407988328217319679646330260051, 18270658641783790298436500815976656434639359292660519943, 36541317283567580596873001631953312869278718585321039933, 73082634567135161193746003263906625738557437170642079557, 146165269134270322387492006527813251477114874341284159187, 292330538268540644774984013055626502954229748682568319149, 584661076537081289549968026111253005908459497365136637489, 1169322153074162579099936052222506011816918994730273275177, 2338644306148325158199872104445012023633837989460546550639, 4677288612296650316399744208890024047267675978921093100909, 9354577224593300632799488417780048094535351957842186202193, 18709154449186601265598976835560096189070703915684372404211, 37418308898373202531197953671120192378141407831368744808629, 74836617796746405062395907342240384756282815662737489616871, 149673235593492810124791814684480769512565631325474979233777, 299346471186985620249583629368961539025131262650949958467413, 598692942373971240499167258737923078050262525301899916935159, 1197385884747942480998334517475846156100525050603799833870263, 2394771769495884961996669034951692312201050101207599667740453, 4789543538991769923993338069903384624402100202415199335480887, 9579087077983539847986676139806769248804200404830398670962011, 19158174155967079695973352279613538497608400809660797341924367, 38316348311934159391946704559227076995216801619321594683848589, 76632696623868318783893409118454153990433603238643189367696947, 153265393247736637567786818236908307980867206477286378735393933, 306530786495473275135573636473816615961734412954572757470787793, 613061572990946550271147272947633231923468825909145514941575667, 1226123145981893100542294545895266463846937651818291029883151299, 2452246291963786201084589091790532927693875303636582059766302161, 4904492583927572402169178183581065855387750607273164119532604827, 9808985167855144804338356367162131710775501214546328239065209309, 19617970335710289608676712734324263421551002429092656478130418881, 39235940671420579217353425468648526843102004858185312956260837791, 78471881342841158434706850937297053686204009716370625912521675239, 156943762685682316869413701874594107372408019432741251825043350933, 313887525371364633738827403749188214744816038865482503650086701631, 627775050742729267477654807498376429489632077730965007300173403187, 1255550101485458534955309614996752858979264155461930014600346806327, 2511100202970917069910619229993505717958528310923860029200693612603, 5022200405941834139821238459987011435917056621847720058401387225581, 10044400811883668279642476919974022871834113243695440116802774451037, 20088801623767336559284953839948045743668226487390880233605548902179, 40177603247534673118569907679896091487336452974781760467211097804309, 80355206495069346237139815359792182974672905949563520934422195608503, 160710412990138692474279630719584365949345811899127041868844391217743, 321420825980277384948559261439168731898691623798254083737688782434753, 642841651960554769897118522878337463797383247596508167475377564869431, 1285683303921109539794237045756674927594766495193016334950755129738583, 2571366607842219079588474091513349855189532990386032669901510259477691, 5142733215684438159176948183026699710379065980772065339803020518955439, 10285466431368876318353896366053399420758131961544130679606041037911061, 20570932862737752636707792732106798841516263923088261359212082075821801, 41141865725475505273415585464213597683032527846176522718424164151643521, 82283731450951010546831170928427195366065055692353045436848328303286787, 164567462901902021093662341856854390732130111384706090873696656606573831, 329134925803804042187324683713708781464260222769412181747393313213147601, 658269851607608084374649367427417562928520445538824363494786626426295597, 1316539703215216168749298734854835125857040891077648726989573252852590549, 2633079406430432337498597469709670251714081782155297453979146505705181131, 5266158812860864674997194939419340503428163564310594907958293011410362151, 10532317625721729349994389878838681006856327128621189815916586022820724713, 21064635251443458699988779757677362013712654257242379631833172045641449279, 42129270502886917399977559515354724027425308514484759263666344091282899159, 84258541005773834799955119030709448054850617028969518527332688182565797907, 168517082011547669599910238061418896109701234057939037054665376365131595397, 337034164023095339199820476122837792219402468115878074109330752730263191089, 674068328046190678399640952245675584438804936231756148218661505460526382467, 1348136656092381356799281904491351168877609872463512296437323010921052764679, 2696273312184762713598563808982702337755219744927024592874646021842105529211, 5392546624369525427197127617965404675510439489854049185749292043684211058533, 10785093248739050854394255235930809351020878979708098371498584087368422117249, 21570186497478101708788510471861618702041757959416196742997168174736844234189, 43140372994956203417577020943723237404083515918832393485994336349473688468663, 86280745989912406835154041887446474808167031837664786971988672698947376937803, 172561491979824813670308083774892949616334063675329573943977345397894753874913, 345122983959649627340616167549785899232668127350659147887954690795789507750073, 690245967919299254681232335099571798465336254701318295775909381591579015499841, 1380491935838598509362464670199143596930672509402636591551818763183158030999967, 2760983871677197018724929340398287193861345018805273183103637526366316061999703, 5521967743354394037449858680796574387722690037610546366207275052732632123999607, 11043935486708788074899717361593148775445380075221092732414550105465264247999373, 22087870973417576149799434723186297550890760150442185464829100210930528495998333]
    result = 13933199430165124423013259771589117378728904744550286890784850004928374811837814
    bits = ''
    for k in reversed(key):
        b = result // k
        bits = str(b) + bits
        result -= b * k
    flag = ''.join(chr(int(bits[i:i+8], 2)) for i in range(0, len(bits), 8))
    print(flag)


if __name__ == '__main__':
    main()

task.py

#!/usr/bin/python3


def main():
    key = [431, 709, 1567, 3119, 6029, 12197, 24499, 48907, 97711, 195319, 390671, 781171, 1562833, 3125257, 6250597, 12501283, 25002667, 50005181, 100010353, 200020663, 400041353, 800082559, 1600165379, 3200330807, 6400661387, 12801323081, 25602645767, 51205291831, 102410583739, 204821167169, 409642334251, 819284668679, 1638569337329, 3277138674913, 6554277349651, 13108554699077, 26217109398391, 52434218796887, 104868437593973, 209736875187689, 419473750375369, 838947500750819, 1677895001501281, 3355790003003029, 6711580006006039, 13423160012012099, 26846320024024133, 53692640048048011, 107385280096096271, 214770560192192533, 429541120384385171, 859082240768770261, 1718164481537540273, 3436328963075080577, 6872657926150161253, 13745315852300322439, 27490631704600644739, 54981263409201289777, 109962526818402579253, 219925053636805158611, 439850107273610317553, 879700214547220634899, 1759400429094441269707, 3518800858188882539501, 7037601716377765078829, 14075203432755530157737, 28150406865511060315663, 56300813731022120631403, 112601627462044241263019, 225203254924088482525639, 450406509848176965051091, 900813019696353930102247, 1801626039392707860204547, 3603252078785415720409261, 7206504157570831440818443, 14413008315141662881636727, 28826016630283325763273907, 57652033260566651526547423, 115304066521133303053095077, 230608133042266606106189909, 461216266084533212212380107, 922432532169066424424759809, 1844865064338132848849519789, 3689730128676265697699040017, 7379460257352531395398079401, 14758920514705062790796159167, 29517841029410125581592317977, 59035682058820251163184636459, 118071364117640502326369272693, 236142728235281004652738545277, 472285456470562009305477090443, 944570912941124018610954181247, 1889141825882248037221908362137, 3778283651764496074443816724631, 7556567303528992148887633449091, 15113134607057984297775266897959, 30226269214115968595550533796011, 60452538428231937191101067592221, 120905076856463874382202135184203, 241810153712927748764404270368499, 483620307425855497528808540737291, 967240614851710995057617081474617, 1934481229703421990115234162949189, 3868962459406843980230468325898207, 7737924918813687960460936651796221, 15475849837627375920921873303592759, 30951699675254751841843746607185583, 61903399350509503683687493214370847, 123806798701019007367374986428741537, 247613597402038014734749972857483277, 495227194804076029469499945714966479, 990454389608152058938999891429932943, 1980908779216304117877999782859866237, 3961817558432608235755999565719732433, 7923635116865216471511999131439464899, 15847270233730432943023998262878929459, 31694540467460865886047996525757859077, 63389080934921731772095993051515718039, 126778161869843463544191986103031436297, 253556323739686927088383972206062872313, 507112647479373854176767944412125744723, 1014225294958747708353535888824251489333, 2028450589917495416707071777648502978543, 4056901179834990833414143555297005957481, 8113802359669981666828287110594011914793, 16227604719339963333656574221188023829619, 32455209438679926667313148442376047659337, 64910418877359853334626296884752095318437, 129820837754719706669252593769504190636733, 259641675509439413338505187539008381273729, 519283351018878826677010375078016762547599, 1038566702037757653354020750156033525095213, 2077133404075515306708041500312067050190171, 4154266808151030613416083000624134100380343, 8308533616302061226832166001248268200760969, 16617067232604122453664332002496536401521861, 33234134465208244907328664004993072803043711, 66468268930416489814657328009986145606087567, 132936537860832979629314656019972291212175051, 265873075721665959258629312039944582424350043, 531746151443331918517258624079889164848700221, 1063492302886663837034517248159778329697400469, 2126984605773327674069034496319556659394800467, 4253969211546655348138068992639113318789601057, 8507938423093310696276137985278226637579202297, 17015876846186621392552275970556453275158404699, 34031753692373242785104551941112906550316809191, 68063507384746485570209103882225813100633618913, 136127014769492971140418207764451626201267237109, 272254029538985942280836415528903252402534474259, 544508059077971884561672831057806504805068948463, 1089016118155943769123345662115613009610137897307, 2178032236311887538246691324231226019220275794563, 4356064472623775076493382648462452038440551589201, 8712128945247550152986765296924904076881103178447, 17424257890495100305973530593849808153762206356773, 34848515780990200611947061187699616307524412713309, 69697031561980401223894122375399232615048825426703, 139394063123960802447788244750798465230097650853241, 278788126247921604895576489501596930460195301706893, 557576252495843209791152979003193860920390603413763, 1115152504991686419582305958006387721840781206827487, 2230305009983372839164611916012775443681562413654827, 4460610019966745678329223832025550887363124827309619, 8921220039933491356658447664051101774726249654619491, 17842440079866982713316895328102203549452499309238859, 35684880159733965426633790656204407098904998618477439, 71369760319467930853267581312408814197809997236955121, 142739520638935861706535162624817628395619994473910469, 285479041277871723413070325249635256791239988947820391, 570958082555743446826140650499270513582479977895641367, 1141916165111486893652281300998541027164959955791282591, 2283832330222973787304562601997082054329919911582564999, 4567664660445947574609125203994164108659839823165129889, 9135329320891895149218250407988328217319679646330260051, 18270658641783790298436500815976656434639359292660519943, 36541317283567580596873001631953312869278718585321039933, 73082634567135161193746003263906625738557437170642079557, 146165269134270322387492006527813251477114874341284159187, 292330538268540644774984013055626502954229748682568319149, 584661076537081289549968026111253005908459497365136637489, 1169322153074162579099936052222506011816918994730273275177, 2338644306148325158199872104445012023633837989460546550639, 4677288612296650316399744208890024047267675978921093100909, 9354577224593300632799488417780048094535351957842186202193, 18709154449186601265598976835560096189070703915684372404211, 37418308898373202531197953671120192378141407831368744808629, 74836617796746405062395907342240384756282815662737489616871, 149673235593492810124791814684480769512565631325474979233777, 299346471186985620249583629368961539025131262650949958467413, 598692942373971240499167258737923078050262525301899916935159, 1197385884747942480998334517475846156100525050603799833870263, 2394771769495884961996669034951692312201050101207599667740453, 4789543538991769923993338069903384624402100202415199335480887, 9579087077983539847986676139806769248804200404830398670962011, 19158174155967079695973352279613538497608400809660797341924367, 38316348311934159391946704559227076995216801619321594683848589, 76632696623868318783893409118454153990433603238643189367696947, 153265393247736637567786818236908307980867206477286378735393933, 306530786495473275135573636473816615961734412954572757470787793, 613061572990946550271147272947633231923468825909145514941575667, 1226123145981893100542294545895266463846937651818291029883151299, 2452246291963786201084589091790532927693875303636582059766302161, 4904492583927572402169178183581065855387750607273164119532604827, 9808985167855144804338356367162131710775501214546328239065209309, 19617970335710289608676712734324263421551002429092656478130418881, 39235940671420579217353425468648526843102004858185312956260837791, 78471881342841158434706850937297053686204009716370625912521675239, 156943762685682316869413701874594107372408019432741251825043350933, 313887525371364633738827403749188214744816038865482503650086701631, 627775050742729267477654807498376429489632077730965007300173403187, 1255550101485458534955309614996752858979264155461930014600346806327, 2511100202970917069910619229993505717958528310923860029200693612603, 5022200405941834139821238459987011435917056621847720058401387225581, 10044400811883668279642476919974022871834113243695440116802774451037, 20088801623767336559284953839948045743668226487390880233605548902179, 40177603247534673118569907679896091487336452974781760467211097804309, 80355206495069346237139815359792182974672905949563520934422195608503, 160710412990138692474279630719584365949345811899127041868844391217743, 321420825980277384948559261439168731898691623798254083737688782434753, 642841651960554769897118522878337463797383247596508167475377564869431, 1285683303921109539794237045756674927594766495193016334950755129738583, 2571366607842219079588474091513349855189532990386032669901510259477691, 5142733215684438159176948183026699710379065980772065339803020518955439, 10285466431368876318353896366053399420758131961544130679606041037911061, 20570932862737752636707792732106798841516263923088261359212082075821801, 41141865725475505273415585464213597683032527846176522718424164151643521, 82283731450951010546831170928427195366065055692353045436848328303286787, 164567462901902021093662341856854390732130111384706090873696656606573831, 329134925803804042187324683713708781464260222769412181747393313213147601, 658269851607608084374649367427417562928520445538824363494786626426295597, 1316539703215216168749298734854835125857040891077648726989573252852590549, 2633079406430432337498597469709670251714081782155297453979146505705181131, 5266158812860864674997194939419340503428163564310594907958293011410362151, 10532317625721729349994389878838681006856327128621189815916586022820724713, 21064635251443458699988779757677362013712654257242379631833172045641449279, 42129270502886917399977559515354724027425308514484759263666344091282899159, 84258541005773834799955119030709448054850617028969518527332688182565797907, 168517082011547669599910238061418896109701234057939037054665376365131595397, 337034164023095339199820476122837792219402468115878074109330752730263191089, 674068328046190678399640952245675584438804936231756148218661505460526382467, 1348136656092381356799281904491351168877609872463512296437323010921052764679, 2696273312184762713598563808982702337755219744927024592874646021842105529211, 5392546624369525427197127617965404675510439489854049185749292043684211058533, 10785093248739050854394255235930809351020878979708098371498584087368422117249, 21570186497478101708788510471861618702041757959416196742997168174736844234189, 43140372994956203417577020943723237404083515918832393485994336349473688468663, 86280745989912406835154041887446474808167031837664786971988672698947376937803, 172561491979824813670308083774892949616334063675329573943977345397894753874913, 345122983959649627340616167549785899232668127350659147887954690795789507750073, 690245967919299254681232335099571798465336254701318295775909381591579015499841, 1380491935838598509362464670199143596930672509402636591551818763183158030999967, 2760983871677197018724929340398287193861345018805273183103637526366316061999703, 5521967743354394037449858680796574387722690037610546366207275052732632123999607, 11043935486708788074899717361593148775445380075221092732414550105465264247999373, 22087870973417576149799434723186297550890760150442185464829100210930528495998333]
    with open('flag.txt', 'rb') as file:
        flag = file.read()
    bits = ''.join(bin(f)[2:].zfill(8) for f in flag)
    assert len(bits) == len(key)
    ciphertext = sum(int(b)*k for b,k in zip(bits, key))
    print(ciphertext)


if __name__ == '__main__':
    main()