Skip to content

prompt.md

Latest commit

 

History

History
468 lines (321 loc) · 9.08 KB

prompt.md

File metadata and controls

468 lines (321 loc) · 9.08 KB
Raw

CTF 密码学自动求解 SKILL

一个为 Claude Code、Codex 等 AI IDE 设计的密码学问题求解知识库

🎯 工作流程

Phase 1: 系统分析

  • 读取所有密码学源代码
  • 识别加密算法、密钥生成、参数
  • 绘制加密流程图
  • 输出系统分析报告

Phase 2: 漏洞识别

  • 分析数学结构寻找理论漏洞
  • 检查实现缺陷
  • 识别攻击面
  • PAUSE - 等待用户反馈

Phase 3: 攻击策略

  • 结合用户输入的分析
  • 综合理论与实践
  • 制定具体攻击计划
  • PAUSE - 等待用户确认

Phase 4: 代码实现

  • 生成 Python/SageMath 代码
  • 进行验证测试
  • 执行攻击获取 Flag

Phase 5: 文档生成

  • 输出完整 analyse.md
  • 包含数学推导和代码

🔒 RSA 攻击决策表

症状识别

观察到的特征 攻击方法 关键工具
e = 3 或 e 很小，单次加密 低加密指数攻击 gmpy2.iroot(c, e)
e = 3，同一消息加密 k 次 Håstad's 广播攻击 CRT + iroot
多个 (n, e) 对，共享因子 公共模数攻击 gcd(n1, n2)
e 异常大，d 可能很小 Wiener 攻击 连分数展开
泄漏 d 的部分比特位 部分密钥泄漏 Coppersmith 方法
已知 p 的高位或低位 部分素数恢复 small_roots()
p 和 q 接近 Fermat 分解 isqrt((n + sqrt(n))/2)
phi(n) 泄漏或部分已知 直接分解 解 n - phi + 1 = p + q
提供加密 Oracle 选择密文攻击 构造 c' = c * r^e mod n
n 的因子数 > 2 逐个分解小因子 Pollard's rho, ECM

实施步骤

低加密指数攻击 (e=3):

from gmpy2 import iroot

# c = m^3 mod n
# 当 m^3 < n 时，m^3 不需要 mod
m = int(iroot(c, 3)[0])

Fermat 分解:

def fermat_factorization(n, max_iter=100000):
    x = isqrt(n)
    x += 1
    y2 = x^2 - n

    for _ in range(max_iter):
        y = isqrt(y2)
        if y^2 == y2:
            p = x - y
            q = x + y
            if p * q == n:
                return (p, q)
        x += 1
        y2 = x^2 - n
    return None

GCD 公共因子分解:

import math

gcd_result = math.gcd(n1, n2)
if gcd_result > 1:
    p = gcd_result
    q = n1 // p

🔐 椭圆曲线 (ECC) 攻击

症状识别

漏洞类型 攻击方法 特征
曲线阶包含小因子 Pohlig-Hellman 阶分解后有小素因子
奇异曲线 Smart 攻击 j_invariant 特殊
Invalid Curve Attack 点不在曲线上 计算仍继续
Twist 安全性问题 Twist 攻击 Twist 曲线阶很小

实施代码

Pohlig-Hellman 离散对数:

