逆向工程实战手册 第 34 章

第 34 章 密码学深度逆向（RSA / 椭圆曲线 / 格）

第 9 章讲"识别算法、找 key、解简单 DIY 加密"；本章讲真密码学对抗：RSA 变体、椭圆曲线、格攻击、非对称加密在 CTF 和实战中的逆向问题。核心是数学攻击面，不是代码。

📍 知识点地图 | 主题：密码学深度 | 前置：第9章 | 后续：第56章 | 核心概念：RSA攻击、ECC、格攻击、RNG缺陷

34.1 密码学逆向的分类（按攻击面）

对称加密（第 9 章已覆盖）: key 在程序里 → 找 key / 暴力 / 已知明文
非对称加密（本章）: 公钥可得到 → 找数学弱点
协议错误用法: 算法对但用法错（重放/选择密文/密钥复用）→ 协议层攻击
随机数缺陷: 种子可预测 / 重放 → 预测密钥

34.2 RSA 攻击面（CTF 与实战最密集）

公钥从哪来

程序里: 硬编码公钥（.rodata/PEM/数组）
证书: 从流量/服务器拿
逆向任务: 找公钥参数（n, e）→ 评估数学弱点

RSA 常见弱点速查表

弱点 识别 攻击工具
小 e + 小消息 e=3，m^e < n 低指数攻击（直接开立方）
相同 n 多消息 两密文同 n 共模攻击
小 d / 大 e e 很大 Wiener 攻击（连分数）
小素数因子 n 有小数因子 Fermat / Pollard p-1 / YAFU
已知 p/q 部分 因子部分泄露 Coppersmith
相近素数 p≈q Fermat 分解
多密文 Hastad 同 e 多 n Hastad 广播攻击
明文线性相关 已知部分明文 Franklin-Reiter
伪造签名 验签逻辑缺陷 攻击验签实现 
# RsaCtfTool 自动尝试全部攻击
RsaCtfTool --publickey pub.pem --uncipherfile cipher.txt
RsaCtfTool --publickey pub.pem --private   # 直接出私钥

# 大整数分解
yafu factor(n)
# 或 Sage: factor(n)

RSA 逆向的三种形态

1. 程序自带 RSA 验签 → 找 n/e → 数学攻击或伪造
2. 程序生成 RSA key → 找随机数源 → 预测（弱 RNG）
3. 程序实现自写 RSA → 实现 bug（非标准运算）→ 逆向找 bug

34.3 椭圆曲线（ECC）基础逆向

认识特征

识别: 曲线参数 a/b/p + 基点 G + 阶 n（常硬编码在大数数组）
库特征: OpenSSL EC_* / 自定义实现
常见曲线: secp256k1（比特币）、NIST P-256、Curve25519

ECC 攻击面

攻击 条件 方法
小阶点 曲线阶含小因子 降阶攻击（Pohlig-Hellman）
奇异曲线 a/b 导致奇异 转加法群攻击
Smart 攻击 特定曲线 异常曲线攻击
无效曲线 验签不校验点在曲线上 注入无效点
私钥泄露（部分） 侧信道/故障 恢复私钥
复用随机数 k 两个签名同 k 直接解出私钥

ECC 参数识别与攻击工具

# Sage 是 ECC 逆向首选（全套数学工具）
# 识别曲线参数 → 建曲线 → 检测弱点
# 小阶点: E.order() 分解 → 有小子群 → Pohlig-Hellman
# 工具: Sage / ECDSA 专用脚本 / RsaCtfTool 的 ecdsa 支持

34.4 格攻击（Lattice）——进阶必学

什么是格

格 = 向量空间的离散子集。许多密码问题可转化为"最近向量/最短向量"问题
（CVP/SVP），用 LLL 算法（格基约减）高效求解。

典型格攻击场景

场景 问题形式 解法
已知 MSB/LSB 部分明文 Coppersmith 构造格 → LLL
小秘密（HNP） 隐藏数问题 构造格 → LLL
背包密码 子集和问题 格攻击
约束整数验证 M*x = v (mod 2^32) CVP/LLL 
# Sage 的 LLL 是标准工具
from sage.all import *
# 构造格矩阵 B → B.LLL() → 还原小向量 → 解出秘密
# 库: fpylll（Python）

逆向中的触发信号

□ 验证逻辑是"大数线性约束"（CTF 常见: 输入满足 M*x = v mod N）
□ 密码系统参数看起来"太小"（秘密空间小 → 可格攻击）
□ 消息有可预测结构（前缀/格式约束）

34.5 随机数与协议错误（实战更常见）

□ 随机数弱: rand() 种子可预测 → 重放攻击
□ nonce 复用: 两个 ECDSA 签名同 k → 私钥直接解出
□ padding 错误: PKCS#1 填充预言机 → Bleichenbacher 攻击
□ CBC 填充预言: 可解密任意密文
□ 时序侧信道: 私钥运算时间泄露
逆向要点: 找 RNG 种子来源/初始化时机 → 复现序列

34.6 密码学逆向工作流（架构）

1. 识别密码系统: 库调用/特征常量/大数数组（第 9 章识别法）
2. 提取参数: 模数/曲线/公钥/密文（从 .rodata/内存/网络）
3. 分类攻击面: 数学弱点 / 实现 bug / 协议错误 / RNG 缺陷
4. 选择攻击: 查表（34.2/34.3）→ 工具（RsaCtfTool/Sage/yafu）
5. 验证: 用解出的 key/明文 → 程序/网络接受

34.7 决策树

拿到加密相关的程序逻辑
├─ 对称加密 → 找 key（第 9 章）
├─ RSA → 提取 n/e → 弱点表查攻击 → RsaCtfTool/Sage
├─ ECC → 提取曲线参数 → 弱点检测 → Sage
├─ 大数线性约束 → 格攻击（LLL）
├─ 签名 → 检查验签实现/RNG 复用
└─ 协议层 → 重放/填充预言/选择密文

动手练习

  1. 用 RsaCtfTool 对一组已知弱 RSA 参数（网上有练习集）逐一跑攻击，看懂每种攻击的触发条件。
  2. 在 Sage 里构造一个 ECC 小阶点攻击：选一条含小子群的曲线，用 Pohlig-Hellman 恢复私钥。
  3. 用 Sage 的 LLL 解一道 CVP/背包类题目，体会格的构造过程。
  4. 逆向一个"随机数可预测"的程序：找到种子来源，预测下一次输出。

深入阅读

  • 仓库：skills/reverse-engineering/crypto-decode-tools.md（RsaCtfTool 等工具用法）
  • 仓库：skills/reverse-engineering/patterns-ctf-2.md（CVP/LLL 格攻击案例）
  • 仓库：skills/reverse-engineering/patterns*.md（S-Box/keystream/字节-at-a-time 等对称侧）
  • 仓库：CTF-Sandbox-Orchestrator/competition-crypto-mobile/（密码学 CTF 子技能）
  • 教材推荐：Cryptopals（第 21 章）、《The LLL Algorithm》