Mobile wallpaper 1Mobile wallpaper 2Mobile wallpaper 3Mobile wallpaper 4Mobile wallpaper 5Mobile wallpaper 6
Profile Image of the Author
Q1uJu
Announcement
Hope my blog can help you.
Site Statistics
Posts
7
Categories
2
Tags
2
Total Words
28,193
Running Time
0 days
Last Activity
0 days ago
3279 words
16 minutes
HECTF 2025 WriteUp
2025-12-22
WriteUp
2025

Crypto#

下个棋吧#

题目：

先别做题了，flag给你，过来陪我下把棋，对了，别忘了flag要大写，RERBVkFGR0RBWHtWR1ZHWEFYRFZHWEFYRFZWVkZWR1ZYVkdYQX0=

base64 解码得到：DDAVAFGDAX{VGVGXAXDVGXAXDVVVFVGVXVGXA}，一眼ADFGVX密码。

ADFGVX
Aabcdef
Dghijkl
Fmnopqr
Gstuvwx
Vyz0123
X456789

HECTF{1145145201314}

simple_math#

题目：

from Crypto.Util.number import *
from secret import flag


def getmodule(bits):
    while True:
        f = getPrime(bits)
        g = getPrime(bits)
        p = (f<<bits)+g
        q = (g<<bits)+f
        if isPrime(p) and isPrime(q):
            assert  p%4 == 3 and q%4 == 3
            n = p * q
            break
    return n


e = 8
n = getmodule(128)


m = bytes_to_long(flag)
c = pow(m,e,n)


print('c =',c)
print('n =',n)


"""
c = ...
n = ...
"""

加密流程并不复杂，生成两个 128 位的素数f和g。然后p和q分别是：p = (f << 128) + g和q = (g << 128) + f，也就是说p的低 128 位是g，高 128 位是f，q则反过来了。加密是一个Rabin加密，e = 8。

解密首先要从特殊结构的p和q来入手，我们设K := 2 ** 128并在模K - 1下展开：

n=(fK+g)(gK+f)≡(f(1)+g)(g(1)+f)(modK−1)≡(f+g)(f+g)(modK−1)≡(f+g)2(modK−1)\begin{aligned} n &= (fK + g)(gK + f) \\ &\equiv (f(1) + g)(g(1) + f) \pmod{K-1} \\ &\equiv (f+g)(f+g) \pmod{K-1} \\ &\equiv (f+g)^2 \pmod{K-1} \end{aligned}

由此在模K - 1环下对n开方就能得到f + g的余数。而f和g的和量级不超过2 ** 129，故sum = sum_mod + k * (K - 1)，其中k < 4。利用 sage 枚举出正确的sum可以由g = S - f回代回n的等式，用roots()求解f，这样就能直接分解n。

后面的Rabin直接开三次方就行，每次开方产生 4 个根，爆一下就行。

exp.py：

# SageMath 10.7
from Crypto.Util.number import long_to_bytes


c = ...
n = ...
bits = 128
K = 2 ** bits
R = Zmod(K-1)
S_candidates_mod = R(n).sqrt(all=True)
PR.<x> = PolynomialRing(ZZ)
real_p = 0
real_q = 0
for s_mod in S_candidates_mod:
    s_val = Integer(s_mod)
    for k in range(4):
        S = s_val + k * (K - 1)
        eq = (x * K + (S - x)) * ((S - x) * K + x) - n
        roots = eq.roots()
        if roots:
            f = roots[0][0]
            g = S - f
            p = f * K + g
            q = g * K + f
            if p * q == n:
                real_p = p
                real_q = q
                break
    if real_p:
        break
curr_roots = [c]
for layer in range(1, 4):
    next_roots = set()
    for r in curr_roots:
        try:
            mps = Zmod(p)(r).sqrt(all=True, extend=False)
        except ValueError:
            mps = []
        try:
            mqs = Zmod(q)(r).sqrt(all=True, extend=False)
        except ValueError:
            mqs = []
        if not mps or not mqs:
            continue
        for mp in mps:
            for mq in mqs:
                val = crt([Integer(mp), Integer(mq)], [p, q])
                next_roots.add(val)
    curr_roots = list(next_roots)
