Learning cyber security by playing and enjoying CTFs

Cyber Security関係の雑記帳です。表明されているお気持ちなどは全て個人的なものであり、筆者が所属もしくは関係する組織・団体の意向とは一切関係ありません。

CakeCTF 2022 参戦記

1. はじめに

 2022/9/3(土) 14:00 JST 〜 2021/9/4(日) 14:00:00 JST で「CakeCTF 2022」に「N30Z30N」でソロ参加しました。競技中 274 点を獲得し、(得点を得た 713 チーム中) 156 位の成績でした。

 …というか、Crypto 以外 Warmup すら出来ていなくて、しかも Crypto も Warmup 以外 1 問しか出来ていません!惨敗です。今年のケーキは苦かった!

 ということで、以下 参戦記(というか、惨戦記)です。

 なお、昨年の景品が非常にハイセンスだったので、今回はスポンサーとして幾許かの寄付をさせていただております。「良いと思ったものにはお金を惜しまず出すのがオタクの矜持」って誰かが言っていました。*1

2. 参戦状況

 以下、時系列に沿って参戦状況を記します。*2

9/3 AM

 24h ガチでやれるよう、朝食後(買い物に出た以外)昼食まで、ひたすら寝る。

 そして競技中の燃料とするためのケーキをゲット。*3 ケーキ(whole)

9/3 13:30

 パソコンの前に座り、気合を入れて開始の時を待つ。

 BGMは「君は天然色」。

9/3 14:00

 競技開始。『frozen cake』に着手。

 目標は、16:00 までに現段階で公開されている Crypto 2問を倒すこと。

9/3 14:15

 『frozen cake』のフラグゲット。まずまずの滑り出し。

 『brand new crypto』にとりかかる。

9/3 15:00

 『brand new crypto』が想定外に不調なので一時撤退。Rev 問の『nimrev』に着手。angr にやらせようとするも失敗。

9/3 16:00

 『Rock Door』が公開される。送り込むパラメータをごにょごにょすれば良さそうだと判断して取り組むも assert 文を見落としてて、ダメなことが判明。

9/3 16:30

 解けないのでケーキを食する。

9/3 18:10

 『hi yoshiking』に着手。AES-GCM なので暗号文改ざんしてタグをごにょごにょすれば出来るんじゃね?と楽観視するも解けず。

 解けないのでケーキを食する(2回目)。

9/3 19:30

 再び『brand new crypto』にとりかかると、突如解法が見えた。

 並行して、他の問題のデータをダウンロード実施。

9/3 20:05

 『brand new crypto』のフラグゲット。

 ようやく解けだしてきた感じでヨシ!*4

9/3 23:00

 『Rock Door』、無駄に discrete log を試行し続けて(当然刺さらない)あきらめムード。

 このあたりから意識が朦朧とし始める。

9/4 2:15

 体力の限界!気力も尽き*5・・・寝ることに。

9/4 7:00

 起床。8:00再開を目標に復帰準備を進める。

 ちなみに、朝食はケーキの残り。

9/4 8:00

 『Rock Door』、DSA との違いを精査して r、x、k が小さいことに着目。

 以降ひたすら defund-coppersmith を試すも撃沈。

9/4 10:00

 体調不良で離脱を検討するも、すぐ回復したので競技続行。

 順位上げではなく、『Rock Door』のフラグゲットのみを目指す。

9/4 14:00

 終了。Subvey を入れ忘れていたので慌てて入れる*6

 なお、ケーキは競技時間内においしく完食しました。*7  

9/4 15:00

 いろいろ戦後処理。upsolve する体力は残っていなかったので先送りに。

9/4 23:30

 ガンダム ZZ を視聴してクールダウン。*8

3. Writeup

 2 問しか解けていないので、短いです。校長先生の話とナントカは短い方が良い、って誰かが言っていました。*9

☆設問

oh your cake is frozen. please warm it up and get the first cake.

from Crypto.Util.number import getPrime
import os

flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}")
m = int(flag.encode().hex(), 16)

p = getPrime(512)
q = getPrime(512)

n = p*q

print("n =", n)
print("a =", pow(m, p, n))
print("b =", pow(m, q, n))
print("c =", pow(m, n, n))
n = 101205131618457490641888226172378900782027938652382007193297646066245321085334424928920128567827889452079884571045344711457176257019858157287424646000972526730522884040459357134430948940886663606586037466289300864147185085616790054121654786459639161527509024925015109654917697542322418538800304501255357308131
a = 38686943509950033726712042913718602015746270494794620817845630744834821038141855935687477445507431250618882887343417719366326751444481151632966047740583539454488232216388308299503129892656814962238386222995387787074530151173515835774172341113153924268653274210010830431617266231895651198976989796620254642528
b = 83977895709438322981595417453453058400465353471362634652936475655371158094363869813512319678334779139681172477729044378942906546785697439730712057649619691929500952253818768414839548038664187232924265128952392200845425064991075296143440829148415481807496095010301335416711112897000382336725454278461965303477
c = 21459707600930866066419234194792759634183685313775248277484460333960658047171300820279668556014320938220170794027117386852057041210320434076253459389230704653466300429747719579911728990434338588576613885658479123772761552010662234507298817973164062457755456249314287213795660922615911433075228241429771610549

