この大会は2022/10/8 21:00(JST)～2022/10/9 21:00(JST)に開催されました。
今回もチームで参戦。結果は710点で203チーム中52位でした。
自分で解けた問題をWriteupとして書いておきます。
Welcome (OSINT)
Discordに入り、#osintチャネルのトピックを見ると、フラグが書いてある。
srdnlen{Welcome_T0_srdnlenctf:εnjoy!}
Easy RSA (Crypto)
サーバの処理概要は以下の通り。
・f: flag ・e = 13 ・nums = [] ・以下15回繰り返し ・x, y: 16ビット素数 ・x * yを表示 ・k: 数値入力(2**128以上、x*yの倍数でない) ・r: 数値入力(2**128以上、numsにない) ・numsに[k, r]を追加 ・N: 512ビット素数の積 ・CT = pow(padding(f, pow(k, r, x * y)), e, N) ・padding(f, pow(k, r, x * y)) ・text: pow(k, r, x * y) % 2**8だけ"poba"をパディング ・textを数値化して返却 ・e, N, CTを表示
"pabo"を1つだけpaddingするようrを(x-1)*(y-1)の倍数を指定する。kはなんでもよい。これを13個集めれば、Hastad's Broadcast Attackで復号できる。
#!/usr/bin/env python3 import socket import sympy import functools 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 chinese_remainder(n, a): sum = 0 prod = functools.reduce(lambda a, b: a*b, n) for n_i, a_i in zip(n, a): p = prod // n_i sum += a_i * mul_inv(p, n_i) * p return sum % prod def mul_inv(a, b): b0 = b x0, x1 = 0, 1 if b == 1: return 1 while a > 1: q = a // b a, b = b, a%b x0, x1 = x1 - q * x0, x0 if x1 < 0: x1 += b0 return x1 def inv_pow(c, e): low = -1 high = c+1 while low + 1 < high: m = (low + high) // 2 p = pow(m, e) if p < c: low = m else: high = m m = high assert pow(m, e) == c return m e = 13 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('easyrsa.challs.srdnlen.it', 15005)) for _ in range(2): data = recvuntil(s, b'\n').rstrip() print(data) Ns = [] Cs = [] k = 2 ** 128 + 1 for _ in range(e): data = recvuntil(s, b'\n').rstrip() print(data) n = int(data.split(':')[1]) fac = sympy.factorint(n) phi = 1 for fc, pw in fac.items(): phi *= (fc - 1) * pow(fc, pw - 1) r = (2 ** 128 // phi + 1) * phi data = recvuntil(s, b':') print(data + str(k)) s.sendall(str(k).encode() + b'\n') data = recvuntil(s, b':') print(data + str(r)) s.sendall(str(r).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) N = int(data.split(':')[1]) data = recvuntil(s, b'\n').rstrip() print(data) CT = int(data.split(':')[1]) data = recvuntil(s, b'\n').rstrip() print(data) Ns.append(N) Cs.append(CT) k += 1 a = chinese_remainder(Ns, Cs) m = inv_pow(a, e) pt = long_to_bytes(m).decode() assert pt[-4:] == 'poba' flag = pt[:-4] print(flag)
実行結果は以下の通り。
Can u break the best encryption tool of the world?
x*y:1758010187
Give me a number:340282366920938463463374607431768211457
Give me another number:340282366920938463463374607432497873000
e:13
N:107916609569250539574427583235973206950341367815385506778669789114839441202033550988679233119371377154080087462488020380568294875049024489409905309836180127900666147201588934411093870900282350967113600321376224722646537237390195881636183917346411521495263801649756084316693169483547186656901536929440661178471
CT:84547507709290301825702456613915631773957206560899812678991804157862667927802953113897818286371026721546502760667542841802588974889554264400653603582849452366380409606674644325801391756626522964371363023279021541557357389030613682216087539584999747469661259570402232807171594745536233664580046922731822634384
x*y:1184296831
Give me a number:340282366920938463463374607431768211458
Give me another number:340282366920938463463374607432043238528
e:13
N:83448066768953269305142431487810660857725187922647975019843942334297589098631769071864418014170208229655303541903609882087837726335352806868326442800757867257855900172681662327214791207294087057116279388097665108472893736306978308716559344297181954472780783680309201146204482664803259014420018034813737949567
CT:2718411712690927353511111809371653892221190654814407167322235966556627845999746151795157333720616217704110250547737287710768050036713493515935261041122359825872595932462013292917511044324152179043834645947175791423191329881705992920218196168403724353438967888042846766183469573129794435620760557924945605512
x*y:1594691653
Give me a number:340282366920938463463374607431768211459
Give me another number:340282366920938463463374607432936789920
e:13
N:85293850464549357606895480819207681764863801929601807862723636524386425353406770492469194303126902446590317749968336478463256073424510862499549801479934470454517056635029736490599176349442016218814028647775917250096585925580193187831110698896385041036223135688867732094968330842644767994322172449282174591739
CT:47351584040464228148366486137293404547558859168831062000458796983955829233183780253991365591475900502064500141794694411706559864999624665205319367326026000372691436083499892299863802957606706691561044714858295336547798497266601780452476592177829167391115560523514634839336327638380968917778702570697606958148
x*y:2885248183
Give me a number:340282366920938463463374607431768211460
Give me another number:340282366920938463463374607432514550640
e:13
N:112479273863866618976074469220499810582177735452073432286516226899711876580718326713791171424396407470528021556515283108969797965898468661435739377952483543575985192472817833000023252986183111903680208417935776973220729411277026438965472239553208855141133327046925779697298567089729603879166216693694413051523
CT:101262309894983125571414773807092971502144139805076657168245773691699779531726622702611723967040132688899085761667836120263017229925064189826064393376926648640692983400965425078816484384127418986616268844376914969151893695424037888194550260095773458575456344521551595197920404889180460663567702437636522860012
x*y:2160780859
Give me a number:340282366920938463463374607431768211461
Give me another number:340282366920938463463374607432964383128
e:13
N:109405247970647471559524080761679235303976854469100219997963845674027170011911113246578431749795085600414559488288823422371415851007116460294296742779889326073534697052902231459098242709690120044777922222232731728339099712248553449745279219433689679839885069594806578455164847394228619334866955210377361592241
CT:64969680962852579555139860708732712857412031393518340644099935492918852043305892075384566705017555771252341536719589640696635733269992004315424208360264789705030882371069425780625914737261753438486045331431772144532443331147936497382641492044001310387526289371741735965243971394701774512433154973351309124074
x*y:1583518579
Give me a number:340282366920938463463374607431768211462
Give me another number:340282366920938463463374607432992560256
e:13
N:49425742971312582504188795381477993797065394612879120542333146123403768343043533824249841806431337145926404651719812202048466689539635374211535403435513126121440932239408234607555559969677956519358263967231942750177149015312493197010384584021029862015993193927655274106527252594953048585169635278829126644689
CT:35975141543492159812487013086879267758788810411680146304876343864569984331648433409089027117847556569349995496877010250649888731126110881657081691825355078935069768320565897325278255011068314936217134846408374440414358255136762852052596828904640252181951109996958620564331270572101249425099250312835702593800
x*y:2715439357
Give me a number:340282366920938463463374607431768211463
Give me another number:340282366920938463463374607434250838016
e:13
N:59241550531514113251951336214353947928986404919094472352959765723298812388625439862131377923321126420332139180532040607651179276320791098731415997121950901950232323946930860325148239652713723131331151841970316676159098132461207644830290049204707371034702593144915946917262846372957242308616315249005440843751
CT:27362288047672193980583616123010160019043579687163176881694597621440118143238635910235064756359613909366898683443812869055314922705379184672913747710943815437867026249472875307525051529654175260314791529608816017987538388555424502982989500907314739746840786301399008452894357387945109825107828477998190510425
x*y:2510404423
Give me a number:340282366920938463463374607431768211464
Give me another number:340282366920938463463374607433964344832
e:13
N:99133978769897078022536822716888533539999761497334900435190448550610839316374193574607069904156247484527639902407347540758277613083070233427295704116121682478179732197845075905163776788617292593102274513207306534822483336746278757947992828181668481750163721123906520775754556674453171651115705695568246478257
CT:27795974019566432716379615467525677332083763972186226539104184226783616044541993507800494250415314123905275152103942686724224450414615231162472946834157089346680893119225424723578851149286923074771309839814369742833222953467701193533930882842208670509142849224319653008708631509850916525572646431446909366607
x*y:2032617029
Give me a number:340282366920938463463374607431768211465
Give me another number:340282366920938463463374607432380848640
e:13
N:97064673797098600118660420965103127263477160386250046973406325548980601162332107318596214467875445651566645095081983705160041808449793322653535573074035842928344071475380052445932243645476076189561890740192570894010941534481915481576286764951499009401423004472118640033762214790596510161217904350085497214801
CT:408514640862611837857493146007164721854648643822358263749933629990312909085557921911280419512760500794928889384633468223737348186461573559382716304424287518322205770474260952429091426085606864318820906143128999073486970442842833463219612812321053215513624627937713660693505602085223292554334637800470773823
x*y:2594956909
Give me a number:340282366920938463463374607431768211466
Give me another number:340282366920938463463374607432502348032
e:13
N:92367338844893815387356228722195143080695473591441392108888334377518031217657967034085052679852374495951560019280662529720122702218775114322390285191351476328036786857973197350285855308282935558134118882771937638010147759362491648078119408307459506024771181896134529486285816053734578689426348992558155182279
CT:69432421993036944509438202999315008312829945875900439238899579973196214654749958490565439043877496200590707488321261661307279778941534589471072264963506883049730401520459883198431344264630112111860936187609302815187161684193823566653561401922685825118955295198778998464963121066492527787630273627703387846427
x*y:1964600233
Give me a number:340282366920938463463374607431768211467
Give me another number:340282366920938463463374607432458216516
e:13
N:114768506838652173153503480459336164243666030947847635757703197836764776333950939776679568607200935701397931281554833323055793516553230009780673821909176047497537431972980146906994548180655341815716603949198043050446944497289069716924565675054006131356759430564755684645339991880887549074352768971729035551567
CT:3694514024725688817584992134700822862918415801006476339486929648413859519284365185253933219704400879312307691630703513943204040894535886578560313685985449211325830779073538736705305136783576913360149560997935017018641200226238995878968327599793827047688911038689347447568284918232357465649761915782127960469
x*y:2531294179
Give me a number:340282366920938463463374607431768211468
Give me another number:340282366920938463463374607433028638880
e:13
N:142870714955350819473147567255057822057790961717511111721485095779154876897255747915845919229856830256111635322195964410937784680700632446325608124674720975781967184152023627683432221999848465383478063821116925598550563670118826808523582741070014045464984633786483836485573916975668474556464670282965788752237
CT:85590395216435916984463580970678271770393609926304472570529292203782538289967666736341206716477969710150777093705307436894154703117727868504378342828521446346921747016902574396450292931562407778752162176729470035290400853164537396519315543885871068343147744460626028856916219721502538066716307428182584391317
x*y:1622556157
Give me a number:340282366920938463463374607431768211469
Give me another number:340282366920938463463374607432408557816
e:13
N:121021609592169771004007732601094334222950507043952798005213000091297415184903077555902087810511376851813769217093245896287750219035278608074105543365740536628495969702633346673454500875920879820554198080613532969169270677651052136004962400995408051712652411869165797019013232444164253112260435854871784066867
CT:36808328423417314270311445063315408489203426490361869254585591990810697678485933595988166768505840329000835305113412029577980730602121728401035967360016930451962263345640340828537730750108549796328000452541136994869590200289040718871953619497122518495865464530413401436260616119054836753690117739025837563776
srdnlen{d0_y0u_kn0w_m0dul4r_ar1thm3t1c?}
srdnlen{d0_y0u_kn0w_m0dul4r_ar1thm3t1c?}
WtfRSA (Crypto)
p, q, e, ctがわかっているが、p - 1とeが互いに素ではないので、通常通り復号することはできない。modulusをqにして復号する。
#!/usr/bin/env python3 from Crypto.Util.number import * e = 18959 p = 8853107629856302430942645802685600792214004993921099904332911487775152756152460899671437787731654521568200225685173143721860070387195312109191089843558621 q = 12263776399134581413994039043220106353464473125114825391625856240762676598269365363349978019785253746863903410731653514543481130557521535535237879154364911 ct = 64521812048352846958817059534278142356568238192123182336017359260377716295619478728140210232152018155950695896362673540987021049139829121799099909484852120051863107269165139203886417085008081775352265576110683356959797391197297615443422020648048621511483229468510937180464189390129089235915976695524813058244 assert GCD(e, p - 1) == e phi_q = q - 1 d_q = inverse(e, phi_q) m = pow(ct % q, d_q, q) flag = long_to_bytes(m).decode() print(flag)
srdnlen{p4y_att3nt1on_wh3n_y0u_ch00s3_th3_valu3_of_e}
