DASCTF Crypto 三题 Writeup

这篇文章记录 DASCTF 中三道 Crypto 题的解题过程，分别是：

  • three_friends：RSA 共因子攻击；
  • lattice_oracle：小维 LWE 暴力恢复秘密向量；
  • phantom_sign：ECDSA nonce 偏置导致的 HNP / LLL 格攻击。

三道题覆盖了 RSA、LWE、ECDSA 和格攻击中比较典型的漏洞场景，适合作为 Crypto 方向的复盘记录。

three_friends

题目分析

题目给出三组 RSA 模数：

1
2
3
n1 = p * q
n2 = q * r
n3 = p * r

并分别加密 flag 的三段：

1
2
3
c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)
c3 = pow(m3, e, n3)

表面上看，每个模数都是 1024 bit 左右，正常分解比较困难。

但是这三个模数之间并不是相互独立的，而是共享了素因子：

1
2
3
gcd(n1, n2) = q
gcd(n1, n3) = p
gcd(n2, n3) = r

所以这道题的核心漏洞是：多个 RSA 模数之间存在共享素因子。

只要对这些模数两两求最大公约数，就可以直接恢复出 p、q、r，进而分别计算私钥并解密。

解题思路

整体流程如下：

  1. 使用 gcd 对 n1、n2、n3 两两求最大公约数；
  2. 恢复出三个素因子 p、q、r；
  3. 分别计算三个 RSA 模数对应的欧拉函数；
  4. 求出私钥指数 d = inverse(e, phi)；
  5. 分别解密得到 m1、m2、m3；
  6. 将三段明文拼接，得到完整 flag。

解题脚本

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
from math import gcd
from Crypto.Util.number import long_to_bytes, inverse

n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401

e = 65537

c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002

# 通过共享素因子分解三个模数
p = gcd(n1, n3)
q = gcd(n1, n2)
r = gcd(n2, n3)

# 分别计算 phi
phi1 = (p - 1) * (q - 1)
phi2 = (q - 1) * (r - 1)
phi3 = (p - 1) * (r - 1)

# 计算私钥指数
d1 = inverse(e, phi1)
d2 = inverse(e, phi2)
d3 = inverse(e, phi3)

# 解密
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
m3 = pow(c3, d3, n3)

flag = long_to_bytes(m1) + long_to_bytes(m2) + long_to_bytes(m3)

print(flag)

Flag

1
DASCTF{thr33_fri3nds_sh@r3_pr1m3s!!}

lattice_oracle

题目分析

题目生成方式大致如下：

1
2
3
4
5
6
7
8
9
10
n = 6
q = 97
m = 30

s = [random.randint(0, 3) for _ in range(n)]

for _ in range(m):
    a_i = [random.randint(0, q - 1) for _ in range(n)]
    e_i = random.randint(-1, 1)
    b_i = (sum(x * y for x, y in zip(a_i, s)) + e_i) % q

这是一个 LWE 形式的问题：

1
b_i = <a_i, s> + e_i mod q

其中：

1
2
3
4
s_i in [0, 3]
n = 6
e_i in {-1, 0, 1}
q = 97

秘密向量 s 的每一维只有 4 种可能，并且维度只有 6，所以总搜索空间只有：

1
4^6 = 4096

这个规模非常小，因此不需要真正使用格规约，直接枚举所有可能的秘密向量即可。

解题思路

  1. 枚举所有可能的 s；
  2. 对每组候选 s，计算 <a_i, s> mod q；
  3. 检查 b_i - <a_i, s> 是否属于误差集合 {-1, 0, 1}；
  4. 找到唯一合法的 s；
  5. 使用 sha256(str(s).encode()).digest()[:16] 生成 AES key；
  6. 使用 AES-CBC 解密密文，得到 flag。

恢复出的秘密向量为：

1
s = [0, 0, 2, 1, 1, 1]

解题脚本

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
import json
import itertools
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

with open("data.txt", "r") as f:
    data = json.load(f)

n = data["n"]
q = data["q"]
A = data["A"]
b = data["b"]
iv = bytes.fromhex(data["iv"])
enc = bytes.fromhex(data["enc"])

ans = None

for s in itertools.product(range(4), repeat=n):
    ok = True

    for ai, bi in zip(A, b):
        val = sum(x * y for x, y in zip(ai, s)) % q

        # 计算误差 e = b_i - <a_i, s>
        e = (bi - val) % q

        # 将模 q 下的大数转成有符号误差
        if e > q // 2:
            e -= q

        if e not in [-1, 0, 1]:
            ok = False
            break

    if ok:
        ans = list(s)
        break

print("s =", ans)

key = hashlib.sha256(str(ans).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc), 16)

print(flag)

Flag

1
DASCTF{LWE_l4tt1c3_r3duct10n_i5_p0w3rful!}

phantom_sign

题目分析

题目使用的是 secp256k1 曲线上的 ECDSA 签名。

ECDSA 签名满足：

1
s_i = k_i^{-1} * (h_i + d * r_i) mod n

其中：

  • d 是私钥；
  • Q = dG 是公钥；
  • k_i 是每次签名使用的 nonce；
  • h_i 是消息哈希；
  • r_i、s_i 是签名结果；
  • n 是椭圆曲线群的阶。

