未來的量子計算機可能會迅速突破現代密碼學。現在研究人員發現，一種設計用于保護計算機免受這些高級攻擊的有前途的算法可能在4分鐘內即被破壞。問題是，這4分鐘的時間還不是由現如今的尖端機器完成的，而是由一臺使用了10年的普通臺式計算機實現的。研究人員說，這一最新的令人驚訝的失敗凸顯了后量子密碼術在采用前需要清除的許多障礙。

理論上，量子計算機可以快速解決問題，而經典計算機可能需要更多難以預測的時間才能解決。例如，許多現代密碼學依賴于經典計算機在處理數學問題時所面臨了極端困難，如分解大量數字。然而，量子計算機原則上可以運行能夠快速破解這種加密的算法。

為了在這一量子威脅面前保持領先，世界各地的密碼學家在過去二十年中一直在設計后量子密碼（postquantum cryptography，PQC）算法。這些都是基于量子和經典計算機都難以解決的新數學問題。

多年來，國家標準與技術研究所（NIST）等組織的研究人員一直在研究哪些PQC算法應該成為世界應該采用的新標準。NIST于2016年宣布正在尋找候選PQC算法，并于2017年收到82份提交。7月，經過三輪審查后，NIST宣布四種算法將成為標準，另外四種算法被認定為是候補選手，將進入下一輪的篩選。

現在，一項新的研究揭示了一種方法，可以完全打破這些被審查的競爭者之一SIKE，微軟、亞馬遜、Cloudflare和其他公司已經對此進行了調查。要知道，他們破解的算法SIKE一直以來都被寄予厚望，過去12年都無人破解。密歇根大學安娜堡分校的密碼學家Christopher Peikert有參與這項新的研究，他說：“這是突然發生的，是一顆銀彈。”

SIKE （Supersingular Isogeny Key Encapsulation） 是一種涉及橢圓曲線的PQC（后量子計算）算法。NIST的數學家Dustin Moody說：“橢圓曲線在數學中已經研究了很長時間了。它們由方程y2=x3+Ax+B描述，其中A和B是數字。例如，橢圓曲線可以是y2=x3+3x+2。”

在1985年，“數學家們找到了一種方法來制作涉及橢圓曲線的密碼系統，這些系統已經被廣泛應用，”Moody說，“然而，這些橢圓曲線密碼系統很容易受到量子計算機的攻擊。”

大約在2010年，研究人員發現了一種在密碼中使用橢圓曲線的新方法。Moody說：“人們相信這一新想法不會受到量子計算機的攻擊。” 這種新方法是基于如何在橢圓曲線上添加兩個點，以獲得橢圓曲線上的另一個點。“同構”是從一條橢圓曲線到另一條保持該加法定律的橢圓曲線的映射。

“如果你把這張地圖弄得足夠復雜，那么可以對數據進行加密的推測難題是，給定兩條橢圓曲線，很難找到它們之間的同構關系，”該研究的合著者、比利時庫魯汶的數學密碼學家Thomas Decru如此表示。

SIKE是一種基于超奇異同根Diffie-Hellman（SIDH）密鑰交換協議的同根密碼學。“SIDH/SIKE是第一個實用的基于同構的密碼協議，”Decru說。

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

為了解釋這種新的攻擊，Decru說，盡管橢圓曲線是一維對象，但在數學上，橢圓曲線可以被視為二維或任意其他維度的對象。也可以在這些廣義對象之間創建同構。

通過應用一個已有25年歷史的定理，新的攻擊利用了SIKE公開的額外信息來構造二維同構。然后，這種同構可以重構SIKE用來加密消息的密鑰。Decru和研究資深作者Wouter Castryck于8月5日在Cryptology ePrint Archive中詳細介紹了他們的發現。

馬里蘭大學帕克分校的密碼學家Jonathan Katz說：“對我來說，最令人驚訝的是，這次攻擊似乎是無緣無故的。之前很少有結果顯示SIKE存在任何弱點，然后突然出現了一個完全破壞性的攻擊，即它找到了整個密鑰，并且在沒有任何量子計算的情況下相對快速地完成了。”

使用基于這種新攻擊的算法，研究人員發現，一臺使用了10年的Intel臺式機需要4分鐘就找到了由SIKE保護的密鑰。

“通常，當一個提出的密碼系統受到嚴重攻擊時，這發生在系統被提出后，或開始引起注意后，或隨著時間的推移，研究結果的進展，或不是完全破壞，而是系統的顯著削弱。在這種情況下，我們沒有看到任何情況，”Peikert說，“對SIDH/SIKE的襲擊從最初提出SIDH以來的11年到12年中基本上沒有進展，直到完全中斷。”

