智东西
作者 | 孙小雯
编辑 | 程茜
智东西 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