谷歌DeepMind用AI攻RSA：4天复现5个月实验，CPU开销降72%

11月10日消息，谷歌DeepMind副总裁Pushmeet Kohli于11月7日在社交平台X上公布了两项AI辅助密码分析成果。在人类研究人员的指导下，AI智能体为旧式1024位RSA密码系统找到了两条改进的攻击路径。其中，两个AI智能体用了不到4天，就复现了此前研究团队耗时约5个月才完成的一项计算实验，把CPU计算量从约1380核心年压到391核心年，减少约72%。

▲谷歌DeepMind官方公告（图源：X）

▲前人实验与AI复现实验的CPU开销对比，GPU成本另计（图源：谷歌DeepMind论文）

这项研究说明，AI智能体已经可以接手密码学研究里大量复杂的程序开发和计算工作，还能帮研究人员找到更省算力的攻击路径。

RSA在互联网里既像一把锁，也像一枚防伪章。它能保护信息，也能验证文件是否出自可信来源。比如电脑下载软件更新时，会检查厂商留下的数字签名，确认安装包没被人替换过。

RSA的原理建立在一道数学难题上：两个大质数相乘很容易，可如果只知道乘积，想反推出原来那两个质数，就难得多。

攻击者要仿造RSA签名，有两条路可走。一条是分解乘积、恢复私钥，再自己生成签名；另一条是跳过恢复私钥，用数学方法仿制出能通过核验的签名。谷歌DeepMind这次从这两个方向分别入手，改进了相关攻击方法。

批量整数分解方面，团队提出了Fan Factories算法，让多个位数相同的目标共享前期计算结果。论文估算，先投入约相当于一次通用数域筛分解的计算成本后，后续每个1024位目标的理论成本，可降到此前最优方法的约1/30。在同等预计算预算下，这是1993年以来后续单目标最优理论成本的首次改进。

▲两种算法在相同预计算预算下的理论成本对比（图源：谷歌DeepMind论文）

数字签名伪造方面，团队发现，当攻击者能控制约一半输入内容时，固定填充不再增加这类攻击的计算难度。部分RSA签名标准会加入预设内容，也就是“填充”，用来限制调用者自行选择输入。研究指出，如果攻击者能暂时调用特定签名接口，并控制数据块约一半或更多的内容，就能用与无填充场景相同的数学方法伪造签名。

当可控部分更少、比如只有32字节的数字摘要时，团队也提出了新算法。按1024位规模做理论估算，其计算成本约为此前最优方法的1/1600。

研究由谷歌DeepMind的Dj Dvijotham和Abhradeep Thakurta牵头，与加州大学圣迭戈分校及法国国家数字科学与技术研究院（Inria）的密码学家合作完成。目前团队已公开两篇工作论文，一篇研究受限签名接口下的模求根方法，另一篇研究共享预计算条件下的批量整数分解。

从实际使用情况看，1024位RSA已经退出主流网站证书体系。眼下大部分公开信任的网站TLS证书要求RSA密钥至少达到2048位。不过出于兼容需要，仍有部分产品保留1024位选项，比如Google Workspace、亚马逊AWS SES等邮件签名服务。

一、两条路径并行，谷歌DeepMind大幅降低1024位RSA攻击成本

谷歌DeepMind这次研究涉及“数字签名伪造”与“批量整数分解”。

1、数字签名伪造：两个AI智能体不到4天复现实验，CPU计算量减少约72%

签名实验中，研究人员先让AI智能体完成前期数据准备，查询模拟签名接口。等接口关闭后，再为此前未知的新目标生成有效签名。

前期，AI智能体编写的程序自行选择输入，向接口发起约40.6亿次查询，保存返回结果，并整理出可供后续使用的数学关系。随后研究人员关闭接口，生成此前未知的随机目标。程序再利用已有算法和保存的数据，完成新目标的签名计算。

为检验AI智能体的计算效率，谷歌DeepMind沿用了前人相同的1024位实例、数学算法和主要参数，让AI智能体重新编写并优化计算程序。

两个主要智能体一个负责监督、一个负责执行。“监督智能体”制定方案、预算和检查要求，“执行智能体”写代码、运行任务并排查故障。人类研究人员确定目标和关键条件，期间发送约20条消息，多数用于批准操作。

▲监督智能体与执行智能体的任务分工（图源：谷歌DeepMind论文）

整个实验历时3天22小时，两个AI智能体新编写约3.35万行代码，开展336次分布式计算实验。期间智能体还发现并修复了一处32位索引溢出问题，使计算结果最终通过验证。

在相同1024位实例上，此次实验的CPU计算量从此前约1380个CPU核心年降至391个，减少约72%。

