只花4 分鐘，就破解了量子加密算法的密鑰。

用的還是一臺有10 年" 高齡 " 的臺式機。

完全破解也只需62 分鐘，CPU 單核即可搞定。

兩位魯汶大學學者基于數學理論破解量子加密算法的消息，最近轟動了密碼學界。

要知道，他們破解的算法SIKE一直以來都被寄予厚望，過去 12 年都無人破解。

在前不久美國公布的后量子標準算法中，它是 4 個候選者之一，后續很可能被加入標準算法中。

而他們使用的方法原理，其實在25 年前就提出了。

這引發了微軟、亞馬遜等多家科技巨頭對 SIKE 的重新調查。

同時也讓不少密碼學大佬開始感慨，理解密碼系統，還是要關注數學基礎理論啊！

如上提到的 SIKE 算法，是一種PQC（后量子計算）算法。

隨著量子計算的出現，很多超大計算量問題迎刃而解，但經典加密算法也受到了威脅。

比如著名的RSA 算法，其 2048 位長的加密信息，超算需要 80 年才能破解，而量子計算暴力破解只要8 個小時。

因此，學界提出后量子密碼的概念，來抵抗量子計算機的破解。

最近，美國國家標準技術研究所（NIST）剛剛公布了首批后量子密碼標準算法，共有 4 個。

SIKE 等另外 4 個算法，被認定為是候補選手，將進入下一輪的篩選。

SIKE的全稱為 Supersingular Isogeny Key Encapsulation。

這是一種利用橢圓曲線作為定理的加密算法，看上去可以由一個 y =x +Ax+B 來表述，其中 A 和 B 是數字。

該方法的關鍵之處是使用了同源（Isogenies），也就是把一條橢圓曲線的點映射到另一條橢圓曲線上。

然后，基于 Supersingular Isogeny Diffie-Hellman ( SIDH ) 密鑰交換協議，實現后量子密鑰封裝。

該方法可以抽象為這樣一個過程：

假設有 Alice 和 Bob 兩方想要秘密交換信息，但是處于一個不安全的環境下。

Alice 和 Bob 可以被理解為是兩個圖（graph），它們有著相同的點，但是邊不同。

其中，每個點代表一條不同的橢圓曲線，如果一條橢圓曲線能以特定方式轉化為另一條橢圓曲線，即在兩點之間畫一條邊，這條邊表示同源關系。

Alice 和 Bob 的邊不同，意味著他們分別由不同的同源關系定義。

現在，Alice 和 Bob 從同一個點出發，每個人沿著自己圖上的邊隨機跳躍，并且跟蹤從一個點到另一個點的路徑。

然后，兩個人公布自己到達的中間點，但是路徑保密。

再然后，二人交換位置，重復自己之前的秘密路徑，這樣一來，二人最后會到達同一個點。

這個終點由于可以被秘密確定，所以可將它作為共享密鑰。

這種加密方式最大的好處在于，即便是攻擊者知道了 Alice 和 Bob 發送給彼此的中間點，也無法得知中間的過程。

更沒法找到最終的終點。

SIDH/SIKE 也被認為是最早被使用的、基于同源的加密協議之一。

但這種方法有個問題，就是它必須對外提供一個輔助扭轉點（auxiliary torsion points），也就是除了 Alice 和 Bob 公開交換位點外的一些信息。

很多破解方法都在嘗試利用這個信息，這次也是如此。

來自比利時魯汶大學的學者們，在 8 月 5 日的一篇論文中詳細解釋了破解方法。

作者 Thomas Decru 表示，雖然橢圓曲線是一維的，但是在數學中，它可以被可視化表示為二維或者任何維度，所以可以在這些廣義對象之間創建映射關系。

Decru 和 Castryck 計算了 Alice 的起點橢圓曲線與公開發給 Bob 的橢圓曲線的乘積，這樣會得到一個阿貝爾曲面。

然后通過一種可以將阿貝爾曲面和橢圓曲線聯系起來的數學定理，以及輔助扭轉點的信息，他們就能找到 Alice 和 Bob 的共享密鑰。

破解中用到的關鍵定理，來自數學家恩斯特 · 卡尼 ( Ernst Kani ) 在1997 年發表的一篇論文。

在實際操作中，研究人員通過一臺已經用了10 年的臺式機，只需 4 分鐘就能找到 SIKE 密鑰。

完全攻破 SIKE 算法也只用了 62 分鐘，而且全程只用了單核。

對此，加密算法專家 Christopher Peikert 表示，一般當一種加密算法被提出后，往往會立刻出現很多破解方法，但是 SIKE 在提出的 12 年來，始終沒有被破解過，直到這次 " 一擊即中 "。

而 SIKE 沒有被選為 PQC 標準，也是因為學界擔心它還沒有被充分研究，有遭受重大攻擊的可能。

這一次，SIKE 被破解的關鍵，被歸功到了對數學理論的應用。

奧克蘭大學的數學家 Steven Galbraith 認為，此次破解中使用的核心理論來自數學。這也在一定程度上驗證了，對于研究密碼學，數學基礎理論的積累非常重要。

SIKE 的提出者之一，加拿大滑鐵盧大學教授 David Jao 肯定了這次工作：

雖然一開始我為 SIKE 被破解感到難過，但這種利用數學的破解方法實在太妙了。

同時，他也為 SIKE 在被大范圍部署前被破解感到慶幸。

不過，雖然 SIKE 被破解了，但是其他使用同源方法加密的方法（CSIDHSQsign）還沒有被破解。

值得一提的是，這不是今年第一個被破解的 PQC 算法。

今年 2 月，多變量算法 Rainbow 也被破解了。

蘇黎世 IBM 研究院的學者 Ward Beullens，用自己的筆記本電腦計算了一個周末（53 個小時），破解了 Rainbow 的密鑰。

這一算法同樣是 NIST PQC 標準算法的候選者之一。