for m in curr_roots:
    flag = long_to_bytes(int(m))
    if b'HECTF' in flag:
        print(flag.decode())
        break
# HECTF{this_is_a_flag_emm_is_a_true_flag_ok_all_right}

ez_rsa#

题目：

from Crypto.Util.number import *
from gmpy2 import next_prime


from secret import flag


e = 65537
while True:
    p1 = getPrime(512)
    p2 = next_prime(p1)
    q1 = getPrime(250)
    q2 = getPrime(250)
    n1 = p1**2*q1
    n2 = p2**2*q2
    if abs(p1-p2)<p1/(4*q1*q2):
        break


l = len(flag) // 2
m1, m2 = bytes_to_long(flag[:l]), bytes_to_long(flag[l:])


c1 = pow(m1,e,n1)
c2 = pow(m2,e,n2)


print('c1 =', c1)
print('c2 =', c2)
print('n1 =', n1)
print('n2 =', n2)


"""
c1 = ...
c2 = ...
n1 = ...
n2 = ...
"""

最近连分数有点太多了，前两天刚在鹏城杯做完hhhh。证明应该就不用了吧emmm：

n1=p12q1,n2=p22q2n1n2=p12q1p22q2≈q1q2\begin{aligned} &n_1=p_1^2q_1,n_2=p_2^2q_2\\ &\frac{n_1}{n_2}=\frac{p_1^2q_1}{p_2^2q_2}\approx \frac{q_1}{q_2} \end{aligned}

连分数展开找q1和q2即可，分母为q2，分子为q1。

exp.py：

# SageMath 10.7
from Crypto.Util.number import long_to_bytes


