この大会は2023/11/5 3:00(JST)～2023/11/6 3:00(JST)に開催されました。
今回もチームで参戦。結果は100点で213チーム中128位でした。
自分で解けた問題をWriteupとして書いておきます。
Random RSA (crypto)
Mersenne Twisterの性質を使って、p, qを割り出す。
一般的には32ビット整数が624個必要。1024ビットの数値を取得しているので、それが20個あれば、次の整数がわかり、p, qを割り出せる。あとは通常通り復号する。
#!/usr/bin/env python3 import socket import random from Crypto.Util.number import * def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) def getPrime(n_bits): while True: a = random.getrandbits(n_bits) if isPrime(a): return a def untemper(rand): rand ^= rand >> 18; rand ^= (rand << 15) & 0xefc60000; a = rand ^ ((rand << 7) & 0x9d2c5680); b = rand ^ ((a << 7) & 0x9d2c5680); c = rand ^ ((b << 7) & 0x9d2c5680); d = rand ^ ((c << 7) & 0x9d2c5680); rand = rand ^ ((d << 7) & 0x9d2c5680); rand ^= ((rand ^ (rand >> 11)) >> 11); return rand s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('chall.polygl0ts.ch', 9022)) N = 624 state = [] while True: data = recvuntil(s, b'\n').rstrip() print(data) if 'not prime' in data: rand = int(data.split(' ')[1]) for i in range(32): state.append(untemper((rand >> (i * 32)) & 0xffffffff)) else: c = int(data.split(' ')[1]) break state = state[-N:] state.append(N) random.setstate([3, tuple(state), None]) p = getPrime(1024) q = getPrime(1024) n = p * q e = 65537 phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, n) flag = long_to_bytes(m).decode() print(flag)
実行結果は以下の通り。
:
Sadly, 160087309027400229880819749743309706041360377309505221069570844990873447311400827936036973217496635829798276380363981633799312737885594303261797100678812945410673512981539565474501048129729532962760368199423003860174440753852830643246282675699327610884847140534288008230460602121606678306611070445978979962665 was not prime
Sadly, 77847234400399552460700764009577520072958335007739218520230325316626214737710866879623811028101534073176746207074926280287106469166968176412059510716682293009066133577892315985966562027172524130500337818883913071905432301410838241507301540509112623255825175126444028458493139320329100335810767068429823181073 was not prime
Sadly, 69522738165954473610461336015365542317947293708880673555778331126659835154318600111047740772093057310633266411368000020181632618597179668127933923505660971155704129114354989079595033771607935104285942416803458974511318611603692353805448589098996536640316602219662510194193635978468506312834031329136267386843 was not prime
Sadly, 112788894880169153120822703772877938484043110827918779404071253395563880984710302083182321452536120612918042400913197328472489404408800246664819609762920206260942651041008432950868731859502425954139404503295880599392360570210849701527932112632953305380508258288944190214222944791743150086153106374098157008401 was not prime
Sadly, 172362123617622745927927358289949805143623130275741472112509153540659564363855216299502103480303480521970206444486109311342317308723684600268751994113134110657647725450267307211048800765053248065376747833324327283743791637234813224951213260174921892463536704295750636773335993166411376387141862662694089101828 was not prime
Sadly, 58836035412770042929098457215009064347484115567736562500865872789114135272252723633642101312616074551960257395816070610159906942169689314088138977188053129441461860693163967699399046949184011069120478156611091099341361477572794592850678334073347222369220442266263446978289934280295341094523834380215722272690 was not prime
Sadly, 156447302452991621715912233484552694479137221633640395288777250859532081100202922454294082427140971850863565656897794793561428388231238263808930127611538178266298869341092077274635900262758047548633795730303189053409430990634748112007550041717814829816000951789049424137955170296059049348301984275503780938966 was not prime
Sadly, 97804909651629519603434028392713871781470460612788555856635869890864020766163509508253207279413267343608059487762924863721037440596075220220297829018804013659692664383828996639234359051690150312971669682558406251597752149422412063412442482349192853264758878437943630547952438794796270937733981558739105726079 was not prime
Sadly, 109721313483454749568576193132340725295513293872324681333346741683861823924751734174872395234000075580174424415816737458535894574114387005480394471901337315707006478843776800038029917992984533340364271356736042563410481361205261256108612667571643786181827441668257365855263126008137398138404866510667795351478 was not prime
Sadly, 139661129257951615448073314601750878407197528763951405191354706669553149679707656958016829749315683600952483689036946386433560482635923137107813250457580029522564466098678896054319024157344466236881607531536499098427171638505330039509606238704880069191126167766965347771066299719009219046451090843527433272961 was not prime
Sadly, 26192705990409779957415691738380825276103539464027622027997982582377785979691977274450944269611871552967048118875590801026334684480627564926980084943658676741882748670827584904918732581962914638940417638942559968517684817247782622479103720251970721239667865484984525921998299680716664120357208912115604218709 was not prime
Sadly, 117393657124041172039045659269635147951669147196611114263832184183989499091065905082617354517947252191838230513782154812224506305029053052127244857446134032398565052466444648302263299879835552722025706893245142736069228222699859790742952564881390445287895786795596968982325832497771571748835363841187894272536 was not prime
Sadly, 172139922399274056853104490207661785248743657110373348902275861841172108717447433254862602981457269438547149126421858000963879429306000164414835132071501659850460154912889584723863219526277927665010476225859483174223518850601443023143900054285196567314693842450487402554558014797911105284317922904040851339750 was not prime
Sadly, 134191715117452179638270207649193238517731631281174992533063638217409602829704125424915623456843214913523516382618989999982229112146047538674746859053045760258399390579239310422056130427187668316573634332479869177331423704666831470688307053826669407570917363097813049698967308823772822948679348465422733693387 was not prime
Sadly, 19233030264473837705062874122961691732181959833099649047007760867334628080340623239816387496460558307009395786271740033138574815327646753533237431575771483375238290028109866140643939837525010097661063784532851938288883719421609682306438613372768448606215051892580341208349409119855583896996625506570245919014 was not prime
Sadly, 13442742493074768696076632584509184595257281773183103757491720131832438914364216963379005103336791784965302673169448257865813405148968930574808154242331213336187905815228542434774900521779895223039218874272321525354739496143353770529586301133684447516084544619071129191962558983339160166714520735902839808587 was not prime
Sadly, 55453060157261565249457792930207377856587940701030462891360980454931662774120540867658082434814434270913964691898058012247700630871698684734105233001004338318657678321213645046191778623489347445482816908464263545279441367519656777894648981462857929062809692448621762942993650773777976832516498071758643616695 was not prime
Sadly, 49931650671702369926294233450734588609831916178730042131064806521041381316135860040411659807561409987433925583588990177857390759753772722101762645527953602425041520093148570488930373745864745264493653243388871550953411389967415920850102037069567162670427962793666709332463656421072992339276349445494069350924 was not prime
Sadly, 131238050353796556973896574489021956525552718359377765148349377114641924094728500703015128285947344612894637401450289655106764379982193473243695039344657698892389091566161587047840691018783198365053472399882357599600751287856790656422882175981062998046887739414571923814063061780684160141771245298162408282483 was not prime
Sadly, 111838874466993603116621859834804474463069356560664375744951119249332925868821201265705603045460568423298223908872728059036118039028424889710130567258909136254715278099900106197114687691240819649905773159622427035894132598952051994018121244781939985726800163130825579574920507009100548801087554451628320923104 was not prime
Sadly, 114173721736871218788199966629238673117647895735545463625182287849609297951380667267921071028836291833651404742667788346240597635105824889090814019875270657014525281964659701387341603410932146616808730535151866229956722382470458478687548477151649597063908410107024157054324876442249482496941749128993452590364 was not prime
Sadly, 168314063176284948098278362371275222937031977943785670758525760931750634232718219232724949455129402657639427700651716381360494285032895679525007732143612465091767943067231908598491488359360909798242974481770107479404201543556858949769613101593619909789646304149428399320704328817478574969824886909858798472259 was not prime
Sadly, 167309731338321376107922568066144219942858255020577145771330346657914598200197251582342062390180417089709181847804188588437096898415818616978459274281268567277384480638144481823617426749095206527388720441874261302289036427966939697468114016142437590288452866392892633659435886882700565521280947614244904632806 was not prime
Sadly, 19837733364150295843217876334543286546800560699430959205223101027218431955198242185109074750159661218824596335195252731674014560790014312930429908580615884341367158170948912501723644086490471785686800762207056142634433285873125586381187537694912916869773474865084535957252129275137082832912667086768377005246 was not prime
Sadly, 132676990689391854986993080341903263200873173747129876606277258448977069549230965547591736692686761381274754175475339657028929672293463741526988041011190134115006900677617787836022281246673073717892097741788924128218130166219494353921772987764649506416422254472248234469345471026092309205875397759207425566618 was not prime
Sadly, 23252732103642571223252224740287275025953554336493408666569767389829736529189796142019145520758604630805360701096221907779334563575281502459841346838531285544199093926245684853684524132865908944919220645414664894521092093223446645829476444207875433586072846978399911714287543323678906554735331428855644316131 was not prime
Sadly, 154851804738781444815324280134828260312128450817914143292708669372631774801115353904348035694485272917245922941566101276376765909949035428727642667499722441352375332383331234855932550874612448771130463232161459253877092354914913611435448859797837261703709754599785898874918647912460659726524880640679424949101 was not prime
Sadly, 133374741122527572009777250385575642416209211341668783751825069562804175680749567404313723476144918315290343926015451712980524088609426822176795296119566828669065024452585855305512442192414796162940670203485166928535972742154786474126242517966422632631782510018936281592882150715995533995030584870801351982389 was not prime
Sadly, 160542581378370152106196988488024674066107850657976822023458507110186157605367793345176743044270801798640096447463886882939466203166125950141444720680536588445474419752174561819275446127700645954808725733526607700044081675666548949318669002808432080510975037907590365195209604406352583006558676209051765004744 was not prime
Sadly, 77010855096911207079695755711049759094858922539072356322587936149742762172851697315478659851859766395637351884030012249054629299468579001455766607907757346476463822005656469151525173884676121388133768565259558660178710459830679597509955141059486529665450176573955586351906449547579493480416752520633880970211 was not prime
Sadly, 2867200019621081078028160745228974767314332460277144128917154081388824179031743248248083900008329823729419696772362672063333338753408662741583004773834961149410916177103241064854020005018557879221635688534294642756352095690422111472041760237820765411092087055525821370266954117950099007274021205953151915067 was not prime
Sadly, 3541789104180745604197331251880899881070521661579466441186718711242649605446920384292357535985936307136307054003580825258564826233904574569137400390320248288060979840593494203510382162898417780773368807360878791484816002371147249329476570613203489492674366200537611657552581962836310099580913267107902647694 was not prime
Sadly, 161791834495366713467949288510226571343931435378631924837637899538836344492695856548698532428613162730465286078857217030954876639654151828986728822289374573300744494848302578053522343812370984607401055861755256852204566300933555629772128259997308677682922577687472942023156663703852667626593805146905948586108 was not prime
Sadly, 35792040527671695111823895776626729913366087512338459232681282106472941218825052465364077324989792191612189476231385708561082242057224161179829865918762193555534273080815892327404650333462930649683871368331070269882334476562813681518806911651348890556715992266885875503014593968410469976764244303070661370421 was not prime
Sadly, 27626244135385563853103968337945320133320038431636005321617675221425822477884260912302731489089899095047721545122870258476069305516833629758360710973585122826543851062272010956173995536770119977535503747234442699454014417575446947922946990463112852133969349465578123409185175612800290469963905508201571040302 was not prime
Sadly, 120505898809950323237803944647161510924386782482563830381978055081273236658273250368570119188624284876036767372382826409582320787741257621500379718424051993048340213549332828473256813174793949104027080650566062879134485481528351206404120506543928302476809362770234956228073053795364396208544523353606608115871 was not prime
Sadly, 44291032665604665088369338163628376592586460210608573712460948362857852999236211466465845297183277964850767993676567848366761813344965224095706932153588337586266935303501846607056913706229529608340652978805025578972227660302298695890767432551042540273790661281168185049325440982512786330468985333281454775228 was not prime
Sadly, 23391855137681779054535539897831727724239734319921909504848820496903284113195605201598878127997908684016525711925706362364493629324491226457340596093751189512191445358697263869856640313464355562944826668488816000497797787451561920655279335357076773208780088106467361131386354260877607897377795924373965520977 was not prime
Sadly, 172415511496059638109789708400418593061297557421747574384793081863809576764713414832299326847882771084390945369395837394682691161852416051810989539915348066840695820565142067625738123851867596362669950377444432752321689943668181438319086298716136579902600350289882578763253700723056817865368396583640883520591 was not prime
Sadly, 17813431001594745130845091126934274573846334129209558919666090933091745659739602245725606332948382071137224803162070323985969019174705546139197406015699570393702757538713092407613210854903608396270290974305189374404842049366094556642406539143342026899293469524914883793703474498678574754694644979479774053031 was not prime
Sadly, 36507089288697183578992749434592148647550124035165881310218725016640959755738632447672008728245841444873623060463700033120078507379943213242935937193857329523405067184276691163045273831469510989608963377064221009426946638245161831614818452061599002403014404870188764887654939629085979576764393090175295106158 was not prime
Sadly, 366738136542074959131556930982462514006243447309233006021389365687186899547744045222478250780005814410096041446391694947372656374357378172139148623311131951390901448580522899085286869229480863151689082606187297339556838010596001826869407055594620869799908258632167697281454365223069239294298772385598693060 was not prime
Sadly, 58021373010334177283599038401850080596506000635621790815132510674959180615562499230390406335791867884312754656131082849439425683747221009175654426872681003496629584774567030955910504470620897548394448744653538304856961617556802383375700552007120090176692728430302235265944573690805111308232759525328734791374 was not prime
Sadly, 92627520300649041465936348679595479691897319139883807426035688160099355692949724969215851325521362603143268637791555124702812398217212266991889875336094165344403560738046408639709142682629662395632636395178519523405051993178580230964325044048901597713385986672494753380438773250345372500978250373597022437760 was not prime
Sadly, 139785317204394434687347539018267412690755503587962443807710886193784563635438468478559081027257849366348038585419180098778929653618597078103991529044703443224294536459852348705616112543731280884539009590280899971261581285151317217972118139068902995504017027773025673804687864712643554787049608877605142496542 was not prime
Sadly, 14316566317961601244077604755810185975246428234429174055769991150641948648342610214657761581054288912820085727638833598985244589589665243110248304418577025641830879478532029657051835558871144123543053395261683415728661860591192303726518488454409535489307265577128184277978162370723737295102151465269675724184 was not prime
Sadly, 90790537907432729394995745160218881067310213859687671613685581660843956554036859371991526147225000052913389923245982424800126544038754613869621404275557170766776675329743633176519871547157388295369433903977330785165613336122623857727601710153627669234949942783695166375962084401516891405161926358513505691902 was not prime
Sadly, 137733212934309498473069296729176493995516557763332757476027989608830849119138437317146110541058594650741236184100862939065339340124840365059639784248123820124759933901906538298325154899364541978512362754962970059980562704314653094510583468078563782022796231170396784362339139303163538647371918079223699118189 was not prime
Sadly, 100164395192740461623755827216854881235117172027353786937371953383597452222142730716211001241610957600568905180238162328143213687542657792285884466936130022819803462198442551139524091073019500137906490561109244604434947365812714591151429861141653267316836327961841274477712582450512467868476831938679989798942 was not prime
Sadly, 66134167921628755536513740798242851273692006145180130862344359411932581765373836894982343025560024709695682912749121579932645684595240085999300502720264766160741143035981289064679341512464585369243418104550825380013279542340058335894022185751178249467729336124902161622061351112194800753482685607002276299774 was not prime
Sadly, 70013268746682169249394466836106954190347964807234534459360585536666281967363808004209190232265364975548034341061636007655288655474871944586520798224477498668301889851480049365630437707453572752693619931004897398465879010781387889657169492289521890366153707142075747532111161997430037889435648107610524201614 was not prime
Sadly, 164890874129219070031890334335122326379888978521210907260216469615007383548009491971653125557723894382796161446206796739319263877355184699419457325607733501152072848741157351047242440435548959845060305152627029270799401561821027673634820885222445376858854961477067939729844211116679689491568482355610360108827 was not prime
Sadly, 159513685949428842810345970394644386513633048809808539991331330739130384159082521198147401446903697825367286362991241401857821559347616212640612468785452715079360820513246145088901864059199645461412452628253254159305090626919474793124026942332103069452980741065610487058428349528805356331762540830985246934732 was not prime
Sadly, 62532651954050829993444182749508982324658248971681756897564633189821959418551940199016514823683362788983741374623824414794582500468562704612890949009003863535598619620272106697796128160574530736265479333312146145925437732934466472546290381285282648407805811199845256822582716712771213412782448482815520902828 was not prime
Sadly, 81260670805391282049820691976009156753114914773127996354658906406188303453877879811734263593370209962905226235401084781889182666870081155356514476087310378204840759345238516854855149885444546420225497478624083461519851027844041071493065281005102181038513659251479413316417465555451925279214290978866057314954 was not prime
Sadly, 24295296538298053270639840524623197219866019826540774489060488030948047800503625501503834222568834353441418148171767370454309611201176561218310450216173379400729640481546730691022067374274209764193063316519561294880417161866918721633799840082564632483771275878881284184130996956156876039964650014101205651420 was not prime
Ciphertext: 2435893664059157358079203269281448345876804981584102043122921498115535857419769096468760953349040545740179850225102627191729542695535947700254262337761868359658355012855075192795339977035410946653437814354027687445521287753007734047192764109491555241983612438128957114975135365676712150876744926223199032513439327692676371496627928060869619979557889860945471846799321286986160740305595635069237951796651370297457978184096439323775287026055166553472747273210390355318193478725781178254862947855163271731195725861235241773909077569730593095133665359858532519306313379434864997712341590881918508133319009009480515437300
EPFL{w0w_s0_much_r4nd000o0oo0om}
EPFL{w0w_s0_much_r4nd000o0oo0om}
Vigenère-CBC (crypto)
暗号化処理の概要は以下の通り。
・SHIFT = 65 ・MOD = 26 ・BLOCKLENGTH = 20 ・KEY = keygen() ・random_block() ・ランダム英大文字20バイト文字列を返す。 ・FLAGTEXT = read_flag() ・flagを返す。 ・CTXT = vigenere_cbc_enc(FLAGTEXT,KEY) ・blocks = get_blocks(FLAGTEXT) ・BLOCKLENGTHごとの配列にして返す。 ・ctxt = get_iv() ・ランダム英大文字20バイト文字列を返す。 ・blocksの各bについて以下を実行 ・to_enc = add(b,ctxt[len(ctxt)-BLOCKLENGTH:len(ctxt)]) ・bをctxt[len(ctxt)-BLOCKLENGTH:len(ctxt)]だけプラスして返す。 ・ctxt = ctxt + vigenere_enc(to_enc,key) ・ctxtにto_encをKEYだけプラスしたものを結合する。 ・ctxtを返す。 ・PTXT = vigenere_cbc_dec(CTXT,KEY) ・PTXTはFLAGTEXTと一致していることをチェック ・CTXTを出力
CTXTの各ブロックで、前のブロックを引いたものを連結すると、Vegenere暗号になる。
#!/usr/bin/env python3 SHIFT = 65 MOD = 26 BLOCKLENGTH = 20 def sub(block1,block2): assert(len(block1)<= len(block2)) assert(len(block2)<= BLOCKLENGTH) b1upper = block1.upper() b2upper = block2.upper() b1 = [ ord(b1upper[i])-SHIFT for i in range(len(block1))] b2 = [ ord(b2upper[i])-SHIFT for i in range(len(block1))] s = [ (b1[i] - b2[i]) % MOD for i in range(len(block1))] slist = [ chr(s[i]+SHIFT) for i in range(len(block1))] sum = ''.join(slist) return(sum) def get_blocks(s): blocks = [] i = 0 while(i + BLOCKLENGTH<len(s)): blocks.append(s[i:i+BLOCKLENGTH]) i = i + BLOCKLENGTH blocks.append(s[i:len(s)]) return(blocks) CTXT = 'AFCNUUOCGIFIDTRSBHAXVHZDRIEZMKTRPSSXIBXCFVVNGRSCZJLZFXBEMYSLUTKWGVVGBJJQDUOXPWOFWUDHYJSMUYMCXLXIWEBGYAGSTYMLPCJEOBPBOYKLRDOJMHQACLHPAENFBLPABTHFPXSQVAFADEZRXYOXQTKUFKMSHTIEWYAVGWWKKQHHBKTMRRAGCDNJOUGBYPOYQQNGLQCITTFCDCDOTDKAXFDBVTLOTXRKFDNAJCRLFJMLQZJSVWQBFPGRAEKAQFUYGXFJAWFHICQODDTLGSOASIWSCPUUHNLAXMNHZOVUJTEIEEJHWPNTZZKXYSMNZOYOVIMUUNXJFHHOVGPDURSONLLUDFAGYGWZNKYXAGUEEEGNMNKTVFYZDIQZPJKXGYUQWFPWYEYFWZKUYUTXSECJWQSTDDVVLIYXEYCZHYEXFOBVQWNHUFHHZBAKHOHQJAKXACNODTQJTGC' blocks = get_blocks(CTXT) vigenere_ctxt = '' for i in range(1, len(blocks)): vigenere_ctxt += sub(blocks[i], blocks[i-1]) print(vigenere_ctxt)
実行結果は以下の通り。
VCXQXOQXGCOJMZBFHUXFKOWKPJODNZSIQFJHEXVJPYPJAEDECAYRYXNTDYWUCBTLSOXGTPDMURJLHINBCGDLVPUZVEXCRQSTSUJFTDIRTJEPNJYLMDYENNFPKQTWDQCQTPYLDAMMWNZXPADPQNUCMTDETUBEJYINUXXNWAHUKYSCGFNOIYKROZHRPGUUUZCCRQSTPIXNVOWCHPQVKDJGAEMICBKMQZHLIEJKVGYECZZRAMTRRCTPLWINQYWRFAPGDNKXDZJLQNUCMLRJCTPNZLVMUJUWTWHURLIQCPPNPCCTCNXQZERTQVUGREDNYYKQGIXRXODQVDUASDZAJSDXTZPLSEJUGPCQRTVTJIKNXZCAQYSCPDQTCUODKSFDDZAGTRUVJLJAMGITALDXFZXQPJODGEJCPUCOJYJCNTSMJXJKVDYLAQDTEMJCKGAHJOJCUFC
https://www.dcode.fr/vigenere-cipherで鍵の長さに20を指定して復号する。
鍵：CVPYPWQCCLQYYMVAWURJ 復号結果： THISISAVERYLONGFLAGWITHMANYBLOCKSTOHIDEANDALLINCAPITALSTHEFLAGENDSHERENOWFOLLOWSALONGTEXTTHETEXTWASWRITTENONLYINORDERTOGIVEYOUMOREINFORMATIONFORBREAKINGVIGENERESCIPHERSINCEITSOMETIMESTAKESSOMETEXTTOGETTHESTATISTICSRIGHTDOESNTITITVIGENERESCIPHERWASLONGTHOUGHTTOBEUNBREAKABLEHUNDREDSOFYEARSPASSEDUNTILKASISKIBROKEITSINCETHENITISNOTSECUREANYMOREANDITSEEMSTHATNOTEVENCBCCANSAVEITDOYOUBELIEVETHATCOUNTERMODEISANYBETTERIHONESTLYDOUBTITSINCEITISSTILLJUSTASUM
フラグは70バイトなので、先頭70バイトにEPFL{...}をラップする。
EPFL{THISISAVERYLONGFLAGWITHMANYBLOCKSTOHIDEANDALLINCAPITALSTHEFLAGENDSHERE}
