【世界聚看點】“量子安全”加密解密遭到10年前的電腦攻擊

未來的量子計算機(jī)有可能迅速破解現(xiàn)代密碼。而現(xiàn)在，研究人員發(fā)現(xiàn)，一種有望保護(hù)計算機(jī)免受高級攻擊的算法在短短4分鐘內(nèi)就能被攻破。令人驚奇的是，這只需4分鐘的破解并不是由尖端機(jī)器完成的，而是一臺10年前的傳統(tǒng)臺式計算機(jī)。研究人員表示，這一最新的意外失敗說明，后量子密碼技術(shù)在應(yīng)用之前，還需要克服諸多障礙。

理論上，量子計算機(jī)能夠快速解決傳統(tǒng)計算機(jī)可能需要花上一輩子才能解決的問題，這種差異被作為現(xiàn)代密碼學(xué)的基礎(chǔ)。密碼學(xué)加密機(jī)制的強(qiáng)度來自傳統(tǒng)計算機(jī)很難解決的某些數(shù)學(xué)難題，例如，巨大數(shù)字的因式分解。但是，量子計算機(jī)原則上能夠運行算法，快速破解這類加密。

(相關(guān)資料圖)

為了應(yīng)對這種量子威脅，世界各地的密碼學(xué)家在過去20年里，一直在設(shè)計后量子密碼學(xué)（PQC）算法。這些算法以量子計算機(jī)和傳統(tǒng)計算機(jī)都難以解決的新數(shù)學(xué)問題為基礎(chǔ)。

多年來，美國國家標(biāo)準(zhǔn)技術(shù)研究所等組織的研究人員一直在研究哪種PQC算法能夠成為世界將采用的新標(biāo)準(zhǔn)。2016年，美國國家標(biāo)準(zhǔn)技術(shù)研究所宣布征求候選PQC算法，并在2017年收到82份提交方案。2022年7月，經(jīng)過3輪審查后，美國國家標(biāo)準(zhǔn)技術(shù)研究所公布了4種算法將成為標(biāo)準(zhǔn)，以及另外4種算法將可能作為附加競爭者進(jìn)入另一輪審查。

目前，一項新的研究揭示了一種可完全破解超奇異同源密鑰封裝（SIKE）的方法，SIKE是正在接受審查的競爭者之一（亞馬遜、Cloudflare、微軟和其他公司一直在研究這種算法）。“這一打擊是突然的，子彈是致命的。”并未參與這項新工作的美國密歇根大學(xué)的密碼學(xué)家克里斯托弗?佩科特（Christopher Peikert）說。

SIKE是涉及橢圓曲線的一類PQC算法。“數(shù)學(xué)研究橢圓曲線由來已久?！蔽磪⑴c相關(guān)研究的美國國家標(biāo)準(zhǔn)技術(shù)研究所數(shù)學(xué)家達(dá)斯汀?穆迪（Dustin Moody）說。

穆迪說，1985年，“數(shù)學(xué)家發(fā)現(xiàn)了一種方法，可以建立涉及橢圓曲線密碼系統(tǒng)，而且這些系統(tǒng)得到了廣泛的部署。不過，事實證明，這些橢圓曲線密碼系統(tǒng)很容易被量子計算機(jī)破解。”2010年左右，研究人員發(fā)現(xiàn)了一種在密碼學(xué)中使用橢圓曲線的新方法?！叭藗兿嘈胚@種新的理念不容易被量子計算機(jī)破解?！彼f。

穆迪說，這種新方法的基礎(chǔ)是，如何在橢圓曲線上添加2點，以導(dǎo)出橢圓曲線上的另一個點。“同源”是指從一條橢圓曲線到另一條橢圓曲線的映射保持橢圓曲線加法定律。

“如果讓這種映射足夠復(fù)雜，假設(shè)很難找到兩條給定的橢圓曲線之間同源，就可用于數(shù)據(jù)加密。”比利時魯汶大學(xué)的數(shù)學(xué)密碼學(xué)家托馬斯?德克魯（Thomas Decru）說，他是介紹SIKE破解論文的共同作者之一。

SIKE是一種基于同源的密碼方法，它以超奇異同源Diffie-Hellman（SIDH）密鑰交換協(xié)議為基礎(chǔ)。“SIDH/SIKE是第一批實用的基于同源的密碼協(xié)議。”德克魯說。

不過，SIKE存在一個漏洞：為了能夠工作，它需要公開提供額外的信息，名為輔助扭轉(zhuǎn)點?！肮粽咭恢痹噲D利用額外信息，但未能用它成功破解SIKE?！蹦碌险f，“不過，這篇新的論文（講述了）一種方法，使用相當(dāng)高級的數(shù)學(xué)來破解SIKE?！?/p>

德克魯解釋說，雖然橢圓曲線是二維對象，但在數(shù)學(xué)中，橢圓曲線可以被視為任意維度的對象。人們可以在這些廣義對象之間創(chuàng)建同源。

應(yīng)用一條25年前的定理，這種新破解方法可以使用SIKE公開的額外信息構(gòu)建二維同源。然后，這種同源可以重構(gòu)SIKE用來加密信息的密鑰。2022年8月5日，德克魯和該小組的首席研究員沃特?卡斯特里科（Wouter Castryck）在密碼研究預(yù)印本（Cryptology ePrint Archive）上詳述了他們的發(fā)現(xiàn)。

“最讓我驚訝的是，這種攻擊似乎不知道是從哪里冒出來的。”未參與這項新工作的馬里蘭大學(xué)帕克分校的密碼學(xué)家喬納森?卡茨（Jonathan Katz）說，“之前很少有研究結(jié)果表明SIKE有任何弱點，然后就突然出現(xiàn)了這種完全毀滅性打擊的研究結(jié)果。也就是說，它找到了整個密鑰，而且不需要任何量子計算即可相對快速地破解。”

使用基于這種新型打擊的算法，一臺10年前的英特爾臺式電腦只用了4分鐘就找到了SIKE保護(hù)的密鑰。

“從首次提出SIDH，到完全被攻破，十一二年來對SIDH/SIKE的攻擊實際上毫無進(jìn)展?！迸蹇铺卣f。

SIKE的漏洞直到現(xiàn)在才被發(fā)現(xiàn)的原因是，這種新型攻擊“采用了非常先進(jìn)的數(shù)學(xué)方法，除了攻破系統(tǒng)外，我想不出還有哪些場景下的攻擊會擁有如此深度的數(shù)學(xué)運算?！蔽磪⑴c該研究的新西蘭奧克蘭大學(xué)的數(shù)學(xué)家史蒂文?加爾布雷斯（Steven Galbraith）說，“世界上能夠同時理解這個底層數(shù)學(xué)方法和加密方法的人不足50個?！?/p>

轉(zhuǎn)載內(nèi)容僅代表作者觀點

不代表中科院物理所立場

如需轉(zhuǎn)載請聯(lián)系原公眾號

來源：悅智網(wǎng)

編輯：掃地僧

關(guān)鍵詞： 量子安全加密解密遭到10年前的電腦攻擊 量子計算機(jī)