遇到 RSA 小根、DSA/ECDSA nonce 偏置…

当 CTF 或密码分析问题可转化为模 N 小根、CVP/SVP 或低密度子集和时，按问题类型构造格并用 LLL/BKZ 恢复私钥、nonce 或明文。

适用场景

解决思路

1. 路由到相关技能：RSA 专用格攻击参考 ../rsa-attack-techniques/SKILL.md；LCG 状态恢复参考 ../symmetric-cipher-attacks/SKILL.md；经典密码分析参考 ../classical-cipher-analysis/SKILL.md。
2. 先按问题类型选择格技术：RSA 小根用 Coppersmith（对多项式格做 LLL），关键边界 X < N^(1/e)；RSA 小私钥 d 用 Boneh-Durfee（多元 Coppersmith），条件 d < N^0.292；DSA/ECDSA nonce 偏置用 Hidden Number Problem → CVP，需要已知偏置比特；背包密码用低密度格攻击，条件 Density < 0.9408；LCG 截断输出用 recurrence lattice 上的 CVP，需要知道每个输出未知比特数；subset sum 用 knapsack lattice 的 LLL 约减，按元素大小与数量选择；NTRU 密钥恢复用 NTRU lattice 的格约减，按维度和密钥大小选择。
3. 掌握格基础：格 L = {a₁·b₁ + ... + aₙ·bₙ | aᵢ ∈ ℤ}，bᵢ 线性无关；核心问题是 SVP（找最短非零向量）和 CVP（给定 t 找最近格点）；一般 SVP NP-hard，但 LLL 可在多项式时间找到近似短向量。
4. 计算格质量指标：det(L) = |det(B)|；Gaussian heuristic 估计最短向量约为 √(n/(2πe))·det(L)^(1/n)。
5. 运行 LLL：输入 basis B，输出 reduced basis B'，向量近似正交，首向量约短，复杂度 O(n^5·d·log³ B)；SageMath 写法 M=matrix(ZZ,[...]); L=M.LLL(); short_vector=L[0]；fpylll 写法 from fpylll import IntegerMatrix, LLL; A=IntegerMatrix(n,n); 填充 A；LLL.reduction(A); print(A[0])。
6. 选择 LLL 还是 BKZ：LLL 质量 2^((n-1)/2) 近似、多项式时间、block size 固定 2、适合快速约减；BKZ-β 质量 2^(n/(β-1)) 近似、时间随 β 指数增长、β 可配置、适合高质量约减。SageMath 用 M.BKZ(block_size=20)；fpylll 用 BKZ.reduction(A, BKZ.Param(block_size=20))；经验是先 LLL，不够再 BKZ，CTF 中 β=20-40 通常足够。
7. 单变量 Coppersmith：给定 f(x) ≡ 0 (mod N) 和小根 |x₀| < X，求 x₀；边界 X < N^(1/d)，d 为 f 的次数。SageMath 用 N=...; R.<x>=PolynomialRing(Zmod(N)); f=...; roots=f.small_roots(X=2^100, beta=1.0, epsilon=1/30)。参数 X 是根上界；beta：N=p^beta，beta=1.0 表示模 N 本身的根，beta=0.5 表示模未知因子 p≈√N 的根；epsilon 越小结果越好但越慢，可试 1/30 到 1/100。
8. RSA stereotyped message attack：已知 n,e,c 和消息高位 known_msb；R.<x>=PolynomialRing(Zmod(n)); f=(known_msb+x)^e-c；x 表示未知低位；X=2^(unknown_bit_count)；roots=f.small_roots(X=X, beta=1.0)；若 roots 非空，m=known_msb+int(roots[0])。
9. RSA 部分密钥暴露求因子 p：已知 p 的高位 p_known，p=p_known+x，x 很小；R.<x>=PolynomialRing(Zmod(n)); f=p_known+x；roots=f.small_roots(X=2^unknown_bits, beta=0.5)；beta=0.5 因为 p≈√n；若 roots 非空，p=p_known+int(roots[0]); q=n//p。
10. 多元 Coppersmith/Howgrave-Graham：对 f(x,y) ≡ 0 (mod N)，没有保证的多项式时间算法，实践中用启发式方法；Boneh-Durfee 用于 RSA 小 d。做法：e*d ≡ 1 (mod phi)，phi=(p-1)(q-1)；改写 e*d = 1 + k*((n+1)-(p+q))；令 x=k，y=(p+q)，二者相对 n 都小；R.<x,y>=PolynomialRing(ZZ)；A=(n+1)//2；f=1+x*(A+y) mod e；构造 shift polynomials 并建格；应用 LLL 找小 (x₀,y₀)。
11. DSA/ECDSA HNP nonce 恢复：已知签名 (rᵢ,sᵢ) 且 nonce kᵢ 有已知偏置（泄漏 MSB 或 LSB）。DSA 方程 s=k⁻¹(H(m)+xr) mod q；重排 k=s⁻¹(H(m)+xr) mod q；若已知 k 的部分比特，问题化为格上的 CVP。实现 ecdsa_nonce_attack(signatures,q,known_bits,bit_position='msb')：n=len(signatures)；B=2^(q.nbits()-known_bits)；建立 M=matrix(QQ,n+2,n+2)；对每个签名计算 t_i=Integer(inverse_mod(s_i,q)*r_i % q)、u_i=Integer(inverse_mod(s_i,q)*h_i % q)；置 M[i,i]=q、M[n,i]=t_i、M[n+1,i]=u_i-a_i（a_i 为已知 nonce 比特）、M[n,n]=B/q、M[n+1,n+1]=B；L=M.LLL()；遍历行，令 x_candidate=Integer(row[n]*q/B)%q，用任一签名验证；返回 x。
12. 按 nonce 偏置来源准备签名数量：MSB 恒为 0（1 bit）约需 100 个签名；k 用错长度（可变）约 50 个；时序侧信道（1-4 bits）约 20-100 个；不安全 PRNG（很多位）少量；nonce 复用（k₁=k₂）2 个即可。
13. ECDSA 复用 nonce 直接代数恢复，无需格：s1-s2=k⁻¹(h1-h2) mod q（r 相同）；k=((h1-h2)*inverse_mod(s1-s2,q))%q；x=((s1*k-h1)*inverse_mod(r,q))%q；返回 (x,k)。
14. 背包/子集和低密度攻击：给定 weights a₁,...,aₙ 和 target S，找 x₁,...,xₙ ∈ {0,1} 使 Σxᵢaᵢ=S。密度 d=n/max(log₂ aᵢ)；若 d<0.9408，格攻击可行。Lagarias-Odlyzko 风格构造：n=len(weights)；N=ceil(sqrt(n)/2)；M=matrix(ZZ,n+1,n+1)；对 i 置 M[i,i]=1、M[i,n]=N*weights[i]；M[n,n]=N*target；对 M 做 LLL。
15. 背包也可用 CJLOSS embedding：M2=matrix(ZZ,n+1,n+2)；对 i 置 M2[i,i]=1、M2[i,n+1]=N*weights[i]；M2[n,n]=1、M2[n,n+1]=N*(-target)；L=M2.LLL()；遍历行，找 row[:n] 全为 0 或 1 的行，并验证 sum(solution[i]*weights[i] for i in range(n))==target。
16. NTRU 密钥恢复：构造 NTRU 格 [[qI,0],[H,I]]，其中 H 是 h 的 circulant matrix。SageMath：H=matrix(ZZ,N,N)；对 i,j 置 H[i,j]=h[(j-i)%N]；M=block_matrix([[q*identity_matrix(N), zero_matrix(N)],[H, identity_matrix(N)]])；L=M.LLL()；遍历行，取 f=vector(row[:N])、g=vector(row[N:])；若 f.norm()<q 且 g.norm()<q，返回 (f,g)。
17. 构造攻击格的通用配方：1) 把密码问题表达为“找小 x 使 f(x) ≡ 0 (mod N)”或“在格 L 中找靠近 target t 的 x”；2) 选择格类型：多项式格 → Coppersmith 风格，模格 → HNP 风格 CVP，背包格 → subset sum/CJLOSS；3) 确定维度：维度越多近似越好但越慢；4) 设置缩放因子：平衡各行使短向量各分量大致相等，常用乘以 N/X，X 为根上界；5) 应用约减：先 LLL（快，通常够），LLL 失败再用 BKZ，增大 block size 20、30、40；6) 提取解：检查约减基各行是否为有效解。
18. CVP 转 SVP 用 Kannan embedding：def cvp_to_svp(basis_matrix,target,scale=1)：n=basis_matrix.nrows()，m=basis_matrix.ncols()；建 M=matrix(ZZ,n+1,m+1)；把 basis_matrix 复制到左上；M[i,m]=0；对 j 置 M[n,j]=target[j]；M[n,m]=scale；L=M.LLL()；遍历行，若 abs(row[m])==scale，返回 vector(target)-vector(row[:m])*(row[m]//abs(row[m]))；scale 先试 1，再调整。
19. 按问题选择维度：Coppersmith 单变量（次数 d）用 d×m，m≈1/ε；HNP 有 n 个签名用 n+2，且 n ≥ known_bits_ratio × q_bits；Knapsack 有 n 个权重用 n+1 或 n+2，取决于密度；LCG 有 n 个输出用 n+1，输出越多越容易；Boneh-Durfee 用 (m+1)(m+2)/2，m 为参数深度。
20. 按决策树选择构造：RSA 相关：消息小未知部分 → Coppersmith 单变量，检查 unknown_bits < n_bits/e；部分因子已知 → Coppersmith mod p，用 beta=0.5、X=2^unknown_bits；小私钥 d → Boneh-Durfee，检查 d < N^0.292；多个相关方程 → 多元 Coppersmith。DSA/ECDSA 相关：复用 nonce → 直接代数恢复（无需格）；部分 nonce 泄漏 → HNP → CVP 格，需要 n ≥ q_bits/leaked_bits；nonce 偏置 → 统计 HNP → 更大格。Knapsack/subset sum：低密度 d<0.9408 → CJLOSS 格攻击；高密度 → 格攻击不太可能；超递增 → 贪心（无需格）。LCG/PRNG：完整输出已知 → 代数恢复（无需格）；截断输出 → recurrence lattice 上的 CVP；模数未知 → 用输出差值的 GCD。NTRU：构造 circulant lattice → LLL/BKZ 找短密钥向量。自定义问题：能表达为“模 N 多项式小根”→ Coppersmith；能表达为“找靠近 target 的格点”→ CVP；能表达为“找短向量”→ SVP/LLL；都不行则大概率不是格问题。
21. 避免和修复常见错误：根上界过大导致 small_roots() 返回空 → 减小 X、增大 epsilon、检查 Coppersmith 边界；缩放错误导致 LLL 找到无关短向量 → 缩放列使目标向量分量平衡；维度不足导致解不在约减基中 → 增大 m（更多 shift polynomials）；beta 错误导致 Coppersmith 找不到因子 → 半尺寸因子用 beta=0.5，完整模数用 beta=1.0；HNP 签名太少导致格攻击失败 → 收集更多带 nonce 偏置的签名；BKZ block size 太小导致解不够短 → 增大 block size（25、30、40）；整数溢出导致 SageMath 崩溃 → 显式使用 ZZ 环，避免混用 QQ 和 ZZ。

适用边界 · 注意事项

• 当背包密度 d ≥ 0.9408、subset sum 为超递增（用贪心），或 LCG 已知完整输出、ECDSA 复用 nonce 可直接代数恢复时，不要硬上格攻击。
• 当问题无法表达为“模 N 的小根”或“格中的最近/最短向量”时，通常不是格问题。
• 当没有 SageMath/fpylll 等格归约环境，或无法承受 BKZ 的指数开销时，不适用。