盡管研究人員對SIKE進行了十多年的測試，“SIKE未被選為標準化的原因之一是人們擔心它太新，研究不夠，”新西蘭奧克蘭大學的數學家Steven Galbraith說（他沒有參與這項新工作），“人們自然會擔心可能仍舊存在重大襲擊有待發現 —— 他們是對的。”

到目前為止，SIKE的漏洞尚未被檢測到的一個原因是，新的攻擊“應用了非常先進的數學——“我想不出還有哪種情況下，與被破壞的系統相比，攻擊使用了如此深入的數學，”Galbraith說。Katz對此表示贊同，他說：“我懷疑世界上只有不到50個人理解基本的數學和必要的密碼術。”

此外，加州帕洛阿爾托PQC初創公司Sandbox AQ的密碼學家David Joseph說，同族基因“從實現和理論角度來看都是出了名的‘困難’（他沒有參與這項新工作）。“這使得更可能的是，根本性缺陷在競爭中持續到很晚才被發現。”

“We proposed a system， which everyone agrees seemed like a good idea at the time， and after subsequent analysis someone is able to find a break. It is unusual that it took 10 years， but otherwise nothing to see here.”

—David Jao， University of Waterloo

此外，“需要注意的是，在前幾輪中有更多的算法，密碼分析的傳播更為稀疏，而在過去幾年中，研究人員能夠專注于較小的一批算法，”Joseph說。

SIKE的共同發明人、加拿大滑鐵盧大學教授David Jao表示，“我認為這項新成果是一項偉大的工作，我對作者給予了最高的贊揚。”他說，“起初，我對SKIE被宣告無效感到難過，因為這是一個數學上的方案，但新發現只是反映了科學是如何運作的。我們提出了一個系統，當時每個人都認為這是一個好主意，在隨后的分析之后，有人能夠找到一個突破。這是不尋常的，它花了10年，但除正常的進展過程外，這里什么都看不到。”

此外，Jao說，“現在打破SIKE比在一些假設的替代世界中要好得多，在這個世界中，SIKE被廣泛部署，每個人都會在它被打破之前依賴它。”

BREAKS IN THE SYSTEM

SIKE是今年第二位被破解的NIST PQC候選人。二月份，蘇黎世IBM研究中心的密碼學家Ward Beullens透露，他可以在周末用筆記本電腦破解第三輪候選人Rainbow。“因此，這表明所有PQC方案仍需要進一步研究，”Katz說。

指出，盡管如此，這些新發現打破了SIKE，但沒有打破其他基于同構的密碼系統，如CSIDH或SQIsign。“來自外部的人可能認為基于同構的密碼術已經死了，但這遠非事實，”Decru說，“如果你問我的話，還有很多需要研究。”

此外，這項新工作也可能不會以某種方式反映NIST的PQC研究。SIKE是NIST收到的82份提交文件中唯一基于同構的密碼系統。Decru說，同樣，Rainbow是這些提交文件中唯一的多元算法。

Galbraith說，NIST正在采用的其他設計作為標準或已進入NIST第四輪的設計“基于數學思想，密碼學家的研究和分析記錄更長。這并不能保證他們一定是安全的，但這只是意味著他們經受了更長時間的攻擊。”

Moody同意這一觀點，并指出“總是會發現一些驚人的突破性結果，打破密碼系統。我們無法絕對保證任何密碼系統的安全性。我們能說的最好的是，經過許多聰明人的大量研究，沒有人在密碼系統中發現任何裂縫”。

Moody表示：“我們的程序設計為允許攻擊和中斷。我們在每一輪評估中都看到了它們。這是獲得對安全的信心的唯一途徑。”Galbraith表示同意，并指出這種研究“正在進行”。

盡管如此，“我覺得Rainbow和SIKE的結合會讓更多人認真考慮為NIST后量子標準化過程中出現的任何贏家制定一個后備計劃，”Decru說，“僅僅依靠一個數學概念或方案可能太危險。這也是NIST自己認為的。他們的主要方案很可能是基于晶格的，但他們需要非晶格備份。”

Decru指出，其他研究人員已經在開發SIDH/SIKE的新版本，他們認為可能會阻止這種新的攻擊。Decru說：“我預計接下來會有更多這樣的結果，人們試圖修補SIDH/SIKE，并改進我們的攻擊。”

總而言之，這一新攻擊的起點是一個“與密碼學完全無關”的定理，這一事實也表明了“為了理解密碼系統，純數學基礎研究的重要性，”Galbraith說。

Decru同意這一觀點，并指出“在數學中，不是所有的東西都能立即適用。有些東西幾乎肯定永遠不會適用于任何現實生活中的情況。但這并不意味著我們不應該讓研究不時轉向這些更模糊的話題。”