WEEK2-CRYPTO

ezDLP

1. 题目分析

题目提供了 main.py 和一个 SageMath 序列化文件 data.sobj。
通过分析源代码 main.py，加密逻辑如下：

生成一个模数 $n$（硬编码在代码中）和模 $n$ 的随机矩阵 $a$。
生成一个 1000 位的随机素数 $k$。
计算 $b = a^k \pmod n$。
将 $k$ 转换为字节后计算 MD5，作为 AES-ECB 的密钥加密 flag。
密文以 Base64 形式给出：ieJNk5335o9lCy6Ar2XymrDy+HVHcQhikluNSra0kBafw1WDCyyuNPkLACeBsavy main.py。

目标：从 data.sobj 中提取 $n, a, b$，求解矩阵离散对数问题 (Matrix DLP) 得到 $k$，从而解密 flag。

2. 数学原理

直接在模 $n$ 的矩阵群上求解离散对数非常困难。但在本题中，我们可以利用线性代数的性质将问题降维。

利用行列式（Determinant）的乘法同态性质：
$b = a^k \pmod n \implies \det(b) \equiv \det(a)^k \pmod n$

令 $y = \det(b), x = \det(a)$，问题转化为标量离散对数问题 (Scalar DLP)：
$y \equiv x^k \pmod n$

由于 $n$ 是合数，我们需要计算群的阶来求解 $k$。这通常需要分解 $n$。
源码注释写道 "Want to factor n? I’ve already done it!" main.py，暗示 $n$ 容易分解或已在数据库中。

3. 解题步骤

步骤一：分解模数 n

使用 SageMath 加载 data.sobj 获得 $n$ 的值。由于 $n$ 很大（324位），本地分解耗时过长。将 $n$ 放入 FactorDB 查询，得到两个大素数因子 $p_1, p_2$。

步骤二：利用 CRT 分步求解

我们需要在模 $n$ 下求解 $k$。根据中国剩余定理（CRT），可以将问题分解到模 $p_1$ 和模 $p_2$ 的有限域下分别求解：

计算 $k_1 = \text{dlog}_{\det(a)}(\det(b)) \pmod {p_1}$
计算 $k_2 = \text{dlog}_{\det(a)}(\det(b)) \pmod {p_2}$

坑点与修正：
在使用 CRT 合并 $k_1$ 和 $k_2$ 时，模数不能简单地设为 $p-1$。因为 $\det(a)$ 生成的子群阶数 (order) 往往是 $p-1$ 的因子。如果直接使用 $p-1$ 作为模数，会导致 CRT 无解（正如我们在调试中遇到的报错 no solution to crt problem）。

正确做法：计算元素 $\det(a)$ 在模 $p$ 下的真实阶数 (multiplicative_order())，将其作为 CRT 的模数。

步骤三：解密

得到 $k$ 后，复现 AES 解密逻辑：
key = md5(long_to_bytes(k))
flag = unpad(AES_decrypt(ciphertext))

HGAME-2026-WEEK2-CRYPTO

import sys
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
import hashlib
from base64 import b64decode

# ---------------------------------------------------------
# 配置区域：请在此处填入 FactorDB 查到的两个素数因子
# ---------------------------------------------------------
p1 = 282964522500710252996522860321128988886949295243765606602614844463493284542147924563568163094392590450939540920228998768405900675902689378522299357223754617695943
p2 = 511405127645157121220046316928395473344738559750412727565053675377154964183416414295066240070803421575018695355362581643466329860038567115911393279779768674224503

# ---------------------------------------------------------
# 辅助函数
# ---------------------------------------------------------
def log(msg):
    print(f"[+] {msg}")
    sys.stdout.flush()

def solve():
    # 1. 加载数据
    log("正在加载 data.sobj ...")
    try:
        objs = load('data.sobj')
        n = objs[0]
        a = objs[1]
        b = objs[2]
        log("数据加载成功！")
    except Exception as e:
        log(f"加载 data.sobj 失败: {e}")
        return

    # 验证因子
    if p1 * p2 != n:
        log("警告：p1 * p2 != n，请检查因子是否正确。")
    else:
        log("因子验证通过 (p1 * p2 == n)")

    # 2. 降维
    log("正在计算矩阵行列式...")
    val_a = a.determinant()
    val_b = b.determinant()

    # 3. 分步求解
    remainders = []
    moduli = []
    
    factors = [p1, p2]
    
    for i, p in enumerate(factors):
        log(f"正在子群 GF(p{i+1}) 中求解离散对数...")
        try:
            R = GF(p)
            g = R(val_a)
            h = R(val_b)
            
            # 计算离散对数
            k_part = discrete_log(h, g)
            
            # === 修正点 ===
            # 计算 g 的真实阶数，作为 CRT 的模数，而不是用 p-1
            log(f"  ->正在计算元素阶数 (multiplicative_order)...")
            order = g.multiplicative_order()
            
            log(f"  -> 得到部分解 k = {k_part} (mod {order})")
            
            remainders.append(k_part)
            moduli.append(order)
            
        except Exception as e:
            log(f"  -> 求解失败: {e}")
            return

    # 4. 合并结果 (CRT)
    log("正在利用中国剩余定理 (CRT) 恢复 k ...")
    try:
        final_k = crt(remainders, moduli)
        log(f"恢复出的 k: {final_k}")
    except Exception as e:
        log(f"CRT 合并失败: {e}")
        return

    # 5. 解密 Flag
    log("开始解密 AES ...")
    ct_b64 = "ieJNk5335o9lCy6Ar2XymrDy+HVHcQhikluNSra0kBafw1WDCyyuNPkLACeBsavy"
    ciphertext = b64decode(ct_b64)
    
    try:
        key = hashlib.md5(long_to_bytes(int(final_k))).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        
        decrypted_raw = cipher.decrypt(ciphertext)
        log(f"解密原始数据(Hex): {decrypted_raw.hex()}")
        
        flag = unpad(decrypted_raw, AES.block_size).decode()
        
        print("\n" + "="*50)
        print(f"FLAG: {flag}")
        print("="*50 + "\n")
        
    except Exception as e:
        log(f"解密或去填充失败: {e}")

