未來(lái)的量子計(jì)算機(jī)可能會(huì)迅速突破現(xiàn)代密碼學(xué)?，F(xiàn)在研究人員發(fā)現(xiàn)，一種設(shè)計(jì)用于保護(hù)計(jì)算機(jī)免受這些高級(jí)攻擊的有前途的算法可能在4分鐘內(nèi)即被破壞。問(wèn)題是，這4分鐘的時(shí)間還不是由現(xiàn)如今的尖端機(jī)器完成的，而是由一臺(tái)使用了10年的普通臺(tái)式計(jì)算機(jī)實(shí)現(xiàn)的。研究人員說(shuō)，這一最新的令人驚訝的失敗凸顯了后量子密碼術(shù)在采用前需要清除的許多障礙。

理論上，量子計(jì)算機(jī)可以快速解決問(wèn)題，而經(jīng)典計(jì)算機(jī)可能需要更多難以預(yù)測(cè)的時(shí)間才能解決。例如，許多現(xiàn)代密碼學(xué)依賴于經(jīng)典計(jì)算機(jī)在處理數(shù)學(xué)問(wèn)題時(shí)所面臨了極端困難，如分解大量數(shù)字。然而，量子計(jì)算機(jī)原則上可以運(yùn)行能夠快速破解這種加密的算法。

為了在這一量子威脅面前保持領(lǐng)先，世界各地的密碼學(xué)家在過(guò)去二十年中一直在設(shè)計(jì)后量子密碼（postquantum cryptography，PQC）算法。這些都是基于量子和經(jīng)典計(jì)算機(jī)都難以解決的新數(shù)學(xué)問(wèn)題。

多年來(lái)，國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）等組織的研究人員一直在研究哪些PQC算法應(yīng)該成為世界應(yīng)該采用的新標(biāo)準(zhǔn)。NIST于2016年宣布正在尋找候選PQC算法，并于2017年收到82份提交。7月，經(jīng)過(guò)三輪審查后，NIST宣布四種算法將成為標(biāo)準(zhǔn)，另外四種算法被認(rèn)定為是候補(bǔ)選手，將進(jìn)入下一輪的篩選。

現(xiàn)在，一項(xiàng)新的研究揭示了一種方法，可以完全打破這些被審查的競(jìng)爭(zhēng)者之一SIKE，微軟、亞馬遜、Cloudflare和其他公司已經(jīng)對(duì)此進(jìn)行了調(diào)查。要知道，他們破解的算法SIKE一直以來(lái)都被寄予厚望，過(guò)去12年都無(wú)人破解。密歇根大學(xué)安娜堡分校的密碼學(xué)家Christopher Peikert有參與這項(xiàng)新的研究，他說(shuō)：“這是突然發(fā)生的，是一顆銀彈?！?/p>

SIKE （Supersingular Isogeny Key Encapsulation） 是一種涉及橢圓曲線的PQC（后量子計(jì)算）算法。NIST的數(shù)學(xué)家Dustin Moody說(shuō)：“橢圓曲線在數(shù)學(xué)中已經(jīng)研究了很長(zhǎng)時(shí)間了。它們由方程y2=x3+Ax+B描述，其中A和B是數(shù)字。例如，橢圓曲線可以是y2=x3+3x+2?！?/span>

在1985年，“數(shù)學(xué)家們找到了一種方法來(lái)制作涉及橢圓曲線的密碼系統(tǒng)，這些系統(tǒng)已經(jīng)被廣泛應(yīng)用，”Moody說(shuō)，“然而，這些橢圓曲線密碼系統(tǒng)很容易受到量子計(jì)算機(jī)的攻擊?！?/p>

大約在2010年，研究人員發(fā)現(xiàn)了一種在密碼中使用橢圓曲線的新方法。Moody說(shuō)：“人們相信這一新想法不會(huì)受到量子計(jì)算機(jī)的攻擊。” 這種新方法是基于如何在橢圓曲線上添加兩個(gè)點(diǎn)，以獲得橢圓曲線上的另一個(gè)點(diǎn)?！巴瑯?gòu)”是從一條橢圓曲線到另一條保持該加法定律的橢圓曲線的映射。

“如果你把這張地圖弄得足夠復(fù)雜，那么可以對(duì)數(shù)據(jù)進(jìn)行加密的推測(cè)難題是，給定兩條橢圓曲線，很難找到它們之間的同構(gòu)關(guān)系，”該研究的合著者、比利時(shí)庫(kù)魯汶的數(shù)學(xué)密碼學(xué)家Thomas Decru如此表示。

