有一种破解 RSA 的新方法，比我们之前见过的任何方法都快

xujunpeng · 2026 年9 月 29 日 21:05

来源: https://arstechnica.com/security/2026/09/theres-a-new-way-to-break-rsa-thats-faster-than-anything-weve-seen-before/

此前，密码学家一直认为因式分解是破解RSA算法的唯一方法。现在情况不同了。

几十年来，世人皆知RSA密码系统的末日已至。一旦量子计算变得实用（据估计，这可能需要3到20年甚至更久），它所提供的基础安全性将不堪一击。一项新的研究揭示了一种利用经典计算将RSA当前安全级别降低到令人无法接受的低水平的新方法。

实际风险虽然有限，但仍然不容忽视。在学术级CPU集群上，针对已弃用的1024位密钥发起的攻击仅耗时数月，远低于目前对1024位密钥分解的预估耗时——后者所需的资源只有拥有庞大资源的国家或公司才能负担得起。广泛使用的RSA实现也是安全的。

然而，这项研究令密码学家们感到意外，因为它引入了签名伪造技术，这是一种无需因式分解即可破解RSA密钥的新方法。同样重要的是，这种新方法将所需的计算资源减少了几个数量级。

不再遥不可及

“如果这一结果经得起同行评审，那确实是一项概念上的突破，”密码学专家、Allurity创新主管卡斯滕·诺尔在接受采访时表示。“RSA的破解难度与分解大整数的难度相当，至少我们之前是这么认为的。但这位研究人员指出，实际上无需破解密钥就能破解RSA。”

加州大学圣地亚哥分校教授兼合著者纳迪亚·亨宁格进一步阐述道：

密码学家认为，计算有效RSA数字签名的唯一方法是先通过因式分解计算私钥，然后再用私钥计算签名。对于1024位RSA，这种方法被认为非常昂贵，但如果你拥有大型科技公司或美国国家安全局（NSA）的计算资源，或许可以做到——计算一个密钥就需要数千万美元的计算时间。而对于2048位RSA，这种方法则被认为完全无法实现。

Heninger 和其他研究人员设计的密钥伪造攻击现在对 1024 位 RSA 算法来说已经完全可行。即使对于 2048 位和 4096 位密钥，该方法也会将 RSA 的安全性降低到不可接受的水平。美国国家安全局、国家标准与技术研究院以及欧盟网络与信息安全局都要求任何密码系统至少提供 128 位或更高的安全级别，这意味着所需的运算次数必须超过2^ 128次。

伪造攻击将1024位、2048位和4096位密钥的安全级别分别降至2^65 2^90 20^119。由于Heninger的团队完全手工编写代码，未使用人工智能或GPU进行伪造，因此这些安全级别可能还会进一步降低。该研究人员表示，这些工具“几乎肯定”会进一步降低安全级别。

这种攻击仅对采用盲签名实现的RSA有效。目前绝大多数RSA都采用PKCS或PSS填充，这种格式会在加密前向明文添加数据。它能防止密文具有确定性，并降低其遭受侧信道攻击和类似攻击的风险。然而，一些实际系统仍然使用盲签名，也就是所谓的教科书式RSA。Heninger指出，最著名的例子是Privacy Pass，这是一种允许用户在不泄露身份的情况下进行身份验证的协议。包括苹果和Cloudflare在内的许多公司都在使用Privacy Pass。

对 Privacy Pass 的攻击需要攻击者向 Cloudflare、Apple 或其他组织请求243个令牌。

亨宁格表示，这项要求“听起来很多，但实际上与Cloudflare公开宣称的每日网络流量量级相当。”大多数隐私通行证方案都会定期轮换密钥，这一措施可以大大降低攻击者成功的几率，但并不能完全消除这种可能性。

该技术实现了一种2007年发明的数字域筛算法的变体。这种“特殊”的数字域筛算法与“预言机”配合使用，预言机是某些加密协议的一种特性，能够对查询的输入给出答案。攻击者通过执行大量运算，可以收集到足够的信息来解密密文。（该技术似乎对采用PKCS或PSS填充的RSA算法构不成实际威胁，因为它们提供的是不同类型的预言机。）虽然分解一个1024位密钥估计需要2^ 80次运算和50万到100万个CPU核心年，但使用该筛算法伪造签名仅需（如前所述）2^ 65次运算和1380个CPU核心年。

论文作者和其他研究人员强调，至少目前来看，这种新的攻击对现实世界的威胁很小。然而，它确实大幅降低了RSA的安全性，而且这种降低方式是前所未见的。

近年来，密码学家们一直在努力设计不易受量子计算攻击的替代密码系统。这种新的攻击将进一步凸显彻底摒弃现有密码系统的紧迫性。论文作者在此处提供了一个更易于理解的解释。

xujunpeng · 2026 年9 月 29 日 21:15

论文作者QA: https://github.com/ucsd-hacc/NSNFSSSFSFN

在接近 SNFS 的时间内伪造 1024 位 RSA 签名

备选标题：近乎 SNFS 的无因子 N 签名伪造速度 (NSNFSSSFSFN)

本代码库与论文（预印本 2026/2131）配套，其中包含实现数字域筛法 (NFS) 算法变体的代码。它表明，攻击者可以利用对原始、未填充的 RSA 签名/解密预言机的临时访问权限，获得永久伪造签名/解密密文的能力。换句话说，攻击者本质上可以窃取私钥（因为他们可以离线伪造签名/解密），而无需实际分解公钥，并且所需的计算量远低于分解公钥所需的计算量。