if __name__ == '__main__':
    solve()

HGAME-2026-WEEK2-CRYPTO

‍

Decision

题目提供了一个 task.py 脚本和一个 output 数据文件。
通过分析源码 [1]，我们可以提取出以下关键信息：

加密参数：
- 维度 $n = 25$。
- 单次采样数 $m = 15$。
- 模数 $q \approx 2^{128}$（由源码注释给出具体的 128 bit 大素数）。
- 误差分布 $D$：离散高斯分布，标准差 $\sigma \approx 2^{16}$。
加密逻辑：
- 题目将 Flag 处理为二进制字符串 flagbin。
- Bit 1 (LWE 样本) ：生成 $m$ 个 LWE 样本 $(\vec{a}, b)$，满足 $b \equiv \langle \vec{a}, \vec{s} \rangle + e \pmod q$。
- Bit 0 (随机噪声) ：生成 $m$ 个完全随机的元组，不满足线性关系。
漏洞点：
- 参数缺陷：单组数据 $m=15 < n=25$，这是一个欠定方程组，无法直接求解。但是，如果我们将两组代表 1 的数据拼接，总样本数变为 $30 > 25$，方程组变得超定，使得恢复私钥成为可能。
- 密钥复用：代码中 lwe = LWE(n=n, q=q, D=D) 是在循环外初始化的 [1]。这意味着所有代表 Bit 1 的数据块都由同一个私钥 $\vec{s}$ 加密。

1. 攻击目标：恢复私钥 $\vec{s}$

由于所有为 1 的块共享私钥 $\vec{s}$，我们只需要找到任意两个比特为 1 的数据块，将它们组合成一个新的方程组，利用格基规约算法（LLL）即可还原出私钥。

2. 格构造 (Lattice Construction)

这是一个典型的 LWE 问题。由于模数 $q$ 非常大（$2^{128}$）而误差 $e$ 相对很小（$2^{16}$），这属于 LWE 的简单实例。我们可以构造 Kannans Embedding 格来解决。

我们需要寻找向量 $\vec{x}$ 使得 $\vec{x} \cdot B$ 很短。
构造格基矩阵 $B$（维度 $N = n + 2m + 1$ 或简化版）：

$$\begin{pmatrix}
I_n & A^T \\
0 & qI_{2m} \\
0 & -b^T
\end{pmatrix}$$

在这个格中，目标短向量包含了误差向量 $e$ 和私钥 $s$。通过 LLL 算法找到格中的最短向量（SVP），即可直接提取出 $\vec{s}$ 或 $\vec{e}$。

3. 绕过 Padding 陷阱

题目中 flagbin 使用了 .rjust(25 * 8, "0") 进行填充 [1]。这导致二进制串的开头部分全是 0（即全是随机噪声）。
如果直接取前两个块（Block 0 和 Block 1）进行攻击，由于它们是随机生成的，LLL 算法无法规约出有意义的结果。

策略：采用随机采样或滑动窗口的方式。随机选取两个索引 $i$ and $j$，假设它们都是 1 并尝试 LLL。由于 Flag 中 1 和 0 的分布相对均匀，尝试几次就能成功命中两个都是 1 的块，从而解出 $\vec{s}$。

4. 全量解密

一旦获得了私钥 $\vec{s}$，解密过程就变成了简单的验证：
对于每一个数据块，计算误差 $err = b – \langle \vec{a}, \vec{s} \rangle \pmod q$。

如果 $|err|$ 很小（例如 $< 2^{40}$），说明符合 LWE 关系，该位为 1。
如果 $|err|$ 很大（接近 $q/2$），说明是随机数，该位为 0。

from sage.all import *
from Crypto.Util.number import long_to_bytes
import random

# 1. 参数配置 (来源于 task.py)
n = 25
q = 256708627612544299823733222331047933697 # [1]