☆方針・解法

 RSA 問です。暗号文の n 乗と p 乗と q 乗がリークされています。 n、p、q といえば、phi = n - (p+q) + 1 という関係式が目に浮かびます。*10実際、modulo n で m = m ^(1-phi) = mp+q-n ですから、平文は m = a * b * inverse(c,n) %n で求めることができてしまいます。

☆ソルバ

from Crypto.Util.number import *

n = 101205131618457490641888226172378900782027938652382007193297646066245321085334424928920128567827889452079884571045344711457176257019858157287424646000972526730522884040459357134430948940886663606586037466289300864147185085616790054121654786459639161527509024925015109654917697542322418538800304501255357308131
a = 38686943509950033726712042913718602015746270494794620817845630744834821038141855935687477445507431250618882887343417719366326751444481151632966047740583539454488232216388308299503129892656814962238386222995387787074530151173515835774172341113153924268653274210010830431617266231895651198976989796620254642528
b = 83977895709438322981595417453453058400465353471362634652936475655371158094363869813512319678334779139681172477729044378942906546785697439730712057649619691929500952253818768414839548038664187232924265128952392200845425064991075296143440829148415481807496095010301335416711112897000382336725454278461965303477
c = 21459707600930866066419234194792759634183685313775248277484460333960658047171300820279668556014320938220170794027117386852057041210320434076253459389230704653466300429747719579911728990434338588576613885658479123772761552010662234507298817973164062457755456249314287213795660922615911433075228241429771610549

c_inv = inverse(c, n)

print(long_to_bytes(a * b * c_inv % n))

☆フラグ

CakeCTF{oh_you_got_a_tepid_cake_sorry}

個人的には Warmup 枠がローカルで解ける問題(しかも RSA)で、波に乗りやすいのでありがたかったです。*11

3-2. brand new crypto

☆設問

One day, I came up with a brand-new idea.

from Crypto.Util.number import getPrime, getRandomRange, inverse, GCD
import os

flag = os.getenv("FLAG", "FakeCTF{sushi_no_ue_nimo_sunshine}").encode()


def keygen():
    p = getPrime(512)
    q = getPrime(512)

    n = p * q
    phi = (p-1)*(q-1)

    while True:
        a = getRandomRange(0, phi)
        b = phi + 1 - a

        s = getRandomRange(0, phi)
        t = -s*a * inverse(b, phi) % phi

        if GCD(b, phi) == 1:
            break
    return (s, t, n), (a, b, n)


def enc(m, k):
    s, t, n = k
    r = getRandomRange(0, n)

    c1, c2 = m * pow(r, s, n) % n, m * pow(r, t, n) % n
    assert (c1 * inverse(m, n) % n) * inverse(c2 * inverse(m, n) % n, n) % n == pow(r, s - t, n)
    assert pow(r, s -t ,n) == c1 * inverse(c2, n) % n
    return m * pow(r, s, n) % n, m * pow(r, t, n) % n


def dec(c1, c2, k):
    a, b, n = k
    return pow(c1, a, n) * pow(c2, b, n) % n


pubkey, privkey = keygen()

c = []
for m in flag:
    c1, c2 = enc(m, pubkey)
    assert dec(c1, c2, privkey)

    c.append((c1, c2))

