2018 网鼎杯-第四场 WriteUp

📝 赛事概况

  • 比赛赛制：采用线上 CTF（夺旗赛） 模式。参赛队伍通过解题获取 Flag 以获得分数

  • 参赛对象：主要面向电子政务、科技、互联网企业、网信等行业

  • 参赛规模：据当时报道，共有 1483 支队伍参与本场比赛的角逐

  • 晋级规则：线上预选赛每场取前 50 名晋级线下半决赛，四场共计 200 支队伍入围

Crypto

shanghai（维吉尼亚密码）

密文第一行是

1
bju lcogx fisep vjf pyztj sdgh 13 gifc qsxw. pkiowxc

其中 fisep vjf pyztj sdgh，根据题目名 shanghai 和数字 13，可以猜测它对应

1
shang hai metro line

如果用维吉尼亚密码反推出 key，可以得到一段密钥流

1
nbsrj ojx dugcv hvtd

继续结合高频词，例如密文中的 glv 很可能是英文高频词 the，可以推出密钥片段 ner

并最终推测出 key 和 vigenere 相关

最后可以确定周期密钥本质是 vigenereicq

但从全文第一个字母开始对齐时，实际使用的 key 相位是它的一个循环位移

1
icqvigenere

apl（APL 表达式）

文件内容本身是 Base64，解码后得到 APL 表达式

核心是中间这个函数，它把输入字符串做一堆矩阵变换、二进制编码、异或操作后，与左侧密文数组比较

1
2
3
4
5
6
7
8
9
10
{⍵(~⍵)/('No_Please_continue')('Yes,This_is_flag')}
(∊(41(41)0+140)(⎕UCS('µě»ÕĀ$#Ğ$èáËĞĞĝ`âÞĠ#"!Ġ"KE(©$#Ğ$Q<k'))146)
{
  +/⍺≠33+2⊥(1(5)×8)⍴∊{
    a≠8↑(1,a←(8⍴2)⊤⍵)
  }¨2⊥8(+/⍴⍳(7*2)-⌊9.1⌊⍴'FlagIsWhat')⍴10⊖⊖⌽
  (∊4(⍴⍴88888)+16)⍴
  (1+(|¯8)⍴1)⊤⎕UCS(⍵)
}
'YourFlagIsWhat?'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
from pathlib import Path
import base64

# 读取 APL 源代码文件（经 base64 编码存储）
path = "/mnt/data/b2e30588-7240-41f7-b67d-8fd99018826f.apl"
raw = Path(path).read_text()
apl = base64.b64decode(raw).decode("utf-8", errors="replace")

print("[+] APL code:")
print(apl)

# 目标数组：由 APL 代码执行后输出的整数序列（左参数得出）
target = [
    181, 181, 140, 181, 283, 187, 213, 256,
    36, 35, 286, 36, 232, 225, 203, 286,
    286, 285, 96, 226, 222, 288, 157, 35,
    34, 33, 288, 34, 75, 69, 40, 169,
    36, 35, 286, 36, 81, 60, 107, 146
]

# 工具函数：整数转 8 位二进制列表（高位在前）
def bits8(x):
    return [(x >> i) & 1 for i in range(7, -1, -1)]

# 工具函数：二进制列表转整数
def from_bits(bs):
    v = 0
    for b in bs:
        v = (v << 1) | b
    return v

# =========================
# 1. 逆 33 + 2⊥(...)
# =========================
# APL 中先对某些 8 位二进制序列做了 2⊥（即二进制转十进制），然后加上 33 得到 target
# 逆向第一步：每个 target 值减去 33，得到原始的十进制值
vals = [x - 33 for x in target]

# 将每个值转换为 8 位二进制，构建 8×40 矩阵，每一列对应一个字符的二进制位
# gmat[i][j] 表示第 j 个值二进制的第 i 位（高位 i=0）
gmat = [[bits8(vals[j])[i] for j in range(40)] for i in range(8)]

# APL 中可能存在 reshape/ravel，将矩阵按行优先展平为一维数组
# 这里的展平顺序：第 0 行所有列，接着第 1 行所有列……
gflat = [gmat[i][j] for i in range(8) for j in range(40)]

# =========================
# 2. 逆 a≠8↑(1,a)
# =========================
# APL 中该操作对每个 8 位序列 b 进行了 a = 1, a[0]=1≠b[0], a[i]=a[i-1]≠b[i] (i>0)
# 这是一种差分编码：a 是 b 的累积异或，且前置了一个 1
# 现在逆向该过程：从 a 恢复 b
mid = []
for i in range(40):
    b = gflat[i * 8:(i + 1) * 8]   # 取出连续 8 位，即某个编码后的 a 序列
    a = [0] * 8
    a[0] = 1 ^ b[0]                # 逆：b[0] = 1 ^ a[0] → a[0] = 1 ^ b[0]
    for j in range(1, 8):
        a[j] = a[j - 1] ^ b[j]     # 逆：b[j] = a[j-1] ^ a[j] → a[j] = a[j-1] ^ b[j]
    mid.append(from_bits(a))       # 恢复成原始字节值

# =========================
# 3. 逆 2⊥
# =========================
# APL 中之前将这些字节又做了一次 2⊥ 转成整数，这里需要再展开为二进制位
c0 = [[bits8(mid[j])[i] for j in range(40)] for i in range(8)]

# 再次按行优先展平
m2_flat = [c0[i][j] for i in range(8) for j in range(40)]

# reshape 成 20×16 的位矩阵（总位数 320 = 20*16）
m2 = [
    [m2_flat[i * 16 + j] for j in range(16)]
    for i in range(20)
]

