不分解模数也能伪造签名：1024 位 RSA 的“午餐攻击”实测

TL;DR

保险柜没有被撬开，但里面的印章却被复制了。加州大学圣迭戈分校与 Inria 南锡的团队用硬件安全模块（HSM）做实验：密钥始终没有离开设备，模数也没有被分解，可他们最终还是伪造出了任意一条 1024 位 RSA 签名。代价是约 43 亿次裸 RSA 预言机查询和 1380 核年计算，其中仅与模数有关的预计算就占约 1200 核年；预计算完成后，每伪造一条新签名还需约 180 核年离线计算。相比之下，直接分解同一模数估计需要 50 万至 100 万核年。作者的结论很直白：在存在裸签名预言机的场景里，RSA 实际安全强度要比按分解难度算出的估计低 15 至 30 比特，连 4096 位 RSA 在该模型下都达不到 128 比特安全。但先别恐慌：这只针对裸的、无填充的 RSA 预言机，日常使用的 PKCS#1 v1.5 与 PSS 填充签名并不直接受影响。

论文信息卡

标题：Forging 1024-bit RSA signatures in nearly SNFS time
作者：Laura Shea、Miro Haller、Adam Suhl、Nadia Heninger（加州大学圣迭戈分校），Emmanuel Thomé（Inria 南锡）
会议/存档：IACR Cryptology ePrint Archive 2026/2131，预印本，2026-09-20 收录、2026-09-22 获批，CC BY 许可
原文链接：https://eprint.iacr.org/2026/2131
代码：https://github.com/ucsd-hacc/NSNFSSSFSFN

背景

几十年来，RSA 参数基本按“分解有多难”来定。通用数域筛法（GNFS）是分解一般整数最快的已知算法，渐近复杂度常数约 1.923；按这个标尺，1024 位 RSA 大致对应 80 比特安全，2048 位对应 112 比特。NIST 已规划 2030 年弃用 RSA、2035 年禁用 RSA。1024 位 RSA 早在 2013 年就被禁止用于签名生成，但至今仍被允许用于验证等遗留场景，在 TLS、OAuth、DNSSEC、DKIM 里还能扫到它。

然而，“攻破 RSA”与“分解模数”从来没有被证明等价：分解只是求 e 次根的一条充分路径，未必是唯一路径。2007 年，Joux、Naccache 与 Thomé 就提出过一种算法：只要攻击者能临时访问一个裸 RSA 签名/解密预言机，就能以接近特殊数域筛法（SNFS，常数约 1.526）的速度伪造签名，而不必分解模数。这个结果理论上很有名，却一直没人跑通过 1024 位规模，直到这篇论文把它从纸面搬进机房。作者给这个设定起了更准确的名字：延迟目标 RSA，也就是“午餐攻击”——攻击者先短暂接触预言机，之后目标才出现、预言机也已收回，但仍能在离线状态下完成伪造。

方法拆解

攻击模型：先借印章，后补签名

整个攻击分三个阶段，时间上可以完全错开。第一阶段是预计算，只依赖公开的模数 N 与指数 e，与任何具体目标无关；第二阶段是预言机查询，攻击者向 HSM 或盲签名服务提交一批精心挑选的数，拿到它们的 e 次根；第三阶段是离线伪造，目标出现后，攻击者不再需要接触预言机，仅用前两阶段的成果拼出目标的 e 次根。关键在于，预计算的成果可以反复使用，伪造第二条、第三条签名的边际成本只是再跑一次离线阶段。

核心 trick：只筛一边，另一边向预言机要

数域筛法的标准流程要在代数侧和有理侧同时筛出“光滑关系”，两边都贵。sqrt(e) NFS 的核心观察是：既然手里有个能给出任意数 e 次根的预言机，就可以只在代数侧筛，另一侧直接向预言机索取。具体做法是选两条多项式 f 与 g，共享一个模 N 的公共根 m，构造数域 $K=\mathbb{Q}(\alpha)$ ，其中 $f(\alpha)=0$ 。实验中取 $\deg(g)=1$ 、 $\deg(f)=6$ ，并要求公开指数 $e=65537$ 在该数域中不分歧，还有若干小素数保持惰性，这是为了后续在数域中开 e 次根时不出问题。

