未來的量子計算機可能會迅速攻破現代密碼學。因此，數學家和密碼學家們一直在尋找合適的新加密算法來抵抗量子計算機的攻擊。這種能夠抵抗量子計算機對現有密碼算法攻擊的新一代密碼算法被稱作「后量子加密（PQC，postquantum cryptography）」算法。

但最近，比利時魯汶大學的研究人員發現，一種很有潛力的 PQC 加密算法可以在短短 1 小時內被完全破解（部分版本破解只需 4 分鐘）。問題是，這個記錄并不是由某臺高端計算機創下的，而是來自一臺搭載了十年高齡 CPU 的臺式機，而且是單核運行。研究人員說，這一最新的、令人驚訝的失敗凸顯了后量子密碼學在被采用之前需要克服的許多障礙。

論文鏈接：https://eprint.iacr.org/2022/975

從理論上講，量子計算機可以快速解決傳統計算機需要大量時間才能解決的問題。例如，現代密碼學在很大程度上依賴于經典計算機在處理復雜數學問題時所面臨的極端困難，如分解大數。而量子計算機原則上可以運行能夠快速破解這種加密技術的算法。

為了應對這種威脅，世界各地的密碼學家花了 20 年的時間設計后量子加密算法。這些算法基于量子計算機和經典計算機都難以解決的新數學問題。

多年來，美國國家標準與技術研究院（NIST）等機構的研究人員一直在研究哪些 PQC 算法應該成為全世界都可以采用的新標準。該機構在 2016 年宣布了正在尋找候選 PQC 算法的消息，并在 2017 年收到了 82 份提案。之后，經過三輪審查，NIST 宣布了四種即將成為標準的算法，另外四種將作為可能的競爭者（contender）進入下一輪審查。

審查還沒結束，其中一位競爭者已經倒下了，而且是被一臺 10 年的舊臺式機攻破了。這個算法名叫 SIKE（Supersingular Isogeny Key Encapsulation），微軟、亞馬遜、Cloudflare 和其他公司都對其進行了研究。密歇根大學安娜堡分校的密碼學家 Christopher Peikert 說：「這次攻擊來得太突然了，是一顆銀彈（具有極端有效性的解決方法）。」

SIKE 算法是什么？

SIKE 是一系列涉及橢圓曲線的 PQC 算法。「長期以來，橢圓曲線一直是數學家們的研究對象，」NIST 的數學家 Dustin Moody 表示。「它們由一個類似于 y^2 = x^3 + Ax + B 的方程描述，其中 A 和 B 是數字。比如，一條橢圓曲線可以是 y^2 = x^3 + 3x + 2。」

1985 年，「數學家想出了一種方法來制作涉及橢圓曲線的密碼系統，這些系統如今已被廣泛部署，」Moody 說道。「然而，這些橢圓曲線密碼系統很容易受到來自量子計算機的攻擊。」

大約在 2010 年，研究人員發現了一種在密碼學中使用橢圓曲線的新方法。人們相信這個新想法不容易受到量子計算機的攻擊。

這種新方法基于這樣一個問題：橢圓曲線上的兩點如何相加得到橢圓曲線上的另一個點。該算法名字中的「isogeny」表示同源性，是從一條橢圓曲線到另一條橢圓曲線的映射，它保留了這個加法定律。

「如果你讓這種映射變得足夠復雜，那么數據加密的挑戰就成了，給定兩條橢圓曲線，很難找到它們之間的同源性，」該研究的合著者、比利時魯汶大學數學密碼學家 Thomas Decru 說道。

SIKE 是一種基于超奇異同源 Diffie-Hellman（SIDH）密鑰交換協議的基于同源的密碼學形式。「SIDH/SIKE 是最早實用的基于同源的加密協議之一，」Decru 說。

然而 SIKE 的一個弱點是：為了使其工作，它需要向公眾提供額外的信息，即輔助扭轉點。「攻擊者嘗試利用這些額外信息已經有一段時間了，但一直未能成功利用它來攻破 SIKE，」Moody 說。「然而這篇新論文找到了一種方式，他們使用了一些相當先進的數學方法。」

為了解釋這種新的攻擊，Decru 說，雖然橢圓曲線是一維對象，但在數學中，橢圓曲線可以被可視化為二維或任何其他維數的對象。人們還可以在這些廣義對象之間創建同源。

通過應用一個 25 年前的定理，新的攻擊使用 SIKE 公開的額外信息來構建二維的同源。然后這種同源性就可以重建 SIKE 用來加密消息的密鑰。 

「對我來說，最令人驚訝的是，這次攻擊似乎是突然冒出來的」，馬里蘭大學帕克分校的密碼學家 Jonathan Katz 說道。雖然沒有參與這項新研究，但他表示：「之前很少有結果表明 SIKE 有任何弱點，而這次的結果突然給 SIKE 帶來了完全毀滅性的攻擊，因為它找到了完整的密鑰，并且是在沒有任何量子計算的情況下很快找到的。」

攻擊十多年，破解四分鐘

使用基于上述新攻擊方式的算法，研究人員發現，一臺搭載了十年「高齡」CPU（ Intel Xeon CPU E5-2630v2）的臺式機最少只需要 4 分鐘就能夠找到由某種 SIKE 算法保護的密鑰，而攻破被認為達到 NIST 量子安全一級標準的 SIKE 算法也只用了 62 分鐘。這些實驗都是在 CPU 的一個核上運行的。

