免分解模數：借簽章 oracle，1024-bit RSA 偽造速度逼近 SNFS
IACR ePrint 2026/2131 · 2026-09-20
只要曾經暫時借到一台會回傳「未加 padding」RSA 簽章結果的機器，攻擊者就不必分解模數，也能在接近 SNFS（特殊數域篩選法）的時間內，偽造這把金鑰之後任何一則訊息的簽章。加州大學聖地牙哥分校與 Inria Nancy 的團隊（Laura Shea、Miro Haller、Adam Suhl、Nadia Heninger、Emmanuel Thomé）把這個想法真的在 1024-bit RSA 上跑了一遍，論文 Forging 1024-bit RSA signatures in nearly SNFS time（IACR ePrint 2026/2131）於 2026 年 9 月 20 日提交。
背景：RSA 金鑰長度是照「分解」訂的，但這攻擊不分解
RSA 的金鑰長度標準（NIST SP 800-56B）是照 GNFS（一般數域篩選法）分解模數 N 的難度換算：漸近複雜度 L_N(1/3, 1.923)，1024-bit RSA 至今未被公開分解過，估計要 500,000 至 1,000,000 CPU core-years。這篇論文用的不是 GNFS，而是 Joux、Naccache、Thomé 在 2007 年提出、一直沒人實作過的「√e NFS」演算法：它不分解 N，而是要求攻擊者曾經取得這把金鑰的「原始 RSA 簽章／解密 oracle」——輸入任意 w，拿回 w^(1/e) mod N。論文把這個威脅模型稱為「delayed-target RSA」，也就是俗稱的 lunchtime attack：先短暫拿到 oracle 存取權，之後失去存取權，仍要能對任意新目標偽造簽章。
核心機制：只篩一邊，另一邊換成 oracle 查詢
RSA 具有乘法同態性：(a·b)^d mod N = a^d · b^d mod N。√e NFS 的做法是：先用數域篩選（NFS）的多項式選取與篩法，對模數 N 建出一組「代數側」的 smooth 元素（factor base），這些元素的 eth 根事先向 oracle 逐一查出來存好；等真正要偽造的目標 t 出現，再用「descent」把 t 表示成這些已知 eth 根元素的乘積組合，最後直接相乘算出 t^(1/e) mod N——全程不需要 φ(N)，也不需要分解 N。論文形容這是「malleability attack」。關鍵差異在於 GNFS 要同時篩代數與有理兩側才能分解，這裡只篩一側，省下的那一側改用 oracle 查詢頂替，複雜度因此逼近 SNFS 的 L_N(1/3, 1.526)，實際跑出來是 L_N(1/3, 1.577)——比 GNFS 快，但仍比真正的 SNFS 慢一點，所以論文標題用「nearly SNFS time」。
| 方法 | 對象 | 漸近複雜度 | 1024-bit 實測／估計耗時 |
|---|---|---|---|
| GNFS 直接分解模數 N | 公鑰即可，不需 oracle | L_N(1/3, 1.923) | 500,000–1,000,000 core-years（迄今未完成） |
本文 √e NFS 偽造簽章 | 需曾取得原始簽章 oracle | L_N(1/3, 1.577) | precompute 1,200 core-years + 2^32 次 oracle 查詢，之後每偽造一則簽章 180 core-years，總計 1,380 core-years、實跑 5 個月 |
Precomputation 只依賴模數 N，可以在拿到 oracle 之前先做完；真正的 2^32 次查詢是團隊接上一台商用 HSM，透過其 PKCS#11 介面的「原始 RSA」操作做出來的——等於只靠黑箱 API 互動就取得了等同私鑰的偽造能力，全程沒有把金鑰從 HSM 中取出。
影響範圍：關鍵在「誰暴露了未加 padding 的 RSA oracle」
論文把攻擊往上外推到常見金鑰長度：1024-bit 實測相當於 2^65 運算量（原本假設 80-bit 安全）；2048-bit 外推為 2^90 運算量、2^43 次查詢（原本假設 112-bit）；4096-bit 外推為 2^119 運算量、2^57 次查詢，仍未達 128-bit 安全門檻。也就是說，只要系統會暴露原始 RSA oracle，2048-bit 甚至 4096-bit RSA 都達不到原本宣稱的安全等級。
真正暴露這種 oracle 的場景，是把 HSM 開成允許原始 RSA 運算（通常是為了支援 PKCS#11 未涵蓋的 padding，例如電子護照 AA 用的 ISO 9796-2、ANSI X9.31、RSA-FDH）；以及RSA 盲簽章——RFC 9474 定義的 RSABSSA、Privacy Pass／Apple Private Access Tokens（Cloudflare、Fastly、Persona 生產環境在用）、GNU Taler 的電子貨幣鑄造，這些協定的「盲簽」查詢本質上就是攻擊者要的 oracle。另外，即使系統本身只支援 PKCS#1v1.5，若存在 Bleichenbacher padding oracle，攻擊者也能疊加漏洞湊出原始 RSA oracle。至於一般的 TLS 憑證、OAuth JWT（RS256）、DNSSEC、DKIM，論文明確指出這些協定本身不暴露原始簽章 oracle，因此不直接受這個攻擊威脅——但論文的掃描同時發現，TLS 憑證中仍有 17,455 把 1024-bit RSA 金鑰、DNSSEC 有 1,212 個 TLD 的 ZSK 是 1024-bit、DKIM 有 33% 的 RSA 金鑰是 1024-bit，Atlassian 官方文件到 2026 年 9 月都還在教人產生 1024-bit RSA 金鑰，顯示 1024-bit RSA 在這些場景仍未真正淘汰。
對還在用 HSM 原始 RSA 模式或 RSA 盲簽章的團隊，論文建議短期先頻繁輪替金鑰、中期換成更大金鑰或改用不受影響的 clause blind Schnorr 簽章（GNU Taler 已這麼做）、長期則直接轉向後量子演算法——這也呼應 NIST 預定 2030 年淘汰、2035 年禁止 RSA 的時間表。對其餘只用 PKCS#1v1.5／RSA-PSS 簽章驗證、沒有暴露原始 RSA oracle 的系統，這篇論文不構成立即威脅，但仍是繼續留著 1024-bit RSA 的又一個理由：該盤點的是憑證鏈、DNSSEC ZSK、DKIM 選擇器裡還殘留的 1024-bit 金鑰，逐步換成 2048-bit 以上或 post-quantum 演算法。
原始來源：Forging 1024-bit RSA signatures in nearly SNFS time（IACR ePrint 2026/2131）