谷歌DeepMind用AI攻1024位RSA：4天复现5个月实验
同步公开两篇工作论文。
11月7日，谷歌
DeepMind副总裁Pushmeet Kohli在社交平台X上公布了两项AI辅助密码分析成果。智东西11月10日消息，在人类研究人员指导下，AI智能体为旧式1024位RSA密码系统找到了两条改进攻击路径。其中一项实验里，两个AI智能体用不到4天，复现了此前研究团队耗时约5个月完成的计算实验，CPU计算量从约1380核心年降到391核心年，少了约72%。
▲谷歌DeepMind官方公告（图源：X）
▲前人实验与AI复现实验的CPU开销对比，GPU成本另计（图源：谷歌DeepMind论文）
研究显示，AI智能体现在可以接手密码学研究里大量繁重的程序开发和计算任务，也能帮研究人员找到更省算力的攻击路径。
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资源大半耗在这里。技术报告给出的数字是，CPU计算量省下的部分里约90%来自对筛选程序的优化。
同样的机器、同样的参数下，优化后的核心筛选程序跑起来约是原版程序的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这次把智能体推进到签名攻击和批量分解算法的改进上，压低了特定条件下的理论计算成本。
密码学研究里的分工大致是这样：人类研究者先定问题、设好实验条件，智能体负责执行计算、优化程序、试不同方案，结果最后由研究者审核。这么配合下来，那些需要反复试的验证工作，研究者能更快做完。