SIKE是一種基于超奇異同根Diffie-Hellman（SIDH）密鑰交換協(xié)議的同根密碼學(xué)?！癝IDH/SIKE是第一個(gè)實(shí)用的基于同構(gòu)的密碼協(xié)議，”Decru說(shuō)。

然而，SIKE的一個(gè)弱點(diǎn)是，為了使其工作，它需要向公眾提供額外的信息，稱為輔助扭轉(zhuǎn)點(diǎn)。Moody說(shuō)：“攻擊者試圖利用這些額外信息已有一段時(shí)間，但未能成功地利用這些信息來(lái)破壞SIKE。然而，這篇新論文找到了一種方法，使用了一些相當(dāng)先進(jìn)的數(shù)學(xué)方法。”

為了解釋這種新的攻擊，Decru說(shuō)，盡管橢圓曲線是一維對(duì)象，但在數(shù)學(xué)上，橢圓曲線可以被視為二維或任意其他維度的對(duì)象。也可以在這些廣義對(duì)象之間創(chuàng)建同構(gòu)。

通過(guò)應(yīng)用一個(gè)已有25年歷史的定理，新的攻擊利用了SIKE公開(kāi)的額外信息來(lái)構(gòu)造二維同構(gòu)。然后，這種同構(gòu)可以重構(gòu)SIKE用來(lái)加密消息的密鑰。Decru和研究資深作者Wouter Castryck于8月5日在Cryptology ePrint Archive中詳細(xì)介紹了他們的發(fā)現(xiàn)。

馬里蘭大學(xué)帕克分校的密碼學(xué)家Jonathan Katz說(shuō)：“對(duì)我來(lái)說(shuō)，最令人驚訝的是，這次攻擊似乎是無(wú)緣無(wú)故的。之前很少有結(jié)果顯示SIKE存在任何弱點(diǎn)，然后突然出現(xiàn)了一個(gè)完全破壞性的攻擊，即它找到了整個(gè)密鑰，并且在沒(méi)有任何量子計(jì)算的情況下相對(duì)快速地完成了?！?/p>

使用基于這種新攻擊的算法，研究人員發(fā)現(xiàn)，一臺(tái)使用了10年的Intel臺(tái)式機(jī)需要4分鐘就找到了由SIKE保護(hù)的密鑰。

“通常，當(dāng)一個(gè)提出的密碼系統(tǒng)受到嚴(yán)重攻擊時(shí)，這發(fā)生在系統(tǒng)被提出后，或開(kāi)始引起注意后，或隨著時(shí)間的推移，研究結(jié)果的進(jìn)展，或不是完全破壞，而是系統(tǒng)的顯著削弱。在這種情況下，我們沒(méi)有看到任何情況，”Peikert說(shuō)，“對(duì)SIDH/SIKE的襲擊從最初提出SIDH以來(lái)的11年到12年中基本上沒(méi)有進(jìn)展，直到完全中斷。”

盡管研究人員對(duì)SIKE進(jìn)行了十多年的測(cè)試，“SIKE未被選為標(biāo)準(zhǔn)化的原因之一是人們擔(dān)心它太新，研究不夠，”新西蘭奧克蘭大學(xué)的數(shù)學(xué)家Steven Galbraith說(shuō)（他沒(méi)有參與這項(xiàng)新工作），“人們自然會(huì)擔(dān)心可能仍舊存在重大襲擊有待發(fā)現(xiàn) —— 他們是對(duì)的。”

到目前為止，SIKE的漏洞尚未被檢測(cè)到的一個(gè)原因是，新的攻擊“應(yīng)用了非常先進(jìn)的數(shù)學(xué)——“我想不出還有哪種情況下，與被破壞的系統(tǒng)相比，攻擊使用了如此深入的數(shù)學(xué)，”Galbraith說(shuō)。Katz對(duì)此表示贊同，他說(shuō)：“我懷疑世界上只有不到50個(gè)人理解基本的數(shù)學(xué)和必要的密碼術(shù)?！?/p>

此外，加州帕洛阿爾托PQC初創(chuàng)公司Sandbox AQ的密碼學(xué)家David Joseph說(shuō)，同族基因“從實(shí)現(xiàn)和理論角度來(lái)看都是出了名的‘困難’（他沒(méi)有參與這項(xiàng)新工作）?！斑@使得更可能的是，根本性缺陷在競(jìng)爭(zhēng)中持續(xù)到很晚才被發(fā)現(xiàn)?！?/p>

“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

此外，“需要注意的是，在前幾輪中有更多的算法，密碼分析的傳播更為稀疏，而在過(guò)去幾年中，研究人員能夠?qū)Ｗ⒂谳^小的一批算法，”Joseph說(shuō)。

