10年老臺式機4分鐘攻破後量子加密演算法，核心原理來自25年前

明敏 發自 凹非寺

量子位 | 公眾號 QbitAI

只花

4分鐘

，就破解了量子加密演算法的金鑰。

用的還是一臺有

10年

“高齡”的桌上型電腦。

完全破解也只需

62分鐘

，CPU單核即可搞定。

兩位魯汶大學學者基於

數學理論

破解量子加密演算法的訊息，最近轟動了密碼學界。

要知道，他們破解的演算法

SIKE

一直以來都被寄予厚望，過去12年都無人破解。

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

而他們使用的方法原理，其實在

25年

前

就提出了。

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

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

一朝破解12年未被攻破的演算法

如上提到的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被破解了，但是其他使用

同源方法

加密的方法（CSIDH\SQsign）還沒有被破解。

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

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

蘇黎世IBM研究院的學者Ward Beullens，用自己的膝上型電腦計算了一個週末（53個小時），破解了Rainbow的金鑰。

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

參考連結：

［1］https：//spectrum。ieee。org/quantum-safe-encryption-hacked

［2］https：//www。degruyter。com/document/doi/10。1515/crll。1997。485。93/html

［3］https：//eprint。iacr。org/2022/214

［4］https：//www。quantamagazine。org/post-quantum-cryptography-scheme-is-cracked-on-a-laptop-20220824/