CISCN 2022 东北赛区Math题目密码学分析与教学

题目背景与核心思路

本题是一个结构化的RSA密码学题目，给出了两个RSA模数N1和N2，它们具有特殊的因子结构关系。

关键结构关系

• N1 ≈ a₁b₁a₂b₂
• N2 ≈ a₁b₂kb₁
• N1/N2 ≈ a₂/k

其中a₁, b₁, a₂, b₂, k均为256bit左右的整数，这种特殊结构为密码分析提供了突破口。

第一阶段：求解a₂和k参数

方法一：连分数展开法

理论基础
连分数展开适用于有理数逼近，当满足条件|α - p/q| < 1/(2q²)时，p/q一定是α的某个收敛子。

可行性验证
计算N1/N2与真实值a₂/k的误差分析：

• 误差范围：2⁻⁵¹¹到2⁻⁵¹²之间
• 临界条件：满足2⁻⁵¹³的阈值要求
• 结论：理论上可以通过连分数展开求解

实施步骤

1. 对N1/N2进行连分数展开，得到收敛子序列
2. 筛选满足条件的候选解：a₂和k均为256bit数量级
3. 经过筛选通常得到1-2组有效候选解

方法二：LLL格基规约法

格构造原理
将问题转化为寻找小向量问题，构造格基使得目标向量(N1·k - N2·a₂)为小向量。

实施要点

• 需要进行数量级缩放，使不同维度量级一致
• 相对于连分数法，LLL具有更好的容错性
• 计算量较大但适用性更广

比较分析

• 连分数法：计算效率高，但要求严格满足理论条件
• LLL法：适用性更广，在边界情况下仍可能找到解

第二阶段：基于a₂和k的参数恢复

方法一：CRT约束求解法（主线方法）

同余关系构造

1. φ(N1) ≡ 0 (mod a₂)
2. k·φ(N1) ≡ -1 (mod e)

前提条件验证
需要确保gcd(a₂, e) = 1，否则需要调整模数计算

CRT求解

• 联立两个同余式得到：φ(N1) ≡ φ_mod (mod a₂·e)
• 由于gcd(a₂, e)=1，可直接计算模a₂·e的解

分解N1的关键技术
利用φ(N1)与N1的接近性：

• φ(N1) = N1 - (p+q) + 1
• p+q = N1 - φ(N1) + 1
• 判别式Δ = (p+q)² - 4N1应为完全平方数

爆破优化

• 搜索空间：|φ(N1) - N1| ≈ 512-513bit
• a₂·e的量级也为512bit左右
• 实际只需要在小范围内枚举即可找到正确解

方法二：直接恢复私钥d法

数学基础

• e·d - 1 = k·φ(N1)
• φ(N1) ≡ 0 (mod a₂) ⇒ k·φ(N1) ≡ 0 (mod k·a₂)
• e·d ≡ 1 (mod k·a₂)

求解步骤

1. 计算e关于k·a₂的逆元：inva2k
2. d ≡ inva2k (mod k·a₂)
3. 利用d的近似值_d = (k·(N1+1)+1)/e
4. 误差分析：x = _d - d的量级与k·a₂相近
5. 爆破参数t：x = (_d - inva2k) mod (k·a₂) + t·k·a₂

BSGS优化
当搜索空间较大时，可使用Bounded BSGS算法：

• 时间复杂度：从O(B)降为O(√B)
• 离散对数形式：Gᵗ ≡ H (mod N1)
• 需要知道x的上界，不需要完整的群阶信息

方法三：Coppersmith攻击法（备选方案）

适用条件

• 需要满足Coppersmith定理的小根条件
• 本题中恰好处于边界情况，稳定性较差

增强措施
通过爆破少量高位比特（2⁸-2¹²级别）提高成功率：

1. 枚举q = a₂·b₂ + 1的高位前缀
2. 将问题转化为已知近似值+小偏移的形式
3. 使用格方法求解小量

技术实现细节

连分数展开实现

def continued_fraction(x, max_terms=100):
    """计算x的连分数展开"""
    terms = []
    for _ in range(max_terms):
        term = int(x)
        terms.append(term)
        if x == term:
            break
        x = 1/(x - term)
    return terms

LLL格构造示例

构造格基矩阵，目标向量为[N1·k - N2·a₂, k, a₂]的小向量。

CRT求解实现

使用中国剩余定理合并同余式，注意模数互质条件的检查。

总结与泛化

核心攻击链条

1. 结构分析：识别N1和N2的特殊因子关系
2. 参数提取：通过比值逼近获得关键参数a₂和k
3. 信息恢复：利用同余关系恢复φ(N1)或直接恢复d
4. 最终解密：分解N1或直接计算私钥完成RSA解密

方法选择策略

• 首选方案：连分数+CRT约束法（稳定性最高）
• 备选方案：LLL格基规约+直接恢复d法
• 特殊情况：Coppersmith+高位爆破（边界条件时使用）

泛化应用

本题目展示的结构化RSA攻击模式可应用于类似场景：

• 多个相关RSA模数的密码分析
• 具有特殊代数关系的因子结构
• 近似比值满足有理数逼近条件的情况

该教学方法强调了从结构信息到可求参数，再到多种收尾工具的完整攻击链条，为处理类似结构化RSA问题提供了系统的解决方案框架。