print(pubkey)
print(c)
(44457996541109264543284111178082553410419033332933855029363322091957710753242917508747882680709132255025509848204006030686617307316137416397450494573423244830052462483843567537344210991076324207515569278270648840208766149246779012496534431346275624249119115743590926999300158062187114503770514228292645532889, 75622462740705359579857266531198198929612563464817955054875685655358744782391371293388270063132474250597500914288453906887121012643294580694372006205578418907575162795883743494713767823237535100775877335627557578951318120871174260688499833942391274431491217435762560130588830786154386756534628356395133427386, 91233708289497879320704164937114724540200575521246085087047537708894670866471897157920582191400650150220814107207066041052113610311730091821182442842666316994964015355215462897608933791331415549840187109084103453994140639503367448406813551512209985221908363575016455506188206133500417002509674392650575098359)
[(45407329054347031671462943733352990423405785239871852919766388653716380674478315503174214528590036701783624146580550794165374415239306839525663023158300526837557014080909086170028906592103649042424746066914113525159948460918940298801848524927126031315219782495938440479872531059016544239798079080583435425272, 53803936997086552930627817379668506302893396793752623708360134917132605596928214528571105049705120619752149234071083180369925875862051592731789425096964405472100251718476911662256938722325188400861316756367788140688700177508892203256571533937287519223938863342057635289100232219250241102383398900866693695652), (43655057390335874506424383722663749879268247658758301232763211203219034349589651957189919237836443955915188039020164771364408742547530334210779314381716283732476569324383808908588686811442984537157164133686423953400300793137466630580146269650901652256761231520608826151296619038805828021253934922305783052068, 22233195992702924578524207396162236484139847008812639391463164055567886910452393492091463760246536738125831803192662206571576172793920367252270085750654989763310242365985521455667232114869169344954690807107158884655752698402756382223555567145081598370775906153285079937174531239253543407433367582200836610175), (48173873193909006408632297373915173790664659725746939094589343816073423919263047699388435118407574844268716955427868555631969644087988395036364141902594843243379684314361966560751185147668489006481398858464098338093514824123877412587515749213491292900765729982214694907759173091312610985653757846721099693705, 76817816373615148654537532291761513097163971256744831379142858777846475358054723383285667408330406512928700971894048395942516839805953619252254847283301512970930741216713747079850697370802425515835725740876449005910904484351656611302288466232416535480093946267856758500867503009449274185328340037258592716371), (88181556564448552743470651647613170657265373286576775460516559200455566480309480705843230497653790999582490266271313892072511625577265833270079728068505993491356494530077152806136276226195967028046339189883006809964435844460698466928587302061692926433760535217381986144262861862566381194116070709037208999401, 63370723636020229642410979908187071508736381021595789419457496843573386844198640322444487840285946294022122763471233336770659096823580764650076994457887836246663976420521365592844871147648096148955435558684689798834090516872947869190607978012558695155976981949795502719139914429074964440672738004797662751885), (29139663737789913345103441763780807040514657935189851468405000837294805478670789331447639954020377820647986737668615350421616354471056827872331675736340460779795705242873854224453751149626796824129656577825274945589606806573528485093768168677458644538824156398404420448765270996254466680503974884590730687378, 21500379801479007023353668056676746223176565487836817834056195997514529407585222504949002514061494924818986877285056823370793801366131278299355198753204202241110732235726065633572048452121474192587926512893685587829196851792871282932391943427859886343407845632783583634735667917765301063973911920849180294098), (54809525172944218202784726054498706998986149532511307519365283214884333880759745646278235574064877808157006111870771237203269184164314286476070475185995594824309208502823107324283920052191671116525458147531253950071276884485238114103420679047825923884557258462480734282087906311641078470196896360487749892573, 81756574947979605476650028939295792851475444895060413278232268139381597769558451189134106037964480236110371112516333929656157296036583135264093244894292249727192183265430654608785016023574686377239496707149469240805172256538547119578612613881470987817240447366420531027722797626494948409537961295222642021444), (64581946911869470666097268473392661044475969923339229140927358267556528172213609787779696090622053952652668978524338470162911316697390949808783655611617876109211286694343109621020960295832172147438415561956308406799304243867943438522877262605902358753239812719829300922953429837677373207350383089531945242948, 4989202309903010953719840716160983131923824435926216390772665631159083535342650887896436920339410183623631783629147570511670117183321361647935232415882559823843152346725088400015157458185719803768183653956581039298618112278104252985108558324521969323520284557339380818947379242004241551972067129406796808935), (24050664789314886113720668704180550072993106310870346083253546267042756407484807570451813004260765063606584428605639572513424172325412403895838039105709376823365323159655659151408268823133835771975457499029638871482209996359202745481739217943688219653831455932633967649578897001344404083554900566236885627737, 5078862691592128263352852510666122840030285630831638766176300357522807318383846716106216568460142803289566847692345952651963412612962105101231388253318702295886925661843963084255196924883678429164955546747674338551155382989815950325295144708239558070428759268472145434251227219248376558739077877118530558188), (10981182755645110147840880990626281909200842864374510902944701655395084603646573786166543516890533214506391857428638845372253733737156456082844743708690266620584024715320183807311628767363209619331085192075820717082732277252596167259879519767012311096053281500843889124066588113231154849160559020474649842587, 48628013989694927962194395415798795873416288084308779260579310956002594515818120285022411082944390380970308604763496857968262138386211780401383400041921478603479196794980964506028622926717244340252781575614138892749112397650400500418854520548246410937778301968094406721694358172486175037101358211904305056188), (44360277072700564667964173299662488309584045678334750273307585678949472488131125933301169268398108693130870610851130563562090826740566901389184325759939555672952981057592887466739014581815332917890531875610787126374523236060844599081895057821080780548090658842826966188770983803744090187804553933028284254496, 48273434685515654186832795186583256450895711192312545965105109470933068272806936185591944079210941237041982601541620984754516345720659776503957564804487602583312942065077659473295380140474319873730351072144589623573969204984854137989929858207704633624005052516826707160016060208365297336358565522317813767464), (74277933307236164326757644922067920801480785119949118589560723492534913135703754520437407922955182889954305118758677121762622579641738595489644476162454299651705753977649890831175535558859659525822911912287630717322506427309948348019059409214267177709825073868587534379366078072632602447954405890179938497461, 66602388097201318405705296520564795735953321348327797787051884532396438924734024286046743628020460734981623607608174540900808784257988960564208045076250282711405581704384244359869398658420527457430106563782524831815546242794912450142390719447021885168566182186664874168746315737538628598891671251478646569617), (49120599997213639306440821727046825314993860762336395139600472507067816244512545746326501825105904276141522344200215109677387108328336551306880558925846585406040392548038673084306865894764819849040850107321143831794486395912595925305805216964539591635806444085598930586673451131584169589994976970980116536532, 89605574950696010170500382341449965286291373776728773984278459956617560551368218268682897979905299084006206665281133782058303029897527802677831995496318862776228671169484298444105000685342284902044064551058007429448992686320553051635977774855333332367078869021201194024528642186911178765073214845075915626179), (41611080343606305830333831923092927711590469283988442378503884159556024189514675436427506145898811044466140448358948186450665318639405341140042120267729049393750987970242498568755250433028344998764727169201091360941372506979616400222249776986452044815280977489214216970290556155565929065571349321400040283913, 21139101480491595249130131428878444537421820606030591689582012187092436765245740512682059135054538501020177284744367692064170753062316751646795161243281614703026407863201142981649528660337350889287055807832758516648170894331032036142036299561727043692745576731855213488764703066239572002910072596534446393839), (20490987020873393090008295620506280766213451771219628158341596111970095830892210293314699090243454110753696301316012556612494750985052684739657739104333864805614326073598419607021749253786050899495974576862156596449007947396263782649180518906154954849534631495476172516357072199237048119032955986061871862791, 52850861480093344347499519384438724817363494693124489593787028233020406143033254649296542300511931220384839505948481451981576902841577951349288618983278854982070953169642507493786846520358246749714992587127533832169910307963688683661599706837139677683369318080006636158263924710701720863830868341920715621682), (80853409152239099736735872194427808832980418988933693163305301375040630938093028681852130708526237031395461431892234731310784471397739336729179565396082711796484062998605410852241177946554055329289624332615396579952280692123661602733627502500253572150193893738215306126792702936942644834961376146152970407738, 80973097743756544665373698310048627537644987905720998071139881933189894486845349857678406443601125043131283549635099209537251523375887247430981981398224532015713216627147625029264837776848999772480406852744590074654410393950652962445457596572984039590092010512293665086904971617310470279237797895412618927277), (59319218621513273128759439143529671215875449536774356293431900286422749894438024740465572847569537475961532836056341881145173986346241368533905956600097412766460790940244451498575184259494816082619182998930076428238477191215660480755765456754809972023953106617826139962192056600709733605285365791427589896063, 24357887632691962970976985089558301595349861281510080484490644157364225341499870438287239961541145111386858884723584247791193028047045783102378922036816196942514480950800457281669365194862805186378709747930469075093267406790928074179402303136297305267690633892780347370398107941822532133246372257691166589137), (85217094645426637465323870559419505823708464072911745322845791142515396143425435811563642023523280324556875259780157674349099556725355218085572779434795588790477800050416896639675576381808694134873024789314835498701807262456973666346363213730337324857207545199143824378358338525580674936703029527863934630717, 12519809087939336216752652200157609404708023684768262633178814643142480959654963499884725352571999224051592636619664254250643563073654054356328411217280512411346187624501189423266941883486844640544641438300961204859007770951322441443967996040926551311322697698960566208311293321822613221572517752610945736721), (57288946944410943903214662819251894187325679110281167871413777309626588356659202019503729275710180126211456100317004343048505327374757520391179465155903349755948006110029367397809480290273245621828529738326508975488971533561543457157080391945152462726278188796142447512710090859975919606541174124792404163439, 22220712351333069567427557033262698652554044414331306784186320378525310196529786644069251717170491091975461914330553302471323642439967695857824172144862510297924161839180824921039392476239749209905961023229296126307918585113463538803539104363412162799858052198868138257236235018855763409241899887882981736173), (19835741197927725763399748301000918602288178863503542825868728476987269999258814871571775923113209674232400500879120632477519746567852214263869025007738377114685857958449533825299792377249175544164445678950341070121158546719612745591169898168884908959545231778812680867085358082303611071527415161205564845836, 19973222326945723408242843496602781956703549960674918557231158176287550473411113128599088863813547842956991616425799997338489003245285107346467937974857394623924044368870123099167824786346528109351675640263942071929065802641683227178884239625722201578691224998522346953657490728954250643776587537140572714205), (25554167339937618394562541331440243699596295966058060814266447870936244405151757140240692565052844806710069702863805265751880795277656508665531889816911791909901907311088532699704960033117566205664374760808670027185744249102732979464429381517071160543081035706218385900233427838370049446027835362206434314894, 10460575105394286237759519141616855215681418062638006251374699808676359893285222802652035401150684072263112025850103371598505554630968820395367459892333902788733965141740736003965094716675836288257806163369303867674203798850601462147738714424954764249099842558882052587505989161855896724365851599582320083878), (76177848157770995554126299097219136005305052869591323919776394353268855113668448401574787806986472922311408362977960044250384277658584897656648319717109157841717890205487034704796193287500391971452387990211710786779973681681249067924737843830540542383699593967515599366065768800959591924848070827108187677038, 46215456815446016335267206114919934650862972950250342038033156364633267171006631241992835931902390699214514408179128537784649609476026300451597941206872970370714837920767587886970200637691626864232711537713162628036756842418037810519178715245505978106233990651312201760477651376960741845640133156005889460316), (11269955952468438206955851954022014926484202386256826823886154452500212338886038898188721201620401061024335996109886736658009035339755667988846131141048272132722822635684725582177693861955752717084282730289676737964038247479485039795472547492379733367037244088054859338662949818649091943035956826076556245029, 65433665727853015848097740627681436799112076610316711683312555103838308687915816938955064441477704797424945098871481738559154443138532109555026129915101258462126126697966967810610052215792514651190200640484500281048963167521750002080463066891449024638705297266122017903593763805594124143092937066371087923895), (35416095072640273615139991580036629511136986196117789245602474636223514660234557491583069779459875766893399012004707240389838301250537022486354763271510837416178071811362701648669343192981137137248360635747954873589833490186622168968903884443338978446268943170357745021757343452875708216900752436145500050611, 74198210279202177497048622771243543325378352654865510737792920865966497575682474568611935597992838029014306039791404338602293378727904580803502242118388817678365086841674799963903665635455280397768184807595161532934929872572806137182454236958317255052971012347581841772471473480687992025887264641568421023573), (52271588561351867515196054498308231113748763360194435525781167443200385650999864949572633987104405248103420676433070012501618045056966961865458241021369414003548111255496814619027717975444266384925711499126319909395622419682795495526760984707336606251988758479565051723035640753454754302367308441170444811397, 16444883713624365851750068156426766563545673093987671965263826320232852536013662548110110380452441678149404515764945427189802575704944181544359984028658512002740548167226803255435840529894499459314255629463585687990207233378008765188475349935177125177609330643599660398310962024503541326271042730261146704654), (42821234468628925922499698480012095721977867526248078133782929564764399713761160280461971921285020761076172034966101269594805345437358037903565786855873514093673962340842716581898569510841678122603340965045893401564705146110936338224582167919921719329278378952856378441516972965654066654323902174906003000033, 27377479209413995816698490519167619990466277095035668746702445475259897984122114655125884884618944472068139049649061934750918516208397034412287316084735607245406699774784069545578344774542778581678647168519798548865507143806856822650079414653438568508869686219136150973497156053194562838177342993772488111456), (58062507824630699098436920212053195649218896789481183328020847490509112063306132695218080639122851511835046085028434265067694447433041929231094097085064292054615070252348709738602574771024737320319719950726743588561079850547931988475348762931856145934925478501955609190195539054130348208656268997983256260294, 240701597589678942567462606537262408517379321625639019616610094642470104136331371212274921877433194919860924517822357991168875346635862636675924235863363690426243173174951386412868896885371134350949980222922834977337505806007699679766656242941471317825749826384691780383233646920584182111481922165072882383), (4125708060865105810034805509930307557940082978071370751313203826359965822310262019150795104206289727495039598144906535821266535334482886208275533478794955539954388025135438406775217806772699844527794916247081118063961790094975760177446181160221497646568446570017643397423449487509240340320086907819889420663, 1836932230493423935444595413409225185810500755349362763840406820979916981342003381216731048384102641345612767094995028141589534874642358670555482441437259836099452565221930021137434738360827985826025963815377675805814928919685086296626376067237513427288172762353445116713716459393061073846340156263331186269), (65931713182668749542175624921968745524321223387852019959124572941503644226665941539336445826103051163475199371141274310660830281707450938072748016603701892392440880217148099992933316712562459434593392856931861328141117424081701015283680263547142090079870038157955781833996061436329676102522123064378500568108, 5440527496347321506994508711672573238933251703083149620918031771093931068622519457635760247201842011662654730667570064333980117020014786948941988041693219720785794828094785180992573895596442733116650832972187556379729236117021344611360799315557240919128004672839877681954508825352834590163995491746162449328), (1356944228036494354052115490423028025300823090360032662752421214773203791145547594362443303861634714763309825766676513349433093687323391141826224172914812024973586196211119852698426577437766311109737653448871758023686496783181761150494775440498238414290143290345016690420389019576910552329873700538338300539, 53647025961779606832847391790850869437595570215517969293674088318733317364276494740168499102137942708502599001177805749589148451272279632854210269432578175137622820986316262894596402763868063474902556123471455711109621458298180746327647163435838766196485517054947577827216501433595425623318294047201016959347), (36818634055835319932984480336134294202118180114169178278340029248632771412526001606501073071921476491068666947585444301902624121669560367233369392214453933850510490937295150923265557861164203437685491354728938094230921990408933786471266430095673823790308864488561137167464491863521930764623489771316094188679, 78243253311711446851687955119808361600692752383790904970462233046330896607484860563599954268004098636082195540350278465163869608284137609490420748250665474071758292700168482969481920660866283010537956996753569406310395290515467626696881945479350635726382997937817375515940679160678519648656866139988564319388), (76840120041164084290556006661381189107512959872512527877514920633961742522749499670880231032585080472851806944109188987242266446755152383005147945448851053420277198872024989789785259189587547636048850520263650841469908135841501877708766384198114528068103780707035363815433360722834986552182822645576328199015, 50074062846148509248344549604017873625536412277864756628420952242913390136198357561081457116697566296501551411670488204565709073751860962324292103597984714513043114923395676308578056967625728730287462445589954801551427722647685123676662471489873779250940702937440720501951774372278339410119792720005344098558), (50163461428489953576004053612907499265999803490005549559244420438902194707839286991574026422725057995822227837537043525859399565756467356066905283472910075618438714309391865932051246754702870448640518356212066064361705917590156375718618940364950837882254094001744528970874952696293137683097955003541836139257, 59416831451197153325400627969950618487412847588489831524681425247369014731366332318413100528312302406457430083784243145530812220078568460958148665584919203707291453922777259666790107421295283849024591088424471297880048525871963549477450230411394690860776792880532135063697486930540577835681762104363371989622), (76650785761954112630096878761400709592616226052105263087421756456891458994695778032788332981918087001556609615471790802410215094854463175632942570802427830352201130688831096001276671195670309226365859496031221274561958126680019380782574462697753506849739880291609930099751143877476835898387465615709136128399, 18163124475719965357998583638921492649077367745051057026376108188696491652851226275515200025115440688329849993540025587934815359688053424195678298769724820068123704988673437401070099713933516465493416742891546631560955429471883942471987997673330729102413645404328394635861466662054753133042324200080631453586), (5380539094648158144269731447069739831541546529159009232736491767614186283389523459270728168517923165609582059857792404933438676104881557075187157970035607798719928593815044194257316991660153446383026057537023237200172373334607696957414043605482240578355513539752352291933087855038649160500371952972642435518, 37272868681285311892320540335507188665933066274743126619307944625583989880844641309242994172264104275130536856240654702795794628245019325261796193527950164502257585430319910309056987912917720031119981455833930898071491366851697560046931942351194533399707804630258069997772038641702853818050354445826383712061), (49619601666042404929919230892231776198099192378743150666287963746413823407663760261510249035908181845358101724898367887197326614465900064959913415585357805262808888737357476995411160388983031520556857955221448114226657503555243291209732174372112955682752626778203304098712688866512730246908173876723073857582, 44840996889387328159172684354120922743910271777351527609935904388419446604192399230033674446767798727496577933060653336706838452512517818991608987955440414816161584687582489828491246147930682617091765610447626130637711482984612792630768779707575839877450237925908332440975399707860344946502346186776059948565), (22958781771732345187204316848076987975059971670488921431474378581890666325156051036244487445258701810957327476927055333872505448155790977268099260050092055693305945290381751279809883495653200273732061673934680669796499820254631148766585953011229318014006949037465368890812834003685076292396606766784226250169, 17099920031969606234234096691836134238969595641557560110099442393331752996575236468114210450291700024219315980818875745502988508765563496602701839788628476907982260930975252911816033475365459331324611173384318240490739799350982376628136015898958825309612348508000462302444825419853737224215324126815125432853), (30656717514078231590975866524172875733745333807410602534893419474697081425009104025841352062549736884948644989907083309036443738343520726970292297399935912835649102133564687634617790382463038628689920460402204565031424197226853138698386752466244612465622554780889142542635432703304552923635861900506143775559, 40411939854112773751662006874982763230208708108754076427955148550516215849098192289637362074290966502046676804977418190869153220508812448022958731224347361982211815853037715160032532678279968503337767753651613622207283842797787238062598771987554935540753841721822846867066266189363280254793170571538914780711), (34927721763388926767602424145820089007146556548751777041209966424535318837501594880896511453245790503266898485153279448538230058738122729148684342270663901343470406975505891302988672799134893728410201537809950290913459730953924879048199200943848633359325456243119257012096516819114325168592508363238140142736, 53615749474627064447599836316842885262307898519123375179072068969035321756587561417041120702820380537882713025654401116235720269697681865216800482492717789008461487872158923575373325063534869720775850496315429243060685436204431201426655310676074617382385128720309251393897046466243029901982261208809837795869), (26658271065213903276829412050255335866161778308305414643138982804683845629689762402754727571410504259116450598396835880131625743291742656122520066094899385999859668707305721850573152096342336269270754500129460390871085335525846167479466823811238311459018365750625589222883351053639847033610943885943991599649, 63367480038228629776574239235230111545901049202319091631188362352003396690591017347608155096880802828898932071416567549015994091510867537591686345776067606068928068605786963005009701749521472861797647776524649500419313923192547563008808602261806809917044755330974653082688338053308989166815535158991683276660), (4952439175075767251330727193762842236997720733433928601189846086068517067282486951609447942718281473873689518689479945605394409464654427408194024386299148307317024353792207291993174153732131984690664568392440864586138043586025454126074349461195808359204470782496620820683400440432165892188824861921952716496, 39506621564899707276621714932812940323192541772931609001749356244789259777505660780211019458647083034195839251410307268167170038735981658890093081153155350449156436601590917611340975743771353770947072832272282947694999923539012669284326179285910900498413716159611492944836692385252487719496563237429222864359), (353864615957248211456593548147288733436232946830782389022011150746590434381159921866658910189704763825441461517782043530397700799245454880046167616969889911781057708292916945560090386958746449099941160545174414847537391882328267649094245053436745820002827340146511344672380975787595368870462339657090754025, 21652037213978393616033255777606331114993726006373231091791321587680393957895130829759631974249988070479126519815038141804240640412421985460131703042014327575391771490402940753196320750789474882286696753664354806815481807224187709171188658952949971383365563332718716244105523249065157421111498014939122449668), (79169384697457164615264523833308539499979735407436650491360452270841526048713122405348279015429721418043061855398233353397168779743948311507366926092302395881817073139852341961737990430549062587090978216743806556108013068871638664031288673265115538296853290686213055780043883934589609228595174647897199340555, 62408327911241863895511354101403908384365193320276742609383798452946917679645451543513946120561363895216860423860435816254712655540309893892142965018878021494579085911806538824880180397954807628565654230569301110335345188441343069399738042207002537923185480545992609090708775016050438923329356289824368060528), (57585029704785710147539274752112440519580287542674657569968683089795300504397139946906135267906715856550334096881909933439053962717233562857148746789495707412477087370129784583080086526242999957218156775073876111995431994318581809555849108199307439491353909277119541246357971239317242617741054673246069214280, 27783094581614514281943099434364804016073415275807509022317808099388776590435421391884588932646261248401975923176641151156622813742964331714375790433992358143300561413055042425635958892899426849084813550453467707614338438866371515052386327897466646026270540921708343983720539751629019476689295235575153453917), (41077250740866790447100465985972835757982726462659500458904629308450991778147801788893308630744298905682441890370493963568928729814718837595173746804968050978611959808981498423375275551464950550673176619375174207915856618665663730207576153355694485377178216961289488954856674421843179435507819598054184939469, 26943346365507944910774328060510704860364161305003573314236904432218442142210667996605234424941372012704130955756634235542459941332726510089413093757752045374196979682932840844323672339067873233421048522391942009004620967841370138899433729724235359858651523417360570908135708893293166703477175648306908683545), (44918787366634518892106390083981948284260910673245794059352962820975492768657545424155419849313433112996850817556161312708292937974296297335131886678971264108245684738174711312026488902202248770315896208266176179956745037068311877655221175930797189094930825651385648855699846510627865487879029522543311005622, 78979601980305569617075034436907321801372187010122570286693698981250137203506219602621994142455907362221755887868701148905732841841259936959747788993129243051445773507138618771991249338599903885651897365071334835565645573905628503560375804343537905258782853227011815599291047972451442767677107438517640160312), (51666949658924342405733281842482325421179362110161773492542420992274074856840316829859206998128541971578319597831084099753340880688273994524443382911613379373659343748669340243306563407572597950821991792193171177254441460079357885357854109308948330977106915069427096509329950708474940868690977240995549258122, 52761412767823220983686386775820042512355646607332261081358000855107536021620748183437703468885124005260780120587683615619188942840795842025713917119747212781027818368479920356829928227176885980467349098084791784067775441955522606658415080587575594800507630920346758785182432805238692195786811034115547912095), (4588176755849559990874105143212886482880035541789043414137863503174998955303700677664939544294092635264330297338331332472025353697885374404868983266347812022745791486261484476841710308468074387935343293176699241090188652111061009201471278410084020655398474914261298850198927083794356654544582517083472666620, 85037581275048280715758647032757959383085610630899293576052724372440724737517365669971209337352103703167318867313191557640467337378589421291041535531495003509796817972929010027189989169755211790862677386366275992170524712466987548553039479802192929946472203762312347270701433684927840144783975632438418650864), (3611469832376257179006614519466729380346705051637855896476550833890325003288224466267785686496193515771491496483497841040776984006243310160476851954024096573048551125620111694220454335636944181902365044718076881258376330144709071041962521294655960719149552462080191870516037354425762003072654651923475417889, 16407221464213183635954007657263709233538452770187865019671477234874961690874533350646551261362718783372434890533479727701339083999685535471377235169395733060763617558566929717523100821784603354916473874919688995925169330872276438484723896884644215414317687969220990254303782316879515914610145923842361425869), (66294955175369445366051223626345473237935532901143675854858005103759816495782061087246322306776038271143013788759733906443735381065871244386188212319097075575210923933544825336444634222151849856488223023188672159173959370826601447382548185668903025621431463604434938736763455640441028242933588219902343355072, 52997681848706092949951286927541641930134498793535541839978127746460273584257425422628154997042960624404276108032593164982040824394546950557581558408382925557388338099341721349316865553858506599719185450132027746504451205479995111345835638840644077342472032701457683474996828181788207666687459371709901822084), (27911981556337013712930157335239281511765759685689650596325660565853535615228138851465775956483057766153574743199103570947029029073500908901801045364879500836762167827543229258162053359855722283291743265378056666812738510754948399787471865027282345697111137579197232877106526152372524571974306357178805491288, 23170831324418941374725150578818022337382143015626258017291899913538067790684515810732538658724883540277731332253444366276367380479308928538997832156335453210801209925556520553962147115469889445406266331497113184402553251888760053016373852466590775372230369912762092254342458069361123861419318643950013806890)]