随后定义三组光滑界：代数侧 $B_{alg}=2^{31}$ 、扩展侧 $B_{ext}=2^{35}$ 、有理侧 $B_{rat}=2^{36}$ 。预计算先做代数筛：找出足够多的关系，使每个范数小于 $B_{alg}$ 的素理想都至少出现在一个关系里；再做扩展筛：对 $B_{alg}$ 到 $B_{ext}$ 之间的每个素理想，找一个只含它和更小素理想的关系。扩展筛不必追求 100% 覆盖，实际做到小于 $2^{33}$ 的约 90%、小于 $2^{35}$ 的约 60% 就够了，剩下的“硬骨头”留给伪造阶段多找一个替代关系即可。筛完之后，攻击者对所有代数、扩展关系做预言机查询，再对所有小于 $B_{rat}$ 的有理素数逐个查询，相当于把“因子基”里每个元素的 e 次根都提前买好、存在手里。

伪造阶段：把目标拆成已知零件

目标出现后，伪造分三步走。第一步是下降：把目标 t 拆成初始比值 $u/v$ 与有理函数 S，使得 S 在数域中的像只含因子基里的素理想，而 $u/v \cdot S(m)$ 在有理侧也光滑。实现上分三段：初始化用 las 加 ECM 找候选拆分，允许 365 比特大余因子，目标光滑度 135 比特；中段直接用 CADO-NFS 现成的下降代码；底段用作者新加的复合筛与嵌入多项式筛，把几百上千个特殊素数打包并行处理。初始化跑了 500 个并行任务、筛了一天后，挑到的最优拆分直接把光滑度压到 80 比特，省掉了原本为 768 位规模准备的“大素数”过渡步骤。

第二步是线性代数：把全部关系排成稀疏矩阵，解出每个因子基元素的 e 次根指数组合。过滤后的矩阵约有 1055 万行、1055 万列、22 亿个非零元，另有 6 列稠密的 Schirokauer 映射列。第三步是在数域中开 e 次根（Montgomery 方法加 CRT 与 p 进提升），把指数层面的解还原成真正的签名。最终下降树包含 5633 个有理素数、8592 个代数素理想、1860 个扩展素理想，分布在 874 个关系里。

flowchart LR
    A[预计算：选多项式<br/>代数筛 + 扩展筛] --> B[预言机查询<br/>买下因子基的 e 次根]
    B --> C[目标出现：下降<br/>把目标拆成光滑零件]
    C --> D[线性代数<br/>解出指数组合]
    D --> E[数域开 e 次根<br/>拼出目标签名]

为什么这不等于分解，也不等于 one-more RSA

作者花了整整一节澄清两个易混淆的点。第一，这不分解模数：即使能算任意奇数次根，也未必能拼出偶数次逆，更谈不上恢复 p 与 q；若目标数量多到次指数级，直接分解反而更划算。第二，这也不直接攻破盲签名常用的 one-more RSA 假设：one-more 游戏要求用 r 次查询伪造 r+1 个目标，而 sqrt(e) NFS 为伪造 1 个目标就要花约 $2^{32}$ 次查询，查询账根本对不上。该攻击的真正靶子是“先查询、后给目标”的 CCA1 式午餐攻击，而不是自适应盲签名游戏。盲签名协议的安全证明如果只写了 one-more RSA，就没有把这条攻击路径算进去，这正是论文要指出的假设缺口。

实验与数据

实验从 2026-03-13 跑到 2026-08-31，名义上 5 个月，中间有停机与并行穿插。按串行折算，大致是扩展筛 2.5 个月、代数筛 0.5 个月、下降 1 个月、线性代数与收尾 1 个月。机群以 2016 年左右的老处理器为主，另有 256 核、1TB 内存的机器做高内存步骤；报告的是虚拟核数，物理核数大约只有一半。

