この大会は2018/2/10 15:00(JST)～2018/2/11 15:00(JST)に開催されました。
今回もチームで参戦。結果は2157点で447チーム中5位でした。
自分で解けた問題をWriteupとして書いておきます。
welcome flag (WarmUp 10)
問題にフラグが書いてある。
HarekazeCTF{Welcome to the Harekaze CTF!}
easy problem (Warmup 30)
ROT13でデコードすると、フラグが得られた。
HarekazeCTF{Hello, world!}
gacha (Crypto 100)
平文にWINが含まれる暗号文を選択すると勝ちで、30回以上の勝負で9割以上の成績を残すと、フラグが得られる。暗号化した結果が合うものを選択するようにすればよい。
from Crypto.Util.number import * import socket import re def recvuntil(s, tails): data = "" while True: for tail in tails: if tail in data: return data data += s.recv(1) pattern1 = '1\. \((.+)\)' pattern2 = '2\. \((.+)\)' pattern3 = '3\. \((.+)\)' e = 65537 m = 6289644257982517902 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('problem.harekaze.com', 30214)) while True: data = s.recv(4096) print data if 'you got the flag' in data: break n = [] c = [] mo = re.search(pattern1, data) n.append(int(mo.group(1).split(', ')[0][2:], 16)) c.append(int(mo.group(1).split(', ')[2][2:], 16)) mo = re.search(pattern2, data) n.append(int(mo.group(1).split(', ')[0][2:], 16)) c.append(int(mo.group(1).split(', ')[2][2:], 16)) mo = re.search(pattern3, data) n.append(int(mo.group(1).split(', ')[0][2:], 16)) c.append(int(mo.group(1).split(', ')[2][2:], 16)) ans = '' for i in range(3): if pow(m, e, n[i]) == c[i]: ans = str(i+1) break print ans s.sendall(ans + '\n') for i in range(6): data = recvuntil(s, '\n') print data
実行すると、フラグが得られる。
： 実行結果は以下の通り。 ： [*] ROUND 30 🔒 1. (0x96a3fa4a676e46330d8bd14eed7a027d1c53b76e45d492bc00a9d11661f30050059cf60cfe91e69be4ed8b944eed56881bfcd15a07e1da8d0314deb591f8b5e24ccc7a1dda4b318b73d8e9eefac36f2c9185bf013abbdca1fad1b561aeab71de3ccd3656bd6b222a77e2fe1d130499c1d76a1ac6e92767d36b8a31c3ec022fc4057b79414420c27ef087fa9a122f2db2390b299296df20883a4e2a22c551f53a55561daa5bcf27716fd4334cfa43235a124432aaf07e89ee86afedf2c96adf1dfb26ea2ac4ec16fc1dba2db8138400abf97b874dc6508b4be57ffef56fb3fd1b99866843ef03b27cec343e5f6d63758b3a324fc474dd6e781523ff73b984556b, 65537, 0x5dc261a7fbaec5e1a13a39732f9af50f219f3a650814597196ae3f34c5bfa6b1be85ae537faeef7651fc1355fb2f196fa661e0a71fd074fa07c179994d5716bb429ee92ac05dc15d92a29499b8fe673df24aa89143135a816374ff6c582b1a20beb5f42b0549c012f342ba3917bb25f3c115ecc9e8b7524002a2e6e7f683bcc2717accc7fec3a6bfc1cd1054c4623124d42a4681a3550a206abb4723c76e8572b20cabce849a1f49f24cb24a1d8994a8a16490bed3dbccae5240d5dc94e826111b5df6ca684311e70956ed9fe3a461734c60e35f92088030cfab0d760b8a6358ca425c0be23d17fd163c4492446da04749081db33682f6654b603267f6f683a8) 🔒 2. (0x9a5834c5981f16c100a84e6b08987d38204a341c5264adb9db968b843b6d29c7f8e54b9d5147f8fd95836cd61192611cfd7c244047c1d80bcdcb77203650989d9b2efbaf45da875cc6932546d87804fe1cecfad358eda31e2e62d7b3711e7769a0bcd3071fd990977262a1635c8836a965be7098fdac49313503324a7f52ee9ad0922f2d43fbf26d556dc8f4eae649190e2c5a24f0a7f6bb0a9210cbf330c7d79a9632f4779935c2960738bbff563f9b12857dcba95f6b1bf961bd8f5b5f330170132edb9d071df84f93f104ce3d7fc1813ddcda2de0ce882e2dc8940e0131e43ca62cf619ee5b74edd56691c9dd0d0587c246d81d6b0793739d7adb9596a2db, 65537, 0x7107ba3b20b50d93ef351014d1087ba251557c644cbbfd8cb64534367a471e20bc253f9397ac9f8fc23d8f7f4795f221e0082bff23c5e9be2c2aa527f0731d55ce18451ef2fcaa0bd2dda95c99baa8759400eea19cae7ee5175900fbf1ff70b20b7ed391f4458179e788d7021f4f1dd8c7299395b3cc41296333db9b2fe874381f4a0c3bd4056c411177b793a77debc396f77f1dc2b8782872e2d574319f3b32ce8b4ff76cf63d1e9a53dfab7947ffcf3ceea6aef7f53069c21468d8da0e4ef3b9cd4515fc898bdcd4a1427c6fa53ce9279d62d66f6cfc124b262548457eb711a61e0b7a9f62bddc622f244d0a9833d2ca6ef3c2456794ef87fb65f00572ae73) 🔒 3. (0xa9377bfd02709b87cc9de8fd4e89b8925efe2ffadf18bc3e7965e96205718dad7d38aafbfc0129b8c6569fa8c06d7856a8bf0cfe2a4692e429a5d8857e65287fa3e498798f0666210623199c469fa242fb4dbe9edcef83c2623e70ef768a40321dbae77c5f06d5e856304e16c00762cc5d32bf405b0c125c4b77984e5cf0002837eea1e511908a3635e896d10aed950febfaa099087121756c88d09fda56ecac463db0024b13b54adf23094b52560d1c515688cb41fc8613de18164b7b1cd23697284a9c9690e2e446321eb3acb6ec4196922905b5d7ac3ac724a0aff46a370a40e7168a52efe5c3a7247b059b5916edbb7c725a5225ecdc4ae56660cef20c47, 65537, 0x9433ce34e7fe6e982a815554b152dfba7af14474aea8e2b6b54879ed9b72cdd61efdf8b2243d80cd7327dc304ab13235d4d03b5935b6f1d3e89f1a8dae7b2fa5e87078c286d25c233bbb5743d902855f19a2613818b6551b6bc7cd64d639372d487a192015480a2ca1338cae785df45896669300a32a61988c89c5af92406382af0b6990639a3a2c0d646e0f93c53674ccf164dabedc944fb6a6ebe7935b675586903dabb524801ca2463df4390f688df21612872ca8fa1ae3cf96c816aad09bdbfb04aaaab7ecdb9896e73055510f6d05c959b09ae05bac03ecbc244522d1ab9e9abeb6ac75294136e5b853663fdb869366d6f32ec4c5ddd81045a2792aa582) [*] select: >>> 1 [*] result: WIN 💎 [+] you win 🎉 [*] here are the keys. please ensure that there is no cheating 🔑 1. 7895995954412064234361798895691268139582514896439045906129410925393920562153770222588810056914159075033981223919158124552006716651188659496199051457286190320692090859788279809860208035893962232678891200034782425161636490486995090748934880560073837212118638861333586572283933749245331568754318155522087116610021719508377831385350502689285698213185323894228949011226089297813776139714178286314631550772569765746889813752314738483697158870342757880124044833572231066140815227624186195450340081288776962154163704962751174334544476745520922480332531682876418638778610050132359898020869921388700867032839447642396387916993 🔑 2. 2871627322414446708739745407118402039320610534821637431875001264463975811751992475697957271173851890530416811405844414754092177877469323661265530941221479080980729838562469207272013132745402277102897808493558717580357314008162012284741604313539737024956744030148499434498239196119467724831745487309200048671876163687694984163513452981701506817302776063871922940228534343535114758434028528047115159167791857750787657828444280964181607895537940726693850558030502638037006053235518046927831325815085574066001263880008741752758330520257823295627563408765106708309024086304411923544230046304150169111392609526309091497273 🔑 3. 4261114175761760556575469170514289305600825279273163390030649634102139374435136757831881552789765575472583792758210792969407840385039637423639005401443714928974149994817795380600031070795405605052235196867895358524894145361839581737987794740475045542297047737773980218646790236328911021370281112922925530542045171181448919011772705698091998520968768119957847461409564121043489635305341398474273372414636652903223459247379405576070241085884391735632148389893011321168254894606485639292403631944531222049369388592286103077814749344046044547383837687022513408530946652002143569207061842709239013253655479969969127409969 [+] you got the flag 🏁: HarekazeCTF{92f4187adbbafd3c592bfdfa8689de3be26b770d}
HarekazeCTF{92f4187adbbafd3c592bfdfa8689de3be26b770d}
Fight (Crypto 100)
gen_seedはまとも計算すると時間がかかる。ただやっていることはn-1までの互いに素となる数字の数を求めることなので、置き換える。seedがわかるので、そのまま乱数を計算すれば、XORの鍵もわかるので、復号できる。
import random import base64 import sympy as sym def xor(msg, key): return bytes([ch1^ch2 for ch1, ch2 in zip(msg, key)]) b64enc = '7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU=' enc = base64.b64decode(b64enc) s = 1 for p in b"Enjoy_HarekazeCTF!!": s *= p seed = sym.totient(s) random.seed(str(seed).rstrip("0")) key = bytes([random.randint(0,255) for _ in range(100)]) print(xor(enc, key))
HarekazeCTF{3ul3rrrrrrrrr_t0000000t1nt!!!!!}
Round and Round (Crypto 200)
p1 = pow(p-1, 0, p) + pow(p-1, 1, p) + pow(p-1, 2, p) + ... + pow(p-1, q-1, p) q1 = pow(q-1, 0, q) + pow(q-1, 1, q) + pow(q-1, 2, q) + ... + pow(q-1, p-1, q)
まともに計算しても時間がかかる。いろいろ試したところ、以下の規則があることに気づいた。
pow(p-1, 奇数, p) = p-1 pow(p-1, 偶数, p) = 1
また、p, qは素数なので奇数。以上を踏まえ式を書き換える。
p1 = (p-1)*((q-1)/2) + (q-1)/2 + 1
= p*(q-1)/2 + 1
q1 = (q-1)*((p-1)/2) + (p-1)/2 + 1
= q*(p-1)/2 + 1
↓
(p1-1)*2 = p*(q-1) = (p-1)*(q-1) + (q-1)
(q1-1)*2 = q*(p-1) = (p-1)*(q-1) + (p-1)
(p1-1)*2 - (q1-1)*2 = q - p ; diffと置く
= (p-1) * (p+diff-1) + (p-1)
この2次方程式を解くことができれば、pが求められ、そこからqも求められる。あとは復号するだけ。コードは以下の通り。
from sympy import * enc = 15507598298834817042463704681892573844935925207353671096676527782423920390858333417805014479686241766827314370902570869063203100704151010294869728739155779685640415815492312661653450808873691693721178331336833872996692091804443257630828512131569609704473214724551132715672202671586891813211353984388741035474991608860773895778988812691240069777435969326282770350038882767450912160134013566175657336041694882842590560100668789803775001750959648059363722039014522592751510672658328196379883088392541680852726136345115484827400366869810045573176782889745710174383221427352027041590910694360773085666697865554456816396551 p1 = 14606124773267989759790608461455191496412830491696356154942727371283685352374696106605522295947073718389291445222948819019827919548861779448943538887273671755720708995173224464135442610773913398114765000584117906488005860577777765761976598659759965848699728860137999472734199231263583504465555230926206555745572068651194660027408008664437845821585312159573051601404228506302601502000674242923654458940017954149007122396560597908895703129094329414813271877228441216708678152764783888299324278380566426363579192681667090193538271960774609959694372731502799584057204257039655016058403786035676376493785696595207371994520 q1 = 14606124773267989759790608461455191496412830491696356154942727371283685352374696106605522295947073718389291445222948819019827919548861779448943538887273671755720708995173224464135442610773913398114765000584117906488005860577777765761976598659759965848699728860137999472734199231263583504465555230926206555745568763680874120108583912617489933976894172558366109559645634758298286470207143481537561897150407972412540709976696855267154744423609260252738825337344339874487812781362826063927023814123654794249583090654283919689841700775405866650720124813397785666726161029434903581762204459888078943696756054152989895680616 e = (1<<16) + 1 # q - p diff = (p1 - 1) * 2 - (q1 - 1) * 2 # (q1 - 1) * 2 val = (q1 - 1) * 2 x = Symbol('x') sol = solve((x - 1) * (x + diff - 1) + (x - 1) - val, x) p = int(sol[1]) q = p + diff phi = (p - 1) * (q - 1) x = 0 while True: if (phi * x + 1) % e == 0: d = (phi * x + 1) / e break x = x + 1 m = pow(enc, d, p * q) flag = ('%x' % m).decode('hex') print(flag)
HarekazeCTF{d1d_y0u_7ry_b1n4ry_se4rch?}