c1 = ...
c2 = ...
n1 = ...
n2 = ...
e = 65537
cf = continued_fraction(Integer(n1) / Integer(n2))
for k in cf.convergents():
    q1 = int(k.numerator())
    q2 = int(k.denominator())
    if q1.bit_length() < 240:
        continue
    if n1 % q1 == 0:
        p1_sq = Integer(n1 // q1)
        if p1_sq.is_square():
            p1 = p1_sq.sqrt()
            if n2 % q2 == 0:
                p2 = Integer(n2 // q2).sqrt()
                d1 = inverse_mod(e, p1 * (p1 - 1) * (q1 - 1))
                d2 = inverse_mod(e, p2 * (p2 - 1) * (q2 - 1))
                m1 = pow(c1, d1, n1)
                m2 = pow(c2, d2, n2)
                flag = long_to_bytes(m1) + long_to_bytes(m2)
                print(flag.decode())
                break
# HECTF{cRoss_0v3r_v&ry_yOxi}

dq#

题目：

from Crypto.Util.number import *
from secret import flag


p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
d = inverse(e,(p-1)*(q-1))
dq = d%(q-1)
m = bytes_to_long(flag)
c = pow(m,e,n)
dq_low = dq&((1<<128)-1)
print("dq_low =",dq_low)
print("qinvp =",inverse(q,p))
print("c =",c)
print("n =",n)


"""
dq_low = ...
qinvp = ...
c = ...
n = ...
"""

简约的题目，果然很难，主要是卡爆破上了hhh。加密流程朴实无华，泄露了dq的低 128 位，然后给了qinvp。和常见dq泄露类似（这里留个la佬的博客），有等式：

e⋅dq=k⋅(q−1)+1e \cdot dq = k \cdot (q-1) + 1

但是这题中我们需要把dq_low通过模2 ** 128转换成q_low：

e⋅dqlow≡k⋅(qlow−1)+1(mod2128)k⋅qlow≡e⋅dqlow−1+k(mod2128)qlow≡k−1⋅(e⋅dqlow+k−1)(mod2128)\begin{aligned} &e \cdot dq_{low} \equiv k \cdot (q_{low} - 1) + 1 \pmod{2^{128}}\\ &k \cdot q_{low} \equiv e \cdot dq_{low} - 1 + k \pmod{2^{128}}\\ &q_{low} \equiv k^{-1} \cdot (e \cdot dq_{low} + k - 1) \pmod{2^{128}} \end{aligned}

这题的关键也是点睛之笔在于qinvp，我们已知：

q−1∗q≡1(modp)q^{-1}*q\equiv 1\pmod{p}

即：

q⋅q−1−1=kq⋅pq\cdot q^{-1}-1=k_q\cdot p

我们再乘一个q可以消去未知的p引入已知的n：

q2⋅q−1−q=kp⋅n⇒q2⋅q−1−q≡0(modn)\begin{aligned} &q^2\cdot q^{-1}-q=k_p\cdot n\\ \Rightarrow&q^2\cdot q^{-1}-q\equiv 0\pmod{n} \end{aligned}

结合到 CopperSmith 的等式里，构造f(x)：

f(x)=qinvp⋅(x⋅2128+qlow)−(x⋅2128+qlow)≡0(modn)f(x)=qinvp\cdot(x\cdot2^{128}+q_{low})-(x\cdot2^{128}+q_{low})\equiv 0\pmod{n}

然后 CopperSmith 打出q即可，这里给一版单线程挂爆破的，但是很慢，当时跑了一看 10+ 分钟就停了，后面发现k很小就又试试了发现其实也能出，还是不太熟练了害。

exp1.py：

# SageMath 10.7
from sage.all import *
from Crypto.Util.number import long_to_bytes
from tqdm import trange


dq_low = ...
qinvp = ...
c = ...
n = ...
e = 65537
PR.<x> = PolynomialRing(Zmod(n))
K = 2 ** 128
for k in trange(1, e):
    g = GCD(k, K)
    target = e * dq_low - 1 + k
    if target % g != 0:
        continue
    mask_p = K // g
    try:
        q_low = ((target // g) * inverse_mod(k // g, mask_p)) % mask_p
    except:
        continue
    x_bounds = 2 ** (512 - 128 + int(g).bit_length())
    f = qinvp * (x * mask_p + q_low)**2 - (x * mask_p + q_low)
    roots = f.monic().small_roots(X=x_bounds, beta=1.0, epsilon=0.1)
    if roots:
        q = int(roots[0]) * mask_p + q_low
        if n % q == 0:
            p = n // q
            phi = (p - 1) * (q - 1)
            d = inverse_mod(e, phi)
            m = pow(c, d, n)
            print(long_to_bytes(int(m)).decode())
            break
#   3%|██▏                                                                           | 1845/65536 [00:21<12:15, 86.65it/s]
# HECTF{ay_mi_gatuto_miau_miau}

发现不行就叫 AI 加了一个多线程爆破，几秒就出了。。。但是确实不太熟怎么用多线程了。

exp2.py：

# SageMath 10.7
from sage.all import *
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
from multiprocessing import Pool, cpu_count


# ---------------- 题目数据 ----------------
dq_low = ...
qinvp = ...
c = ...
n = ...
e = 65537


# ---------------- Worker 函数 (定义处理逻辑) ----------------
def solve_batch(k_list):
    # 多进程必须在函数内重新定义环，否则会段错误
    try:
        F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
        (x,) = F._first_ngens(1)
    except: return None


    K = 2 ** 128


    for k in k_list:
        g = GCD(k, K)
        target = e * dq_low - 1 + k
        if target % g != 0: continue


        mask_p = K // g
        try:
            q_low = ((target // g) * inverse_mod(k // g, mask_p)) % mask_p
        except: continue


        x_bounds = 2 ** (512 - 128 + int(g).bit_length())
        f = qinvp * (x * mask_p + q_low)**2 - (x * mask_p + q_low)


        # 你的参数: beta=1.0, epsilon=0.1
        roots = f.monic().small_roots(X=x_bounds, beta=1.0, epsilon=0.1)


        if roots:
            q = int(roots[0]) * mask_p + q_low
            if n % q == 0: return q
    return None


cores = cpu_count()
print(f"[*] Blasting on {cores} cores (Direct Mode)...")


# 1. 切分任务 (Batch Size 设大一点减少通信开销)
BATCH_SIZE = 200
batches = [range(i, min(i + BATCH_SIZE, e)) for i in range(1, e, BATCH_SIZE)]


# 2. 启动多进程
pool = Pool(cores)
found_q = None


try:
    # 3. 进度条监控
    iterator = pool.imap_unordered(solve_batch, batches)
    for res in tqdm(iterator, total=len(batches), unit="batch"):
        if res:
            found_q = res
            pool.terminate() # 找到结果，杀死其他进程
            break
except KeyboardInterrupt:
    pool.terminate()
finally:
    pool.close()
    pool.join()


# 4. 输出结果
if found_q:
    print(f"\n[+] Found q: {found_q}")
    p = n // found_q
    d = inverse_mod(e, (p-1)*(found_q-1))
    print(f"[+] Flag: {long_to_bytes(int(pow(c, d, n))).decode(errors='ignore')}")
else:
    print("\n[-] Failed.")
"""
[*] Blasting on 16 cores (Direct Mode)...
  0%|                                                                                        | 0/328 [00:01<?, ?batch/s]


[+] Found q: ...
[+] Flag: HECTF{ay_mi_gatuto_miau_miau}
"""

ez_ecc#

题目：

from Crypto.Util.number import *
from secret import add,flag,P,Q,b,p


def oncurve(P):
    x,y = P
    if (y**2 - x**3 - x - b)%p == 0:
        return True
    else:
        return False


l = len(flag) // 2
m1, m2 = bytes_to_long(flag[:l]), bytes_to_long(flag[l:])


assert m1 == P[0] and m2 == Q[0]
assert oncurve(P) and oncurve(Q)


print('P + P =', add(P,P))
print('P + Q =', add(P,Q))
print('Q + Q =', add(Q,Q))


"""
P + P = (..., ...)
P + Q = (..., ...)
Q + Q = (..., ...)
"""

又是一道简洁的题，但是就没很卡了。题目给出了三个椭圆曲线上的坐标：

  • R1=P+P=2PR_1=P+P=2P
  • R2=P+QR_2=P+Q
  • R3=Q+Q=2QR_3=Q+Q=2Q

其中flag被拆成两半分别是P和Q的x坐标。我们需要恢复p和b来找到曲线方程，在求出P和Q的坐标恢复flag。

令f(P) = y ** 2 - x ** 3 - x，题目给出的点可以两两相减消去b：

f(R1)−f(R2)=(k1−k2)⋅pf(R2)−f(R3)=(k2−k3)⋅p\begin{aligned} f(R_1)-f(R_2)=(k_1-k_2)\cdot p\\ f(R_2)-f(R_3)=(k_2-k_3)\cdot p \end{aligned}

gcd就能打出p了，b回代p就能求出b了。

求P和Q的坐标可以直接用 SageMath 的division_points(m)方法，可以高效地求出满足m * X = Y的所有点X，但是会有多解，筛一下就行。

exp.py：

# SageMath 10.7
from Crypto.Util.number import long_to_bytes


P_plus_P = (..., ...)
P_plus_Q = (..., ...)
Q_plus_Q = (..., ...)
x1, y1 = P_plus_P
x2, y2 = P_plus_Q
x3, y3 = Q_plus_Q
val1 = y1 ** 2 - x1 ** 3 - x1
val2 = y2 ** 2 - x2 ** 3 - x2
val3 = y3 ** 2 - x3 ** 3 - x3
p = gcd(val1 - val2, val2 - val3)
b = val1 % p
E = EllipticCurve(GF(p), [1, b])
Point_2P = E(x1, y1)
Point_PQ = E(x2, y2)
Point_2Q = E(x3, y3)
possible_Ps = Point_2P.division_points(2)
possible_Qs = Point_2Q.division_points(2)
real_P = None
real_Q = None
for cand_P in possible_Ps:
    for cand_Q in possible_Qs:
        if cand_P + cand_Q == Point_PQ:
            real_P = cand_P
            real_Q = cand_Q
            break
    if real_P:
        break
m1, m2 = int(real_P[0]), int(real_Q[0])
flag = long_to_bytes(m1) + long_to_bytes(m2)
print(flag.decode())
# HECTF{W00O0O_Y0U_G@t_the_ez_Ecc!!___}

ez_random#

题目：

from Crypto.Util.number import *
import random


with open('shuffle_flag.txt', 'r') as fp:
    flag = fp.read().encode()


m = bytes_to_long(flag)
flag_list = [ int(i) for i in bin(m)[2:] ]


rand = random.Random()


rand.shuffle(flag_list)
with open("output.txt","w") as fp:
    for _ in range(312):
        fp.write(str(rand.getrandbits(64))+'\n')


print('flag_list =',flag_list)


"""
flag_list = [...]
"""

MT19937，可以分成两部分看，一部分是shuffle，一部分是后半的随机数恢复state。后半直接用 maple佬的 gf2bv 可以秒，就是要注意一下好像直接 64 bit 塞应该不行，把高低位取出来按 32 位塞。

这题逆向shuffle的地方还有点不是很懂，给了提示之后喂给 Gemini 3 Pro 出的，后面有时间了再学习学习，准备和 MT19937 整个一起学习一下，现在还不是很熟悉，之前 0xGame Week 4 的恢复种子的其实也还不是很清楚hhhh，之后看看整个总结！目前先鸽了~

exp.py：

# SageMath 10.7
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from Crypto.Util.number import long_to_bytes
import sys


# ==========================================
# 1. 基础工具：Untemper
# ==========================================
def right_shift_inverse(value, shift):
    res = value
    for i in range(32):
        res = value ^ (res >> shift)
    return res


def left_shift_inverse(value, shift, mask):
    res = value
    for i in range(32):
        res = value ^ ((res << shift) & mask)
    return res


def untemper(y):
    # 逆向 Tempering 过程
    y = right_shift_inverse(y, 18)
    y = left_shift_inverse(y, 15, 0xefc60000)
    y = left_shift_inverse(y, 7, 0x9d2c5680)
    y = right_shift_inverse(y, 11)
    return y


def mt_temper(y):
    # 正向 Tempering
    y ^= (y >> 11)
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 15) & 0xefc60000
    y ^= (y >> 18)
    return y


# ==========================================
# 2. 核心：GF(2) 线性缝合求解器
# ==========================================
def solve_split_state_gf2bv(raw_stream, split_idx):
    """
    使用 gf2bv 求解被 Split 的状态。
    raw_stream: output.txt 对应的 624 个 Untempered 内部状态值
    split_idx (K): Shuffle 消耗的随机数数量
    """


    # 1. 初始化 624 个 32位变量的线性系统
    # 这些变量代表 S_old (Shuffle 使用的那个原始状态)
    lin = LinearSystem([32] * 624)
    S_old = lin.gens() # 符号变量列表 S_old[0]...S_old[623]


    equations = []


    # 2. 约束一：Old State 的后半部分 == stream 的前半部分
    # output.txt 的前 (624-K) 个数，实际上是 S_old 剩下的没被 shuffle 用掉的部分
    len_part1 = 624 - split_idx
    for i in range(len_part1):
        # 在 GF(2) 中，a == b 等价于 a ^ b == 0
        equations.append(S_old[split_idx + i] ^ raw_stream[i])


    # 3. 约束二：Twist(S_old) 的前半部分 == stream 的后半部分
    # output.txt 的后 K 个数，是 Twist 之后产生的新状态的前 K 个


    # 我们需要用符号变量模拟 Twist 过程
    mt = list(S_old) # 复制引用，用于模拟 In-place Update


    # 只需计算前 split_idx (K) 个由 Twist 生成的新值
    for i in range(split_idx):
        # --- Symbolic MT19937 Twist ---


        # 1. y = (mt[i] & UPPER) | (mt[i+1] & LOWER)
        # 符号运算: (A & mask) ^ (B & mask)
        val_i = mt[i]
        val_i1 = mt[(i + 1) % 624]
        y = (val_i & 0x80000000) ^ (val_i1 & 0x7fffffff)


        # 2. mag01 = (y & 1) ? 0x9908b0df : 0
        # 符号运算: LSB(y) * MATRIX_A
        # 我们需要手动实现“标量乘向量”的位操作逻辑
        lsb = y & 1
        magic_const = 0x9908b0df
        mag01 = 0


        # 遍历 Magic Constant 的每一位，如果为 1，则将 LSB 异或到对应位
        for bit_pos in range(32):
            if (magic_const >> bit_pos) & 1:
                mag01 ^= (lsb << bit_pos)


        # 3. mt[i] = mt[i+M] ^ (y >> 1) ^ mag01
        val_iM = mt[(i + 397) % 624]
        new_val = val_iM ^ (y >> 1) ^ mag01


        # In-place update (重要！模拟真实 Twist 的更新流)
        mt[i] = new_val


        # 添加约束: 这个计算出的新值必须等于 stream 的对应部分
        equations.append(new_val ^ raw_stream[len_part1 + i])


    # 4. 求解
    # solve_one 内部使用 M4RI 算法，极快
    sol = lin.solve_one(equations)


    if sol is not None:
        return list(sol)
    return None


# ==========================================
# 3. 主程序
# ==========================================


# 题目 Shuffled Flag List
flag_list = [...]


# 1. 读取 output.txt 并 Untemper (恢复为内部状态值)
try:
    with open("output.txt", "r") as f:
        outputs = [int(line.strip()) for line in f if line.strip()]
except:
    print("[-] output.txt not found")
    sys.exit()


raw_stream = []
for o in outputs:
    # getrandbits(64) 是先 low 后 high
    raw_stream.append(untemper(o & 0xffffffff))
    raw_stream.append(untemper((o >> 32) & 0xffffffff))


print("[*] Loaded stream. Probing split index K (Range 380-450)...")


# 2. 爆破 Split Index K
# K 是 Shuffle 消耗的随机数个数，大约在 400 左右
for k in trange(380, 450):


    # 使用 gf2bv 尝试求解缝合状态
    S_recovered = solve_split_state_gf2bv(raw_stream, k)


    if S_recovered:
        print(f"\n[+] FOUND Split Index K={k}!")


        # S_recovered 就是 shuffle 阶段使用的那个完整状态 (Old State)
        # Shuffle 消耗了它的前 K 个数


        # 3. 恢复 Random Stream
        rand_stream = [mt_temper(x) for x in S_recovered]


        # 4. 模拟 Shuffle (解决 Rejection Sampling 定位问题)
        swaps = []
        stream_idx = 0
        possible = True


        # Fisher-Yates 逻辑: for i in reversed(range(1, N)): j = randbelow(i+1)
        for i in range(len(flag_list)-1, 0, -1):
            n = i + 1
            bits = n.bit_length()


            while True:
                # 如果消耗超过了 K，说明这个状态虽然数学上成立，但不符合 shuffle 过程
                if stream_idx >= k:
                    possible = False
                    break


                # 取出随机数
                r_full = rand_stream[stream_idx]
                stream_idx += 1


                # 模拟右移
                r = r_full >> (32 - bits)


                if r < n:
                    swaps.append((i, r))
                    break
            if not possible: break


        if possible:
            print("[+] Shuffle simulation successful.")


            # 5. Unshuffle (逆向交换)
            curr_list = list(flag_list)
            # 逆向执行 swaps (LIFO)
            for i, j in reversed(swaps):
                curr_list[i], curr_list[j] = curr_list[j], curr_list[i]


            # 6. 补 0 并解码
            final_bits = [0] + curr_list
            try:
                m = int("".join(str(x) for x in final_bits), 2)
                flag = long_to_bytes(m)
                print(f"[+] Flag: {flag.decode()}")
                if b"HECTF" in flag:
                    break
            except:
                pass
        else:
            print(f"[-] K={k} solved linearly but failed simulation.")


print("[*] Done.")
# [+] FOUND Split Index K=406!
# [+] Shuffle simulation successful.
# [+] Flag: HECTF{emmm___its_a_correct_flag?___}
# [*] Done.
HECTF 2025 WriteUp
https://q1uju.cc/posts/hectf-2025-writeup/hectf2025-crypto-writeup/
Author
Q1uJu
Published at
2025-12-22
License
CC BY-NC-SA 4.0

Some information may be outdated

QCTF 2025 WriteUp
鹏城杯 2025 WriteUp
© 2025 Q1uJu. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6