只花 4 分鐘，就破解了量子加密算法的密鑰。用的還是一臺(tái)有 10 年“高齡”的臺(tái)式機(jī)。完全破解也只需 62 分鐘，CPU 單核即可搞定。
兩位魯汶大學(xué)學(xué)者基于數(shù)學(xué)理論破解量子加密算法的消息，最近轟動(dòng)了密碼學(xué)界。要知道，他們破解的算法 SIKE 一直以來都被寄予厚望，過去 12 年都無人破解。
在前不久美國公布的后量子標(biāo)準(zhǔn)算法中，它是 4 個(gè)候選者之一，后續(xù)很可能被加入標(biāo)準(zhǔn)算法中。而他們使用的方法原理，其實(shí)在 25 年前就提出了。這引發(fā)了微軟、亞馬遜等多家科技巨頭對 SIKE 的重新調(diào)查。
同時(shí)也讓不少密碼學(xué)大佬開始感慨，理解密碼系統(tǒng)，還是要關(guān)注數(shù)學(xué)基礎(chǔ)理論??！
一朝破解 12 年未被攻破的算法
如上提到的 SIKE 算法，是一種 PQC（后量子計(jì)算）算法。隨著量子計(jì)算的出現(xiàn)，很多超大計(jì)算量問題迎刃而解，但經(jīng)典加密算法也受到了威脅。比如著名的 RSA 算法，其 2048 位長的加密信息，超算需要 80 年才能破解，而量子計(jì)算暴力破解只要 8 個(gè)小時(shí)。因此，學(xué)界提出后量子密碼的概念，來抵抗量子計(jì)算機(jī)的破解。
最近，美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）剛剛公布了首批后量子密碼標(biāo)準(zhǔn)算法，共有 4 個(gè)。SIKE 等另外 4 個(gè)算法，被認(rèn)定為是候補(bǔ)選手，將進(jìn)入下一輪的篩選。SIKE 的全稱為 Supersingular Isogeny Key Encapsulation。這是一種利用橢圓曲線作為定理的加密算法，看上去可以由一個(gè) y2=x3+Ax+B 來表述，其中 A 和 B 是數(shù)字。
該方法的關(guān)鍵之處是使用了同源（Isogenies），也就是把一條橢圓曲線的點(diǎn)映射到另一條橢圓曲線上。然后，基于 Supersingular Isogeny Diffie-Hellman (SIDH) 密鑰交換協(xié)議，實(shí)現(xiàn)后量子密鑰封裝。
該方法可以抽象為這樣一個(gè)過程：假設(shè)有 Alice 和 Bob 兩方想要秘密交換信息，但是處于一個(gè)不安全的環(huán)境下。
Alice 和 Bob 可以被理解為是兩個(gè)圖（graph），它們有著相同的點(diǎn)，但是邊不同。其中，每個(gè)點(diǎn)代表一條不同的橢圓曲線，如果一條橢圓曲線能以特定方式轉(zhuǎn)化為另一條橢圓曲線，即在兩點(diǎn)之間畫一條邊，這條邊表示同源關(guān)系。
Alice 和 Bob 的邊不同，意味著他們分別由不同的同源關(guān)系定義?，F(xiàn)在，Alice 和 Bob 從同一個(gè)點(diǎn)出發(fā)，每個(gè)人沿著自己圖上的邊隨機(jī)跳躍，并且跟蹤從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的路徑。然后，兩個(gè)人公布自己到達(dá)的中間點(diǎn)，但是路徑保密。再然后，二人交換位置，重復(fù)自己之前的秘密路徑，這樣一來，二人最后會(huì)到達(dá)同一個(gè)點(diǎn)。這個(gè)終點(diǎn)由于可以被秘密確定，所以可將它作為共享密鑰。
這種加密方式最大的好處在于，即便是攻擊者知道了 Alice 和 Bob 發(fā)送給彼此的中間點(diǎn)，也無法得知中間的過程。更沒法找到最終的終點(diǎn)。SIDH / SIKE 也被認(rèn)為是最早被使用的、基于同源的加密協(xié)議之一。
但這種方法有個(gè)問題，就是它必須對外提供一個(gè)輔助扭轉(zhuǎn)點(diǎn)（auxiliary torsion points），也就是除了 Alice 和 Bob 公開交換位點(diǎn)外的一些信息。
很多破解方法都在嘗試?yán)眠@個(gè)信息，這次也是如此。來自比利時(shí)魯汶大學(xué)的學(xué)者們，在 8 月 5 日的一篇論文中詳細(xì)解釋了破解方法。
作者 Thomas Decru 表示，雖然橢圓曲線是一維的，但是在數(shù)學(xué)中，它可以被可視化表示為二維或者任何維度，所以可以在這些廣義對象之間創(chuàng)建映射關(guān)系。
Decru 和 Castryck 計(jì)算了 Alice 的起點(diǎn)橢圓曲線與公開發(fā)給 Bob 的橢圓曲線的乘積，這樣會(huì)得到一個(gè)阿貝爾曲面。然后通過一種可以將阿貝爾曲面和橢圓曲線聯(lián)系起來的數(shù)學(xué)定理，以及輔助扭轉(zhuǎn)點(diǎn)的信息，他們就能找到 Alice 和 Bob 的共享密鑰。破解中用到的關(guān)鍵定理，來自數(shù)學(xué)家恩斯特?卡尼 (Ernst Kani) 在 1997 年發(fā)表的一篇論文。
在實(shí)際操作中，研究人員通過一臺(tái)已經(jīng)用了 10 年的臺(tái)式機(jī)，只需 4 分鐘就能找到 SIKE 密鑰。完全攻破 SIKE 算法也只用了 62 分鐘，而且全程只用了單核。
對此，加密算法專家 Christopher Peikert 表示，一般當(dāng)一種加密算法被提出后，往往會(huì)立刻出現(xiàn)很多破解方法，但是 SIKE 在提出的 12 年來，始終沒有被破解過，直到這次“一擊即中”。而 SIKE 沒有被選為 PQC 標(biāo)準(zhǔn)，也是因?yàn)閷W(xué)界擔(dān)心它還沒有被充分研究，有遭受重大攻擊的可能。
這一次，SIKE 被破解的關(guān)鍵，被歸功到了對數(shù)學(xué)理論的應(yīng)用。
奧克蘭大學(xué)的數(shù)學(xué)家 Steven Galbraith 認(rèn)為，此次破解中使用的核心理論來自數(shù)學(xué)。這也在一定程度上驗(yàn)證了，對于研究密碼學(xué)，數(shù)學(xué)基礎(chǔ)理論的積累非常重要。
SIKE 的提出者之一，加拿大滑鐵盧大學(xué)教授 David Jao 肯定了這次工作：雖然一開始我為 SIKE 被破解感到難過，但這種利用數(shù)學(xué)的破解方法實(shí)在太妙了。同時(shí)，他也為 SIKE 在被大范圍部署前被破解感到慶幸。
不過，雖然 SIKE 被破解了，但是其他使用同源方法加密的方法（CSIDH\SQsign）還沒有被破解。
值得一提的是，這不是今年第一個(gè)被破解的 PQC 算法。今年 2 月，多變量算法 Rainbow 也被破解了。蘇黎世 IBM 研究院的學(xué)者 Ward Beullens，用自己的筆記本電腦計(jì)算了一個(gè)周末（53 個(gè)小時(shí)），破解了 Rainbow 的密鑰。這一算法同樣是 NIST PQC 標(biāo)準(zhǔn)算法的候選者之一。
參考鏈接：
[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/
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。