2026—SHCTF-crypto-Writeup

Crypto 方向

题目1：阶段1-AES的诞生

Step 1. 源代码审计

结合题目名字和多出来的附件，采用AES被官方发布的时间2001-11-26，然后换成Unix时间戳，得到key
Step 2. 读取data.txt，运行exp拿到flag
exp：

import re
from binascii import unhexlify
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import padding

# 1) 从 data.txt 读 iv 和密文
with open("data.txt", "r", encoding="utf-8") as f:
    lines = f.read().splitlines()

iv_hex = lines[0].split("=")[1].strip()
cts = [re.search(r"\|\s*([0-9a-f]{32})\s*\|", ln).group(1) for ln in lines if ln.strip().startswith("|")]

iv = unhexlify(iv_hex)

# 2) “AES的诞生” => 2001-11-26 00:00:00 (UTC+8) => unix=1006704000
t = 1006704000 * 10**6
key = (str(t) * 2).encode()  # 32 bytes

# 3) 解密每一块（注意：题目里每次都是用同一个 iv 重新 CBC，所以这里也每块独立解）
cipher = Cipher(algorithms.AES(key), modes.CBC(iv))

groups = []
for ct_hex in cts:
    decryptor = cipher.decryptor()
    pt_padded = decryptor.update(unhexlify(ct_hex)) + decryptor.finalize()

    unpadder = padding.PKCS7(128).unpadder()
    pt = unpadder.update(pt_padded) + unpadder.finalize()
    groups.append(pt.decode())

# 4) 拼回二进制串：最后一组会混入随机字母数字，截到只剩 0/1
bin_str = "".join(groups[:-1]) + re.match(r"[01]+", groups[-1]).group(0)

flag_int = int(bin_str, 2)
flag_bytes = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, "big")
print(flag_bytes.decode())

运行结果：

题目2：阶段1-Ez_RSA

简单的维纳攻击

题目3：阶段1-Stream

Step 1. 源代码审计
流密码+LCG，一块明文和一块LCG生成的stream单独异或得到密文
由P_known和C_known先恢复LCG的基本参数，然后预测全部LCG状态，再解密C_flag得到flag

Step 2. exp

import math
from functools import reduce

P_known = b'Insecure_linear_congruential_random_number!!!!!!'
C_known = bytes.fromhex("44e18dfa1acd14aa790fc3bac4ca54c137bcd47bdfc2209a53b83715ecad3e29249845720588cac007bfb94f8476d91a")
C_flag  = bytes.fromhex("1995374a5b64c6696578c1d5bdc6fa3d1e974b813436eab4348db801fb7a6703658eaa4fefa2c6fd6792beb969df8ca70ad87a4f4aea6ca0040d65a3c1e3a5bf2655cafc1e5603a171edc9aa077c0ca264677c351907f35756c14dd7ece428cb424a3804b544ccb53e99935f9bc2d8483dd7587379c99b3542c222008a")

def blocks8(b):
    return [int.from_bytes(b[i:i+8], 'big') for i in range(0, len(b), 8)]

# 1) 恢复 x1..x6（keystream blocks）
P_blocks = blocks8(P_known)
C_blocks = blocks8(C_known)
x = [p ^ c for p, c in zip(P_blocks, C_blocks)]  # x1..x6

# 2) 恢复 m：m | (t_{i+2}*t_i - t_{i+1}^2)，取 gcd
t = [x[i+1] - x[i] for i in range(len(x)-1)]
u = [t[i+2]*t[i] - t[i+1]*t[i+1] for i in range(len(t)-2)]
m = reduce(math.gcd, [abs(ui) for ui in u])

# 3) 恢复 a,c
num = (x[2] - x[1]) % m
den = (x[1] - x[0]) % m
a = (num * pow(den, -1, m)) % m
c = (x[1] - a * x[0]) % m

# 4) 生成足够的 keystream 解密 C_flag
need_blocks = math.ceil(len(C_flag) / 8)
cur = x[-1]
ks = []
for _ in range(need_blocks):
    cur = (a * cur + c) % m
    ks.append(cur)

ks_bytes = b''.join(k.to_bytes(8, 'big') for k in ks)[:len(C_flag)]
flag = bytes(cb ^ kb for cb, kb in zip(C_flag, ks_bytes))
print(flag.decode(errors="replace"))

运行结果：

题目4：阶段1-TE

简单的共模攻击

题目5：阶段1-not_eight_length