阶段	规模
总计算	约 1380 核年，5 个日历月
预计算	约 1200 核年，其中扩展筛约 1054 核年、代数筛约 150 核年
预言机查询	共 4,067,419,331 次：有理查询 2,874,398,515 次、代数查询 144,973,282 次、扩展查询 1,048,047,534 次
单次离线伪造	约 180 核年
对照：分解同一模数	估计 500,000–1,000,000 核年

预言机是两台 Thales Luna HSM：本地一台已停产的 Luna K6（为跑裸 RSA，作者关闭了 FIPS 140-2 批准模式，启用 PKCS#11 的 CKM_RSA_X_509 裸 RSA 机制），远程一台仍在售的 Luna S750（约 2.2 万至 3.2 万美元）。本地 HSM 以 40 线程跑出约 6500 签名/秒，有理查询约 123 小时、代数查询约 6.6 小时、扩展查询约 45 小时；远程那台约 2500 签名/秒，说明攻击完全可以跨互联网实施，并不依赖物理接触。作者强调，密钥是自行生成后导入 HSM 的测试密钥，并非生产系统里偷来的真实密钥。

外推到更大密钥时，作者用了两种方法交叉验证（按 GNFS 标尺定标的渐近公式，以及按 2.3GHz CPU 周期数缩放），结果相当接近，但作者也明确警告：外推忽略了隐藏常数与低阶项，且自家实现远非最优，这些数字应理解为攻击成本的上界，而非下界。

密钥长度	按分解估计的安全强度	sqrt(e) NFS 下的安全强度	所需查询量级
1024 位	80 比特	65 比特	$2^{32}$
2048 位	112 比特	90 比特	$2^{43}$
3072 位	128 比特	105 比特	$2^{51}$
4096 位	144–152 比特	119 比特	$2^{57}$

局限与开放问题

攻击模型很强：必须有裸的、无填充的 RSA 预言机。PKCS#1 v1.5 与 PSS 填充接口本身不提供这种预言机，对大多数现代部署不构成直接威胁。
成本仍是学术级：1380 核年、43 亿次查询、5 个月机房时间，离“随手可跑”还很远；实现远非最优，数字应视为上界。
外推有不确定性：更大密钥的强度是按渐近公式外推的，隐藏常数与参数最优性都未验证，只能作参考。
假设缺口未被填上：论文指出 one-more RSA 与延迟目标 RSA 的建模差异，但没有给出能覆盖预计算攻击的新假设。
填充预言机情形未解决：若预言机只能做带仿射变换的查询（AMR 模型，最接近 PKCS#1 v1.5 的情形），复杂度常数约 1.817，几乎追不上分解，作者因资源有限没有实现这一版本。
1024 位之外的实测仍是空白：2048 位及以上的数字全是外推，没有实测佐证。

一点思考

这篇论文最值得带走的不是“RSA 已死”的标题，而是“安全边界要按接口算，不按算法算”：同一套 RSA，放在带填充的签名接口里是一回事，放在裸 RSA 的 HSM 机制或盲签名服务里就是另一回事，安全强度能差出 15 至 30 比特。落到实操上，第一是盘点自家 HSM、KMS、签名服务里有没有开启裸 RSA 机制（PKCS#11 的 CKM_RSA_X_509 这类），没有正当理由的一律关掉；第二是给盲签名与 Privacy Pass 类服务定好密钥轮换周期，别让一把密钥在预言机前暴露太久；第三是把这篇论文放进后量子迁移的论证材料里——连经典密码分析都还在给 RSA 降级，拖延迁移的理由又少了一个。当然也要保持分寸：不要拿它去吓唬还在用 PSS 的正常系统，这次攻击打中的是接口，不是填充本身。

原文链接

论文：https://eprint.iacr.org/2026/2131
代码：https://github.com/ucsd-hacc/NSNFSSSFSFN