def recover_s(samples):
    """
    构造 Embedding Lattice 利用 LLL 恢复私钥
    """
    m_local = len(samples)
    A_list = [x[0] for x in samples]
    b_list = [x[1] for x in samples]
    
    # 构造矩阵求解 A*s + e = b + k*q
    # 我们寻找短向量 (e, 1) 并推导 s
    M = Matrix(ZZ, n + m_local + 1, m_local + 1)
    
    # [ A^T     ]
    # [ q * I_m ]
    # [ -b^T  1 ]
    
    for i in range(n):
        for j in range(m_local):
            M[i, j] = A_list[j][i]
    for i in range(m_local):
        M[n + i, i] = q
    for j in range(m_local):
        M[n + m_local, j] = -b_list[j] # 注意符号
    M[n + m_local, m_local] = 1
    
    # LLL 规约
    L = M.LLL()
    
    # 检查最短向量，寻找形如 (e_0, ..., e_m, 1) 的向量
    for row in L:
        if abs(row[-1]) == 1:
            e_vec = row[:-1]
            sign = row[-1]
            # 验证误差大小
            if max([abs(x) for x in e_vec]) < (1 << 40):
                # 找到误差 e，反解 s
                # A * s = b - e (mod q)
                target = vector(GF(q), [b - e*sign for b, e in zip(b_list, e_vec)])
                A_mat = Matrix(GF(q), A_list)
                try:
                    s = A_mat.solve_right(target)
                    return vector(ZZ, s)
                except:
                    continue
    return None

def main():
    # 读取数据
    with open("output", "r") as f:
        # 处理可能的格式问题
        raw = f.read().strip()
        if raw.startswith("b'"): 
            import ast
            cipher_data = ast.literal_eval(ast.literal_eval(raw))
        else:
            cipher_data = eval(raw)

    # 格式化数据
    formatted_data = []
    for block in cipher_data:
        block_samples = []
        for row in block:
            block_samples.append((vector(ZZ, row[:-1]), row[-1]))
        formatted_data.append(block_samples)

    print(f"[*] Total blocks: {len(formatted_data)}")
    secret_s = None

    # 2. 随机采样寻找私钥
    # 由于存在 padding 0，我们需要随机抽取直到找到两个都是 Bit 1 的块
    print("[*] Searching for secret key...")
    for _ in range(200):
        idx1, idx2 = random.sample(range(len(formatted_data)), 2)
        combined = formatted_data[idx1] + formatted_data[idx2]
        
        s = recover_s(combined)
        if s is not None:
            print(f"[+] Key found using blocks {idx1} and {idx2}")
            secret_s = s
            break
            
    if not secret_s:
        print("[-] Failed to find key.")
        return

    # 3. 解密全量数据
    flag_bits = ""
    for block in formatted_data:
        a, b = block[0] # 取每个块的第一个样本验证即可
        err = (b - a.dot_product(secret_s)) % q
        if err > q // 2: err -= q
        
        # 误差小 -> 1, 误差大 -> 0
        if abs(err) < (1 << 50):
            flag_bits += "1"
        else:
            flag_bits += "0"
            
    # 4. 还原 Flag
    # 根据 task.py，flagbin 是 int.from_bytes(..., 'little') 转换而来
    flag_int = int(flag_bits, 2)
    flag_bytes = long_to_bytes(flag_int)
    
    # 反转字节序 (Little Endian)
    final_flag = flag_bytes[::-1]
    print(f"[+] Flag: hgame{{{final_flag.decode()}}}")

if __name__ == "__main__":
    main()

这道题考察了对 LWE (Learning With Errors) 基础原理的理解以及利用 LLL 算法 解决格问题的能力。
核心突破口在于：

参数不安全：$m$ 虽小但可以组合。
实现不当：私钥 $\vec{s}$ 全局复用。
数据预处理：识别出 rjust 造成的全 0 填充，使用随机采样定位有效数据块。

HGAME-2026-WEEK2-CRYPTO

‍

eezzDLP

这是一个非常经典的基于 $n=p^2$ 模数下的矩阵离散对数问题 的题目。这类题目考察了选手对群论结构（特别是 P-adic 数/亨塞尔引理思想）以及中间相遇攻击（BSGS）的综合运用。

以下是一份详细的 Write-Up，旨在帮助你从原理上理解这道题的解法。

1. 题目分析

关键代码逻辑

根据 main.py [1]：

模数生成：n = p * p。模数 $n$ 不是传统的 $p \times q$，而是素数的平方。这是最大的弱点。
矩阵生成：a 是模 $n$ 下的一个随机矩阵。
加密过程：k 是一个 660 位的素数，计算 b = a^k mod n。
目标：已知 n, a, b，求解 k。

难点评估

DLP 难度：在一般的 $GL(2, \mathbb{Z}_n)$ 群上求解离散对数通常是困难的。
数据规模：$k$ 的长度（660 bits）大于 $p$ 的长度（实测约 612 bits）。这意味着仅仅在 $\mathbb{F}_p$ 域上求解是不够的，我们需要利用 $\mathbb{Z}_{p^2}$ 的完整结构。

2. 数学原理 (核心考点)

漏洞点 1：P-adic Lifting (模 $p^2$ 的特殊性质)

