结合连分数与格基约化(Coppersmith方法)的小私钥RSA混合攻击

《Cryptography》：A Hybrid Attack on Small Private Exponent RSA via Continued Fractions and Lattices

　　

本研究提出一种针对采用小私钥(small private exponent)实例化RSA公钥密码体制的混合密码分析(cryptanalytic)技术。通过将连分数(continued fraction)方法与Coppersmith基于格(lattice)的技术相结合，研究人员构建了一个新的脆弱性分析框架。利用从连分数渐近分数(convergent)中提取的创新关系式，研究人员推导出了私钥(secret key)的改进上界：d < N(1/2?δ)/(1+γ)，其中γ = log e / log N，δ = log u / log N，S为素数之和p+q的已知近似值。作为前期会议论文的扩展版本，本文给出了所有理论命题的完整证明，进行了全面的参数敏感性评估，并给出了部分素数泄露(partial prime exposure)情形下的攻击界。实验评估验证了该框架的理论机制，表明在特定部分泄露场景下，相比传统的纯格基(lattice-only)基准方法，该方法提供了改进的攻击界。

基于连分数与Coppersmith格方法的RSA小私钥混合攻击论文解读

一、研究背景与开展的研究及意义

RSA公钥密码体制的安全性在大整数分解困难性的假设下成立，但实际实现中常采用小私钥d以加速解密运算，这引入了已知的密码分析风险。传统针对小私钥d的攻击主要分为两类：一是Wiener等人提出的连分数(continued fraction)方法，可在d < N^1/4时高效恢复私钥；二是基于Coppersmith找小根技术与Boneh–Durfee、Herrmann–May的格(lattice)基约化方法，理论上可将界推至d < N^0.292。然而纯连分数法界较紧且难以扩展，而纯格方法在实际高维格计算中往往达不到渐近理论极限，且在已知p+q近似值或部分素数位泄露时未充分利用连分数的代数结构信息。为此，研究人员提出一种将连分数理论与多元Coppersmith格技术相融合的混合(hybrid)密码分析框架，利用连分数渐近分数(convergent)导出k与d的关系式(k为ed ≡ 1 mod φ(N)中的倍数)，将其嵌入三元模方程构建更优的格，从而在已知S ≈ p+q或部分素数MSB/LSB泄露时获得比Herrmann–May攻击更宽松的d的上界。该工作发表于《Cryptography》。

二、主要关键技术方法

研究人员首先回顾连分数展开与Legendre定理判定某有理数是否为给定实数的渐近分数，以及LLL算法与Howgrave-Graham引理用于模小根求解。核心方法为：(1)从e/N的连分数展开中取相邻渐近分数k_i/d_i、k_i?1/d_i?1，利用连分数性质得存在整数u,v使k = u·k_i+v·k_i?1, d = u·d_i+v·d_i?1且uv ≠ 0；(2)将RSA密钥方程ed = 1 + kφ(N)代入φ(N) = N ? S + w（S已知近似p+q，w未知小量）改写为关于(x=k?uk_i?vd_i?1, y=v, z=w)的三元模多项式f(x,y,z) ≡ 0 mod N；(3)采用Jochemsz–May多元Coppersmith格构造策略，以移位多项式(shift polynomials)建三角格阵，经LLL约化并结合Howgrave-Graham引理求小根，导出可解条件并优化参数m,t得d的上界。对素数共享MSB或LSB情形，类似地用p = A + Δp、q = A + Δq（Δp,Δq小量）或p = gn + r, q = g'n + r形式改写方程后套用同一框架。实验在SageMath中用随机生成RSA实例验证，Gr?bner基解根，重复多次取均值与标准差，并与Herrmann–May基准对照。

三、研究结果

3.1 第3节 既有攻击回顾(Revisiting Previous Attacks)