def pohlig_hellman(P, Q, order, factor_dict):
    """
    利用小因子快速求离散对数

    factor_dict: {素因子: 个数}
    """
    crt_equations = []

    for p, e in factor_dict.items():
        # 在子群中求解
        p_e = p^e

        P_sub = (order // p_e) * P
        Q_sub = (order // p_e) * Q

        # 离散对数求解（小规模）
        for i in range(p_e):
            if i * P_sub == Q_sub:
                crt_equations.append((i, p_e))
                break

    # 中国剩余定理合并
    return crt(crt_equations)

🧮 格密码攻击

LWE/NTRU 问题

格约简 (Lattice Reduction):

# 构造格
M = Matrix(ZZ, basis)  # basis 是格基

# LLL 约简
M_reduced = M.LLL()

# BKZ 约简（更强）
M_reduced = M.BKZ()

# 最短向量通常对应解
shortest_vector = M_reduced[0]

背包密码系统

低密度格攻击:

# 构造背包问题的格表示
# [1  0  0  ... a_1]
# [0  1  0  ... a_2]
# [0  0  1  ... a_3]
# [..............]
# [0  0  0  ... S]

# 其中 S = sum(a_i * x_i)，x_i ∈ {0,1}

# 使用 LLL 求最短向量

🔑 格 (Lattice) 四大问题

  1. SVP (最短向量问题)

    • 在格中找到最短的非零向量
    • NP 困难

  2. CVP (最近向量问题)

    • 给定格和目标点，找最近的格点
    • NP 困难

  3. SIVP (连续最短向量问题)

    • 找到 n 个线性独立的短向量

  4. LWE (格上学习问题)

    • 给定 $(a_i, \langle a_i, s \rangle + e_i)$
    • 恢复隐藏秘密 $s$

🎨 对称加密模式攻击

ECB 模式

  • 漏洞: 相同明文块 → 相同密文块
  • 攻击: 模式分析、字典攻击
  • 检测: ciphertext[0:16] == ciphertext[16:32]

CBC 比特翻转

  • 漏洞: 修改 $C_{i-1}$ 影响 $P_i$ 的对应比特
  • 利用: 
    m'_i = D(C'_{i-1} ⊕ C_i) = C'_{i-1} ⊕ C_i ⊕ P_i

CBC Padding Oracle

  • 漏洞: 返回不同的错误信息透露填充正确性
  • 利用: 逐字节恢复明文

CTR/GCM Nonce 重用

  • 漏洞: 密钥流重用
  • 利用: 
    C_1 ⊕ C_2 = M_1 ⊕ M_2

📝 通用分析清单

使用此清单确保完整分析：

  • 加密流程清晰: 能画出 [plaintext] → [operations] → [ciphertext] 流程
  • 参数来源明确: 所有公开参数生成方式理解
  • 数据格式确认: 密文是字节串、整数、还是其他
  • Oracle/约束: 清楚所有输入输出和限制
  • 特殊条件: "只能询问 100 次" 等隐式约束

🛠 SageMath 必需库

基础导入

# 整数分解和素性测试
from sage.all import *
from sage.misc.all import *

# 格论应用
from sage.matrix.all import *
from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF

# 数论
from sympy import factorint, divisors

关键函数

操作 代码
质因数分解 factor(n) 或 factorint(n)
离散对数 discrete_log(Q, P)
最短向量 Matrix(basis).LLL()[0]
模逆 pow(a, -1, n) 或 inverse_mod(a, n)
中国剩余定理 crt_list([a1,a2,...], [m1,m2,...])
平方根 sqrt(x) 或 tonelli_shanks(a, p)
椭圆曲线离散对数 E.discrete_log(Q, P)

🚀 执行指令

Claude Code 中使用

分析系统:

/skill analyze-crypto secret.py

生成攻击:

/skill generate-attack "common-modulus"
/skill generate-attack "low-exponent"
/skill generate-attack "wiener-attack"

执行 SageMath:

/skill run-sage
# 输入或粘贴 SageMath 代码
# 按 Ctrl+D 执行

一键求解:

/skill solve-challenge challenge.py output.txt

📊 输出标准

analyse.md 结构

# [题目名称] 题解分析

## A. 问题结构

### 加密系统构造

...

### Flag 加密过程

...

### 给定条件

...

---

## B. 求解思路

### 核心漏洞

$$
\text{数学公式}
$$

### 攻击路径

1. **步骤 1**: ...
   $$
   \text{推导公式}
   $$

---

## C. 解题代码

### 完整 Exploit

\`\`\`python

# exploit.py

... 代码 ...
\`\`\`

**执行方式**:
\`\`\`bash
python exploit.py
\`\`\`

**结果**:
\`\`\`
Flag: flag{...}
\`\`\`

---

## D. 总结反思

...

⏱ 时间约束

  • 快速测试 (< 5min): 直接执行
  • 长时间计算 (> 5min):
    1. 估计运行时间
    2. 通知用户
    3. 等待用户批准
    4. 显示进度

🔧 故障排除

问题: "模块不存在"

解决:

# WSL 中安装
wsl sudo apt install python3-pip
wsl pip3 install gmpy2 sympy pwntools
wsl python3 -c "import gmpy2; print('OK')"

问题: "Sage 命令未找到"

解决:

# WSL 中验证 sage
wsl which sage
wsl sage --version

# 或指定完整路径
wsl /usr/bin/sage

问题: "超时错误"

解决:

  • 减少迭代次数
  • 使用更快的算法
  • 或增加超时时间

📚 参考资源

教科书

  • Handbook of Elliptic and Hyperelliptic Curve Cryptography
  • Understanding Cryptography by Paar & Pelzl
  • A Course in Number Theory and Cryptography by Koblitz

工具

CTF 参考

✅ 检查清单 (求解前必读)

在开始求解前，确保满足以下条件：

  • 读取所有密码学源代码
  • 理解加密算法和参数
  • 绘制加密流程图
  • 识别出至少一个可利用的漏洞
  • 有具体的攻击计划
  • 所有 SageMath 依赖已安装
  • 准备好处理超过 5 分钟的计算
  • 能够解释所有数学步骤

版本: 1.0.0
最后更新: 2026-02-06
维护者: Crypto-Solver-Team