正常情况下，只要 nonce k_i 足够随机且不泄露，ECDSA 是安全的。

但是题目中 nonce 的生成方式为：

1
k_i = bytes_to_long(os.urandom(31))

也就是说，k_i 只有 31 字节，满足：

1
0 <= k_i < 2^248

而 secp256k1 的阶 n 接近 2^256，所以每个 nonce 的最高 8 bit 都是 0。

这属于典型的 ECDSA nonce 偏置问题，可以转化为 Hidden Number Problem，然后通过 LLL 格规约恢复私钥 d。

公式推导

ECDSA 签名满足：

1
s_i * k_i = h_i + d * r_i mod n

整理得到：

1
k_i = s_i^{-1} * h_i + s_i^{-1} * r_i * d mod n

令：

1
2
a_i = r_i * s_i^{-1} mod n
b_i = h_i * s_i^{-1} mod n

则有：

1
k_i = a_i * d + b_i mod n

由于每个 k_i < 2^248，所以可以将问题建模为 HNP。

为了消去私钥 d，选第 0 个签名为基准：

1
k_0 = a_0 * d + b_0 mod n

于是：

1
d = a_0^{-1} * (k_0 - b_0) mod n

代入第 i 个方程：

1
k_i = a_i * a_0^{-1} * k_0 + b_i - a_i * a_0^{-1} * b_0 mod n

令：

1
2
c_i = a_i * a_0^{-1} mod n
u_i = b_i - c_i * b_0 mod n

得到：

1
k_i = c_i * k_0 + u_i mod n

此时未知量变成所有较小的 k_i。构造格后进行 LLL 约化，即可寻找包含 nonce 的短向量。

格构造

构造如下格基：

1
2
3
4
5
6
[1, c1, c2, ..., c39, 0]
[0, n,  0, ...,   0, 0]
[0, 0,  n, ...,   0, 0]
...
[0, 0,  0, ...,   n, 0]
[0, u1, u2, ..., u39, B]

其中：

1
B = 2^248

LLL 约化后，期望得到形如下面的短向量：

1
[k0, k1, k2, ..., k39, B]

从而恢复 k0，再恢复私钥：

1
d = a_0^{-1} * (k_0 - b_0) mod n

最后使用私钥派生 AES key：

1
key = sha256(long_to_bytes(d)).digest()[:16]

再通过 AES-CBC 解密得到 flag。

解题脚本

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
import json
import hashlib
from sympy import Matrix
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes

with open("data.json", "r") as f:
    data = json.load(f)

n = data["curve"]["n"]
sigs = data["signatures"]
iv = bytes.fromhex(data["iv"])
enc = bytes.fromhex(data["enc"])

B = 2 ** 248

ab = []

for h, r, s in sigs:
    inv_s = pow(s, -1, n)
    a = r * inv_s % n
    b = h * inv_s % n
    ab.append((a, b))

a0, b0 = ab[0]
inv_a0 = pow(a0, -1, n)

cs = []
us = []

for a, b in ab[1:]:
    c = a * inv_a0 % n
    u = (b - c * b0) % n
    cs.append(c)
    us.append(u)

m = len(cs) + 1

basis = []

# 第一行用于关联所有 k_i
basis.append([1] + cs + [0])

# 中间行放入模数 n
for i in range(1, m):
    row = [0] * (m + 1)
    row[i] = n
    basis.append(row)

# 最后一行放入 u_i 和缩放参数 B
basis.append([0] + us + [B])

M = Matrix(basis)
L = M.lll()

d = None

for row in L.tolist():
    if abs(row[-1]) == B:
        sign = 1 if row[-1] == B else -1
        ks = [sign * x for x in row[:-1]]

        if all(0 <= x < B for x in ks):
            k0 = ks[0]
            d = (k0 - b0) * inv_a0 % n
            break

assert d is not None

print("d =", d)

key = hashlib.sha256(long_to_bytes(d)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc), 16)

print(flag)

恢复结果

1
d = 69733894115169365517439430123407937761015055472912247236884018827222720875663

Flag

1
DASCTF{3cd5a_b1as3d_n0nc3_HNP_l4tt1c3_4ttack!}

总结

三道题分别考察了三个常见密码学漏洞：

题目 漏洞点 解法
three_friends RSA 模数共享素因子 gcd 分解模数
lattice_oracle 小维 LWE，秘密空间极小 枚举秘密向量并解 AES
phantom_sign ECDSA nonce 最高 8 bit 固定为 0 HNP 建模 + LLL 格攻击恢复私钥

最终三个 flag 为：

1
2
3
DASCTF{thr33_fri3nds_sh@r3_pr1m3s!!}
DASCTF{LWE_l4tt1c3_r3duct10n_i5_p0w3rful!}
DASCTF{3cd5a_b1as3d_n0nc3_HNP_l4tt1c3_4ttack!}

这三道题的共同点是：表面上看使用了标准密码算法，但实现细节破坏了安全假设。

  • RSA 题的问题在于模数之间共享素因子；
  • LWE 题的问题在于秘密空间过小，可以直接枚举；
  • ECDSA 题的问题在于 nonce 存在高位偏置，可以通过格攻击恢复私钥。

Crypto 题中，很多时候算法本身并没有被破解，真正被利用的是参数生成、随机数、密钥空间和实现细节中的问题。