最近美國科研圈估計很頭大。
就在上個月美國國家標準與技術研究所（ NIST ）結束了一項為期 6 年的國際競賽，目的是尋找對抗量子計算機的加密演算法。
之所以，有這麼個競賽，實在是加密專業的人的活的太慘，堪比國內的土木專業。
自從量子計算機出現，各個學科都贏麻了，唯獨搞密碼學的崩潰了。
這源於密碼學一向叛逆的定位：別的學科是為了算出一個答案，密碼學是防止別人算出一個答案。
因此，量子計算機直接對密碼學帶來了 「 連根拔起 」 的威脅。
拿最常見的 RSA-2048 演算法舉例，這個演算法是由 2048 位長的加密資訊組成的，即使是最先進超級計算機也需要 3 千萬年才能破解。（ 日本的富嶽超級計算機，計算速度 442 Pflop/s ）
但是量子計算只需要 8 個小時。（ 使用窮舉法，一個一個的試 ）
這就導致量子計算機原則上可以快速破解大多數的加密演算法。
為了應對這種量子層面威脅，世界各地的密碼學家在過去的二十年裡一直在設計用來抵抗量子計算機攻擊的後量子加密演算法，並誕生了相應的演算法競賽。
不過，更戲劇的是，這個競賽剛宣佈結果沒多久，8 強選手之一的 SIKE 演算法，就被人滿血給秒了。
而且，SIKE 演算法是被一臺十年前的桌上型電腦，用單核處理器在 4 分鐘內破解了低安全版本，並在一個小時內破解了該演算法的最強形態。
這有多麻瓜呢？
和 SIKE 安全級別相同的 RSA3068 演算法，用目前最先進的超級計算機破解，（日本的富嶽超級計算機，計算速度 442 Pflop/s。）需要大約 2 萬億年的時間，比宇宙存在的時間都要長。
然而， SIKE 演算法，在一臺 10 年前的英特爾單核桌上型電腦面前，只堅持了一個小時。
一個對抗量子計算機的超級演算法，被桌上型電腦給擊敗了，這離譜程度不亞於哥吉拉（哥斯拉），被咱們的二踢腳給炸飛了。
不過，差評君仔細研究了一下發現：這可能只是一個嚴肅科學界的烏龍事件。
這個名為 SIKE 的演算法之所以 「 一碰就碎 」，還得從演算法的核心說起。
在這個么蛾子之前，SIKE 算的上是 21 世紀的演算法新星了。
這個演算法是一種基於超橢圓曲線的年輕加密演算法。在它誕生的 12 年裡，一直在加強，從未被超越。
它最大的賣點，在超高的價效比上 —— 安全性很高，而且體積還小。
一個由 335 個數字組成的 SIKE 演算法，和由 3068 個數字組成的常用演算法（ RSA 演算法 ），安全性是同一級別的。
這就好像用十進位制來表達二進位制的數字，不僅方便，而且更加簡潔。
在 NIST 收集的 90 多種後量子演算法中，SIKE 及其衍生的演算法佔據了絕對的上風，成為最短後量子密碼中的的前 16 強。
也正是因此，SIKE 演算法一直有不少的擁護者，想要見證和創造歷史。
不過，有趣的是，這個演算法的破解者托馬斯 · 德克魯也是其中之一。
托馬斯是這麼描述他的破解過程的：
一天，托馬斯在和同事沃特 · 卡斯特里克，在研究 SIKE 演算法，試圖用來增強其他密碼的安全性。
結果在研究相關文獻的時候，發現了一篇 1997 年的論文。
論文中，有一個 「 幾乎立即適用於 SIKE 演算法 」 的定理，以至於他們在兩天之內 「 反向加強 」 了 SIKE 演算法，並用桌上型電腦破解了它。
這就邪門了呀，要知道在此之前這個演算法的破解已經 10 年沒有進展了，而托馬斯只用了兩天，甚至還寫出了一個沒有 bug 的破解程序。
不僅是密碼學家，就連程式設計師都得羞愧難當了。
8 月 5 日，他們在一篇論文中記錄了這一神奇的破解方法：
雖然橢圓曲線是一維對象，但在數學中，橢圓曲線可以被視覺化為二維或任何其他維數的對象。人們可以在這些廣義對象之間創建同源。
通過應用一個 25 年前的定理，新的攻擊使用 SIKE 公開的額外資訊來構建二維的同源。然後這種同源性就可以重建 SIKE 用來加密訊息的金鑰。
專業以外的人其實很難理解，這一過程的有趣之處。
做一個不是很恰當的比方：
這個 SIKE 演算法就像一個平面幾何問題（ 也就是二維問題 ），專門用來對抗量子計算機的運算能力，因為平面幾何的難點在於畫輔助線。
讓計算機一條一條地試輔助線，不知道得試到什麼時候去了。
但是 Thomas 將這個圖形三維化了，它變成空間向量座標系的問題。
這樣子，這個問題就可以通過列方程組來解決，這就又回到計算的範疇了。
所以，這一次破解 SIKE 演算法的關鍵，被歸功於數學之神的青睞。
對此，有位密碼學家對這個演算法的破解給予了高度的評價，「 我懷疑：世界上只有不到 50 人掌握了破解 SIKE 演算法必要的數學和密碼學知識。」
當然，我也懷疑這個密碼學家是在強行找回面子。
因為這個問題的破解者，只是一個非著名大學 「 魯汶大學 」 的博士後，甚至不是 NIST 密碼破解組的成員，而是一個業餘愛好者。
也有大佬比較客觀地表示：「 我們應該做好剩下的 7 個選手都被幹掉的準備，畢竟所有的密碼在被破解之前，看起來都很可靠。」
總而言之，自從 1981 年量子計算機的概念被提出以來，演算法的加密和破解之間的戰鬥，比之前的幾千年都要劇烈。
在此之前，密碼學的聖經是：「 想要密碼更安全？簡單加大計算量就行了 」。
相較於計算機運算速度的發展，將加密資訊從 100 位增加到 1000 位，或者是將一種演算法更換成更復雜的演算法，就已經夠用了。
但是，後量子時代要求密碼學家的思維更加開闊。
比如，這次競賽中的另一個種子選手 — 格演算法（ Ring learning with errors ）就是一個格局非常打開的存在。
格演算法看起來比較簡單，像是一個將經典問題放在座標系裡。
但是它這個座標系有些霸道，為了保證安全性，這個座標系的維度常年保持在 1000 維以上。
這就相當於，大家還在做一元二次方程的年紀，你已經在進行 1000 元二次方程的求解了。
同樣是九年義務教育，為啥你這麼優秀呢？
當然，這也只是冰山一角。
過去幾十年，整個密碼學都被量子計算機，這一個沒有落地的概念給唬住了，然後開始拼了命的逃亡。
我們見證了密碼學的崩潰、重構，甚至衍生出了一種理論上無敵的量子密碼，想要找回場子。
科學，真是太 tm 魔幻了。
撰文：及格編輯：面線
圖片、資料來源：
【 後量子密碼 】基於格 ( RLWE ) 問題的金鑰交換協議和原理 知乎
十年桌上型電腦，單核1小時破解後量子加密演算法，密碼學家：太突然了 機器之心
為什麼說量子計算機比超級計算機速度快？ 知乎
【 後量子密碼 】是什麼？為什麼RSA”不行了”？有什麼用？研究和應用現狀如何？ 知乎
「 Quantum-Safe 」 Crypto Hacked by 10-Year-Old PC
Data Is Vulnerable to Quantum Computers That Don’t Exist Yet
‘ Post-Quantum ’ Cryptography Scheme Is Cracked on a Laptop
What Is the Future of Quantum-Proof Encryption?
