概要
- URI:https://score.ctf.tsg.ne.jp/
- Date: 2023.11.4 PM 4:00 ～ 2023.11.5 PM 4:00 (JST)
単独参加で簡単なCryptoなどを解いた。
Upside-down cake (Web)
設定が正しいか、413回チェックしました。
http://34.84.176.251:12349
長い回文を送信できるWebページになっている。適当にaaaaaなどと入れると短すぎる！と弾かれてしまう。
Webサービスのソースコードは以下の通り。
import {serve} from '@hono/node-server';
import {serveStatic} from '@hono/node-server/serve-static';
import {Hono} from 'hono';
const flag = process.env.FLAG ?? 'DUMMY{DUMMY}';
const validatePalindrome = (string) => {
if (string.length < 1000) {
return 'too short';
}
for (const i of Array(string.length).keys()) {
const original = string[i];
const reverse = string[string.length - i - 1];
if (original !== reverse || typeof original !== 'string') {
return 'not palindrome';
}
}
return null;
}
const app = new Hono();
app.get('/', serveStatic({root: '.'}));
app.post('/', async (c) => {
const {palindrome} = await c.req.json();
const error = validatePalindrome(palindrome);
if (error) {
c.status(400);
return c.text(error);
}
return c.text(`I love you! Flag is ${flag}`);
});
app.port = 12349;
serve(app);
validatePalindrome関数では1000文字未満の場合に"too short"と返すため、入力文字は1000文字以上が必要となる。しかしnginxの設定が次のようになっている。
events {
worker_connections 1024;
}
http {
server {
listen 0.0.0.0:12349;
client_max_body_size 100;
location / {
proxy_pass http://app:12349;
proxy_read_timeout 5s;
}
}
}
client_max_body_sizeの設定によって、request bodyには100文字までしか含めることができない。100文字以下の入力でvalidatePalindrome関数をパスさせたい。
const validatePalindrome = (string) => {
if (string.length < 1000) {
return 'too short';
}
for (const i of Array(string.length).keys()) {
const original = string[i];
const reverse = string[string.length - i - 1];
if (original !== reverse || typeof original !== 'string') {
return 'not palindrome';
}
}
return null;
}
validatePalindrome関数ではstringの入力を想定しているが、パースされたjsonがそのまま入るため、JavaScriptオブジェクトを与えることができる。
{"palindrome":{"length":1000;}}
例えばlengthというパラメータを持つJSONを送信すると、string.lengthで参照させることができる。このJSONでは最初のif文は抜けることができるが、次のfor文ではstring.length個の文字を参照しようとするのでうまく行かない。
{"palindrome":{"length":"aaaa"}}
lengthを数値以外にしても最初のif文はfalseを返すので突破することができる。この場合、for文はi=0の1回のみで、string[i]はstring[0]、string[string.length - i - 1]はstring[NaN]を参照しようとする。
{"palindrome":{"length":"aaaa","0":"aaaa","NaN":"aaaa"}}
そこでプロパティとして"0"と"NaN"を付け加えると、string[0]とstring[NaN]で参照させることができるようになる。
これでflagが入手可能。リクエストの加工にはBurp Suiteを使用した。
TSGCTF{pilchards_are_gazing_stars_which_are_very_far_away}
Complicated Function (Crypto)
みんな q = p + 8 みたいに簡単な式で q を決めるからハックされちゃうんだよ。こんなふうに複雑な関数で p から q を計算してやれば…
暗号文と暗号化に使用したコードが配布される。プログラムを確認する。
from Crypto.Util.number import isPrime, getStrongPrime
from math import isqrt, sin, ceil
from secrets import flag
def f(p):
return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023
while True:
p = getStrongPrime(1024)
if p < 2**1023:
continue
q = f(p)
if isPrime(q):
break
N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)
print(f'N = {N}')
print(f'c = {c}')
素数p,qの決め方が特殊で、pに対して何やら複雑な関数fを使ってq=f(p)としている。
実際に動作させてどのようなpとqになるのかを確かめる。
p =
127989863684467746724395460928903530266346872910384629582270666962997480142016958222241629916003180621913143711035786970151620051853398876827793769043529439190148043877989255240990389059815135001303381446710747704224918199736779415045591236982502009493966560145685357809478552051222760794178862527861788610261
q =
217874520427583542110860720468354766947245721857499958218985707541863818044767439788595868577206948632473200650971483648981014936260607188074217484363266508082935955561720547666153997963361245800712833218949939450424715401790025892556036193190064711527355660503907600172477601897404024919881513909498403720913
p,qは全桁異なる値に見えるが、qは最後に2^1023を加算している。16進数で表示させる。
p =
0xb6437c54d5f9c5362cfd2b7a3359a37debcad4d5f33abe1131e706cd8b10ba30d8254f8407de9a3e3d97fb0639766e56a909b8b348132ea0560f54fcbf694f76b1cad9e4aa949403d5345306f8415d4631a4807934427d6cff91f232b1752b1400fd64a16a4b19075d75bce1e5ecab02455fc26bf409def58c77090602918ed5
q =
0x136437c54d5f9c5362cfd2b7a3359a37debcad4d5f33abe1131e706cd8b10ba30d8254f8407de9a3e3d97fb0639766e56a909b8b348132ea0560f54fcbf694f7731cad9e4aa949403d5345306f8415d4631a4807934427d6cff91f232b1752b1400fd64a16a4b19075d75bce1e5ecab02455fc26bf409def58c77090602918ed1
16進数表示にすると、pとqはほとんど同じ値になっている。ただし末尾以外にも真ん中付近に微妙に異なるところがあり、単純にn≒p(p+2^1023)とすることはできない。
何度か繰り返してみると、どうやらqは2^1023に加えて2^511だけ大きいようだ。よって、n≒p(p+2^1023+2^511)としておおよそのpを求め、最後に前後一定範囲のpをなぞってnで割り切れるものを探す。
次のソルバーを作成
from Crypto.Util.number import inverse,long_to_bytes
import gmpy2
n = 36517404305297844159564250986998364545749151568667732337564141796428285198409567155495468780386611544242689580089026301007867731616501462571857014948329304677585682534513311931280592743677919741211277066420279973665839898693462080087384474270473468411814863104608060945012301810206919347219744349831947632420533489933798065496290612931089442978868423837068735855183319271953531607892676482508704408482509645764820088854762889436761417245871075875762331247987854763068633058894469255779600684845456979405817748289218533715177711802661303055514957438072072036882111277967476497338901040854808789173453802590826788192053
c = 10955441460830702971387335888341162305090757526159743008807609823673521696863955454033040842132899414049783504960968117620860408142538216669369693386110678382112863315608217382774969191050306778748875856817288367369848881561750362221050586276876239956129985854245190619132772579774800480316624847309710595491090120189333272498817039509311650265968036568364234815921263181086438290844976279974023236010641698308664245573159698211860696725554580817928576304048869309097043078452170158082597167199813821750238244173483019805092246803337196768846732908994751887507198151471659940647272634351206676375579258509003076141110
e = 0x10001
#search
x = 2**1023+2**511
p = (-x+gmpy2.iroot(x**2+4*n,2)[0])//2
q = p + x
for i in range(-1000,1000,1):
if n % (p+i) == 0 :
p = p+i
q = n//p
print("find!")
break
print("p="+hex(p))
print("p="+hex(q))
#decrypt
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}
Unique Flag (Crypto)
フラグの内容はユニークにしたほうがいい問題になるって聞きました。
解き方はわかったがソルバーの作成が間に合わなかった問題。とりあえずソルバーと結果まで載せる。
暗号文と暗号化に使用したコードが配布される。プログラムを確認する。
from Crypto.Util.number import getPrime
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 0x10001
with open('flag.txt', 'rb') as f:
flag = f.read()
assert len(flag) == 33
flag_header = flag[:7] # TSGCTF{
flag_content = flag[7:-1]
flag_footer = flag[-1:] # }
assert len(flag_content) == len({byte for byte in flag_content}) # flag_content is unique
c_list = [pow(byte, e, N) for byte in flag]
clues = [x * y % N for x, y in zip(c_list[:-1], c_list[1:])]
clues.sort()
print(f'N = {N}')
print(f'e = {e}')
print(f'clues = {clues}')
RSA暗号をかけているが、1文字ずつなので既知のASCIIコードの暗号化結果と比較すれば解読する必要はない。隣接する2文字ずつを乗算した結果についてソートしているので文字の位置情報は失われているように見えるが、flagの括弧内に同じ文字がないことが保証されているため、隣り合う文字を繋いでいけばもとに戻すことができるだろう。
やや手間のかかる以下のソルバーを作成。同じ暗号文となる複数の文字の組み合わせが存在するため、単純にTSGCTF{から文字を探すだけでは不十分で、再帰関数を使ってすべてのチェーンを辿る必要があった。最後に"}"で終わったものを列挙する。
N = 23270433480920204754247611545325351123344837487480637119344134402239723224072753511766733288907047277110318616688410345451695008290697208699431350412549980332693080979894504737640802849242656337537061128034361792156302502329044951868719492095983428863678764573927362740207756141512536958600798465368672826288270218390845725069636496528488276905161318078890887808033722334376853632300178257589009018165644740844747444214979597702959381078126401914809713991087656801656368079319383579542103855944156160231935875884314630699684359910296730669798237991501134339113682532446997472722560474195749179320370386661938616345489
e = 65537
clues = [790128007826920672966041424911766354167695121053219604283198146207007061791691778597663178563455647947105718896263099495348666331968821896627253287975936857535926164644548223394731131868459847861503995994130787209417795249554290922334587840664276128893082715626698208421033163870050616673531495044580102830036983208043090136212931697438690030675611301000171270559392107484305007589373493054650247495594665847524590737367285135216109196557363472975056201832374767680569696302197844301099024043070258479146726214414688459938129079248125143388403636784068208501745074616490491553776387248926153964494371491351883633209, 2603711767185838325352475153597847161854130118046369285623915043550612314176250745686994158628404520769025735077328213489305045750703593138538988340789187229888984902266067604215108157628606721779126603704209046389682027226116051092595210765409544706918465385789940134172311788347486915924020739666375005469879097995622537311532236494537245411805276338873499191960938465585934543775755531517716535416304391622644348521922876999587501073379321712481689748053619310595304248483018790236975241904276396525088600521271478581198340688684196813199138458166434400373640927130152301112142288723416868406008752554068971897796, 3555341764263168489859556591176672830061219988177503466050405264336799992429135972104282899942353497557907652603350792489036502274605405291660887915416806360972250779650137925049172948193768071600510818240408613776868308398496542674893829543607137246662897358746317583492470427929271497748068342690213991707491115445413140859740482959186024227616377454531805749180736700863648663258910520198205760375727899867937645622163083304815955402598214976712655286175624671893539673068172120613290880503614440004957010458255469774287344198988168780496350286219383906192401923310489444670837618343011413316177831554304813263293, 4392082234365429459669635522490994995545586622061892472817657701654688511628534821883962531710455275948798581412337865098670688087280709878221953558349740960329160083052847343991585094759562763366071177122979453158141777809615757029472963694552128931278267696610442930805576661385112057944278069707887638239490706210686333113376066401571156753733092557168107224196049486567238631166786676598900544251407195743615657256591953956049341610070209608544320990612354876845027617374094455067062785749092329211594227845595088640923695318792943759161256049917608399044564463672780212345061033003580514031008070984006394521668, 6978684590718573243656949612105542758488203443423350685382013479128441571089892176317290844763856663774755922991003851926082052833399193817638062111399819008457173066656968710933915780345439852889885256407111306528134824030362697685736295137459712033151836378581847902384300946884645175079050691372299609133912373238921511680524246835804911263766704418407215767692780171673688161098855454535667470100406268512578658298590762764201801122154299700156455886608231139966939989436753650901587246230468663005258431711603830727021655440551309738459469083116564621458459773745615809415945961545341435040532110184451588706909, 7730262380985917599887572033422177147289651970502093448402835145164830024426315228806715285722659089566236129886746480764786215693984588815504124791891393731400575988135841499609611797069840377647924075117377822033352586269608104804125510707845643611710455554838427560803831147423159767827522768368918988345993436576494036323665588754259053163989171434047082195256858849152960407740290442654588260794482691958589991068313525613320625439489177141737508702594419202694397478381467839720929129426927668998377854144326405841432095191488744613115154408572282654135532074279295245338650730047025690759623846022642571071963, 7870428672617888994422906853248211446366754259733482277745650556132131582761503165723404791505714110195629648744360328326420176714096715656418558504951970022788814322102278336415722851826552839236483969562821649541794780657722003849928232610560989749085154296910943580468121448389230575504988958640111467569744601441342152829070870718010034108398733578934054919041551400855436743799387390257957855545880360755020395022783083503166714335601095744185285348725860445725936407700491229265197561539811624147428412389726767719262845468067268220408467424614068704646047656505819137603600314223155281334867541677294657269390, 8609510284694803043189705088389821843021038300248628370429317978814889304430328856895995414830838739620301124621301721537775180909783646308710312015748757692570074444146048063288330338241388649181127306992151615819806150752330593447168414624657327459419994792062262566992856822874586796213398413460564073159223988672183437164224830058703931407420751347450506434382840960774130788709586835237024062653074786060686562890430445063234694495435768852328222652802008741192860317680389695015771978657721235243624844185665810736779862719888645610567314465422364407861744887985325045151347091814327252867102598023702123634893, 8764012548720665713701201793155399309870111965369993371803350036539422185650799931107265721471961540862241262644925810817557287987388612113771424453413029690339343352048592343900357225140896471551985699215620154773850213962677651930062137448251705285861554850231313763242085813951196025573454108680549038776926779092562595635561865377427363791539907677647388233742883434894879173415977599370552750513325217529346778748301898211759441267178121774471269812805873578379664777277726959180923972945741326150250571072096537087980515856259481465906892196132539685345329249252030441836333228304113901123751209313594774048411, 9008821235404534774894891840865644757418002303365121156019461336283705824480673407281784353738233629927976889096625448460073180574899056351401937861566897823469165990311234532903677780258240301012377511917098868850017485389860900161403497054524629055763134706771541438200372479388084747248076874591357294592908214804614821614134453271058041821309928429492064920317496131336615880002176651354627658576705156794615097981712459554762647700173303841240037417204812844860127520500295842333216976016883771600927798062138428278165410002807841897458765380987909422855298376904935944755071636375020175879303691494691648729571, 10474911617314344093035296274381234749101583500527437860041431188313938156453438490783669910408601907840231565111467423937905944246300919566807077410926355571241589514754269643137702018163430659263615177391720920777071669679112457463342818217687533446232740783283032619985290522536451057260694049911207086850829161304525815898322999460249349418001236987856485233784175562194872850068860587367749350367692115642230663276488474831786206392289391683584796316038243477608620299442818925558267755743944966965590254288900990166554824598295411812423812057962439493264058570961162833692763593404011287652460274292011178704229, 13110381638342217700044116835482318354178640599253721255902105118218292921908590875402841920977595295587154969905468217393514029780192254567805167189561981288346541104187097786158686610182752582262736216900889630694589441983532956902475092397149348354578876977278601897135958677041840489787116994835677415918526784950587842308692695028053266428000179056540851210672916239382320991277325978720399398297894385691874713065477018336173537483516990191924630941831467023912809007439219185416637094870113459693399267881245563091987656247602891135995257754370121186475874895953059792350690971513600960862888017703690554083459, 13722721572470236588898440206865856389152421592146331372623620761105236258642769428613680530235913336412231001256536483370539801648315256149288975606335360634006014491805081550253603688595254959670129531815820738880819515467443628589419885739357776607879281030305390788462268201177519696379582421075205825223506882790846127395851423387355250518925599458496527319759716961190269475043488198823985171705163502605280956855529982181144980535693738091067309543085139412462069952512044802852746114286283887473219768202644823684600027741551806766726373880658547387314450097217066672915328591025976805608015523890515132426387, 13907378143102130732902591528175452184668250175669078564922722729277532332899307298492183863825002170085267037120966710137296520632659066245811450863381591820314104559304716576579947768421047268607544985860210956387427521210211129755935598531328869037393608408989674670981088938567613781468335811260237492104595950519517518617578677677787025453461327336960623845610621752404588399599991001699803056576669100638249157172825774364065063815561453951010729993716989597143669677725856650954155213710311820417545885775510044222220541796461890558861039133971629201524057880779170401640703503019641132712790726669921828415791, 14120400860385637396632607286135661793958438285062218101343811442329217898129411032002000350977425825996409346097620544352258144601308497322065150782257038383914436998782920142187156177557396917159637452504378331382141301919552487290646033095326670250741650299062291668092793457098216953317991446828793222200503107261585592188754090447817955186450059917734158228634856449513892854663100410202968587025379391901260869884847048181290904241170031050049608323224619595992013998760176044527640260560226425674718522654115796289752023951046001416701610705547940854507383323162061543349749057955527154808438878655873381924405, 14698896348088063156187270997421588677714399061222880874144618906068645039117367567961854550911710929776929577319055009436987940195644271595440197688498312761277731697978188128431643248470794438585436719216257105191878641049129049923301277529851691883566500423292922218796681106904405477311127758973402766359242062810538614875409810216565025132923823792242500786728482925652318681058145996956719422754840265487588886384210435421642534141346623264992306879009731648539475819770296162993354959588928869246795665015356541113141789547198151388517967205114998707046242427529782450631008568205068970921337432050960660682459, 15029884228277986489199399805546744756384194842114602643592034471387136929994797445880809477875738231285145593249223445053535965293809750894912475666388265290853063554307747052471064827789230626431100261538591961826419047326217130106954938564102444946805966835435441345928820303084749906070834370292328693504130454703539813471516484793230944669747561760610824827040233316834137947013336066206964971490936063361717836670055655255008278013748443661849914080655007167036195301285165244039723352500939219835986599194370637835048745016392523067465483063368927290961796554522196264881536578834490630583213917304029865939161, 15309200221723806616467815527508949449508016308667619503475045946652621652525992305168651560887284176353924931956269939787077811973514566176608684620809151397625885719537402839920369797647002257990605085738377504988859240254084164590957509486682488178961349129559926308115898888408809018423909717677181884526722126502322318455704911203649111381107113783748969172970323298774692322646329004904087523994990271905442581272126396627211570936941571392711592683960657204560162191971440131508850959242922017207256661353383453193118931908674343390887637124979355811285785638033429254835197971636826274879249886842048918432736, 15724182462935088662707915446655107878278152894209881300967803307334781347515606304746531472463196270125945780931765849147216669235630418637875694444778675771594247113061143844136107527843426140240070502431201960657331892635213118991405460668666027672294906783791441223090507736721265283630015340939375871798311963795515181453223204337362840111547002251197009848653679561190486710064616795228154486847718903419257804283649208020835219877286500226549440463845774258811597945314325403472598511132833259835975605936073505765246811661546643859844350550681749257518136665405784760339373876106842193544962035364141936283753, 16010598613006269242394494415481073404802885743759056303920374396389364406805008152009154054902831052653758678196829556029416363334310779301534650601102392985616360749664385284718557734612612334579643566581651102242306222193227111260448228193714693240481130347390382116855512299873569881326939972343314570039547897580924071328599722614389921295511670529095683738107704146361532800780429539031159556496976109863114080778133301779747597407525649360836980458868113543694436862963884485475906909931191611405995601484367864575876650055986787526037062685039522257827670426684466191523819658566267710796063797508503673575508, 16176225157815061780398885654620420828395273758161309313595904684794782916031471005382323856662285262373051339479066795020066992972796748770489374700029745240899106774349950323621974876991346899532267757945372794675963763211677154442477490480764334758589065403101041835380412036155680032278713692380636751799800174173937468277604554776759076686957635653867348211328058462563934841255845438021673179325752005903202195307236777237380608739528664802974483747876242106584283139484518385093456386588108230286642702223901374448669968747735244954159162896226605024555185352576619896951345620018917148886974802087005061112135, 16681188269653223654724315030136682210774552752554458086958468278548783168739866695726975896035811383412108751120213372631892032120642218357242947180926422406518062384144340315186804028028673285952917556435047990619394575021747680589947318197008430952647870055239411272055715760414079469566525762018667573302151696340104245475784099738670745323261117058044792751584716381734074389247651104965039208100878784761184187575420884985536037251587193757974760803271209026578181938823090178086385927565035063194430696540320842560908821318551920518079959829776767797371769064772564881430027427764161144068312324251665729488780, 17829658117323428808747868598742075440062137591346852189083905589271168845051505272630777599191830286419880652433509964145788364929611644511812576526573426916933568982874857304389571078641719134887390902234897633109911630620064342448365833021501305097046535685687516423128015236731938861706627775842928316810722656485753731575710818024516292222339926273882441860157758675960292785969030577768637311050941129992914285935037973635612973287046435622821551354639344767359753011162290622995439092970304336429989082391680592785895499607898534896211918901223135266662562647266007027360588113757029416715494934165222739616683, 18142530606909716062376251786389643324197492525662369626779351589827519710596398063341881492070698478957535529402981903035193439593816123316087575219925977686245766113691521350584328679759502382807285523704968935762596078425008178057360086647386696939735982650179504583840710564525731340265745482252714541820058727354731450644763797071558334414897585733667272516453556559972684675125516239673811780523512745567106915629379361310179451294037943334450423100411431081620714967277818090200519889910181746783471882899674667241036338987708997780333893361059800622713833148966642131905197255377905810743498001951198125311059, 18916874915493297936079891268802075451235734846035427583955430843324283662366324633202233385782932817340850020378986785716061936989209245162032573305936283861299211919092036584752926046345006676182392365941514696661367329055550272171753927543111392356350737216020653037731493630053105987250335352958368913760588484193482490045930904427197949983588313643868410274754829287237363788001109161904345279546393663787324578514084534019735002594130069819170331383328434044289905874038021158845855747798172165049208337121421852611456896877370705022828767867961460247191792131749388018583310316369606660652603473617620362220776, 19761531445789644550941649188821673088534370105097262343329866705687995865103813168376859916409080934942621503804632853819460640556129955518535485874638416201423297931706690054251711146751875933841075798086049232897482741510517534219163312537149829346821694199026849981873391746409094894635786418504655918594084378562506966684113615145069297495931332254115518216812302704944162971621215874347240778158691664956918543903100361085291794226778736356304744575442579466683011144983985184446648189753472950753969800901371318514176099102941183927711143295688852105189853285767981704534129685617787251540530767915253022947490, 20256094547551427361159536964089120192470579547856867798123148497076148597338094007239708853868154430044018965669548800520357708625488500840886524107263842898564620995651088843299156623903379275911887021467406220229809304913979273339544306605180744927202065302617395980949445708701034751035277692178613703611237789111970396029694552402613307432231659723290421165555788483472386785358943811922285121036435102796254087074468046006584551405865525781432291674627713381806461231003764884384009047079053403228562795215671383412031358781402019097452515349062662042796744413040430120541108838183559554461277378419187930920413, 20363523683403754850477941996268145873307803894978921710228462628146999736940222671129222862265160379946415684464747917659662321205107403115837157035374067466188228334375906081151411079001619437896818940656122691708169785711806055272700179185892964477917806030204206763229340531579796772278526520943763997401381029845705999036446407497831084737277684996161128395539244139220962069262836778956401801008041186706885436332324336681638085145485728737526432916392575653655187967807139187810035548902309557063161478464221501395056289134752409225031789805569864167180786090815982754846720197089740299363472750121282729340973, 20814912434079654358712994986655938285672355659172554521972448981339195273278087029468453535698010595236459533086499060463317723686547000241667857244712653564557545738168820338242942485233926997951781862259839493112100996378583435254659260667047548564231904421776634552680502559175487802626042304303449745827230709927179704869112666087937034760280611168221409540432787302943151703739428105219869226885922197133645265907625314478690899327851652074282189138427005746519010639537824886929608878348016360424645895051778822009871610495121610883214100573360743476671172464995366677557757239376079084722813893096016326823606, 20978978782083985514808414763592752188297832781732994978611517153950737776001188808668923478821417090172961435355822072526474663371493271175072308071960227368747274906534977118068778902399152185246696702689800010100729290250592141361416806610123159371068751278126481137723149743960233299432386251076215253444110113219693470037719585135531616598037376091905011497168565184564212550608338331996940342482386974738408168008861574665395721197042150006344988032346900944468633093984681022454475106597004968263850271320396630355903399323458669065574677651201990075334529713587085951400864385000308137999968746200082025015416, 21510393992991434219771555281382073811886457282216421285690979093137458508475954568419056773565332788894486275426908163637126421408657102596322971185031241956913463507854888295227362444328359266706872420059719619657069662925599952624262906407162386789979523361641558714567193670965811155805593371330497659154542639258412356476199441487088405118103359273682288473187622391831093531374603531951020860755898239699034003278466710154923269181470911166256665818879112416320538492976301262952831443514831107346725637206419870968005748691921100981160236843650083592044728031025798498262451919405184577923803192873012465402408, 21702370286383142896382980896421981414971906140748132749535149467159561579953330771029906461700411301795811236217402115596536451372996903939804016345835732303546870765245612262653631530944318690150045446899350265189274003884240988723566380751519278171721537440720211256644999794264781281823566708722358903968738834874217357352233640572984862487562571610283183746852625175244503706166323292070046358158579157876780137070957640130723554973407811810584917266738218587446647624045843454142231125439581659799761005303756629310091897520981148547565077534090671712715361212723249781422387730181374938558849132220687101010195]
# set lists
chrs = []
for i in range(0x20,0x7f,1):
chrs.append(chr(i))
enc_bytes = []
for c in chrs:
enc_bytes.append(pow(ord(c), e, N))
end_pr = []
for i in enc_bytes:
line = []
for j in enc_bytes:
line.append((i * j) % N)
end_pr.append(line)
dec_pr = []
used = []
for i in clues:
dec_line = []
used_line = []
for j1 in range(len(chrs)):
for j2 in range(len(chrs)):
if i==end_pr[j1][j2]:
f = True
for k in dec_line:
if k==chrs[j2]+chrs[j1]:
f = False
break
if f :
dec_line.append(chrs[j1]+chrs[j2])
used_line.append(False)
dec_pr.append(dec_line)
used.append(used_line)
for i in range(len(dec_pr)):
for j in range(len(dec_pr[i])):
s = dec_pr[i][j]
if s=="ST" or s=="GS" or s=="CG" or s=="CT" or s=="FT" or s=="F{" : # TSGCTF{
used[i][j] = True
print(dec_pr)
print(used)
#decode
def decs(flag,ss,w):
if w > 60 :
return
f = False
for i in range(len(dec_pr)):
for j in range(len(dec_pr[i])):
s = dec_pr[i][j]
if used[i][j] :
continue
if ss == s[0]:
used[i][j] = True
decs(flag+s[1],s[1],w+1)
used[i][j] = False
f = True
if ss == s[1]:
used[i][j] = True
decs(flag+s[0],s[0],w+1)
used[i][j] = False
f = True
if not f and flag[-1]=="}":
print(flag)
decs("TSGCTF{","{",7)
結果
TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}
TSGCTF{OK,IsTHi5A_un1x?XD}
TSGCTF{OK,IsTHi8lf-eUq1x?XD}
TSGCTF{OK,IsTHi8lag?XD}
TSGCTF{OK,IsTHMFlf-eUq1x?XD}
TSGCTF{OK,IsTHMFlf-eUq1nu_A5i8lag?XD}
TSGCTF{OK,IsTHMFl8i5A_un1qUe-flag?XD}
TSGCTF{OK,IsTHMFl8i5A_un1x?XD}
TSGCTF{OK,IsTHMFlag?XD}
この中に正解があるといいなあ。※競技終了後は正解の確認ができない
Sanity Check (Warmup)
TSGCTF{G3n3r@t1v3_@I_4lways_c0mes_up_w1th_b3tt3r_punchl1n3s_th@n_m3!}