Hack.lu CTF 2021 Writeup

この大会は2021/10/30 3:00(JST)～2021/11/1 3:00(JST)に開催されました。
今回もチームで参戦。結果は146点で174チーム中119位でした。
自分で解けた問題をWriteupとして書いておきます。

Silver Water Industries (crypto)

サーバの処理概要は以下の通り。

・p: 4で割って1余る素数
・q: 4で割って3余る素数
・N = p * q
・token: ランダム20バイト文字列
・N表示
・tokenの各文字で暗号化をして表示
　・encryptByte(uint8(b), N)
　　・各bitを取り出し、以下を実行
　　　・x: ランダムN未満整数
　　　・x = pow(x, 2, N)
　　　・bitが1の場合、以下を実行
　　　　・x = x * -1 % N
　　・xが各bitの暗号結果
・tokenを入力し、当てたらフラグが表示される。

legendreの定理を使って、平方が取れるかどうかを判定し、bitを構成し、tokenを求める。

import socket
import primefac

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('flu.xxx', 20060))

data = recvuntil(s, '\n').rstrip()
print data
N = int(data)

factors = list(primefac.primefac(N))
if int(factors[0]) % 4 == 1:
    p = int(factors[0])
    q = int(factors[1])
else:
    p = int(factors[1])
    q = int(factors[0])

token = ''
for _ in range(20):
    data = recvuntil(s, '\n').rstrip()
    print data
    cs = map(int, data[1:-1].split(' '))
    bits = ''
    for c in cs:
        if legendre(c, q) == 1:
            bits += '0'
        else:
            bits += '1'
    token += chr(int(bits, 2))

print token
s.sendall(token + '\n')
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

205201352501296706577599140901269118023
[15551150965336841481303694869076376235 31280307824210708974663470243763905866 29686532167500809255011608954026372858 106309129038325740668553576547575722895 202531659368076325005653483089932408387 36899989699214318343493638727401747895 63095878593574183611076025132760595344 139603090508040346067839585710972344278]
[133511823929658508276605320930926599852 68586205733744541217165989652076854754 95125055626225880615545091125114396233 58406967620528760082049126513783953661 149803365505036756094383920414814034180 55337697109939807564346950612040780505 137524867405573002059152942916469074128 129714072386835569939954105066623406483]
[128649732687775885720385521607178838031 76204584633415310803161678896708350340 204786253625542731010067073941390579527 160304440720186755379605741827373000642 73115465943360493635501681281223039753 159650430042498768063614263507303096475 85361659488918561618080960678978331978 123456508766250080643937363353522254593]
[98425794902769757596716306639794966788 92174663485868637274383535623840358573 75818285289244849967541025638562962176 180289210331278907132862285537725229365 164776478841649708171768154006703309546 196898475808670431539757322983047172971 148808528938083105592657924913417458857 120121982460640324634782225223471183892]
[115056394227165395945251281863618542959 75122527388613039270230125442823485697 117034480692333340306908298750547182987 1438843669871314472396152833444486852 142803248690470930825313585552584556160 91234879379394171868749588702961652271 77412719608943537094763387646810099914 89156390846956305088860301084043650512]
[86192829635697200577218087522899943459 129586423689102613522357277789515638279 155815667661835675814818301461770227888 10212485135984014220307068963077651384 42740615256728263789280142476464602132 7819911283038414646998817462881739972 173779491342105988175201259938793272308 104884949494215628951062126653855559326]
[23457085896895845707206998523185162382 5259437546149171221102572201142630435 185240734713383466650798228124258331001 185955037187995129859497733288068407433 65340204326777479200320970493255444515 72368707321429810047977140074735777164 130475328722169242267617517251537045859 155860175925187117502416307195294074913]
[167333881284315974076689229507936292849 80967121439621246958868367811702953631 129782445878924195241138753525421371721 94541685485544767842606502263635963916 177887553330868767090172627293472689277 146195016766634146570076290040841897575 94228282252782373260284019275845673627 165894835442458505682232521757664908596]
[27627079191803081189498795874627868748 92750378963906147943981362484287300563 131539828540776851482888319039364260983 156297277982273389436032005817584491748 187940581833148381157688334100610426088 69619406525610122532016909182657515854 197014005833487535828398767242650189476 103727650931880287581778336091578488268]
[93359695352067960497958687805523252317 130256350313027598032765038156173064299 182511755067475677810022439401644709497 172720643848505738997457792316018466526 111737541180623808942756845878561402792 114233851666580025244497001560190154445 70535956066086395009129943025469992621 117624415448786377850230056200647559317]
[92285594805332770709094052943031340274 195278675997794609545719313718490751144 66290220940291796682502496143968489379 74582188356191533084742131163342201764 162322236492596447076935974648303224105 122520490762427824874611262823154423125 80342655063526134071906544720414361460 62962578858339846261489550596447930224]
[75038194159941741829719056722047315640 142896132478711771987714869142021478121 121385825808562058103172682192188110478 160822770320337466430249041498628888952 101551593114175050638697193369680021327 138452480906735836204678964256515125740 178242975807969656190357744983715424471 189235561802013679222822581501905164084]
[29208023268952078758314169734331828302 31575796165648827278123934950635425369 129717598372873687829838818378652097018 72627448123432734061519333165084761076 92566789171206206963466118419173482198 140667507776942907234366607998372615819 72045512926442515077667246509030650847 127487924694539321892066736533453851331]
[124160668065795792776067267796896140899 167349962518637938933418758267177534982 113022889506344406365921634984737164844 60649217807726994468712511333963761081 142176351095809333381984017409458561727 100614657831085302527950065195982582902 109657192238613782412584622675817063983 113594650128438423930448472045220085063]
[12624223549004718866784263005147337707 57947195513931203527325943649357945563 27785896821585777774703269039420417306 84698745598981229057306235174243849761 186874597158155713602425267782282008365 159570925999583130335192156674460454845 74976884768597269206124131205506238750 41210158849268768204793917833611736588]
[97435289611410296911178284306527121688 204617103647324192868935876796294159980 80713346298216454647242300111524682952 144361211534468840160576871421355114370 112705443200226417328449002988365186669 9708913692045139739751848467961427225 180144691200330557034140944683713229003 118077983370592709058056959092434914275]
[81349280591429048964841772453198844388 143461533563614820049749141592051885544 17014264063427099447758762678696473142 83752614307257667896895499684774264028 76832960558236829260557562405949352064 66378954906348076753462545555373133579 158644768414361930508332021019700454518 8054683295619130495371596062911939218]
[47728993412305131451931502291552250872 23565345831842523792160044844958492728 96832534655723584168028624329294189834 61901281902075663285491389728930083533 7197696702122637803381123097795861279 113755545563597210552227528438270615155 131204445269445780037258391301346873280 94068747071933819507007583789271536414]
[125552728026235392096233188470748995165 204768855308703680830869863325240086846 102353228058667708035709878745447703302 154851188131576658808473706129586246164 148049793750982061245696908183859447400 39875326904411423450657949118317447750 26823906622662091318638055988729177746 49113285052080237590860162332963904668]
[185614492613659480830200228605006121522 49858624092147477156687742141026495328 14111466418951255666353671900770556827 49246480288598949383181909942870603640 148596901330661963565901746277303701137 204950093608505889253830145585012363982 21406548080121661018862741467018894407 82738943507387042533755879283809695674]
OVGWrpcU4xXvQ8PA7GeO

flag{Oh_NO_aT_LEast_mY_AlGORithM_is_ExpanDiNg}

flag{Oh_NO_aT_LEast_mY_AlGORithM_is_ExpanDiNg}