“量子安全”加密解密遭到10年前的電腦攻擊

未來的量子計算機有可能迅速破解現代密碼。而現在，研究人員發現，一種有望保護計算機免受進階攻擊的算法在短短4分鐘内就能被攻破。令人驚奇的是，這隻需4分鐘的破解并不是由尖端機器完成的，而是一台10年前的傳統台式計算機。研究人員表示，這一最新的意外失敗說明，後量子密碼技術在應用之前，還需要克服諸多障礙。

理論上，量子計算機能夠快速解決傳統計算機可能需要花上一輩子才能解決的問題，這種差異被作為現代密碼學的基礎。密碼學加密機制的強度來自傳統計算機很難解決的某些數學難題，例如，巨大數字的因式分解。但是，量子計算機原則上能夠運作算法，快速破解這類加密。

為了應對這種量子威脅，世界各地的密碼學家在過去20年裡，一直在設計後量子密碼學（PQC）算法。這些算法以量子計算機和傳統計算機都難以解決的新數學問題為基礎。

多年來，美國國家标準技術研究所等組織的研究人員一直在研究哪種PQC算法能夠成為世界将采用的新标準。2016年，美國國家标準技術研究所宣布征求候選PQC算法，并在2017年收到82份送出方案。2022年7月，經過3輪審查後，美國國家标準技術研究所公布了4種算法将成為标準，以及另外4種算法将可能作為附加競争者進入另一輪審查。

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

SIKE是涉及橢圓曲線的一類PQC算法。“數學研究橢圓曲線由來已久。”未參與相關研究的美國國家标準技術研究所數學家達斯汀•穆迪（Dustin Moody）說。

穆迪說，1985年，“數學家發現了一種方法，可以建立涉及橢圓曲線密碼系統，而且這些系統得到了廣泛的部署。不過，事實證明，這些橢圓曲線密碼系統很容易被量子計算機破解。”2010年左右，研究人員發現了一種在密碼學中使用橢圓曲線的新方法。“人們相信這種新的理念不容易被量子計算機破解。”他說。

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

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

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

不過，SIKE存在一個漏洞：為了能夠工作，它需要公開提供額外的資訊，名為輔助扭轉點。“攻擊者一直試圖利用額外資訊，但未能用它成功破解SIKE。”穆迪說，“不過，這篇新的論文（講述了）一種方法，使用相當進階的數學來破解SIKE。”

德克魯解釋說，雖然橢圓曲線是二維對象，但在數學中，橢圓曲線可以被視為任意次元的對象。人們可以在這些廣義對象之間建立同源。

應用一條25年前的定理，這種新破解方法可以使用SIKE公開的額外資訊建構二維同源。然後，這種同源可以重構SIKE用來加密資訊的密鑰。2022年8月5日，德克魯和該小組的首席研究員沃特•卡斯特裡科（Wouter Castryck）在密碼研究預印本（Cryptology ePrint Archive）上詳述了他們的發現。

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

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

“從首次提出SIDH，到完全被攻破，十一二年來對SIDH/SIKE的攻擊實際上毫無進展。”佩科特說。

SIKE的漏洞直到現在才被發現的原因是，這種新型攻擊“采用了非常先進的數學方法，除了攻破系統外，我想不出還有哪些場景下的攻擊會擁有如此深度的數學運算。”未參與該研究的紐西蘭奧克蘭大學的數學家史蒂文•加爾布雷斯（Steven Galbraith）說，“世界上能夠同時了解這個底層數學方法和加密方法的人不足50個。”

轉載内容僅代表作者觀點

不代表中科院實體所立場

如需轉載請聯系原公衆号

來源：悅智網

編輯：掃地僧