在模 $p^2$ 的环中，乘法群的结构可以被“降维打击”。

根据欧拉定理或群论性质，矩阵 $A$ 的阶通常是 $p(p-1)$ 的倍数（取决于特征方程）。关键在于，如果我们计算 $A^{p-1} \pmod{p^2}$，结果会落入一个特殊的子群。

定理：对于 $GL(2, \mathbb{Z}_{p^2})$ 中的矩阵 $A$（且 $\det(A) \not\equiv 0 \pmod p$），有：

$$A^{p-1} \equiv I + p \cdot \Delta_A \pmod{p^2}$$

其中 $I$ 是单位矩阵，$\Delta_A$ 是某个整数矩阵。

这个子群 $\{I + p\cdot \Delta\}$ 同构于模 $p$ 的加法群。这意味着在这个子群上的乘法运算变成了加法运算（对数映射）：

$$(I + p\Delta)^k \equiv I + p \cdot (k \cdot \Delta) \pmod{p^2}$$

利用方法：
我们已知 $A^k = B \pmod n$。
两边同时取 $p-1$ 次幂：

$$(A^{p-1})^k \equiv B^{p-1} \pmod{p^2}$$

代入上述性质：

$$I + p \cdot k \cdot \Delta_A \equiv I + p \cdot \Delta_B \pmod{p^2}$$

消去 $I$ 并除以 $p$：

$$k \cdot \Delta_A \equiv \Delta_B \pmod p$$

这就变成了一个简单的线性方程。我们可以直接算出 $k_p = k \pmod p$。

漏洞点 2：BSGS (针对高位的爆破)

通过上述方法，我们只能求出 $k \pmod p$。但是题目中 k (660 bits) > p (612 bits)。
这意味着真实的 $k$ 可以表示为：

$$k = k_p + m \cdot p$$

其中 $m$ 是未知的高位部分。

搜索空间：$k$ 比 $p$ 多大约 $660 – 612 = 48$ 位。所以 $m \in [0, 2^{48}]$。
方程变换：

$$A^{k_p + m \cdot p} = B \pmod n$$$$A^{m \cdot p} = B \cdot A^{-k_p} \pmod n$$

令 $Base = A^p$, $Target = B \cdot A^{-k_p}$，问题转化为：

$$(Base)^m = Target \pmod n$$
BSGS：对于 $2^{48}$ 的搜索空间，直接遍历太慢。使用 BSGS（小步大步法）可以将复杂度降至 $\sqrt{2^{48}} = 2^{24} \approx 1.6 \times 10^7$。这个计算量在现代 CPU 上只需要几秒到几分钟。

3. 解题步骤详解

Step 1: 预处理

读取 data.sobj。
利用 $n = p^2$，直接计算 p = isqrt(n)。

Step 2: 求解线性部分 ($k \pmod p$)

计算 $A’ = A^{p-1} \pmod{p^2}$ 和 $B’ = B^{p-1} \pmod{p^2}$。
计算 $\Delta_A = (A’ – I) / p$ 和 $\Delta_B = (B’ – I) / p$。
在 $\Delta_A$ 中找一个非零元素（例如位置 $[0,0]$），计算 $k_p = \Delta_B[0,0] \cdot (\Delta_A[0,0])^{-1} \pmod p$。
- 注意：如果 *$A^{p-1} \equiv I \pmod{p^2}$* ，则 $\Delta_A$ 为全 0，此时需要改用 $p(p-1)$ 或 $p^2-1$ 作为指数。

Step 3: BSGS 求解高位 ($m$)

设定目标：$Base^m = Target$。
Baby Steps：计算 $Base^0, Base^1, \dots, Base^{S}$ 并存入哈希表。
- 内存优化：为了防止内存爆炸，只存储矩阵特征值（如左上角元素的 Hash）和对应的指数 $j$。
Giant Steps：计算 $Target \cdot (Base^{-S})^i$，检查结果是否在哈希表中。
找到匹配后，恢复 $k = k_p + (i \cdot S + j) \cdot p$。

Step 4: 解密

利用恢复的 $k$ 计算 MD5 密钥，解密 AES 密文。

4. 最终payload

这是基于之前调试成功的最终版本代码，包含了内存优化和完整的注释。

from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
from base64 import b64decode
import time