☆方針・解法

 オレオレ暗号問題です。一瞬、enc() の return 文が罠で、python のバグ的なところを突くものかと思いましたが、そうではありませんでした。*12

 さて、enc() の結果 (c1, c2) は r の取り方にします。そこで邪魔な r を消すことを考えます。*13

 r を消したいお気持ちを抱きながら少し式を眺めていると、pow(c1,t,n) * pow(c2, -s, n) = pow(m, t-s, n) であることに気づきます。

 幸いなことに、暗号文は 1 文字ずつの暗号化によって作られているので、フラグに使われ得る文字 c 全数に対して pow(ord(c), t-s, n) を計算し、それらを暗号文を変換((c1,c2) => pow(c1,t,n) * pow(c2, -s, n))した結果と突き合わせれば OK です。

☆ソルバ

import ast

out = open(".\\brand_new_crypto\\output.txt","r").read().strip().split("\n")
(s, t, n), cs = map(ast.literal_eval, out)

d = {}
for m in range(0x20, 0x7f):
  d[pow(m, t-s, n)] = chr(m)

flag = ""
for c in cs:
  flag += d[pow(c[0], t, n) * pow(c[1], -s, n) % n]

print(flag)

☆フラグ

CakeCTF{s0_anyway_tak3_car3_0f_0n3_byt3_p1aint3xt}