「通常，密碼系統受到嚴重攻擊都發生在該系統提出之后不久，或者該系統剛開始吸引大家注意力的時候。隨著時間的推移攻擊逐漸變強，或是顯著削弱系統。但這次的攻擊，沒有任何前兆，密碼系統突然就被完全攻破。Peikert 說：「自 SIDH 被首次提出以來，對 SIDH/SIKE 的攻擊近 12 年來幾乎沒有任何進展，直到這次徹底攻破。」

盡管研究人員已經對 SIKE 進行了十多年的測試，但 SIKE 未被選中作為標準的原因之一是人們擔心它太新且研究還不夠充分。奧克蘭大學的數學家 Steven Galbraith 表示：「人們擔心 SIKE 可能有被重大襲擊的風險，事實證明這是對的。」

那么，為什么直到現在人們才檢測到 SIKE 的漏洞？Galbraith 認為，一個重要原因是新的攻擊「應用了非常高級的數學知識」。Katz 表示同意，他說：「我懷疑世界上只有不到 50 人同時掌握 PQC 底層的數學和必要的密碼學知識。」

此外，PQC 初創公司 Sandbox AQ 的密碼學家 David Joseph 曾說：「無論是從實現角度還是從理論角度講，同源問題都是『出了名的困難』，這使得其根本性缺陷更有可能在較晚的時候被發現。」

此外，「還應該注意的一點是，在 NIST 進行幾輪篩審查之前，可供分析的 PQC 算法是非常多的，因此研究精力被攤薄了。而經過幾輪篩選之后，研究人員已經能夠專注于一小撮算法了。」Joseph 說。

SIKE 的發明者之一、加拿大滑鐵盧大學教授 David Jao 表示：「我認為這項新成果是一項了不起的工作，我對作者們給予了最高的評價。起初，我對 SIKE 的破解感到難過，因為它在數學上是一個如此優雅的方案。」

「但新發現只不過是反映了科學的運作方式：我們提出了一個系統，當時每個人都認為它好像還不錯，然后經過分析，有人找到了它的弱點。他們花了 10 多年的時間才找到弱點，這點是不尋常的，但除此之外，這件事并沒有超出普通科學進展的范圍。」David Jao 補充說。

在 Jao 看來，SIKE 現在被破解是一件好事，畢竟它還沒有被廣泛部署。

SIKE 被破解意味著什么？

SIKE 是今年第二個被破解的 NIST PQC 候選算法。今年 2 月，蘇黎世 IBM 研究院的密碼學家 Ward Beullens 透露，他可以用筆記本電腦破解參與 NIST 第三輪審查的 Rainbow 算法。「這表明所有 PQC 方案都需要進一步研究」，Katz 說道。

不過，Moody 指出，盡管 SIKE 被破解了，但其他基于同源的密碼系統，如 CSIDH 或 SQIsign，還沒被破解，「有些人可能以為基于同源的密碼學已經死了，但事實遠非如此，我認為基于同源的密碼學還有很多東西要研究，」Decru 表示。

此外，這項新工作可能也無法反映 NIST 的 PQC 研究水平。正如 Decru 所說，SIKE 是 NIST 收到的 82 份提案中唯一一個基于同源的密碼系統；同樣，Rainbow 是這些提交中唯一的多變量算法。

那些被 NIST 采納為「標準」或進入其第四輪審查的算法都是基于已經被密碼學家研究、分析了很久的數學思想，Galbraith 說。「這并不能保證它們是安全的，只是意味著它們經受住了更長時間的攻擊。」

Moody 同意這一點，并指出「總是會發現一些驚人的突破性結果來破解密碼系統。對于任何密碼系統，我們都沒有絕對的安全保證。最好的說法是，經過很多聰明人的大量研究，沒有人發現該密碼系統有任何漏洞。」

「我們的程序被設計為允許攻擊和破解，」Moody 說。「我們在每一輪評估中都見過它們。這是獲得對安全的信心的唯一途徑。」 Galbraith 對此表示贊同，并指出這樣的研究「正在發揮作用」。

盡管如此，「我覺得，Rainbow 和 SIKE 的雙雙隕落會讓更多的人認真考慮，是否需要為 NIST 后量子標準化過程中出現的任何贏家制定后備計劃，」Decru 說。「僅僅依靠一個數學概念或方案可能太冒險了。這也是 NIST 自己的想法——他們的主要方案很可能是基于格密碼學（lattice-based）的，但他們想要一個非格密碼學方案備選。」

Decru 指出，其他研究者已經開始開發新版本的 SIDH/SIKE，他們認為這可能會阻止這種新型攻擊。「我預計到會有這樣的結果，當攻擊升級之后，人們試圖修補 SIDH/SIKE，」Decru 說。

總而言之，事實表明這種新攻擊的起點是一個「與密碼學完全無關」的定理，并且「揭示了進行純數學基礎研究以理解密碼系統的重要性」，Galbraith 表示。

Decru 對此表示同意，并指出「在數學中，并非所有東西都能立即適用。有些事情幾乎永遠不會適用于任何現實生活中的情況。但這并不意味著我們不應該讓研究導向這些更晦澀的議題。」