研究人员给出Lemma 3证明φ(N) = N ? (p+q) + 1及|N/φ(N) ? 1| < 3/N^1/2；Lemma 6证明当d < N^1/4时k/d是e/N的渐近分数，d < N^1/2时k/d是e/(N?p?q+1)的渐近分数；Theorem 2证明若e/N与e/(N?p?q+1)有非平凡公共渐近分数k/d则d < N^1/4·√(2N/e)；Theorem 4证明当e为满尺寸(full-size)且d > N^1/4时e/N的渐近分数无法恢复d，说明Wiener攻击在纯连分数意义下近最优。由此明确连分数单独使用的局限性，引出需结合格方法。

3.2 第4.1节 主攻击(The Main Attack — Theorem 6)

研究人员设e/N两相邻渐近分数k_i/d_i, k_i?1/d_i?1满足d_i?1< d < d_i，存在u,v使k = uk_i+vk_i?1, d = ud_i+vd_i?1，已知S = p+q?w且|w| ≤ N^β。将ed = 1+kφ(N)化为关于x = k?uk_i?vk_i?1, y = v, z = w的三元多项式f(x,y,z)。经Jochemsz–May格构造与LLL+Howgrave-Graham分析得可解条件d < N^{(1/2?δ?β·t/(m+t))/(1+γ)}（优化后t=m得d < N^{(1/2?δ?β/2)/(1+γ)}式中δ = log u / log N）。由于u ? d_i≈d，δ较小，相比Herrmann–May界d < N^{(1/2?β)/(1+γ)}多出δ项改善，实验例证实在相同格维度下本方法可恢复Herrmann–May框架失败的实例。

3.3 第4.2节 素数共享MSB或LSB的应用(Theorems 7 & 8)

— Theorem 7（共享MSB）：设p = A + Δp, q = A + Δq，|Δp|,|Δq| < N^δ'/2，则S = 2A已知高位，误差w = Δp+Δq < N^δ'。代入主攻击框架得条件d < N^{(1/2?δ?δ'/2)/(1+γ)}，优于同情形下Herrmann–May直接用S ≈ p+q的界。

— Theorem 8（共享LSB）：设p = gn + r, q = g'n + r，n已知，g,g'未知小，由Lemma 5得φ(N) = N ? n(g+g') ? 2r + 1，令误差项为小量后同样套用主攻击框架得d < N^{(1/2?δ?(1?η)/2)/(1+γ)}（η为LSB比例），较Sun等人基于Boneh–Durfee的界更优。Remark 3指出两情形去相同部分后剩余攻击界一致。

3.4 第5节 实验结果与讨论(Experimental Results and Discussion)

— 5.1与5.2节：1024位N、d约N^0.265、S取p+q前若干MSB，取m=3~5优化t，构126维格，10次独立实验成功率100%，数值例给出完整因式分解流程。

— 5.3节参数敏感性：m从2增至5可恢复更大d（达N^0.27），低维(m=2)偶现代数相关导致10%失败，增m后全成功；计算时间随维数增长（m=5约1500秒）。

— 5.4节素数泄露场景实验：共享MSB/LSB位数增加（δ'增大）放宽可解条件，与理论预测相符。

— 5.5节理论与实验差距：理论渐近界接近N^0.292，实测可靠约N^0.27，差距源于高维LLL基质量下降与多项式代数独立启发式(Assumption 1)偶尔不成立，超一定维数受计算资源限制。

四、讨论与结论总结

研究人员得出结论：所提混合框架将连分数渐近分数关系融入Coppersmith三元模方程格构造，在已知S ≈ p+q或部分素数MSB/LSB泄露时，给出了比Herrmann–May攻击更宽松的小私钥d的上界，数值实验证实了可行性。理论界与实证间存在差距，主要归因于高维格约化质量与多项式独立性启发假设，未来可探索额外x方向移位优化特定γ区域，并可扩展至多素数(multi-prime) RSA情形检验连分数结构是否保留脆弱性。该工作完善了RSA小私钥攻击中连分数信息与格技术的协同利用，为评估实际RSA参数安全及侧信道结合代数攻击减少需提取位数提供了理论依据。