这表明，基于因子分析的 RSA 安全性估计可能过于乐观，应该进行修正，但可能不会对现实世界中大多数已部署的 RSA 构成直接的运行威胁。

该算法并非多项式时间算法， 甚至远非如此。它属于“亚指数时间”算法，与目前最好的因式分解算法属于同一级别。然而，它之所以能达到更快的亚指数时间速度，是因为它使用了“特殊”的数域筛法，而非“通用”的数域筛法。据预测，分解一个 1024 位模数需要 50 万到 100 万核心年的时间。而我们实际运行该算法处理一个 1024 位模数，仅耗时 1380 核心年。

该算法并非全新，它由 Joux、Naccache 和 Thomé于 2007 年发明。然而，这是该算法的首次公开实现和大规模运行。大部分代码并非原创，而是基于CADO-NFS构建的。

该算法仅在存在原始签名预言机的情况下才有效。 大多数 RSA 实际应用（即使用 PKCS#1v1.5 或 RSA-PSS 填充的 RSA 签名）不会暴露此类预言机，因此这种攻击不会构成实际风险。会暴露此类签名预言机的 RSA 应用示例包括盲 RSA 签名（例如 Privacy Pass）或 HSM API。

常见问题解答

现在还有人用RSA吗？
是的，尤其是在数字签名方面（例如证书、TLS握手、令牌、OAuth）。TLS等协议的密钥交换使用ECDH或已过渡到ML-KEM，因此这种攻击不适用于这些算法。
现在是否需要立即停止使用 RSA？
不会。对于 RSA 的大多数应用场景而言，这种攻击并不构成实际风险。即使在可能存在漏洞的场景下，我们估算针对 2048 位 RSA 的攻击成本为 $2^{90}$。这一数值低于分解 2048 位 RSA 密钥所需的估算成本（$2^{112}$），但其计算量是分解 1024 位 RSA 密钥所需估算成本（$2^{80}$）的 1000 倍——而迄今为止，尚无公开记录显示有人成功分解过 1024 位 RSA 密钥。如果您仍有顾虑，可以考虑使用椭圆曲线密码学（例如用于签名的 ECDSA 或 Ed25519），因为这类算法似乎不易受到此类攻击的影响。
是否有必要立即停止使用RSA？
我们认为答案是肯定的。此次攻击表明，RSA密钥长度高达4096位已无法满足现代密码学的安全要求。向后量子密码学的过渡为我们提供了一个契机，可以彻底摆脱RSA等传统密码学。
如果我使用 2048 位密钥进行盲 RSA 加密（例如 Privacy Pass）会怎样？
这种攻击仍然适用。我们估计需要花费一定的时间。2^90 工作和2^43预言机查询可能低于您期望的安全裕度，而且除了规模最大、技术最精湛的攻击者之外，几乎无人能够利用这种漏洞。短期内，您可以考虑缩短密钥周期并增加 RSA 密钥长度。中期来看，协议设计者可以通过添加零知识证明来消除这种攻击途径。长期来看，我们希望未来能够出现可接受的后量子时代替代方案，以取代盲签名等机制。
我能否编译这段代码并立即伪造 1024 位 RSA 签名？
只有拥有强大的计算资源才能做到。即使使用我们学术规模的 CPU 集群，也花了数月时间才完成伪造计算。计算量介于 RSA-240 和 RSA-250 记录之间。
AI/GPU能否加速这一实现过程？
几乎可以肯定可以。
你使用了人工智能/GPU吗？
没有。
我使用 2048 位密钥，并采用 PKCS 或 PSS 填充进行签名。我需要担心吗？
不用担心，在这种情况下，我们的攻击似乎不可行。
为什么这不只是教科书式的RSA攻击？
这种攻击更强大，因为攻击者可以利用请求签名的临时能力，窃取相当于拥有私钥的能力，而无需实际拥有私钥。（也就是说，攻击者将来可以离线伪造任何他们选择的签名。）大部分工作都集中在一个仅依赖于公钥的预计算中；预计算完成后，伪造单个签名的效率要高得多。
为什么到了 2026 年 9 月，我还会听到关于 2007 年算法的消息？
我们当时进行的 1024 位计算耗费了大量精力（详见我们的论文）。目前从事这一领域的研究人员相对较少，资金也有限，而且就业市场更青睐研究后量子密码学（以及现在的人工智能）的学生。然而，如果没有这类计算工作，这些算法就只能停留在理论层面。
这是什么SNFS time 意思？
“特殊”数域筛法。它也指分解特殊形式整数（例如梅森数）的运行时间，分解这类整数比分解普通整数（例如格式良好的RSA模数）要快得多。如果你感兴趣，可以去维基百科上查阅相关内容。

特别常见问题解答

我使用的是 1024 位 RSA 密钥，模数是119761307924183143227323805033445425142683607945593313835302891299066516303843000359184032065280614739228104709307215190162897575231548821264285875476222037118119400262673724895150267064851629266552653543645482302630040586124860255443008330625425740446416414144702538281275665910057429738414800482721215922451 。我该怎么办？
更换密钥。
你们是什么时候做的这个计算？
1024 位的数据量计算花了我们几个月的时间，于 2026 年 8 月 31 日完成。