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