未來(lái)的量子計(jì)算機(jī)可能會(huì)迅速攻破現(xiàn)代密碼學(xué)。因此，數(shù)學(xué)家和密碼學(xué)家們一直在尋找合適的新加密算法來(lái)抵抗量子計(jì)算機(jī)的攻擊。這種能夠抵抗量子計(jì)算機(jī)對(duì)現(xiàn)有密碼算法攻擊的新一代密碼算法被稱(chēng)作「后量子加密（PQC，postquantum cryptography）」算法。

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

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

從理論上講，量子計(jì)算機(jī)可以快速解決傳統(tǒng)計(jì)算機(jī)需要大量時(shí)間才能解決的問(wèn)題。例如，現(xiàn)代密碼學(xué)在很大程度上依賴(lài)于經(jīng)典計(jì)算機(jī)在處理復(fù)雜數(shù)學(xué)問(wèn)題時(shí)所面臨的極端困難，如分解大數(shù)。而量子計(jì)算機(jī)原則上可以運(yùn)行能夠快速破解這種加密技術(shù)的算法。

為了應(yīng)對(duì)這種威脅，世界各地的密碼學(xué)家花了 20 年的時(shí)間設(shè)計(jì)后量子加密算法。這些算法基于量子計(jì)算機(jī)和經(jīng)典計(jì)算機(jī)都難以解決的新數(shù)學(xué)問(wèn)題。

多年來(lái)，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）等機(jī)構(gòu)的研究人員一直在研究哪些 PQC 算法應(yīng)該成為全世界都可以采用的新標(biāo)準(zhǔn)。該機(jī)構(gòu)在 2016 年宣布了正在尋找候選 PQC 算法的消息，并在 2017 年收到了 82 份提案。之后，經(jīng)過(guò)三輪審查，NIST 宣布了四種即將成為標(biāo)準(zhǔn)的算法，另外四種將作為可能的競(jìng)爭(zhēng)者（contender）進(jìn)入下一輪審查。

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

SIKE 算法是什么？

SIKE 是一系列涉及橢圓曲線(xiàn)的 PQC 算法。「長(zhǎng)期以來(lái)，橢圓曲線(xiàn)一直是數(shù)學(xué)家們的研究對(duì)象，」NIST 的數(shù)學(xué)家 Dustin Moody 表示?！杆鼈冇梢粋€(gè)類(lèi)似于 y^2 = x^3 + Ax + B 的方程描述，其中 A 和 B 是數(shù)字。比如，一條橢圓曲線(xiàn)可以是 y^2 = x^3 + 3x + 2。」

1985 年，「數(shù)學(xué)家想出了一種方法來(lái)制作涉及橢圓曲線(xiàn)的密碼系統(tǒng)，這些系統(tǒng)如今已被廣泛部署，」Moody 說(shuō)道?！溉欢@些橢圓曲線(xiàn)密碼系統(tǒng)很容易受到來(lái)自量子計(jì)算機(jī)的攻擊?！?/span>

大約在 2010 年，研究人員發(fā)現(xiàn)了一種在密碼學(xué)中使用橢圓曲線(xiàn)的新方法。人們相信這個(gè)新想法不容易受到量子計(jì)算機(jī)的攻擊。

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

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

SIKE 是一種基于超奇異同源 Diffie-Hellman（SIDH）密鑰交換協(xié)議的基于同源的密碼學(xué)形式?！窼IDH/SIKE 是最早實(shí)用的基于同源的加密協(xié)議之一，」Decru 說(shuō)。

然而 SIKE 的一個(gè)弱點(diǎn)是：為了使其工作，它需要向公眾提供額外的信息，即輔助扭轉(zhuǎn)點(diǎn)?！腹粽邍L試?yán)眠@些額外信息已經(jīng)有一段時(shí)間了，但一直未能成功利用它來(lái)攻破 SIKE，」Moody 說(shuō)。「然而這篇新論文找到了一種方式，他們使用了一些相當(dāng)先進(jìn)的數(shù)學(xué)方法?！?/span>

為了解釋這種新的攻擊，Decru 說(shuō)，雖然橢圓曲線(xiàn)是一維對(duì)象，但在數(shù)學(xué)中，橢圓曲線(xiàn)可以被可視化為二維或任何其他維數(shù)的對(duì)象。人們還可以在這些廣義對(duì)象之間創(chuàng)建同源。

