天天微頭條丨專克量子計(jì)算機(jī)的超級(jí)密碼 被10年前的老爺機(jī)干碎了

最近美國科研圈估計(jì)很頭大。就在上個(gè)月美國國家標(biāo)準(zhǔn)與技術(shù)研究所（ NIST ）結(jié)束了一項(xiàng)為期 6 年的國際競賽，目的是尋找對(duì)抗量子計(jì)算機(jī)的加密算法。之所以，有這么個(gè)競賽，實(shí)在是加密專業(yè)的人的活的太慘，堪比國內(nèi)的土木專業(yè)。自從量子計(jì)算機(jī)出現(xiàn)，各個(gè)學(xué)科都贏麻了，唯獨(dú)搞密碼學(xué)的崩潰了。

(資料圖片)

訪問：

阿里云1核2G云服務(wù)器低至1折 最高可得500元滿減優(yōu)惠券

這源于密碼學(xué)一向叛逆的定位：別的學(xué)科是為了算出一個(gè)答案，密碼學(xué)是防止別人算出一個(gè)答案。

因此，量子計(jì)算機(jī)直接對(duì)密碼學(xué)帶來了 “ 連根拔起 ” 的威脅。

拿最常見的 RSA-2048 算法舉例，這個(gè)算法是由 2048 位長的加密信息組成的，即使是最先進(jìn)超級(jí)計(jì)算機(jī)也需要 3 千萬年才能破解。（ 日本的富岳超級(jí)計(jì)算機(jī)，計(jì)算速度 442 Pflop/s ）

但是量子計(jì)算只需要 8 個(gè)小時(shí)。（ 使用窮舉法，一個(gè)一個(gè)的試 ）

這就導(dǎo)致量子計(jì)算機(jī)原則上可以快速破解大多數(shù)的加密算法。

為了應(yīng)對(duì)這種量子層面威脅，世界各地的密碼學(xué)家在過去的二十年里一直在設(shè)計(jì)用來抵抗量子計(jì)算機(jī)攻擊的后量子加密算法，并誕生了相應(yīng)的算法競賽。

不過，更戲劇的是，這個(gè)競賽剛宣布結(jié)果沒多久，8 強(qiáng)選手之一的 SIKE 算法，就被人滿血給秒了。

而且，SIKE 算法是被一臺(tái)十年前的臺(tái)式機(jī)，用單核處理器在 4 分鐘內(nèi)破解了低安全版本，并在一個(gè)小時(shí)內(nèi)破解了該算法的最強(qiáng)形態(tài)。

這有多麻瓜呢？

和 SIKE 安全級(jí)別相同的 RSA3068 算法，用目前最先進(jìn)的超級(jí)計(jì)算機(jī)破解，（日本的富岳超級(jí)計(jì)算機(jī)，計(jì)算速度 442 Pflop/s。）需要大約 2 萬億年的時(shí)間，比宇宙存在的時(shí)間都要長。

然而， SIKE 算法，在一臺(tái) 10 年前的英特爾單核臺(tái)式機(jī)面前，只堅(jiān)持了一個(gè)小時(shí)。

一個(gè)對(duì)抗量子計(jì)算機(jī)的超級(jí)算法，被臺(tái)式機(jī)給擊敗了，這離譜程度不亞于哥斯拉，被咱們的二踢腳給炸飛了。

不過，差評(píng)君仔細(xì)研究了一下發(fā)現(xiàn)：這可能只是一個(gè)嚴(yán)肅科學(xué)界的烏龍事件。

這個(gè)名為 SIKE 的算法之所以 “ 一碰就碎 ”，還得從算法的內(nèi)核說起。

在這個(gè)幺蛾子之前，SIKE 算的上是 21 世紀(jì)的算法新星了。這個(gè)算法是一種基于超橢圓曲線的年輕加密算法。在它誕生的 12 年里，一直在加強(qiáng)，從未被超越。

它最大的賣點(diǎn)，在超高的性價(jià)比上 —— 安全性很高，而且體積還小。

一個(gè)由 335 個(gè)數(shù)字組成的 SIKE 算法，和由 3068 個(gè)數(shù)字組成的常用算法（ RSA 算法 ），安全性是同一級(jí)別的。

這就好像用十進(jìn)制來表達(dá)二進(jìn)制的數(shù)字，不僅方便，而且更加簡潔。

在 NIST 收集的 90 多種后量子算法中，SIKE 及其衍生的算法占據(jù)了絕對(duì)的上風(fēng)，成為最短后量子密碼中的的前 16 強(qiáng)。

也正是因此，SIKE 算法一直有不少的擁護(hù)者，想要見證和創(chuàng)造歷史。

不過，有趣的是，這個(gè)算法的破解者托馬斯 · 德克魯也是其中之一。

托馬斯是這么描述他的破解過程的：

