Wani Hackaseで参加して1032点の23位。
開始時刻ちょっと後に、予定を入れてしまっていたのでそんなに取り組めなかったけど勉強になりました。問題設定はシンプルだけど一筋縄では解けない問題が好きなので楽しかったです。 Harekazeの方々運営ありがとうございました🙇🙇
rsa [Crypto]
$$ \begin{aligned} n &= pq \ e &= 65537 \ c_1 &\equiv m^e \mod n \ c_2 &\equiv (p+q)^e \mod n \ c_3 &\equiv (p-q)^e \mod n \ \end{aligned} $$
が与えられるので、$m(={\rm flag})$を復元する。
$c_2, c_3$ は実際に展開すると $$ c_2 \equiv p^e + q^e \mod n \ c_3 \equiv p^e - q^e \mod n $$ であるから、$(c_2+c_3) / 2 \equiv p^e \mod n$ を得る。 $\gcd(n, p^e) = p$ となるので、あとは秘密鍵を復元して復号する。
1import shutil
2import math
3
4shutil.copy("output.txt", "output.py")
5
6from output import *
7
8p = math.gcd((c2 + c3) // 2, n)
9q = n // p
10assert p * q == n
11
12d = pow(e, -1, (p - 1) * (q - 1))
13flag = pow(c1, d, n)
14print(bytes.fromhex(f'{flag:x}'))
QR [Crypto]
近傍？4マスの情報を元にオリジナルのQRコードを復元する。 QRコードには確定パターンがあるので、そこを足がかりに探索するようなコードを書く。
1import ast
2from itertools import product
3
4with open("output.txt") as f:
5 qr = ast.literal_eval(f.read())
6
7size = len(qr) + 1
8
9# 0: white, 1: black, 2: pending
10flag = [[2 for _ in range(size)] for _ in range(size)]
11
12
13def fill(x1, y1, x2, y2, status):
14 for i in range(y1, y2 + 1):
15 for j in range(x1, x2 + 1):
16 flag[i][j] = status
17
18
19fill(0, 0, 7, 7, 0)
20fill(0, 0, 6, 6, 1)
21fill(1, 1, 5, 5, 0)
22fill(2, 2, 4, 4, 1)
23
24fill(size - 8, 0, size - 1, 7, 0)
25fill(size - 7, 0, size - 1, 6, 1)
26fill(size - 6, 1, size - 2, 5, 0)
27fill(size - 5, 2, size - 3, 4, 1)
28
29fill(0, size - 8, 7, size - 1, 0)
30fill(0, size - 7, 6, size - 1, 1)
31fill(1, size - 6, 5, size - 2, 0)
32fill(2, size - 5, 4, size - 3, 1)
33
34
35for i in range(size - 2 * 7):
36 flag[6][i + 7] = i % 2
37 flag[i + 7][6] = i % 2
38
39
40for _ in range(100):
41 for i, j in product(range(size - 1), repeat=2):
42 neighbor = ((i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1))
43 white = [(I, J) for I, J in neighbor if flag[I][J] == 0]
44 black = [(I, J) for I, J in neighbor if flag[I][J] == 1]
45 pending = [(I, J) for I, J in neighbor if flag[I][J] == 2]
46 if pending:
47 if qr[i][j] == 0:
48 if len(white):
49 for I, J in pending:
50 flag[I][J] = 0
51 if len(black):
52 for I, J in pending:
53 flag[I][J] = 1
54
55 if len(white) == 4 - qr[i][j]:
56 for I, J in pending:
57 flag[I][J] = 1
58
59 if len(black) == qr[i][j]:
60 for I, J in pending:
61 flag[I][J] = 0
62
63
64flag = "\n".join("".join(map(str, line)).replace("2", "1") for line in flag)
65flag = flag.replace("0", " ").replace("1", "██")
66print(flag)
Wilhelmina says [Crypto]
$y_i = z_i + \hat{z_i}$ ($\hat{z_i}$は未知)とすると、 $$ \begin{aligned} z_i+\hat{z_i} &\equiv x_im \mod p \\ \hat{z_i} - x_im + z_i &\equiv 0 \mod p \end{aligned} $$ このPDFの4.1 The hidden number problem に書いてある格子でそのまま解けそうなので採用した。
LLL後に$\hat{z_i}$が復元されていることが期待されるので、これを利用してflagを復元する。
1from Crypto.Util.number import *
2
3n = 5
4t = 311
5p = 10701453001723144480344017475825280248565900288828152690457881444597242894870175164568287850873496224666625464545640813032441546675898034617104256657175267
6xs = [7891715755203660117196369138472423229419020799191062958462005957463124286065649164907374481781616021913252775381280072995656653443562728864428126093569737, 9961822260223825094912294780924343607768701240693646876708240325173173602886703232031542013590849453155723572635788526544113459131922826531325041302264965, 7554718666604482801859172289797064180343475598227680083039693492470379257725537783866346225587960481867556270277348918476304196755680361942599070096169454, 5460028735981422173260270143720425600672799255277275131842637821512408249661961734712595647644410959201308881934659222154413079105304697473190038457627041, 8621985577188280037674685081403657940857632446535799029971852830016634247561494048833624108644207879293891655636627384416153576622892618587617669199231771]
7zs = [2445678981428533875266395719064486897322607935804981139297064047499983860197487043744531294747013763946234499465983314356438694756078915278742591478169600, 6687262023290381303903301700938596216218657180198116459210103464914665663217490218525920847803014050091904359944827298080739698457116239163607201903280128, 9144515139738671257281335253441395780954695458291758900110092599410878434836587336752247733779617485272269820837813132894795262162555273673307500761317376, 7005359236736263649027110410188576532095684249796929034336135801107965605961711614006159825405033239188458945408990893269975105260656611838449490684018688, 4638291797440604671051855904609667375394026160401800326727058461541969151082727684535417653507524951373254537356784859777006179731400955193335900924805120]
8
9M = 1<<400
10B = matrix(ZZ, [
11 [ p, 0, 0, 0, 0, 0, 0],
12 [ 0, p, 0, 0, 0, 0, 0],
13 [ 0, 0, p, 0, 0, 0, 0],
14 [ 0, 0, 0, p, 0, 0, 0],
15 [ 0, 0, 0, 0, p, 0, 0],
16 [xs[0],xs[1],xs[2],xs[3],xs[4], M//p, 0],
17 [zs[0],zs[1],zs[2],zs[3],zs[4], 0, M],
18]).LLL()
19
20for b in B:
21 for i in range(n):
22 if b[-1] != M:
23 continue
24 x, z_, z = map(abs, (xs[i], b[i], zs[i]))
25 y = z+z_
26 flag = y*pow(x, -1, p)%p
27 flag = bytes.fromhex(f'{int(flag):x}')
28 if b'Harekaze' in flag:
29 print(flag)
30 exit(0)
What time is it now? [Web]
formatパラメータに好きなpayloadを送れるので、
"date '+" . escapeshellcmd($format) . "' 2>&1"
をうまく利用してflagを読み出す。
とりあえず別のコマンドを割り込ませられないか考えたが、諸々escapeされているので難しい。
ちゃんとdateの仕様を確認しようとman date したら-fオプションが使えそうだったのでこれを利用してpayloadを組んだ。dateのformatの部分は適当でも通る。
${URL}?format=' -f /flag'