第一次是比利時魯汶大學(KU Leuven)通過一個名為Magma的程序，在62分鐘的時間內，使用單核處理器，完成了安全級別為level 1的SIKEp434的有效密鑰恢復攻擊。對於具有更高安全級別的SIKEp503 (level 2)、SIKEp610 (level 3)和SIKEp751 (level 5)，分別在2小時19分鐘、8小時15分鐘和21小時37分鐘內被破解。
現在，布里斯托大學團隊在其最新文章《對任意起始曲線的SIDH的攻擊》中[1]再次破解了SIKE：通過一種稱為“撓點”(torsion point)的方法顯著降低了SIKE的安全性。
01
什麼是SIKE？
SIKE全稱Supersingular Isogeny Key Encapsulation(超奇異同源密鑰封裝)，基於超奇異同源Diffie-Hellman（SIDH）協議，2011年由David Jao提出，它利用了橢圓曲線之間的同源性。
如下圖所示，如果我們有兩條橢圓曲線(E1和E2)，我們可以創建一個函數，將E1上的點(P)映射到E2上的點Q。這個函數被稱為同源。如果我們能映射這個函數，E1上的每一點都可以映射到E2。秘密密鑰是同源的，公開密鑰是橢圓曲線。對於密鑰交換，Alice和Bob互相將其同源曲線混合，以生成一條秘密曲線。
SIDH的安全性與尋找兩條具有相同點數的超奇異橢圓曲線之間的同源映射問題密切相關。
以SKIE為例來說明上圖中的密鑰交換，首先，Alice和Bob從同一條曲線(E0)開始，然後他們隨機離開曲線。這就產生了EA(Alice曲線)和EB(Bob曲線)。Alice和Bob相互把他們的曲線發給對方。然後，Alice再次從EB開始隨機行走，並重復她的隨機行走。Bob從EA開始行走，重複他的隨機行走，然後最終在一條新的秘密曲線處相遇。這是一條只有他們知道的曲線，他們可以用它來創建一個新的密鑰，因為沒有人知道這條曲線，除非他們知道Bob、Alice的隨機行走。
02
什麼是撓點？
所謂撓點，假設有兩個點P、Q，那麼PQ連線與曲線的第三個交點R對x軸的鏡像點，就是P+Q。因為橢圓曲線是上下對稱的，所以P+Q也一定在曲線上。
那麼P點和它自己相加（P+P）怎麼計算？想象一下Q點越來越靠近P點，最後PQ兩點的連線就變成P點處的切線，所以P+P就是這個切線與橢圓曲線交點的鏡像點。如果P點反覆加上自己，經過有限次加法後（P+P+……+P）又回到P點，那麼P就叫做“撓點”（torsion point）。
03
針對SIKE的攻擊
SIKE的破解難度依賴於“超奇異同源問題”(SSI)，也就是前文所說在兩個給定的超奇異橢圓曲線之間找到某種映射（稱為同源）。這是一個已經分析了10多年的問題。但與純粹依靠同源問題的密碼系統相比，SIKE的難度假設較弱，因為秘密同源下的一些撓點的圖像也被揭示，從而產生了下面更精確地描述的超奇異同源撓率（SSI-T）問題。
布里斯托大學團隊最新提出的算法可以在合理的時間內解決SSI-T問題，而不需要預先知道任何關於起始曲線的相關屬性。
這大大降低了SIDH和SIKE的安全性，最重要的是，這意味著在經典計算機上就可以破解算法，根本不需要量子計算機。
SSI-T問題的數學解釋。給出共素整數A和B，兩條超等橢圓曲線E0/Fp2和EA/Fp2由一個未知程度的A-同源φA：E0→EA連接，並給出φ對E0（起始曲線）的B-扭轉的限制，恢復一個同源體φ與這些限制匹配。
針對這些威脅，SIKE的主要提出者David Jao表示[2]：“對SIKE的攻擊雖然對SIKE來說不是好消息，但它是一個積極的信號，表明研究界正在認真對待這一挑戰。如果研究界仍然沒有達成共識，那麼這本身就表明SIKE還沒有準備好被標準化。這個結果沒有任何問題。事實上，從研究的角度來看，它可能是最令人興奮的應用場景。但NIST的PQC標準化需要穩定性。”
參考鏈接：
[1]https://eprint.iacr.org/2022/1026.pdf
[2]https://www.fedscoop.com/cracked-nist-cryptography-candidate-has-time/