單核CPU一小時破解后量子加密候選算法

使用運行英特爾至強 CPU 的計算機在一小時內輕松破解了一種后期候選加密算法，該算法旨在抵御未來強大的量子計算機的解密。

有問題的算法是 SIKE——Supersingular Isogeny Key Encapsulation 的縮寫——它進入了美國商務部國家標準與技術研究院 (NIST)的第四輪后量子密碼學 (PQC) 標準化過程。

“在單核上運行，附加的Magma 代碼分別在大約 4 分鐘和 6 分鐘內打破了 Microsoft SIKE 挑戰$IKEp182 和 $IKEp217，”KU Leuven 研究人員 Wouter Castryck 和 Thomas Decru在一篇新論文中說。

“SIKEp434 參數的運行，以前被認為符合 NIST 的量子安全級別 1，大約需要 62 分鐘，再次在單個核心上運行。”

學者們進一步指出，該代碼是在 2.60GHz 的 Intel Xeon CPU E5-2630v2上執行的，該 CPU于 2013 年使用芯片制造商的 Ivy Bridge 微架構發布。

NIST 在 7 月初宣布了第一套抗量子加密算法：用于通用加密的 CRYSTALS-Kyber，以及用于數字簽名的 CRYSTALS-Dilithium、FALCON 和 SPHINCS+。

“SIKE 是一種基于同源的密鑰封裝套件，它基于超奇異同源圖中的偽隨機游走，”算法作者的描述中寫道。

微軟是該算法的主要合作者之一，它表示 SIKE使用“在有限域上定義的橢圓曲線上的算術運算，并計算這些曲線之間的映射，即所謂的同源性”。

“SIDH 和 SIKE 的安全性取決于在兩條這樣的橢圓曲線之間找到特定同源的難度，或者等效地，在同源圖中找到它們之間的路徑的難度，”這家科技巨頭的研究團隊解釋道。

抗量子密碼學是一種嘗試開發對量子和傳統計算系統都安全的加密系統，同時還可以與現有的通信協議和網絡進行互操作。

這個想法是為了確保今天使用當前算法加密的數據，如RSA、橢圓曲線加密 ( ECC )、AES和ChaCha20，在未來隨著量子計算機的出現不會容易受到暴力攻擊。

“這些系統中的每一個都依賴于某種數學問題，這在一個方向上很容易解決，但反過來卻很難，”SIKE 的共同發明者之一、evolutionQ 的首席密碼學家 David Jao 告訴黑客新聞。

“量子計算機可以輕松解決 RSA 和 ECC 背后的難題，如果要構建量子計算機，這將影響大約 100% 的加密互聯網流量。”

雖然 SIKE 被定位為 NIST 指定的 PQC 競爭者之一，但最新研究有效地使該算法無效。

“Castryck 和 Decru 的作品打破了 SIKE，”Jao 說。“具體來說，它打破了SIDH [Supersingular Isogeny Diffie-Hellman]，這是 SIKE 所基于的‘難題’（類似于整數分解是 RSA 所基于的難題）。”

“除了 SIKE 之外，還有其他基于同源的密碼系統。其中一些，例如B-SIDH，也是基于 SIDH 的，也被新的攻擊破解了。其中一些，例如CSIDH和SQIsign，不是基于在 SIDH 上，據我們所知，并沒有直接受到新攻擊的影響。”

至于接下來的步驟，Jao 表示，雖然可以更新 SIDH 以修復密鑰恢復攻擊的新線路，但預計將推遲到進一步檢查。

“有可能對 SIDH 進行修補或修復以避免新的攻擊，我們對如何做到這一點有一些想法，但在我們可以自信地就任何可能的修復發表聲明之前，需要對新攻擊進行更多分析， ”喬說。