Agent 4天复现人类5个月实验！谷歌DeepMind拿下两项密码分析新成果

智东西

作者 | 孙小雯

编辑 | 程茜

智东西11月10日消息，11月7日，谷歌DeepMind副总裁Pushmeet Kohli在社交平台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%。

▲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此次进一步让智能体参与签名攻击和批量分解算法的改进，降低了特定条件下的理论计算成本。

在密码学研究中，人类研究者先确定问题、设置实验条件，再让智能体执行计算、优化程序和尝试不同方案，最后由研究者审核结果。借助这种分工，研究者可以更快完成需要反复试验的验证工作。

来源：谷歌DeepMind、X