费马分解得到的m：m=2659816110426110758853408064477848108780584180748829547395156778024725420435889565769424125
直接long_to_bytes后发现是乱码，结合题目，发现不是正常的8bit对齐，而是7-bit ASCII，且有少量padding
exp：

from Crypto.Util.number import long_to_bytes

m = 2659816110426110758853408064477848108780584180748829547395156778024725420435889565769424125

b = long_to_bytes(m)
bits = ''.join(f'{x:08b}' for x in b)

# 304 bits 不是 7 的倍数 -> 前面有 3 个 padding bit
bits = bits[3:]

flag = ''.join(chr(int(bits[i:i+7], 2)) for i in range(0, (len(bits)//7)*7, 7))
print(flag)

flag：SHCTF{99f4a238-9bd5-498a-b8ea-5cd243a36a19}

题目6：阶段1-古典也颇有韵味啊

秘钥找个培根密码的在线网址解密得到：NOTVIGENERE（其中 U/V 合并）
然后自钥维吉尼亚解密得到：oops!you made it! here is your flag:shctf{cl@ssic_c2ypto_also_crypt0}
修改flag头：SHCTF{cl@ssic_c2ypto_also_crypt0}

题目7：阶段2-Titanium Lock

Step 1. 源代码审计
总共有3个加密函数，我们一层一层剥开
先看f3：泄露的out可以回复出AES的key，每次操作选随机一个128位（与key一样位数）的n，然后做位与操作，输出模3，模2的结果
说得简单一点，也就是统计同一个比特位，key和n都是1的个数，然后取个数模3，模2的结果，那么我们可以发现余1的情况是确定的，所以取所有trace中余1的情况构建方程组，在GF(3)下可以解出key，也就可以破解f3的AES解密，得到f2的最终数据
再看f2：一个线性的变化，直接逆就行
相当于在方程y=C1*x+C2中，我们已知y，C1，C2，解出x即可
最后看f1：seed可以爆破，但是要注意坑点：last = ((int(c) + r) if int(c) % 2 == 0 else (int(c) * r)) ^ last
所以0和1的输出是一样的，难以分辨，那么就通过DFS和确定flag头SHCTF{}，先确定高位，再爆破

Step 2. exp

import numpy as np
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import random
import ast
import sys

# 增加整数转字符串的长度限制，防止超长数字报错
sys.set_int_max_str_digits(1000000)

def solve():
    print("========================================")
    print("      SHCTF Crypto Challenge Solver     ")
    print("========================================")

    # ---------------------------------------------------
    # 第一步：读取并解析数据
    # ---------------------------------------------------
    print("[-] Step 1: Loading data.txt...")
    try:
        with open("data.txt", "r") as f:
            lines = f.readlines()
    except FileNotFoundError:
        print("[!] Error: data.txt not found.")
        return

    p1, p2, trace, result = None, None, None, None
    for line in lines:
        line = line.strip()
        if not line: continue
        if "=" in line:
            k, v = line.split("=", 1)
            k, v = k.strip(), v.strip()
            # 使用 ast.literal_eval 安全解析列表，result 作为字符串直接读取
            if k == "p1": p1 = ast.literal_eval(v)
            elif k == "p2": p2 = ast.literal_eval(v)
            elif k == "trace": trace = ast.literal_eval(v)
            elif k == "result": result = v

    if not (p1 and p2 and trace and result):
        print("[!] Error: Failed to parse variables from data.txt")
        return

    # ---------------------------------------------------
    # 第二步：利用侧信道泄露恢复 Key (GF(3) 高斯消元)
    # ---------------------------------------------------
    print("[-] Step 2: Recovering Key using Side-Channel Leakage...")
    equations = []
    targets = []
    
    # 筛选出 output=1 的方程: popcount(n & k) % 3 == 1
    for n, b in trace:
        if b == 1:
            bits = [(n >> i) & 1 for i in range(128)]
            equations.append(bits)
            targets.append(1)
            
    # 取前 200 个方程构建矩阵
    eq_count = min(len(equations), 200)
    M = np.array(equations[:eq_count], dtype=int)
    Y = np.array(targets[:eq_count], dtype=int)
    
    # 高斯消元求解 Ax = b mod 3
    rows, cols = M.shape
    pivot_row = 0
    aug = np.hstack((M, Y.reshape(-1, 1)))
    
    for j in range(cols):
        if pivot_row >= rows: break
        candidates = np.where(aug[pivot_row:, j] % 3 != 0)[0]
        if len(candidates) == 0: continue
        curr = candidates[0] + pivot_row
        aug[[pivot_row, curr]] = aug[[curr, pivot_row]]
        inv = 1 if aug[pivot_row, j] % 3 == 1 else 2
        aug[pivot_row] = (aug[pivot_row] * inv) % 3
        for r in range(rows):
            if r != pivot_row and aug[r, j] % 3 != 0:
                factor = aug[r, j]
                aug[r] = (aug[r] - factor * aug[pivot_row]) % 3
        pivot_row += 1

    key_val = 0
    for j in range(cols):
        for r in range(rows):
            if aug[r, j] == 1 and np.sum(aug[r, :j]) == 0:
                if aug[r, -1] == 1:
                    key_val |= (1 << j)
                break
    
    print(f"    [+] Recovered Key: {key_val}")

    # ---------------------------------------------------
    # 第三步：解密 AES
    # ---------------------------------------------------
    print("[-] Step 3: Decrypting AES layer...")
    try:
        k_hash = md5(str(key_val).encode()).digest()
        cipher = AES.new(k_hash, AES.MODE_CTR, nonce=b"Tiffany\x00")
        decrypted_bytes = cipher.decrypt(bytes.fromhex(result))
        data_list = ast.literal_eval(decrypted_bytes.decode())
        print(f"    [+] AES Decryption successful. Data length: {len(data_list)}")
    except Exception as e:
        print(f"[!] AES Error: {e}")
        return

    # ---------------------------------------------------
    # 第四步：逆向 f2 (线性变换)
    # ---------------------------------------------------
    print("[-] Step 4: Reversing f2 (Matrix Inversion)...")
    c1 = np.array(p1)
    c2 = np.array(p2)
    v_out = []
    
    # 求解 C1 * x = y - C2
    for i in range(0, len(data_list), 16):
        y_chunk = np.array(data_list[i:i+16])
        target = y_chunk - c2
        x_sol, _, _, _ = np.linalg.lstsq(c1, target, rcond=None)
        x_rounded = np.rint(x_sol).astype(int)
        v_out.extend(x_rounded.tolist())

    # 去除 Padding
    # Padding 是 0-255 的随机数，有效数据通常远大于 100000
    # 我们找到第一个小于 300 的数作为截断点
    enc_data = []
    for val in v_out:
        if val > 300: # 阈值，区分 valid data 和 padding
            enc_data.append(val)
        else:
            break
            
    print(f"    [+] Recovered encrypted data stream. Length: {len(enc_data)}")

    # ---------------------------------------------------
    # 第五步：逆向 f1 (Seed爆破 + DFS 歧义消除)
    # ---------------------------------------------------
    print("[-] Step 5: Cracking f1 (Brute-force Seed & DFS)...")
    
    TARGET_PREFIX = b"SHCTF{"  # 用于剪枝的已知前缀
    correct_seed = None
    digit_choices = []
    
    # 1. 寻找正确的 Seed
    # 遍历 100000 - 999999
    for seed in range(100000, 1000000):
        random.seed(seed)
        last = 0
        possible = True
        current_choices_list = []
        
        for val in enc_data:
            target = val ^ last
            last = val
            r = random.randint(100000, 999999)
            
            opts = []
            # 偶数规则: d + r = target
            for d in range(0, 10, 2):
                if d + r == target: opts.append(d)
            # 奇数规则: d * r = target
            for d in range(1, 10, 2):
                if d * r == target: opts.append(d)
            
            if not opts:
                possible = False
                break
            # 去重并排序
            current_choices_list.append(sorted(list(set(opts))))
            
        if possible:
            correct_seed = seed
            digit_choices = current_choices_list
            print(f"    [+] Found valid Seed: {seed}")
            break
            
    if correct_seed is None:
        print("[!] Failed to find seed. Check padding logic.")
        return

    # 2. DFS 搜索解决 0/1 歧义
    print("    [+] Starting DFS to resolve '0/1' collisions...")
    
    ambiguous_count = sum(1 for opts in digit_choices if len(opts) > 1)
    print(f"    [i] Ambiguous positions found: {ambiguous_count}")

    # DFS 函数
    def check_solution(digits):
        """将数字列表转为 Flag 字符串并检查前缀"""
        s = "".join(str(d) for d in digits)
        try:
            b = long_to_bytes(int(s))
            # 检查前缀
            if len(b) >= len(TARGET_PREFIX):
                if not b.startswith(TARGET_PREFIX):
                    return False
            # 检查完整性 (如果长度不够长，只要前缀对就可以继续)
            # 但这里我们是在最后一步检查
            return b
        except:
            return False

    def dfs(idx, current_digits):
        # 剪枝优化：每确定 2 位数字，就检查一次前缀
        # 两位数字大约对应 6-7 bit，足够快速排除错误分支
        if len(current_digits) > 10 and len(current_digits) % 2 == 0:
            # 估算当前字节
            s_partial = "".join(str(d) for d in current_digits)
            # 补全后续为 0 以计算最小可能值
            s_min = s_partial + "0" * (len(digit_choices) - len(current_digits))
            s_max = s_partial + "9" * (len(digit_choices) - len(current_digits))
            try:
                b_min = long_to_bytes(int(s_min))
                b_max = long_to_bytes(int(s_max))
                
                # 获取已确定的公共前缀字节
                common_len = 0
                for i in range(min(len(b_min), len(b_max))):
                    if b_min[i] == b_max[i]:
                        common_len += 1
                    else:
                        break
                
                stable_bytes = b_min[:common_len]
                
                # 检查 Flag 头部
                check_len = min(common_len, len(TARGET_PREFIX))
                if stable_bytes[:check_len] != TARGET_PREFIX[:check_len]:
                    return None # 剪枝
                
                # 检查可打印性 (除了头部)
                for k in range(len(TARGET_PREFIX), common_len):
                    if not (32 <= stable_bytes[k] <= 126):
                        return None # 剪枝
            except:
                pass

        # 终止条件
        if idx == len(digit_choices):
            s = "".join(str(d) for d in current_digits)
            try:
                final_bytes = long_to_bytes(int(s))
                if final_bytes.startswith(TARGET_PREFIX) and final_bytes.endswith(b"}"):
                    return final_bytes
            except:
                pass
            return None

        # 递归搜索
        for digit in digit_choices[idx]:
            current_digits.append(digit)
            res = dfs(idx + 1, current_digits)
            if res: return res
            current_digits.pop()
        
        return None

    # 执行搜索
    # 为了避免递归深度过深（虽然这里只有几百层，Python默认1000，通常没问题），可以设置一下
    sys.setrecursionlimit(5000)
    
    flag = dfs(0, [])
    
    if flag:
        print("\n" + "="*40)
        print(f" SUCCESS! Flag Found: \n {flag.decode()}")
        print("="*40)
    else:
        print("\n[!] DFS finished but no flag found. Review constraints.")

if __name__ == "__main__":
    solve()

运行结果：

题目8-10：阶段2/3-hash 1 2 3

hash1 2 3是一个系列的，所以放在一起写
1只需要两串数据不同即可，2需要前16字节都是字母或者数字，在2的基础上加上前16字节必须不同
正常做法应该是用在线网站或者写脚本运行，但是鄙人偷了个懒，让Agent去已知的库里找一组出来，俗称站在巨人的肩膀上
1：Apple 1 (Hex): 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2
Apple 2 (Hex): 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2
2：
3：Apple 1 (Hex): 69733161626369733161626369733161873339a7b1bdd071422a083b5f18b442d47365ee296aba07a2fd8ba1d5b5b43cf781f965218b61caa1fb197642f530ef760cf0db02f7ad2f3bbcd7f54e5c5aa214373a6831a94e2385fce4347642dceda16dcf1724037898cf42580b91d853db382270ee09bfd985a1792010d6ac4a5b
Apple 2 (Hex):
69733161626369733162626369733161873339a7b1bdd071422a083b5f18b442d47365ee296aba07a2fd8ba1d5b5b43cf781f965218b61caa1fb197642f530ef760cf0db02f7ad2f3bbbd7f54e5c5aa214373a6831a94e2385fce4347642dceda16dcf1724037898cf42580b91d853db382270ee09bfd985a1792010d6ac4a5b
然后输入终端分别得到flag，这里写wp的时候懒得去重新截屏flag了，不好意思（

题目11：阶段2-隐藏的子集和？

本人线代基础较差，现阶段暂时不能完全将设计到格问题的原理讲得非常明白，目前多依赖于Agent，未来会及时补上
这是一个经典的HSSP问题，目标是恢复原始矩阵A，但是有个巨大的干扰：x
所以得先消除x，也就是寻找正交空间，找到很多个向量u来构成矩阵A的补空间。
这些u首先满足在模p下与h正交：

$$u \cdot h \equiv 0 \pmod p$$

代入：$$
u \cdot (xA) \equiv x \cdot (uA) \equiv 0 \pmod p

x很大，u和A都很小，也就是说u和A也大概率在模p下是正交的（不正交的概率为1/p） 然后再计算这些u的核空间，最后进行LLL找到包含flag的矩阵A的原始向量 这里有很多线代的专业知识，初次接触我也是一脸懵逼，慢慢补吧 exp：得用sage环境运行

import ast
from Crypto.Util.number import long_to_bytes

# 1. 读取数据
# 请确保 data.txt 在同一目录下
with open('data.txt', 'r') as f:
    p = int(f.readline().strip())
    h = ast.literal_eval(f.readline().strip())

# 过滤掉 h 中的方括号标记 (如果有的话，根据你提供的文件内容样例)
# 假设 h 是一个纯整数列表，如果 data.txt 格式复杂，请自行调整解析
# 这里假设 h 已经是一个 list of integers

n = 70
m = len(h)
print(f"[*] Parameters: n={n}, m={m}")
print(f"[*] Modulus p (approx {p.bit_length()} bits)")

# 2. 构建正交格 (Orthogonal Lattice)
# 我们寻找向量 u 使得 u * h = 0 mod p
# 构造格基矩阵 B (m x m):
# [ 1  0 ...  -h_0 * h_{m-1}^-1 ]
# [ 0  1 ...  -h_1 * h_{m-1}^-1 ]
# ...
# [ 0  0 ...  p ]

# 确保 h 的最后一个元素可逆（p是质数，只要不为0即可）
# 如果 h[-1] 为 0，通常交换位置即可，但为了保持顺序对应，这里假设题目生成的随机数不为0
if h[-1] % p == 0:
    raise ValueError("h[-1] is 0 mod p, need to swap specific columns.")

h_last_inv = inverse_mod(h[-1], p)

# 初始化单位阵
M = Matrix(ZZ, m, m)
for i in range(m - 1):
    M[i, i] = 1
    M[i, m - 1] = (-h[i] * h_last_inv) % p
M[m - 1, m - 1] = p

print("[*] Running LLL on orthogonal lattice (this may take a minute)...")
L = M.LLL()

# 3. 利用正交性恢复 A 的行空间
# 理论上，L 中的短向量 u 都满足 u * A^T = 0
# 我们取前 m-n 个最短的向量构成矩阵 U
# A 的行向量应该在 U 的右核 (Right Kernel) 中

print("[*] Computing kernel...")
# 取足够多的约束向量。理论上 rank(A) = n，所以我们需要 m-n 个正交约束
U = L[0 : m - n] 
Kernel = U.right_kernel()

print("[*] Running LLL on Kernel basis to recover rows of A...")
# Kernel 的基包含了 A 的行向量。A 的行向量很短 (0,1,2)，所以 LLL 应该能把它们找出来
Recovered_Basis = Kernel.basis_matrix().LLL()

# 4. 寻找 Flag
# flag 对应的行只包含 0 和 1 (或者全为 0 和 -1，因为基向量符号不确定)
print("[*] Searching for flag candidate...")

found = False
for row in Recovered_Basis:
    vec = list(row)
    
    # 检查是否只由 0, 1 组成
    if all(x in [0, 1] for x in vec):
        bits = "".join(str(x) for x in vec)
        # 转为 bytes
        try:
            flag_int = int(bits, 2)
            flag = long_to_bytes(flag_int)
            if b'SHCTF{' in flag:
                print(f"\n[SUCCESS] Flag found: {flag.decode()}")
                found = True
                break
        except:
            continue
            
    # 检查是否只由 0, -1 组成 (LLL 可能会翻转符号)
    elif all(x in [0, -1] for x in vec):
        bits = "".join(str(-x) for x in vec)
        try:
            flag_int = int(bits, 2)
            flag = long_to_bytes(flag_int)
            if b'SHCTF{' in flag:
                print(f"\n[SUCCESS] Flag found: {flag.decode()}")
                found = True
                break
        except:
            continue

if not found:
    print("[-] Flag row not found immediately. Check the recovered basis manually or parameters.")
    # 打印一些只有少量非0/1元素的行作为调试
    for i, row in enumerate(Recovered_Basis):
        vec = list(row)
        # 简单统计非 0/1/-1 的元素个数
        weird_counts = sum(1 for x in vec if x not in [0, 1, -1])
        if weird_counts == 0:
            print(f"Row {i} looks binary: {vec[:20]}...")

运行结果：  ### 题目12：阶段3-椭圆曲线 这题也蛮有意思的，两个漏洞，第一个利用start和end简单的线性关系直接得到secret 第二个是经典的ECDSA椭圆曲线数字签名中，两条消息共用一个k的情况，做个变化可以得出secret 懒得写脚本了，最后的flag是SHCTF{205436e5-d598-4859-a237-d3f40e7ed45b}