智东西（公众号：zhidxcom） 作者 | 孙小雯 编辑 | 程茜

▲1024位RSA计算实验的任务执行记录（图源：谷歌DeepMind论文）

说到省算力，AI智能体把力气主要花在了筛选这一步。实验要排查海量候选，从中挑出能用于后续求根的数学关系，这个过程很吃CPU。技术报告给出的数字是：约90%的CPU计算量节省来自筛选程序的优化。

同一台机器、同样的参数下，优化后的核心筛选程序跑出的速度是原版的1.8-1.9倍左右，第二层筛选程序则达到原版的3.4-4.4倍。前期准备花掉约318个CPU核心年，新目标的计算用了约73个CPU核心年。

▲前期准备与新目标计算的CPU开销对比；SHS+26代表此前实验（图源：谷歌DeepMind论文）

工期能压下来，还靠并行规模的扩大。谷歌DeepMind的研究人员把峰值拉到约30万个CPU核心和16张GPU。论文认为，约5个月和不到4天之间的差距，主要就来自并行规模的不同。GPU的开销是另外统计的。

2、批量整数分解：提高预计算利用率，后续目标理论成本降至约1/30

面对多个位数相同的RSA整数，传统做法是先做一次成本不低的预计算，再把结果套用到不同目标上，把成本摊薄。这类方案有个名字，叫“分解工厂”。

问题是，传统分解工厂给每个目标配一个数域，前期投入不够高就发挥不出优势。假如预计算预算只相当于一次通用数域筛分解，它就跑不过通用数域筛。在这个预算水平上，研究者过去的最优选择仍是分别运行1993年提出的多数域筛方法。

谷歌DeepMind的Fan Factories算法换了个思路：给每个目标配多个数域，让同一批预计算结果的利用率更高。算法会在不同数域之间查找共享结果——某个结果在一个数域里形不成有效关系，放到另一个数域里可能还有用；随后算法把同一目标拿到的关系汇总起来，完成后面的分解。

论文的估算是，先投入约相当于一次通用数域筛分解的成本，之后每个1024位目标的理论成本可以降到此前最优方法的约1/30。

把预计算也算进总成本，按论文的理论估算，处理至少3个1024位目标时，新方法依然比逐个运行此前的多数域筛更便宜。同样的预计算预算下，这项成果首次压低了自1993年以来再未改进的后续单目标最优理论成本。

▲在预计算预算相当于一次通用数域筛分解的条件下，后续单个目标的最优理论分解成本自1993年以来首次下降。按1024位规模估算，Fan Factories将该成本降至此前方法的约1/30（图源：谷歌DeepMind论文）

二、AI发展助力，年内多项RSA研究接连推进，分别沿两条攻击路径展开

RSA密码分析历来是个算力大户。今年情况有变，多家AI公司先后入场，用智能体优化GPU程序、调度计算资源，把成本往下压，进展一个接一个。

9月9日，Cognition靠旗下AI编程智能体Devin，从整数分解这条路切入，完成了约862位的RSA-260分解。Devin帮忙把已有的计算程序改成GPU实现。据Cognition发布的技术文章，以2020年RSA-250实验为基准推算，同等分解规模下新GPU实现的估算成本约是此前CPU实现的1/10，RSA-260也成了当时公开完成分解的最大RSA挑战题。

9月19日，Anthropic研究员Stephen Weis用该公司旗下大模型Claude，走的同样是整数分解路径，完成了896位RSA整数分解。Claude在其中协助移植GPU程序、调度最多2048张GPU，调用集群的空闲算力，前后算了约10天。

同月，美国加州大学圣迭戈分校与法国Inria的研究者另辟蹊径，从数字签名伪造入手，借助已有求根算法和签名设备的查询结果，在不提取私钥的前提下生成了1024位RSA有效签名。实验耗时约5个月，消耗约1380个CPU核心年。

谷歌DeepMind这次的实验，复现的正是那项签名伪造工作。两个AI智能体沿用相同实例、算法和主要参数，把计算程序重新实现并加以优化。结果不到4天，就复现了此前约5个月的实验，CPU计算量从约1380核心年降到391核心年，少了约72%。

结语：AI智能体降低旧式RSA攻击成本，帮助检验密码安全

在此之前，Devin和Claude参与的RSA整数分解研究，主要靠改写GPU程序、调度算力来提升效率。谷歌DeepMind这回则让智能体进一步介入签名攻击和批量分解算法的改进，把特定条件下的理论计算成本压了下来。

密码学研究里的分工大致是这样：人类研究者先定问题、设好实验条件，智能体负责执行计算、优化程序、试各种方案，最后由研究者审核结果。靠这种配合，那些需要反复试错的验证工作能更快做完。