def solve():
    print("[*] 正在加载数据...")
    # 加载题目给出的数据
    n, a, b = load("data.sobj")
    
    # 1. 分解模数 n = p^2
    p = isqrt(n)
    print(f"[*] p 的位数: {p.nbits()}")
    
    # 2. P-adic Lifting: 利用模 p^2 的加法群同构求解 k mod p
    print("[*] 正在求解 k mod p (Lifting)...")
    
    phi = p - 1
    # 计算 A^(p-1) = I + p*Delta_A
    # 这里的运算是在 Zmod(p^2) 下进行的
    A_pow = a ** phi
    B_pow = b ** phi
    
    # 转为整数矩阵进行差分计算
    I_int = Matrix.identity(ZZ, 2)
    A_int = Matrix(ZZ, [[Integer(x) for x in row] for row in A_pow])
    B_int = Matrix(ZZ, [[Integer(x) for x in row] for row in B_pow])
    
    Delta_A = A_int - I_int
    Delta_B = B_int - I_int
    
    # 提取系数矩阵 L = Delta / p (映射到 GF(p))
    L_A = Delta_A.apply_map(lambda x: x // p).change_ring(GF(p))
    L_B = Delta_B.apply_map(lambda x: x // p).change_ring(GF(p))
    
    # 求解 k_p * L_A = L_B
    k_p = None
    for r in range(2):
        for c in range(2):
            if L_A[r,c] != 0:
                k_p = Integer(L_B[r,c] / L_A[r,c])
                break
        if k_p is not None: break
        
    print(f"[*] k_p (low bits) = {k_p}")

    # 3. BSGS: 求解高位 m
    # k = k_p + m * p
    # A^(m*p) = B * A^(-k_p) => (A^p)^m = Target
    print("[*] 正在求解高位 m (BSGS)...")
    
    Base = a ** p
    Target = b * (a ** (-k_p))
    
    # 估算范围：k(660) - p(612) = 48 bits
    # 步长设为 2^25 (约3300万)
    limit = 1 << 25
    baby_steps = {}
    
    print("    [+] 构建 Baby Steps (Hash Map)...")
    curr = Matrix(Zmod(n), [[1,0],[0,1]])
    
    # 内存优化：只存矩阵左上角元素的低64位作为Key
    mask = (1 << 64) - 1
    
    for j in range(limit):
        key = int(curr[0,0]) & mask
        if key not in baby_steps:
            baby_steps[key] = j
        curr = curr * Base
        
    print("    [+] 开始 Giant Steps 搜索...")
    G = Base ** (-limit)
    curr_giant = Target
    found_m = None
    
    for i in range(limit + 1000):
        key = int(curr_giant[0,0]) & mask
        if key in baby_steps:
            j = baby_steps[key]
            candidate_m = i * limit + j
            
            # 碰撞检测：验证完整解
            temp_k = k_p + candidate_m * p
            if a ** temp_k == b:
                found_m = candidate_m
                print(f"    [!] 找到 m: {found_m}")
                break
        curr_giant = curr_giant * G
        
    if found_m is None:
        print("[!] BSGS 失败，需扩大搜索范围")
        return

    # 4. 解密
    k_final = k_p + found_m * p
    print(f"[*] 最终私钥 k: {k_final}")
    
    ct_b64 = "Q3UBa1pz1fi35L94peaFbPvpQe4UyXOUif3CKS/CmZdXOiV7bA5NNNjJ1KeUiAFE"
    key = hashlib.md5(long_to_bytes(int(k_final))).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    flag = cipher.decrypt(b64decode(ct_b64))
    
    print(f"[*] FLAG: {flag.decode(errors='ignore').strip()}")

if __name__ == '__main__':
    solve()

5. 总结

这道题是学习 DLP 变种问题的绝佳案例。

遇到 $n=p^2$：第一时间想到 Paillier 密码系统或 P-adic Lifting，利用 $1+p\mathbb{Z}_{p^2}$ 同构于加法群的性质。
遇到 $k > p$：第一时间想到先求模 $p$（或模阶数）的解，再利用 BSGS 或 Pohlig-Hellman 恢复剩余的高位。
工程优化：在处理大规模 BSGS 时，必须注意内存管理，使用哈希截断来存储状态是 CTF 中常用的技巧。

HGAME-2026-WEEK2-CRYPTO

‍

EZRSA

题目信息

题目名称: ezRSA
题目类型: Crypto (RSA)
关键词: RSA Oracle, Parity Oracle Attack, Bit-flipping

题目分析

1. 源码逻辑

服务端提供了一个 RSA 交互环境，使用了 Python 的 socketserver。
主要参数生成：

p, q: 512 位素数
n: 1024 位模数 ($n = p \times q$)
e: 50 位的随机整数 (较小，但未知)
d: 私钥指数

提供的菜单选项：

Encrypt: 输入明文 m 和位移 x，计算 $c \equiv m^{e \oplus 2^x} \pmod n$。输出 base64 编码的密文。如果 safe=False，输出会经过 disguise 混淆。
Decrypt: 输入密文 c，计算 $m \equiv c^d \pmod n$。输出 base64 编码的明文 (bytes)。如果 safe=False，输出会经过 disguise 混淆。
Get flag: 计算 $c_{flag} \equiv \text{flag}^e \pmod n$，并将 safe 标记设为 False。

2. 漏洞点

N 和 e 未知，但可恢复：
- 利用解密 Oracle 的乘法同态性质可以恢复模数 N。
- 利用加密 Oracle 的异或特性 ($e \oplus 2^x$) 配合解密 Oracle，可以逐位恢复 e。
混淆函数 disguise 的缺陷：
当 safe=False (即获取 Flag 后) 时，解密结果会被混淆。混淆代码如下：
```
def disguise(self, msg):
    res = bytearray(msg)
    mask = os.urandom(1)
    # 正向异或
    for i in range(len(res)):
        res[i] = res[i] ^ int.from_bytes(mask)
    # 反向异或
    for i in range(len(msg) - 1, -1, -1):
        res[i] = res[i] ^ int.from_bytes(mask)
        mask = os.urandom(1) # mask 在这里更新了
    return bytes(res)
```
仔细观察最后一个字节 res[L-1] (其中 $L$ 是长度)。
- 正向遍历：res[L-1] ^= mask_1
- 反向遍历：从 L-1 开始。第一次循环时 i = L-1，此时 mask 还没有更新 (仍是 mask_1)。
- 所以：res[L-1] ^= mask_1
- 最终结果：res[L-1] = original[L-1] ^ mask_1 ^ mask_1 = original[L-1]。
结论：混淆后的字节流，最后一个字节其实没有变。这意味着我们依然拥有一个 LSB Oracle (最低有效位/奇偶性预言机) 。

解题思路

第一步：恢复模数 $N$

RSA 的解密操作满足乘法同态性：$Dec(c_1 \cdot c_2) \equiv Dec(c_1) \cdot Dec(c_2) \pmod n$。
我们在不知道 $N$ 的情况下，可以构造：

选取随机密文 $c_1, c_2$。
获取 $m_1 = Dec(c_1)$，$m_2 = Dec(c_2)$。
获取 $m_3 = Dec(c_1 \cdot c_2)$ (注意这里是整数乘法)。
在模 $N$ 意义下，$m_1 \cdot m_2 \equiv m_3 \pmod n$。
因此 $N$ 必然整除 $m_1 m_2 – m_3$。可以通过多次尝试取最大公约数 (GCD) 来恢复 $N$。

第二步：恢复公钥指数 $e$

题目允许计算 $Enc_x(m) = m^{e \oplus 2^x} \pmod n$。我们需要确定 $e$ 的每一位 $e_x$。
利用恒等式 $e \oplus 2^x = e + (1 – 2e_x)2^x$ (即如果第 $x$ 位是 0，则是加；如果是 1，则是减)。

对于选定的底数 $m$：

计算测试值 $t_x = Dec(m^{2^x} \pmod n) \equiv m^{2^x \cdot d} \pmod n$。
调用加密 oracle 获取 $C = m^{e \oplus 2^x} \pmod n$。
调用解密 oracle 获取 $P = Dec(C) \equiv m^{(e \oplus 2^x) \cdot d} \pmod n$。
计算 $R = P \cdot m^{-1} \pmod n$。

判断逻辑：

如果 $e$ 的第 $x$ 位是 0：
$e \oplus 2^x = e + 2^x$
$P \equiv m^{(e + 2^x)d} \equiv m^{ed} \cdot m^{2^x d} \equiv m \cdot t_x \pmod n$。
此时 $R \equiv t_x \pmod n$。
如果 $e$ 的第 $x$ 位是 1：
$e \oplus 2^x = e – 2^x$
$P \equiv m^{(e – 2^x)d} \equiv m^{ed} \cdot m^{-2^x d} \equiv m \cdot t_x^{-1} \pmod n$。
此时 $R \equiv t_x^{-1} \pmod n$。

遍历 $x = 0$ 到 49，即可完全恢复 $e$。

第三步：LSB Oracle 攻击 (Parity Oracle)

拥有了 $N, e$ 和 Flag 的密文 $C_{flag}$，且虽然解密接口在获取 Flag 后受到了混淆，但我们已经知道最后一个字节是准确的。
这等价于我们要判定任意密文对应的明文是奇数还是偶数。

经典的 RSA LSB Oracle 攻击（二分法）：
设明文为 $M$，密文为 $C$。区间 $[L, H) = [0, N)$。

令 $C’ = C \cdot 2^e \pmod n$。这对应于明文 $M’ = 2M \pmod n$。
解密 $C’$ 并查看最后一个字节的奇偶性。
- 如果 $2M \pmod n$ 是偶数，说明 $2M < N$（没有发生取模溢出），则 $M < N/2$，区间变为 $[L, \frac{L+H}{2})$。
- 如果 $2M \pmod n$ 是奇数，说明 $2M > N$（发生了取模，变成了 $2M – N$，因为 $N$ 是两个大素数乘积，总是奇数，偶减奇=奇），则 $M > N/2$，区间变为 $[\frac{L+H}{2}, H)$。
重复 $1024$ 次 (即 $N$ 的位数)，最终区间收敛于 $M$。

攻击脚本核心代码片段

def parity_oracle_attack(sock, n, e, c):
    # 乘数：加密后的 2
    two_e = pow(2, e, n)
    
    # 初始区间
    lo, hi = 0, n
    cur = c
    
    # 循环次数等于模数比特长度
    for i in range(n.bit_length()):
        # 密文乘 2^e -> 明文乘 2
        cur = (cur * two_e) % n
        
        # 解密 (虽然有混淆，但取最后字节)
        pt = menu_decrypt_raw(sock, cur)
        last_byte = pt[-1]
        parity = last_byte & 1 # 获取 LSB
        
        mid = (lo + hi) // 2
        if parity == 0:
            hi = mid # Lower half
        else:
            lo = mid # Upper half
            
    return hi

总结

这就完成了一道典型的 RSA 综合利用题目：从信息泄露 (Oracle) 恢复参数，到发现混淆算法的缺陷，最后利用 LSB Oracle 进行全明文恢复。

import base64
import math
import random
import socket
import sys
import time
import binascii

HOST = "1.116.118.188"
PORT = 30496
TIMEOUT = 10


def dbg(msg):
    ts = time.strftime("%H:%M:%S")
    print(f"[{ts}] {msg}", flush=True)


def recv_until(sock, marker=b"> "):
    data = b""
    while marker not in data:
        try:
            chunk = sock.recv(4096)
            if not chunk:
                break
            data += chunk
        except socket.timeout:
            break
    return data


def extract_b64(data):
    # Try to find a line that is valid base64 and looks like our payload
    # Payloads are base64 encoded long_to_bytes, so they can be any length.
    # Usually they are the last line before the menu.
    lines = [ln.strip() for ln in data.splitlines() if ln.strip()]
    
    # Iterate backwards, skip the menu line if captured
    for ln in reversed(lines):
        if b"Your choice" in ln:
            continue
        if b"1. Encrypt" in ln:
            continue
        # Heuristic: base64 lines usually don't have spaces (unless very short and accidentally matching words)
        if b" " in ln:
            continue
        
        # Try to decode
        try:
            # Validate=True to ensure strictly base64
            decoded = base64.b64decode(ln, validate=True)
            if len(decoded) > 0:
                return ln
        except Exception:
            continue
    return b""


def recv_b64_payload(sock):
    data = recv_until(sock, b"> ")
    b64 = extract_b64(data)
    if not b64:
        dbg("DEBUG: Failed to parse base64. Received data:")
        dbg(data.decode(errors='replace'))
        return None 
        # Don't raise immediately, let caller handle or return empty
    return b64


def b64_to_int(s):
    if not s:
        return 0
    b = base64.b64decode(s.strip())
    return int.from_bytes(b, "big")


def menu_encrypt(sock, m, x):
    # Clear buffer
    # recv_until(sock) # Assuming previous call consumed prompt
    
    sendline(sock, 1)
    recv_until(sock, b"plaintext")
    sendline(sock, m)
    recv_until(sock, b"flip")
    sendline(sock, x)
    
    out = recv_b64_payload(sock)
    if not out:
        raise RuntimeError("Encrypt failed to get response")
    return b64_to_int(out)


def menu_decrypt_raw(sock, c):
    # recv_until(sock)
    sendline(sock, 2)
    recv_until(sock, b"ciphertext")
    sendline(sock, c)
    
    out = recv_b64_payload(sock)
    if not out:
         # Retry or fail?
         # If disguise mode is active, maybe we got nothing? No, disguise returns bytes.
         raise RuntimeError("Decrypt failed to get response")
    return base64.b64decode(out)


def menu_get_flag(sock):
    # recv_until(sock)
    sendline(sock, 3)
    out = recv_b64_payload(sock)
    if not out:
        raise RuntimeError("Get flag failed")
    return b64_to_int(out)


def sendline(sock, s):
    sock.sendall((str(s) + "\n").encode())


def bytes_to_int(b):
    return int.from_bytes(b, "big")


def recover_n(sock, rounds=6):
    g = 0
    # Ensure we are at menu
    recv_until(sock, b"> ")
    
    for i in range(rounds):
        c1 = random.getrandbits(512) | 1
        c2 = random.getrandbits(512) | 1
        
        m1 = bytes_to_int(menu_decrypt_raw(sock, c1))
        m2 = bytes_to_int(menu_decrypt_raw(sock, c2))
        m3 = bytes_to_int(menu_decrypt_raw(sock, c1 * c2))
        
        v = m1 * m2 - m3
        g = abs(v) if g == 0 else math.gcd(g, abs(v))
        if g > 1 and i > 2:
             # Check if g behaves like N (composite) 
             # For this task, just trust after a few rounds
             pass
        dbg(f"n gcd round {i+1}/{rounds}, current gcd bits: {g.bit_length()}")
        
    return g


def recover_e(sock, n, bits=50):
    while True:
        m = random.randrange(2, n - 1)
        if math.gcd(m, n) == 1:
            break
    
    dbg("Using chosen plaintext for E recovery")
    
    e = 0
    for x in range(bits):
        # 1. Oracle for m^(d*2^x)
        c_tx = pow(m, 1 << x, n)
        # We need to call decrypt. 
        # The menu loop: we just finished a command, so we are at menu logic usually.
        # But menu_decrypt_raw handles sending '2'.
        t_x = bytes_to_int(menu_decrypt_raw(sock, c_tx))

        # 2. Get Dec(Enc_x(m))
        c = menu_encrypt(sock, m, x)
        p = bytes_to_int(menu_decrypt_raw(sock, c))
        
        inv_m = pow(m, -1, n)
        r = (p * inv_m) % n

        if r == t_x:
            bit = 0
        else:
            # Verify bit 1
            inv_tx = pow(t_x, -1, n)
            if r == inv_tx:
                bit = 1
            else:
                dbg(f"Error at bit {x}: r matches neither t_x nor t_x^-1")
                # Fallback or retry? 
                # might be because t_x is 0? unlikley
                # Assume bit 0 if close? No.
                raise RuntimeError("Bit recovery failed")
        
        e |= (bit << x)
        if x % 10 == 0:
            dbg(f"Recovered {x} bits of e...")
            
    return e


def pkcs7_unpad(data, block=127):
    if not data:
        return data
    pad_val = data[-1]
    if pad_val == 0 or pad_val > block:
        # Maybe not padded or incorrect?
        return data
    # Verify
    if data[-pad_val:] == bytes([pad_val]) * pad_val:
        return data[:-pad_val]
    return data


def parity_oracle_attack(sock, n, e, c):
    nbits = n.bit_length()
    dbg(f"Starting parity oracle attack (modulus {nbits} bits)")
    
    # We need to maintain the running ciphertext
    # C_0 = C_flag
    # C_{i+1} = C_i * (2^e) mod n => Dec(C_{i+1}) = 2 * Dec(C_i) mod n
    
    two_e = pow(2, e, n)
    
    # Interval [L, H)
    L = 0
    H = n
    
    cur_c = c
    
    for i in range(nbits):
        # Update ciphertext
        cur_c = (cur_c * two_e) % n
        
        # Get LSB
        pt_bytes = menu_decrypt_raw(sock, cur_c)
        
        # Last byte is preserved by disguise()
        # "res[i] = res[i] ^ int.from_bytes(mask)" -> for last byte:
        # Forward: xor with m1.
        # Backward: begins at len-1. xor with m1. mask updates.
        # So last byte is xor m1 xor m1 = original.
        
        if not pt_bytes:
             # If empty, treat as 0? 
             lsb = 0
        else:
             lsb = pt_bytes[-1] & 1
             
        mid = (L + H) // 2
        
        if lsb == 0:
            # even => 2m < n => m < n/2 => lower half
            H = mid
        else:
            # odd => 2m > n => m > n/2 => upper half
            L = mid
            
        if i % 20 == 0:
            dbg(f"Step {i}/{nbits} | Range size: {(H-L).bit_length()} bits")
            
    return H


def main():
    dbg(f"Connecting to {HOST}:{PORT}")
    try:
        s = socket.create_connection((HOST, PORT), timeout=TIMEOUT)
    except Exception as e:
        dbg(f"Connection failed: {e}")
        return

    try:
        dbg("--- Phase 1: Recover N ---")
        n = recover_n(s)
        dbg(f"Recovered N ({n.bit_length()} bits)")
        
        dbg("--- Phase 2: Recover E ---")
        e = recover_e(s, n)
        dbg(f"Recovered E: {e}")
        
        dbg("--- Phase 3: Get Flag Ciphertext ---")
        c_flag = menu_get_flag(s)
        dbg(f"Flag Ciphertext: {c_flag}")
        
        dbg("--- Phase 4: Parity Oracle ---")
        m_int = parity_oracle_attack(s, n, e, c_flag)
        
        m_bytes = m_int.to_bytes((m_int.bit_length() + 7) // 8, "big")
        dbg(f"Decrypted int: {m_int}")
        dbg(f"Decrypted bytes (raw): {m_bytes}")
        
        flag = pkcs7_unpad(m_bytes, 127)
        print(f"\nFLAG: {flag.decode(errors='ignore')}\n")
        
    except Exception as e:
        dbg(f"Error during exploit: {e}")
        import traceback
        traceback.print_exc()
    finally:
        s.close()

if __name__ == "__main__":
    try:
        main()
    except KeyboardInterrupt:
        print("\nInterrupted.")

HGAME-2026-WEEK2-CRYPTO

‍

HGAME-2026-WEEK2-CRYPTO

WEEK2-CRYPTO

ezDLP

1. 题目分析

2. 数学原理

3. 解题步骤

步骤一：分解模数 n

步骤二：利用 CRT 分步求解

步骤三：解密

Decision

1. 攻击目标：恢复私钥 $\vec{s}$

2. 格构造 (Lattice Construction)

3. 绕过 Padding 陷阱

4. 全量解密

eezzDLP

1. 题目分析

关键代码逻辑

难点评估

2. 数学原理 (核心考点)

漏洞点 1：P-adic Lifting (模 $p^2$ 的特殊性质)

漏洞点 2：BSGS (针对高位的爆破)

3. 解题步骤详解

Step 1: 预处理

Step 2: 求解线性部分 ($k \pmod p$)

Step 3: BSGS 求解高位 ($m$)

Step 4: 解密

4. 最终payload

5. 总结

EZRSA

题目信息

题目分析

1. 源码逻辑

2. 漏洞点

解题思路

第一步：恢复模数 $N$

第二步：恢复公钥指数 $e$

第三步：LSB Oracle 攻击 (Parity Oracle)

攻击脚本核心代码片段

总结

近期文章

近期评论