# APL 中执行了 10⊖⊖⌽，即：左右翻转(⌽)，上下翻转(⊖)，然后向上旋转 10 行(10⊖)
# 现在我们逆向操作：先向下旋转 10 行，然后上下翻转，再左右翻转
def rot_rows(mat, k):
    """矩阵行循环移动，正数向下旋转（上移），负数向上。这里 k=10 表示下移 10 行"""
    k %= len(mat)
    return mat[k:] + mat[:k]

def rev_rows(mat):
    """上下翻转"""
    return mat[::-1]

def rev_cols(mat):
    """左右翻转"""
    return [row[::-1] for row in mat]

# 逆向：先旋转回来（10⊖ 的逆是 -10⊖，即向下旋转 10 行，与正向相同因为 20 行旋转 10 两次回到原位）
m1 = rev_cols(rev_rows(rot_rows(m2, 10)))

# =========================
# 4. 逆 reshape，恢复原始字符 bit
# =========================
# 将 20×16 矩阵展平成一维
m0_flat = [m1[i][j] for i in range(20) for j in range(16)]

# 重新 reshape 成 8×40，每列是一个字符的二进制位（高位在前）
m0 = [
    [m0_flat[i * 40 + j] for j in range(40)]
    for i in range(8)
]

# 每列二进制转整数，再转换为字符
chars = []
for j in range(40):
    chars.append(from_bits([m0[i][j] for i in range(8)]))

flag = bytes(chars).decode()
print("[+] flag =", flag)

shenyue2（RSA 近似分解 n）

pasted_1787202168253_ayfy2c.png

源码里先把 FLAG 转成整数，然后设置 RSA 参数：e=65537，随机生成两个 2048 bit 素数 p,q，并给了一个固定的 100 bit 左右的 r

关键泄露点在这里：

1
2
3
phi = (p-1)*(q-1)
d = modular_mul_inverse(e, phi)
k = (p-r)*d

标准 RSA 中：

1
2
3
n = p * q
phi = (p - 1)(q - 1)
e * d ≡ 1 (mod phi)

所以一定存在一个整数 t，使得

1
e * d = 1 + t * phi

所以

1
d = (1 + t * phi) / e

因为 0 < d < phi，所以

1
2
3
1 <= t < e

1 <= t <= 65536

这就给了我们爆破空间，把泄露的 k 代入

1
2
3
k = (p - r) * d

e * k = (p - r) * e * d

又因为 e * d = 1 + t * phi，所以

1
e * k = (p - r) * (1 + t * phi)

在 RSA 中

1
2
3
4
5
6
7
phi = (p - 1)(q - 1)

phi = pq - p - q + 1

n = p * q

phi = n - p - q + 1

代入得到

1
e * k = (p - r) * (1 + t * (n - p - q + 1))

这个式子里，n,e,k,r 已知，t,p,q 未知

对于真实的 t

1
phi = n - p - q + 1

而 p + q 相比 n 非常小，所以

1
2
3
phi = n - (p + q - 1)

phi ≈ n

于是

1
2
3
e * k = (p - r) * (1 + t * phi)

e * k ≈ (p - r) * t * n

所以

1
p ≈ e * k / (t * n) + r

于是解题策略变成：

  • 枚举 t = 1 ~ 65536

  • 计算 p0 = floor(e*k / (t*n)) + r

  • 在 p0 附近小范围搜索

  • 如果某个候选 p_candidate 可以整除 n，说明找到了真正的 p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import re
from pathlib import Path

# 从注释中提取 n, e, k, enc
n = 
e = 
k = 
enc = 

# 从源码中提取 r
r = 

found = False

for t in range(1, e):
    # 由 e*k ≈ (p-r)*t*n 得到 p 的近似值
    p0 = (e * k) // (t * n) + r

    # 真实 p 只会在 p0 附近，搜索一个小范围即可
    for delta in range(-50, 51):
        p = p0 + delta

        if p > 1 and n % p == 0:
            q = n // p
            print("[+] found t =", t)
            print("[+] found delta =", delta)
            print("[+] p =", p)
            print("[+] q =", q)

            phi = (p - 1) * (q - 1)
            d = pow(e, -1, phi)

            m = pow(enc, d, n)
            flag = m.to_bytes((m.bit_length() + 7) // 8, "big")

            print("[+] flag =", flag.decode())
            found = True
            break

    if found:
        break

运行结果

1
2
3
[+] found t = 38634
[+] found delta = 2
[+] flag = flag{61c31024-5dad-4f8f-b641-b2bf1f4afde7}

Misc

双色块（文件附加隐写 + 色块隐写 + Base64 + DES）

pasted_1784320271282_0kdvxy.png

文件尺寸为 240 × 240，动画共有 576 帧，每帧中都有一个 10×10 的彩色方块，方块位置依次覆盖整个 24×24 网格

两种颜色分别为绿色和品红色，因此可以将两种颜色看成二进制 0 和 1

末尾附加了一张 PNG 图片

pasted_1784353195544_h7yp4j.png

将二进制转为 ASCII 码得到

1
o8DlxK+H8wsiXe/ERFpAMaBPiIcj1sHyGOMmQDkK+uXsVZgre5DSXw==hhhhhhhhhhhhhhhh

去除末尾的填充得到

1
o8DlxK+H8wsiXe/ERFpAMaBPiIcj1sHyGOMmQDkK+uXsVZgre5DSXw==

Base 64 解码得到

1
2
3
a3c0e5c4af87f30b225defc4445a4031
a04f888723d6c1f218e32640390afae5
ec55982b7b90d25f

DES 解密得到 flag{2ce3b416457d4380dc9a6149858f71db}\x00\x00，密钥在图片中给出了