4. 解けなかった問題

Rock Door

 残り時間はほぼ此れにつぎ込んでいました。DSA もどきの署名なのですが、かなりの時間を溶かして DSA との違いを考察しているうちに「LLL 問なのかな」と結論づけてツール(いわゆる「defund-coppersmith」)でごにょごにょしたのですが、うまくいかず。基本に戻って、自分で行列作っていれば良かったのかもしれません。

 これは、後日検証します。何か得られるものがあったら、発表させていただきます。

hi yoshiking

 Ruby が使われていた理由をちゃんと見立てていれば。。。と後悔。

その他

 ptr-yudai 氏の問題を全部積み残してしまいました。*14

5. おわりに

 リアルの世界で甘いケーキを食べすぎた分、こちらの世界では辛酸をなめる結果となりました。*15

 しかし、我々は不死鳥のごとく、 TSG CTF で必ずや復活を遂げるでしょう。*16ジーク、ジオン!

*1:上川隆也ボイスで再生してください。

*2:ロクなものではないので、ビギナーの方は、反面教師的視点で追っていただけると幸いです。

*3:これはいくらなんでもやりすぎたと反省。。。

*4:結果的にはこれで打ち止め。無念。。。

*5:千代の富士ボイスで再生してください。

*6:事後なので点数は入りませんが、運営陣へのリスペクトのお気持ち表明するため事後に入れました。なお、去年も入れ忘れたと思っていたのですが、実際には競技終了前に入れていたようです。

*7:今回の戦績で唯一誇れる部分です。

*8:やっぱりエルピー・プルは可愛い。

*9:再び上川隆也ボイスで再生してください。

*10:ちなみに、n、e、cと来れば日本電気ですね?知らんけど。

*11:結局波には乗れませんでしたが。。。

*12:TSG CTFのトラウマがあったので、しばらくの間余計な詮索をしてしまいました。

*13:邪魔者は消す。悪・即・BAN!

*14:あえて言わなくてもワタクシがカスなので。upsolve しますので許してください。

*15:我らが N30Z30N は、某ツヨツヨ王国のような「優れた部下」はいません。すべて総帥の責となるため、本件での処分は免れないでしょう。一説によれば、罰直として競技プログラミングへの強制参戦が噂されていますが、どうなることやら。。。

*16:開催お願いします!