一天，托馬斯在和同事沃特 · 卡斯特里克，在研究 SIKE 算法，試圖用來增強(qiáng)其他密碼的安全性。

結(jié)果在研究相關(guān)文獻(xiàn)的時(shí)候，發(fā)現(xiàn)了一篇 1997 年的論文。

論文中，有一個(gè) “ 幾乎立即適用于 SIKE 算法 ” 的定理，以至于他們?cè)趦商熘畠?nèi) “ 反向加強(qiáng) ” 了 SIKE 算法，并用臺(tái)式機(jī)破解了它。

這就邪門了呀，要知道在此之前這個(gè)算法的破解已經(jīng) 10 年沒有進(jìn)展了，而托馬斯只用了兩天，甚至還寫出了一個(gè)沒有 bug 的破解程序。

不僅是密碼學(xué)家，就連程序員都得羞愧難當(dāng)了。

8 月 5 日，他們?cè)谝黄撐闹杏涗浟诉@一神奇的破解方法：

雖然橢圓曲線是一維對(duì)象，但在數(shù)學(xué)中，橢圓曲線可以被可視化為二維或任何其他維數(shù)的對(duì)象。人們可以在這些廣義對(duì)象之間創(chuàng)建同源。

通過應(yīng)用一個(gè) 25 年前的定理，新的攻擊使用 SIKE 公開的額外信息來構(gòu)建二維的同源。然后這種同源性就可以重建 SIKE 用來加密消息的密鑰。

專業(yè)以外的人其實(shí)很難理解，這一過程的有趣之處。

做一個(gè)不是很恰當(dāng)?shù)谋确剑?/p>

這個(gè) SIKE 算法就像一個(gè)平面幾何問題（ 也就是二維問題 ），專門用來對(duì)抗量子計(jì)算機(jī)的運(yùn)算能力，因?yàn)槠矫鎺缀蔚碾y點(diǎn)在于畫輔助線。讓計(jì)算機(jī)一條一條地試輔助線，不知道得試到什么時(shí)候去了。但是 Thomas 將這個(gè)圖形三維化了，它變成空間向量坐標(biāo)系的問題。

這樣子，這個(gè)問題就可以通過列方程組來解決，這就又回到計(jì)算的范疇了。

所以，這一次破解 SIKE 算法的關(guān)鍵，被歸功于數(shù)學(xué)之神的青睞。

對(duì)此，有位密碼學(xué)家對(duì)這個(gè)算法的破解給予了高度的評(píng)價(jià)，“ 我懷疑：世界上只有不到 50 人掌握了破解 SIKE 算法必要的數(shù)學(xué)和密碼學(xué)知識(shí)。”

當(dāng)然，我也懷疑這個(gè)密碼學(xué)家是在強(qiáng)行找回面子。

因?yàn)檫@個(gè)問題的破解者，只是一個(gè)非著名大學(xué) “ 魯汶大學(xué) ” 的博士后，甚至不是 NIST 密碼破解組的成員，而是一個(gè)業(yè)余愛好者。

也有大佬比較客觀地表示：“ 我們應(yīng)該做好剩下的 7 個(gè)選手都被干掉的準(zhǔn)備，畢竟所有的密碼在被破解之前，看起來都很可靠。”

總而言之，自從 1981 年量子計(jì)算機(jī)的概念被提出以來，算法的加密和破解之間的戰(zhàn)斗，比之前的幾千年都要?jiǎng)×摇?/strong>

在此之前，密碼學(xué)的圣經(jīng)是：“ 想要密碼更安全？簡單加大計(jì)算量就行了 ”。

相較于計(jì)算機(jī)運(yùn)算速度的發(fā)展，將加密信息從 100 位增加到 1000 位，或者是將一種算法更換成更復(fù)雜的算法，就已經(jīng)夠用了。但是，后量子時(shí)代要求密碼學(xué)家的思維更加開闊。

比如，這次競賽中的另一個(gè)種子選手 -- 格算法（ Ring learning with errors ）就是一個(gè)格局非常打開的存在。格算法看起來比較簡單，像是一個(gè)將經(jīng)典問題放在坐標(biāo)系里。

但是它這個(gè)坐標(biāo)系有些霸道，為了保證安全性，這個(gè)坐標(biāo)系的維度常年保持在 1000 維以上。這就相當(dāng)于，大家還在做一元二次方程的年紀(jì)，你已經(jīng)在進(jìn)行 1000 元二次方程的求解了。

同樣是九年義務(wù)教育，為啥你這么優(yōu)秀呢？當(dāng)然，這也只是冰山一角。

過去幾十年，整個(gè)密碼學(xué)都被量子計(jì)算機(jī)，這一個(gè)沒有落地的概念給唬住了，然后開始拼了命的逃亡。我們見證了密碼學(xué)的崩潰、重構(gòu)，甚至衍生出了一種理論上無敵的量子密碼，想要找回場子。科學(xué)，真是太 tm 魔幻了。