技能介绍

面对的密码分析难题

在 CTF 与实际密码分析中，许多非对称密码算法的弱点最终都会归结为格上的数学问题。例如 RSA 的小私钥或小根攻击、DSA/ECDSA 的随机数（nonce）偏差泄露，以及 NTRU 的密钥恢复。然而，从密码学等式到可计算的格基构建，中间存在巨大的工程鸿沟。基础模型在面对这些问题时，常因攻击格维度设置错误、缺少合理的缩放因子，或错误计算 Coppersmith 方法的边界而导致攻击失败。本技能专为填补这一鸿沟而生，提供经过验证的格攻击实战手册。

核心攻击工作流

技能通过清晰的决策树和参数指南，将复杂的数学攻击转化为标准化的操作步骤：

问题路由与技术选型：根据目标算法快速匹配最佳格技术。例如，RSA 小根对应 Coppersmith，小私钥 d 对应 Boneh-Durfee，随机数偏差则转化为 CVP（最近向量问题）。
攻击格构建：详细指导如何构造格基，包括维度选择指南（如 HNP 需 n+2 维）以及使用嵌入技术（Embedding）将 CVP 转化为更易求解的 SVP（最短向量问题）。
归约与参数调优：推荐先用 LLL 算法进行多项式时间的快速归约；若解不够短，则逐步提升 BKZ 的块大小（CTF 中通常 20-40 即可）。同时提供 Coppersmith 中 beta 和 epsilon 等关键参数的调优策略。

适用边界与常见陷阱

格攻击并非银弹，其成功高度依赖于输入条件的严格满足。在实际应用中需特别注意以下陷阱：

边界与维度：若 Coppersmith 的根边界 X 过大或格维度不足，求解器（如 small_roots()）将直接返回空集。必须严格验证边界条件并增加平移多项式。
缩放因子：未进行合理的列缩放会导致 LLL 找到与目标无关的短向量，需确保目标向量各分量大小均衡。
签名数量与算力：HNP 攻击对样本量敏感，偏差位数越少，所需的签名数量越多；同时，过高的 BKZ 块大小会导致运行时间呈指数级爆炸。
数值溢出：在 SageMath 中混合使用 QQ 和 ZZ 环易导致崩溃，需显式指定 ZZ 环以处理大整数。