通過(guò)應(yīng)用一個(gè) 25 年前的定理，新的攻擊使用 SIKE 公開(kāi)的額外信息來(lái)構(gòu)建二維的同源。然后這種同源性就可以重建 SIKE 用來(lái)加密消息的密鑰。 

「對(duì)我來(lái)說(shuō)，最令人驚訝的是，這次攻擊似乎是突然冒出來(lái)的」，馬里蘭大學(xué)帕克分校的密碼學(xué)家 Jonathan Katz 說(shuō)道。雖然沒(méi)有參與這項(xiàng)新研究，但他表示：「之前很少有結(jié)果表明 SIKE 有任何弱點(diǎn)，而這次的結(jié)果突然給 SIKE 帶來(lái)了完全毀滅性的攻擊，因?yàn)樗业搅送暾拿荑€，并且是在沒(méi)有任何量子計(jì)算的情況下很快找到的。」

攻擊十多年，破解四分鐘

使用基于上述新攻擊方式的算法，研究人員發(fā)現(xiàn)，一臺(tái)搭載了十年「高齡」CPU（ Intel Xeon CPU E5-2630v2）的臺(tái)式機(jī)最少只需要 4 分鐘就能夠找到由某種 SIKE 算法保護(hù)的密鑰，而攻破被認(rèn)為達(dá)到 NIST 量子安全一級(jí)標(biāo)準(zhǔn)的 SIKE 算法也只用了 62 分鐘。這些實(shí)驗(yàn)都是在 CPU 的一個(gè)核上運(yùn)行的。

「通常，密碼系統(tǒng)受到嚴(yán)重攻擊都發(fā)生在該系統(tǒng)提出之后不久，或者該系統(tǒng)剛開(kāi)始吸引大家注意力的時(shí)候。隨著時(shí)間的推移攻擊逐漸變強(qiáng)，或是顯著削弱系統(tǒng)。但這次的攻擊，沒(méi)有任何前兆，密碼系統(tǒng)突然就被完全攻破。Peikert 說(shuō)：「自 SIDH 被首次提出以來(lái)，對(duì) SIDH/SIKE 的攻擊近 12 年來(lái)幾乎沒(méi)有任何進(jìn)展，直到這次徹底攻破?！?/span>

盡管研究人員已經(jīng)對(duì) SIKE 進(jìn)行了十多年的測(cè)試，但 SIKE 未被選中作為標(biāo)準(zhǔn)的原因之一是人們擔(dān)心它太新且研究還不夠充分。奧克蘭大學(xué)的數(shù)學(xué)家 Steven Galbraith 表示：「人們擔(dān)心 SIKE 可能有被重大襲擊的風(fēng)險(xiǎn)，事實(shí)證明這是對(duì)的。」

那么，為什么直到現(xiàn)在人們才檢測(cè)到 SIKE 的漏洞？Galbraith 認(rèn)為，一個(gè)重要原因是新的攻擊「應(yīng)用了非常高級(jí)的數(shù)學(xué)知識(shí)」。Katz 表示同意，他說(shuō)：「我懷疑世界上只有不到 50 人同時(shí)掌握 PQC 底層的數(shù)學(xué)和必要的密碼學(xué)知識(shí)?！?/span>

此外，PQC 初創(chuàng)公司 Sandbox AQ 的密碼學(xué)家 David Joseph 曾說(shuō)：「無(wú)論是從實(shí)現(xiàn)角度還是從理論角度講，同源問(wèn)題都是『出了名的困難』，這使得其根本性缺陷更有可能在較晚的時(shí)候被發(fā)現(xiàn)?！?/span>

此外，「還應(yīng)該注意的一點(diǎn)是，在 NIST 進(jìn)行幾輪篩審查之前，可供分析的 PQC 算法是非常多的，因此研究精力被攤薄了。而經(jīng)過(guò)幾輪篩選之后，研究人員已經(jīng)能夠?qū)Ｗ⒂谝恍〈樗惴恕！笿oseph 說(shuō)。

SIKE 的發(fā)明者之一、加拿大滑鐵盧大學(xué)教授 David Jao 表示：「我認(rèn)為這項(xiàng)新成果是一項(xiàng)了不起的工作，我對(duì)作者們給予了最高的評(píng)價(jià)。起初，我對(duì) SIKE 的破解感到難過(guò)，因?yàn)樗跀?shù)學(xué)上是一個(gè)如此優(yōu)雅的方案。」

