この大会は2020/12/6 18:30(JST)~2020/12/7 18:30(JST)に開催されました。
今回もチームで参戦。結果は2386点で124チーム中46位でした。
自分で解けた問題をWriteupとして書いておきます。
Euler's Empire (Cryptography)
pow(2, pow(2, t), n) = pow(2, pow(2, t, phi(n)), n)であることを使って復号する。nを素因数分解し、phiを算出する。
n = 611738359 * 648863389 * 775357619 * 806952673 * 834612803 * 848994661 * 856368371 * 914351299 * 940957051 * 973139887
from Crypto.Util.number import * n = 126176329335043454027341235009057683290541781096785538088437185779950106283534462102786883 t = 1138895128842708275167 z = 22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165185658681843519312254372108072512792854040590016772780908271525769845284796145687079308339 c = 22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165145471041974060620715112664770187765206877310029241277556084680387431469989638143534950344 ps = [611738359, 648863389, 775357619, 806952673, 834612803, 848994661, 856368371, 914351299, 940957051, 973139887] phi = 1 for p in ps: phi *= p - 1 l = pow(2, pow(2, t, phi), n) m = c ^ l ^ z flag = long_to_bytes(m) print flag
b00t2root{Eul3r_w4s_4_G3niu5}
Try try but don't cry (Cryptography)
フラグの前半と後半をXORしたあと、base64またはhexエンコードしている。base64やhexデコードを一回ずつしながら元に戻し、11バイトまで戻したら、フラグが"b00t2root{"で始まり、"}"で終わることを使って、復号する。
with open('chall.txt', 'r') as f: c = f.read() c = c.decode('hex') c = c.decode('hex') c = c.decode('base64') c = c.decode('hex') c = c.decode('hex') c = c.decode('hex') c = c.decode('hex') c = c.decode('hex') c = c.decode('base64') c = c.decode('base64') c = c.decode('base64') c = c.decode('base64') c = c.decode('base64') c = c.decode('base64') c = c.decode('base64') c = c.decode('hex') head_flag = 'b00t2root{' tail_flag = '}' flag1 = chr(ord(c[-1]) ^ ord(tail_flag)) flag2 = '' for i in range(len(head_flag)): flag2 += chr(ord(c[i]) ^ ord(head_flag[i])) flag = head_flag + flag1 + flag2 + tail_flag print flag
b00t2root{fantasticcc}
007 (Cryptography)
暗号化の処理概要は以下の通り。
・アルファベット小文字のみ、何回かシーザー暗号(シフト数不明) ⇒結局1回シフト数不明の暗号をしているのと変わらない。 ・base64エンコード ・文字列の0番目と1番目でXORを繰り返し、連結。最後は先頭と末尾でXOR。 ・base64エンコード
XORではprintableな文字列に復号できることを前提に復号し、あとはシーザー暗号で"b"から始まることを前提に復号する。
import string def rot(s, num): l = '' for i in s: if(ord(i) in range(97, 97 + 26)): l += chr((ord(i) - 97 + num) % 26 + 97) else: l += i return l def decrypt_xor(s, k): d = chr(k) for i in range(len(s) - 1): d += chr(ord(s[i]) ^ ord(d[-1])) return d def is_base64(s): b64chars = string.letters + string.digits + '/+' b64 = s.rstrip('\n').rstrip('=') for i in range(len(b64)): if b64[i] not in b64chars: return False return True cipher = 'MRU2FDcePBQlPwAdVXo5ElN3MDwMNURVDCc9PgwPORJTdzATN2wAN28=' l = cipher.decode('base64') for code in range(32, 127): cipher = decrypt_xor(l, code) if is_base64(cipher): break cipher = cipher.decode('base64') flag = rot(cipher, ord('b') - ord(cipher[0])) print flag
b00t2root{Bond. James Bond.}
brokenRSA (Cryptography)
e = 4のため、通常のRSA暗号として復号できない。Tonelli-Shanks Algorithmにより、平方剰余を2回繰り返すことによってフラグを求める。
#!/usr/bin/python3 from Crypto.Util.number import * def legendre(a, p): return pow(a, (p - 1) // 2, p) def tonelli_shanks(a, p): if legendre(a, p) != 1: raise Exception("not a square (mod p)") q = p - 1 s = 0 while q % 2 == 0: q >>= 1 s += 1 for z in range(2, p): if legendre(z, p) == p - 1: break m = s c = pow(z, q, p) t = pow(a, q, p) r = pow(a, (q + 1) // 2, p) t2 = 0 while True: if t == 0: return 0 if t == 1: return r t2 = (t * t) % p for i in range(1, m): if t2 % p == 1: break t2 = (t2 * t2) % p b = pow(c, 1 << (m - i - 1), p) m = i c = (b * b) % p t = (t * c) % p r = (r * b) % p n = 11183632493295722900188836927564142822637910363304123337597708503476804292242860556684644449701772313571249316546794463854991452685201761786385895405863639 c = 8939043592146774508422725937231398285333145869395369605787177287036646137314173055510198460479672008589091362568215564488685390459997440273900039337645280 r = tonelli_shanks(c, n) rs = [r, n - r] for i in range(len(rs)): m = tonelli_shanks(rs[i], n) flag = long_to_bytes(m) if flag.startswith(b'b00t2root'): print(flag.decode()) break
b00t2root{finally_legendre_symbol_came_in_handy}
The Heist (Cryptography)
IVと鍵は同じもので暗号化されているので、IVを求め、鍵として渡せば、フラグが表示される。
[平文1ブロック目] ^ IV --(暗号化)--> [暗号文1ブロック目] [平文2ブロック目] ^ [暗号文1ブロック目] --(暗号化)--> [暗号文2ブロック目]
以下の方針でIVを求める。
1.aaaaaaaaaaaaaaaa\x10...\x10 を暗号化 ・aaaa... ^ IV -> ct1 ・\x10... ^ ct1 -> ct2 2.ct2を復号 ・\x10... ^ ct1 ^ ivが表示される。 ⇒iv = \x10... ^ ct1 ^ 復号結果
以上を元にスクリプトにする。
import socket def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def str_xor(s1, s2): return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2)) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('157.230.237.229', 2200)) try_pt = 'a' * 16 data = recvuntil(s, ': ') print data + '2' s.sendall('2\n') h_try_pt = try_pt.encode('hex') data = recvuntil(s, ': ') print data + h_try_pt s.sendall(h_try_pt + '\n') data = recvuntil(s, '\n').rstrip() print data try_ct = data.split(': ')[1].decode('hex') data = recvuntil(s, ': ') print data + '3' s.sendall('3\n') xor_key = str_xor(try_ct[:16], chr(16) * 16) h_try_ct = try_ct[16:].encode('hex') data = recvuntil(s, ': ') print data + h_try_ct s.sendall(h_try_ct + '\n') data = recvuntil(s, '\n').rstrip() print data try_pt = data.split(': ')[1].decode('hex') key = str_xor(try_pt, xor_key).encode('hex') data = recvuntil(s, ': ') print data + '1' s.sendall('1\n') data = recvuntil(s, ': ') print data + key s.sendall(key + '\n') data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
1. Enter key and get flag 2. Encrypt plaintext 3. Decrypt ciphertext Enter option: 2 Enter hex plaintext: 61616161616161616161616161616161 Ciphertext: d035b7dd8704f7b634a65a25e29d931045f8da8740a09825fd6512895d3618b7 1. Enter key and get flag 2. Encrypt plaintext 3. Decrypt ciphertext Enter option: 3 Enter hex ciphertext: 45f8da8740a09825fd6512895d3618b7 Plaintext: b04ad7a8ee7193ce41c52b5c9ee2f172 1. Enter key and get flag 2. Encrypt plaintext 3. Decrypt ciphertext Enter option: 1 Enter hex key: 706f706579657468657361696c6f7272 b00t2root{th3y_4r3_g0ing_t0_k1ll_u5}
b00t2root{th3y_4r3_g0ing_t0_k1ll_u5}