SIKE的共同發(fā)明人、加拿大滑鐵盧大學(xué)教授David Jao表示，“我認(rèn)為這項(xiàng)新成果是一項(xiàng)偉大的工作，我對(duì)作者給予了最高的贊揚(yáng)?！彼f(shuō)，“起初，我對(duì)SKIE被宣告無(wú)效感到難過(guò)，因?yàn)檫@是一個(gè)數(shù)學(xué)上的方案，但新發(fā)現(xiàn)只是反映了科學(xué)是如何運(yùn)作的。我們提出了一個(gè)系統(tǒng)，當(dāng)時(shí)每個(gè)人都認(rèn)為這是一個(gè)好主意，在隨后的分析之后，有人能夠找到一個(gè)突破。這是不尋常的，它花了10年，但除正常的進(jìn)展過(guò)程外，這里什么都看不到?！?/p>

此外，Jao說(shuō)，“現(xiàn)在打破SIKE比在一些假設(shè)的替代世界中要好得多，在這個(gè)世界中，SIKE被廣泛部署，每個(gè)人都會(huì)在它被打破之前依賴它。”

BREAKS IN THE SYSTEM

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

指出，盡管如此，這些新發(fā)現(xiàn)打破了SIKE，但沒(méi)有打破其他基于同構(gòu)的密碼系統(tǒng)，如CSIDH或SQIsign?！皝?lái)自外部的人可能認(rèn)為基于同構(gòu)的密碼術(shù)已經(jīng)死了，但這遠(yuǎn)非事實(shí)，”Decru說(shuō)，“如果你問(wèn)我的話，還有很多需要研究?！?/p>

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

Galbraith說(shuō)，NIST正在采用的其他設(shè)計(jì)作為標(biāo)準(zhǔn)或已進(jìn)入NIST第四輪的設(shè)計(jì)“基于數(shù)學(xué)思想，密碼學(xué)家的研究和分析記錄更長(zhǎng)。這并不能保證他們一定是安全的，但這只是意味著他們經(jīng)受了更長(zhǎng)時(shí)間的攻擊?！?/span>

Moody同意這一觀點(diǎn)，并指出“總是會(huì)發(fā)現(xiàn)一些驚人的突破性結(jié)果，打破密碼系統(tǒng)。我們無(wú)法絕對(duì)保證任何密碼系統(tǒng)的安全性。我們能說(shuō)的最好的是，經(jīng)過(guò)許多聰明人的大量研究，沒(méi)有人在密碼系統(tǒng)中發(fā)現(xiàn)任何裂縫”。

Moody表示：“我們的程序設(shè)計(jì)為允許攻擊和中斷。我們?cè)诿恳惠喸u(píng)估中都看到了它們。這是獲得對(duì)安全的信心的唯一途徑?！盙albraith表示同意，并指出這種研究“正在進(jìn)行”。

盡管如此，“我覺(jué)得Rainbow和SIKE的結(jié)合會(huì)讓更多人認(rèn)真考慮為NIST后量子標(biāo)準(zhǔn)化過(guò)程中出現(xiàn)的任何贏家制定一個(gè)后備計(jì)劃，”Decru說(shuō)，“僅僅依靠一個(gè)數(shù)學(xué)概念或方案可能太危險(xiǎn)。這也是NIST自己認(rèn)為的。他們的主要方案很可能是基于晶格的，但他們需要非晶格備份?！?/p>

Decru指出，其他研究人員已經(jīng)在開(kāi)發(fā)SIDH/SIKE的新版本，他們認(rèn)為可能會(huì)阻止這種新的攻擊。Decru說(shuō)：“我預(yù)計(jì)接下來(lái)會(huì)有更多這樣的結(jié)果，人們?cè)噲D修補(bǔ)SIDH/SIKE，并改進(jìn)我們的攻擊?！?/p>

總而言之，這一新攻擊的起點(diǎn)是一個(gè)“與密碼學(xué)完全無(wú)關(guān)”的定理，這一事實(shí)也表明了“為了理解密碼系統(tǒng)，純數(shù)學(xué)基礎(chǔ)研究的重要性，”Galbraith說(shuō)。

Decru同意這一觀點(diǎn)，并指出“在數(shù)學(xué)中，不是所有的東西都能立即適用。有些東西幾乎肯定永遠(yuǎn)不會(huì)適用于任何現(xiàn)實(shí)生活中的情況。但這并不意味著我們不應(yīng)該讓研究不時(shí)轉(zhuǎn)向這些更模糊的話題?！?/p>