「但新發(fā)現(xiàn)只不過(guò)是反映了科學(xué)的運(yùn)作方式：我們提出了一個(gè)系統(tǒng)，當(dāng)時(shí)每個(gè)人都認(rèn)為它好像還不錯(cuò)，然后經(jīng)過(guò)分析，有人找到了它的弱點(diǎn)。他們花了 10 多年的時(shí)間才找到弱點(diǎn)，這點(diǎn)是不尋常的，但除此之外，這件事并沒(méi)有超出普通科學(xué)進(jìn)展的范圍?！笵avid Jao 補(bǔ)充說(shuō)。

在 Jao 看來(lái)，SIKE 現(xiàn)在被破解是一件好事，畢竟它還沒(méi)有被廣泛部署。

SIKE 被破解意味著什么？

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

不過(guò)，Moody 指出，盡管 SIKE 被破解了，但其他基于同源的密碼系統(tǒng)，如 CSIDH 或 SQIsign，還沒(méi)被破解，「有些人可能以為基于同源的密碼學(xué)已經(jīng)死了，但事實(shí)遠(yuǎn)非如此，我認(rèn)為基于同源的密碼學(xué)還有很多東西要研究，」Decru 表示。

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

那些被 NIST 采納為「標(biāo)準(zhǔn)」或進(jìn)入其第四輪審查的算法都是基于已經(jīng)被密碼學(xué)家研究、分析了很久的數(shù)學(xué)思想，Galbraith 說(shuō)?！高@并不能保證它們是安全的，只是意味著它們經(jīng)受住了更長(zhǎng)時(shí)間的攻擊?！?/span>

Moody 同意這一點(diǎn)，并指出「總是會(huì)發(fā)現(xiàn)一些驚人的突破性結(jié)果來(lái)破解密碼系統(tǒng)。對(duì)于任何密碼系統(tǒng)，我們都沒(méi)有絕對(duì)的安全保證。最好的說(shuō)法是，經(jīng)過(guò)很多聰明人的大量研究，沒(méi)有人發(fā)現(xiàn)該密碼系統(tǒng)有任何漏洞。」

「我們的程序被設(shè)計(jì)為允許攻擊和破解，」Moody 說(shuō)?！肝覀?cè)诿恳惠喸u(píng)估中都見(jiàn)過(guò)它們。這是獲得對(duì)安全的信心的唯一途徑?！?Galbraith 對(duì)此表示贊同，并指出這樣的研究「正在發(fā)揮作用」。

盡管如此，「我覺(jué)得，Rainbow 和 SIKE 的雙雙隕落會(huì)讓更多的人認(rèn)真考慮，是否需要為 NIST 后量子標(biāo)準(zhǔn)化過(guò)程中出現(xiàn)的任何贏(yíng)家制定后備計(jì)劃，」Decru 說(shuō)。「僅僅依靠一個(gè)數(shù)學(xué)概念或方案可能太冒險(xiǎn)了。這也是 NIST 自己的想法——他們的主要方案很可能是基于格密碼學(xué)（lattice-based）的，但他們想要一個(gè)非格密碼學(xué)方案?jìng)溥x?！?/span>

Decru 指出，其他研究者已經(jīng)開(kāi)始開(kāi)發(fā)新版本的 SIDH/SIKE，他們認(rèn)為這可能會(huì)阻止這種新型攻擊。「我預(yù)計(jì)到會(huì)有這樣的結(jié)果，當(dāng)攻擊升級(jí)之后，人們?cè)噲D修補(bǔ) SIDH/SIKE，」Decru 說(shuō)。

總而言之，事實(shí)表明這種新攻擊的起點(diǎn)是一個(gè)「與密碼學(xué)完全無(wú)關(guān)」的定理，并且「揭示了進(jìn)行純數(shù)學(xué)基礎(chǔ)研究以理解密碼系統(tǒng)的重要性」，Galbraith 表示。

Decru 對(duì)此表示同意，并指出「在數(shù)學(xué)中，并非所有東西都能立即適用。有些事情幾乎永遠(yuǎn)不會(huì)適用于任何現(xiàn)實(shí)生活中的情況。但這并不意味著我們不應(yīng)該讓研究導(dǎo)向這些更晦澀的議題。」