DASCTF 2026 夏季赛 WriteUp

Crypto#

three_friends#

题目：

1
from Crypto.Util.number import *
2

3
flag = b"***********"
4

5
L = len(flag)
6
m1 = bytes_to_long(flag[:L//3])
7
m2 = bytes_to_long(flag[L//3:2*L//3])
8
m3 = bytes_to_long(flag[2*L//3:])
9

10
p = getPrime(512)
11
q = getPrime(512)
12
r = getPrime(512)
13

14
e = 65537
15

16
n1 = p * q
17
n2 = q * r
18
n3 = p * r
19

20
c1 = pow(m1, e, n1)
21
c2 = pow(m2, e, n2)
22
c3 = pow(m3, e, n3)
23

24
print(f"n1 = {n1}")
25
print(f"n2 = {n2}")
26
print(f"n3 = {n3}")
27
print(f"e = {e}")
28
print(f"c1 = {c1}")
29
print(f"c2 = {c2}")
30
print(f"c3 = {c3}")
31

32
"""
33
n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
34
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
35
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401
36
e = 65537
37
c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
38
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
39
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002
40
"""

n1 = p * q, n2 = q * r, n3 = p * r，gcd打出公因子p，q，r即可：p = gcd(n1, n2), q = gcd(n1, n3), r = gcd(n2, n3)。

exp.py：

1
from math import gcd
2
from Crypto.Util.number import long_to_bytes, inverse
3

4
def dec(c, p, q):
5
    phi = (p - 1) * (q - 1)
6
    d = inverse(e, phi)
7
    return long_to_bytes(pow(c, d, p * q))
8

9
n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
10
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
11
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401
12
e = 65537
13
c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
14
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
15
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002
16
q = gcd(n1, n2)
17
p = gcd(n1, n3)
18
r = gcd(n2, n3)
19
flag = dec(c1, p, q) + dec(c2, q, r) + dec(c3, p, r)
20
print(flag.decode())
21
# DASCTF{thr33_fri3nds_sh@r3_pr1m3s!!}

lattice_oracle#

题目：

1
from Crypto.Cipher import AES
2
import hashlib, os, json, random
3

4
flag = b"?"
5

6
n = 6
7
q = 97
8
m = 30
9

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

12
A = []
13
b = []
14
for _ in range(m):
15
    a_i = [random.randint(0, q - 1) for _ in range(n)]
16
    e_i = random.randint(-1, 1)
17
    b_i = (sum(x * y for x, y in zip(a_i, s)) + e_i) % q
18
    A.append(a_i)
19
    b.append(b_i)
20

21
key = hashlib.sha256(str(s).encode()).digest()[:16]
22
iv = os.urandom(16)
23
pad_len = 16 - len(flag) % 16
24
enc = AES.new(key, AES.MODE_CBC, iv).encrypt(flag + bytes([pad_len]) * pad_len)
25

26
print(f"n = {n}")
27
print(f"q = {q}")
28
print(f"m = {m}")
29
print(f"A = {A}")
30
print(f"b = {b}")
31
print(f"iv = '{iv.hex()}'")
32
print(f"enc = '{enc.hex()}'")
33

34
"""
35
n = 6
36
q = 97
37
m = 30
38
A = [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]]
39
b = [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28]
40
iv = 'bcdad772f7a0ec967887f7b8f36234c8'
41
enc = '00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc'
42
"""

s只有 6 维，每维0 ~ 3，直接爆破4 ** 6 = 4096种s，对每个候选s计算：

v_i=\langle A_i,s\rangle \bmod q,e_i\equiv b_i-v_i\pmod{q}

筛选满足所有误差e ∈ {-1, 0, 1}的解即可。

exp.py：

1
import json, hashlib
2
from itertools import product
3
from Crypto.Cipher import AES
4

5
data = json.load(open("data.txt"))
6
A = data["A"]
7
b = data["b"]
8
q = data["q"]
9
n = data["n"]
10
for s in product(range(4), repeat=n):
11
    ok = True
12
    for ai, bi in zip(A, b):
13
        v = sum(x * y for x, y in zip(ai, s)) % q
14
        e = (bi - v) % q
15
        if e > q // 2:
16
            e -= q
17
        if e not in (-1, 0, 1):
18
            ok = False
19
            break
20
    if ok:
21
        s = list(s)
22
        print("s =", s)
23
        break
24
key = hashlib.sha256(str(s).encode()).digest()[:16]
25
iv = bytes.fromhex(data["iv"])
26
enc = bytes.fromhex(data["enc"])
27
cipher = AES.new(key, AES.MODE_CBC, iv)
28
pt = cipher.decrypt(enc)
29
pt = pt[:-pt[-1]]
30
print(pt.decode())
31
# s = [0, 0, 2, 1, 1, 1]
32
# DASCTF{LWE_l4tt1c3_r3duct10n_i5_p0w3rful!}

phantom_sign#

题目：

1
import os, hashlib, json
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import pad
4
from Crypto.Util.number import long_to_bytes, bytes_to_long
5

6
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
7
a  = 0
8
b  = 7
9
n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
10
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
11
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
12

13
def inv_mod(val, mod):
14
    return pow(val, -1, mod)
15

16
def point_add(P, Q):
17
    if P is None: return Q
18
    if Q is None: return P
19
    x1, y1 = P
20
    x2, y2 = Q
21
    if x1 == x2 and y1 != y2:
22
        return None
23
    if P == Q:
24
        lam = (3 * x1 * x1 + a) * inv_mod(2 * y1, p) % p
25
    else:
26
        lam = (y2 - y1) * inv_mod(x2 - x1, p) % p
27
    x3 = (lam * lam - x1 - x2) % p
28
    y3 = (lam * (x1 - x3) - y1) % p
29
    return (x3, y3)
30

31
def point_mul(k, P):
32
    R = None
33
    Q = P
34
    while k > 0:
35
        if k & 1:
36
            R = point_add(R, Q)
37
        Q = point_add(Q, Q)
38
        k >>= 1
39
    return R
40

41
G = (Gx, Gy)
42

43
flag = b"DASCTF{************************************}"
44
d = bytes_to_long(os.urandom(32)) % n
45

46
Q = point_mul(d, G)
47

48
NUM_SIGS = 40
49

50
messages = []
51
sigs = []
52

53
for i in range(NUM_SIGS):
54
    msg = f"transaction_{i:04d}".encode()
55
    h_i = int(hashlib.sha256(msg).hexdigest(), 16) % n
56
    k_i = bytes_to_long(os.urandom(31))
57
    R_i = point_mul(k_i, G)
58
    r_i = R_i[0] % n
59
    s_i = inv_mod(k_i, n) * (h_i + d * r_i) % n
60
    messages.append(msg.decode())
61
    sigs.append((h_i, r_i, s_i))
62

63
key = hashlib.sha256(long_to_bytes(d)).digest()[:16]
64
iv = os.urandom(16)
65
enc = AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16))
66

67
output = {
68
    "curve": {"p": p, "a": a, "b": b, "n": n, "Gx": Gx, "Gy": Gy},
69
    "Q": [Q[0], Q[1]],
70
    "messages": messages,
71
    "signatures": [(h, r, s) for h, r, s in sigs],
72
    "iv": iv.hex(),
73
    "enc": enc.hex(),
74
}
75

76
with open("data.json", "w") as f:
77
    json.dump(output, f, indent=2)

题目实现了 secp256k1 上的 ECDSA 签名。签名公式为：

s_i \equiv k_i^{-1}(h_i + d \cdot r_i) \pmod{n}

其中d是私钥，k_i是每次签名使用的 nonce。正常情况下，k_i应该在[1, n)中均匀随机选取，但题目中使用了：

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

因此每个 nonce 只有 31 字节，即0 <= k_i < 2^248。而 secp256k1 的阶n约为 256 bit，所以 nonce 的最高 8 bit 恒为 0，存在明显偏置。由 ECDSA 签名公式可得：

s_i\cdot k_i \equiv h_i + d \cdot r_i \pmod{n}

两边乘以s_i^{-1}：

k_i \equiv h_i s_i^{-1} + d \cdot r_i \cdot s_i^{-1} \pmod{n}

令：

a_i \equiv r_i\cdot s_i^{-1} \pmod{n}, b_i \equiv h_i\cdot s_i^{-1} \pmod{n}

得到：

k_i \equiv a_i \cdot d + b_i \pmod{n}

由于所有k_i都小于2 ** 248，所以可以将其转化为 Hidden Number Problem，使用 LLL 格规约恢复私钥d。

exp.py：

1
# SageMath 10.7
2
from sage.all import *
3
import json
4
import hashlib
5
from Crypto.Cipher import AES
6
from Crypto.Util.Padding import unpad
7
from Crypto.Util.number import long_to_bytes
8

9
with open("data.json", "r") as f:
10
    data = json.load(f)
11
n = data["curve"]["n"]
12
sigs = data["signatures"]
13
m = len(sigs)
14
K = 2 ** 248
15
a = []
16
b = []
17
for h, r, s in sigs:
18
    inv_s = inverse_mod(s, n)
19
    a.append((r * inv_s) % n)
20
    b.append((h * inv_s) % n)
21
# 构造格
22
# 目标短向量形如：
23
# (n*k_1, n*k_2, ..., n*k_m, d*K, n*K)
24
M = Matrix(ZZ, m + 2, m + 2)
25
for i in range(m):
26
    M[i, i] = n * n
27
for i in range(m):
28
    M[m, i] = a[i] * n
29
M[m, m] = K
30
for i in range(m):
31
    M[m + 1, i] = b[i] * n
32
M[m + 1, m + 1] = n * K
33
L = M.LLL()
34
d = None
35
for row in L.rows():
36
    if abs(row[m + 1]) == n * K:
37
        c = row[m + 1] // (n * K)
38
        cand = (row[m] // K) * inverse_mod(c, n)
39
        cand %= n
40
        d = int(cand)
41
        break
42
assert d is not None
43
print("[+] d =", d)
44
key = hashlib.sha256(long_to_bytes(d)).digest()[:16]
45
iv = bytes.fromhex(data["iv"])
46
enc = bytes.fromhex(data["enc"])
47
cipher = AES.new(key, AES.MODE_CBC, iv)
48
flag = unpad(cipher.decrypt(enc), 16)
49
print("[+] flag =", flag.decode())
50
# [+] d = 69733894115169365517439430123407937761015055472912247236884018827222720875663
51
#abs [+] flag = DASCTF{3cd5a_b1as3d_n0nc3_HNP_l4tt1c3_4ttack!}

持续更新中~

Crypto#

three_friends#

lattice_oracle#

phantom_sign#