“量子年”時鐘逼近，現(xiàn)代密碼技術(shù)面臨破解威脅，如何保護(hù)今天的秘密？

“量子年”時鐘目前被設(shè)置在2030年4月14日，其對應(yīng)的是通用量子計(jì)算機(jī)可以攻破公鑰加密技術(shù)的預(yù)計(jì)日期。

在網(wǎng)絡(luò)信息傳輸過程中，公鑰密碼算法是最重要的技術(shù)保障，也是互聯(lián)網(wǎng)時代網(wǎng)絡(luò)信息安全的基石。然而，隨著量子計(jì)算機(jī)技術(shù)的迅猛發(fā)展，公鑰加密技術(shù)正面臨巨大安全威脅。為了提醒人們關(guān)注這一巨大隱患，數(shù)字安全專家設(shè)立了“量子年”時鐘，其代表的量子計(jì)算機(jī)攻破現(xiàn)代密碼技術(shù)的日期正在不斷提前。

站在這場新技術(shù)變革的邊緣，發(fā)展“后量子密碼”變得刻不容緩。美國國家標(biāo)準(zhǔn)與技術(shù)研究院自2016年12月起發(fā)出后量子密碼學(xué)標(biāo)準(zhǔn)化流程的公開征集，今年將有三種新算法標(biāo)準(zhǔn)投入使用，各類系統(tǒng)將開始向后量子密碼技術(shù)切換。不過，問題似乎還未就此解決�？茖W(xué)家仍在不懈努力，希望“量子年”危機(jī)能像“千年蟲”危機(jī)一樣順利渡過。

——編者

如果有一臺計(jì)算機(jī)，能在眨眼間解決當(dāng)今速度最快的超級計(jì)算機(jī)也無法解決的數(shù)學(xué)問題；如果有一種技術(shù)，可以讓觀察者透過墻壁看到墻后的事物，或者看到最黑暗的海洋世界深處，還可以在構(gòu)建完全不可攻破的網(wǎng)絡(luò)的同時，破解對手最機(jī)密的數(shù)據(jù)——這就是量子計(jì)算機(jī)和量子技術(shù)。今后幾十年甚至幾個世紀(jì)內(nèi)，它們將重新界定全球信息技術(shù)的未來。

當(dāng)這一天到來，當(dāng)前廣泛使用的加密技術(shù)將在量子計(jì)算機(jī)面前不堪一擊。為此，全世界的數(shù)字安全專家都在關(guān)注“量子年”（Years to Quantum，Y2Q）時鐘，它指向的時間對應(yīng)的是通用量子計(jì)算機(jī)可以攻破非對稱加密技術(shù)（現(xiàn)代密碼學(xué)的一種重要加密形式）的預(yù)計(jì)日期。

非對稱加密技術(shù)又稱公鑰加密技術(shù)，因能在公開場合共享密碼而得名。這種加密技術(shù)可以保證網(wǎng)上購物時信用卡的安全，也可確保手機(jī)軟件更新來自手機(jī)公司而非黑客。但是，量子計(jì)算機(jī)會讓目前廣泛使用的公鑰加密技術(shù)形同虛設(shè)。

“量子年”時鐘

傳統(tǒng)密碼“最后期限”將至

云安全聯(lián)盟（CSA）量子安全工作組聯(lián)合主席布魯諾·胡特納說，如果明天就有一臺量子計(jì)算機(jī)出現(xiàn)，那所有人都將無法找到一種安全的方式在一起交談，“這確實(shí)非常嚴(yán)重”。

胡特納是Y2Q時鐘的創(chuàng)造者之一。Y2Q時鐘的命名是為了紀(jì)念那個可能導(dǎo)致計(jì)算機(jī)崩潰但最終在技術(shù)人員努力下得以避免的Y2K（千年蟲）危機(jī)。這一危機(jī)之所以得以天衣無縫地順利渡過，主要是因?yàn)槠髽I(yè)和政府都在抓緊時間，及時修復(fù)了“千年蟲”。

與“千年蟲”危機(jī)不同的是，沒有人確切知道，足以打破現(xiàn)有密碼標(biāo)準(zhǔn)的量子計(jì)算機(jī)何時才能研制成功。目前，Y2Q時鐘的結(jié)束日期被設(shè)置在2030年4月14日。但這只是一個猜測，胡特納說，“Y2Q時鐘是一個提醒，有助于引起人們的關(guān)注。”

實(shí)際上，對保密有長期需求的政府及相關(guān)機(jī)構(gòu)來說，真正的“最后期限”會比Y2Q時鐘設(shè)定的早很多年到來——如果今天發(fā)送的加密數(shù)據(jù)被存儲起來，那么未來的量子計(jì)算機(jī)就可追溯性地解密這些信息。

美國密歇根大學(xué)的計(jì)算機(jī)科學(xué)家克里斯-佩克特說，如果一些信息需要保密20年，破解這種加密技術(shù)的量子計(jì)算機(jī)可能在20年內(nèi)出現(xiàn)，那么現(xiàn)在為這些信息加密時，就不得不考慮這個問題了。

正是預(yù)見到了這種威脅，美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）于2016年12月發(fā)起了公開競賽，征集“后量子”或“抗量子”密碼學(xué)方案——這些密碼可以在目前使用的計(jì)算機(jī)上運(yùn)行，但卻可以強(qiáng)大到連量子計(jì)算機(jī)也無法破解。

經(jīng)過四輪提交和評審，NIST最終于2022年7月選定了四種算法作為“后量子密碼學(xué)”標(biāo)準(zhǔn)化流程的成果，其中公鑰封裝機(jī)制為CRYSTALS—Kyber，數(shù)字簽名方案為CRYSTALS—Dilithium、FALCON和SPHINCS+。NIST正在與研究人員合作，將獲獎算法標(biāo)準(zhǔn)化，以便程序員可以此為基礎(chǔ)，研發(fā)能夠抵御量子計(jì)算機(jī)的密碼技術(shù)。

專家們確信，它們肯定都是非常難以破解的，但誰也不能保證未來的量子計(jì)算機(jī)不會破解它們。

經(jīng)典計(jì)算機(jī)運(yùn)行的是一長串0和1，被稱為“比特”，而量子計(jì)算機(jī)使用的是可以處于疊加狀態(tài)的“量子比特”——通過在0和1這兩種狀態(tài)之間徘徊，量子計(jì)算機(jī)能夠以比經(jīng)典計(jì)算機(jī)快得多的速度執(zhí)行某些任務(wù)。

現(xiàn)在的量子計(jì)算機(jī)看起來就像巨大的金色吊燈一樣懸掛在天花板上——令人印象深刻，但功能卻還不夠強(qiáng)大�？茖W(xué)家們只能控制數(shù)量不多的量子比特進(jìn)行計(jì)算。2012年，英國布里斯托爾大學(xué)的研究人員利用量子計(jì)算機(jī)推算出21是7的3倍。

盡管如此，許多專家還是認(rèn)為，足以破解目前使用最廣泛的RSA和迪菲-赫爾曼這兩種加密算法的量子計(jì)算機(jī)，將在未來幾十年內(nèi)問世，不過時間線還不確定。

第六屆進(jìn)博會中國館展出的可編程量子計(jì)算系統(tǒng)——祖沖之號，未來量子計(jì)算機(jī)將強(qiáng)大得多，能破解目前廣泛使用的公鑰密碼。本報記者 張伊辰攝

對于需要與量子計(jì)算機(jī)“趕時間”的密碼學(xué)家來說，這種不確定性令人擔(dān)憂。IBM公司的雷-哈里尚卡爾說，幾乎每個行業(yè)都會涉及到信息保密和安全。比如，醫(yī)療公司需要確保他們醫(yī)學(xué)研究的數(shù)據(jù)安全，而電力公司則必須保護(hù)電網(wǎng)免受黑客攻擊，“而最壞的情況是，這些系統(tǒng)一旦遭受量子計(jì)算機(jī)攻擊，它們就會完全暴露”。

揀選加密“基石”

新算法何以青睞格理論

每一種公鑰密碼學(xué)都會以一個困難的數(shù)學(xué)問題為基礎(chǔ)。為了確保密碼系統(tǒng)不受未來量子計(jì)算機(jī)的影響，研究人員在設(shè)計(jì)后量子密碼時，需要使用那些即使量子計(jì)算機(jī)也無法在合理時間內(nèi)破解的難題。

NIST發(fā)起的征集要求所提交的方案必須是可以在標(biāo)準(zhǔn)計(jì)算機(jī)上廣泛實(shí)施的公鑰加密算法，從而能夠替代目前的RSA和迪菲-赫爾曼算法。NIST的數(shù)學(xué)家陳莉莉表示，這種新型密碼必須滿足人們在許多不同網(wǎng)絡(luò)系統(tǒng)和設(shè)備上都能互相交流的需求。

在征集所規(guī)定的第一輪截止日2017年11月前，研究人員共提交了82份不同方案。此后一年，研究人員對這些算法進(jìn)行了測試，NIST專家從中選出了26種算法在2019年1月進(jìn)入下一輪測試。

在NIST的測試過程中，研究人員會試圖從候選算法中不斷找出漏洞。有一種候選算法使用了“基于同源性”的加密技術(shù)，這種技術(shù)已經(jīng)被研究了十年，似乎很有前途。但兩位研究人員注意到，利用一個已經(jīng)被確認(rèn)25年的數(shù)學(xué)定理就能破解這種算法——他們使用一臺筆記本電腦，僅花了一個小時就完成了破解。

在被選出的四種算法中，有三種基于的都是格理論。CRYSTALS-Kyber的作者之一、IBM公司的瓦迪姆·柳巴舍夫斯基認(rèn)為，選擇格理論作為后量子密碼算法基礎(chǔ)很自然，因?yàn)?ldquo;20多年來，人們一直在以各種形式研究這個問題”。

在格理論中，格點(diǎn)是由點(diǎn)組成的重復(fù)陣列，其中最簡單的格子看起來就像一塊釘板——圓點(diǎn)排列在一個正方形網(wǎng)格中。數(shù)學(xué)家認(rèn)為，這種“格”是由兩條基本線構(gòu)成的：等長的垂直線和水平線。

假設(shè)有人在一張紙上畫了兩條線，并告訴你這兩條線是網(wǎng)格的組成部分，然后再在紙上某處畫一個點(diǎn)，你能找出離那個點(diǎn)最近的格點(diǎn)嗎？

或許在一張紙這樣的二維平面上最終可以找到，但如果將這個點(diǎn)放在三維空間中呢？人類的視覺想象力一般僅限于三維空間，但數(shù)學(xué)家卻可以描述數(shù)百維的網(wǎng)格。在這些網(wǎng)格中，要找到最近的點(diǎn)是非常困難的。

研究人員利用這種巨型網(wǎng)格構(gòu)建密碼系統(tǒng)。例如，在一個1000維的網(wǎng)格中，從這些點(diǎn)中選擇一個點(diǎn)，這個點(diǎn)的精確位置代表秘密信息，然后從這個點(diǎn)開始一點(diǎn)點(diǎn)移動，浮出網(wǎng)格，進(jìn)入環(huán)境空間。你可以在不泄露秘密點(diǎn)位置的情況下公開分享新位置——尋找附近的網(wǎng)格點(diǎn)是一道非常難的數(shù)學(xué)題。

幾十年來，計(jì)算機(jī)科學(xué)家一直在研究這類問題，并相信它們很難解決。但在設(shè)計(jì)新算法時，密碼學(xué)家還需要考慮安全性之外的許多其他問題，并在這些問題間取得平衡，例如兩臺計(jì)算機(jī)需要交換的信息量以及加密和解密信息所需的計(jì)算難度。在這方面，基于格理論的密碼學(xué)非常出色。有學(xué)者調(diào)侃說，格理論之于新型密碼學(xué)就像一位“金發(fā)女郎”戀人——沒什么太差，也沒什么太好，一切都在合理的點(diǎn)上。

密碼代際切換

“后量子”時代即將開啟

然而，沒有人能保證基于格理論的加密技術(shù)永遠(yuǎn)安全。為了防止數(shù)學(xué)基礎(chǔ)研究上某次根本性突破使得“抗量子”密碼全線覆滅，密碼學(xué)家需要使用各種類型的算法。

NIST的競賽征集為數(shù)字簽名算法設(shè)立了一個類別。數(shù)字簽名算法可以保證信息是由誰發(fā)送的，并且沒有被修改過。美國加州蒙特雷海軍研究生院的密碼學(xué)家布里塔·黑爾解釋，加密算法回答的是“我可以知道沒有其他人會讀到這個信息”，而數(shù)字簽名回答的是“我能相信這些數(shù)據(jù)沒有被修改過”。

目前廣泛使用的加密系統(tǒng)可能在量子計(jì)算機(jī)面前不堪一擊。

此次，NIST選擇將三種數(shù)字簽名算法標(biāo)準(zhǔn)化，其中有兩種基于格理論。然而，如此嚴(yán)重依賴單一類型的數(shù)學(xué)問題是有風(fēng)險的。首先，沒人能保證數(shù)學(xué)家最終不會破解它。其次，它也沒有給用戶提供任何選擇余地——或許另一種加密技術(shù)更契合他們的特定需求。出于以上這些原因，NIST希望標(biāo)準(zhǔn)化方案可以拓展到基于格理論以外的其他數(shù)學(xué)基石上。

即使是已經(jīng)被選中進(jìn)行標(biāo)準(zhǔn)化的算法，也需要不斷調(diào)整。德國馬普安全與隱私研究所的彼得·施瓦貝是CRYSTALS-Kyber的創(chuàng)建者之一。第一輪提交后，研究人員發(fā)現(xiàn)該算法有一個小問題，隨后作者就把它解決了。在下一輪競賽中，作者又找到了一些方法來對算法進(jìn)行微調(diào)。

去年8月，NIST正式發(fā)布了三種入選算法的標(biāo)準(zhǔn)化草案，第四種算法FALCON的標(biāo)準(zhǔn)化草案則會在今年發(fā)布。

目前，NIST正在制定前三種算法的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)將逐條詳細(xì)地描述程序員應(yīng)如何實(shí)現(xiàn)這些算法。“互聯(lián)網(wǎng)上的一切都必須有極其具體、詳細(xì)的標(biāo)準(zhǔn)。否則，計(jì)算機(jī)之間就無法相互對話。”柳巴舍夫斯基說。

這些標(biāo)準(zhǔn)制定后，每個計(jì)算機(jī)系統(tǒng)都將開始向后量子加密技術(shù)切換。各大軟件公司也得開始升級相關(guān)產(chǎn)品的協(xié)議，不少硬件設(shè)備也需要更換。

整個社會系統(tǒng)要完成向后量子加密技術(shù)的過渡，可能需要很多年。在此之前，任何使用舊式加密技術(shù)發(fā)送的信息都有可能被未來的量子計(jì)算機(jī)讀取。你期望的保密時限是多久？或許，“量子年”時鐘忽然就提醒你“密碼過期了”。

>>>延伸閱讀

密碼發(fā)展簡史

愷撒密碼

迄今已知人類最早使用的密碼形式，是一種用來替換文字中字母的密碼。羅馬愷撒大帝在消息傳遞中，用羅馬字母表中相隔三個位置的字母來替換原文字母。在英語中，這意味著“a”變成“d”，“b”變成“e”，以此類推，將字母按字母表順序移動三個位置即可。

愷撒密碼的替換方案有無窮無盡的變化。比如，上課傳紙條的孩子們可以自己創(chuàng)造規(guī)則，把“a”換成心形，把“b”換成星形等等。這樣，即使紙條被老師沒收，也不會輕易泄露同學(xué)之間的小秘密。

破解此類密碼相對容易，只需逆向操作即可解密。密碼破譯者通�？赏ㄟ^比較不同符號與常見英文文本中字母的出現(xiàn)頻率，來破解復(fù)雜一些的替換方案。

上世紀(jì)三四十年代的機(jī)械加密裝置

對稱加密技術(shù)

現(xiàn)代密碼學(xué)的黃金標(biāo)準(zhǔn)，即高級加密標(biāo)準(zhǔn)（AES），在愷撒加密方法的基礎(chǔ)上進(jìn)行了大幅擴(kuò)展。它通過反復(fù)替換條目和像洗撲克牌一樣洗牌來擾亂信息。要解密信息，就必須通過撤銷每次洗牌和替換來解碼。計(jì)算機(jī)是根據(jù)一套精確的指令來洗牌的，例如“將第二個條目移到第五個位置”，計(jì)算機(jī)只需在解密時反向執(zhí)行指令“將第五個條目移到第二個位置”即可。

AES的加密和解密程序是對稱的，就像朝相反方向擰鑰匙來鎖門和開鎖一樣。直到20世紀(jì)70年代，對稱加密技術(shù)一直是唯一的加密技術(shù)。它有一個很大的局限性，即在交換任何信息之前，發(fā)送方和接收方需要就加密和解密的程序達(dá)成一致，可以當(dāng)面交換，也可通過可信的單獨(dú)通信方式交換。

公鑰密碼學(xué)

1974年，美國加州大學(xué)伯克利分校的本科生拉爾夫·默克爾提出了一個設(shè)想中的系統(tǒng)：在這個系統(tǒng)中，兩個人完全在公開場合交換信息，而且總是假定有人在監(jiān)聽。能否建立一個編碼和解碼方案，在這種公開通信場景中發(fā)送秘密信息，即使其他人閱讀到這些信息也無法解密？

當(dāng)時，默克爾的設(shè)想被一位專家以“想法不切實(shí)際”為由否決了。然而，僅僅幾年后，幾篇數(shù)學(xué)論文實(shí)現(xiàn)了默克爾的設(shè)想。其中提出的兩種算法被稱為迪菲-赫爾曼（Diffie-Hellman）和RSA（該算法三位創(chuàng)造者的姓氏Rivest、Shamir、Adleman的縮寫），它們在現(xiàn)代通信中幾乎無處不在。事實(shí)上，在默克爾的課堂設(shè)想之前，英國情報組織的研究人員就已經(jīng)發(fā)現(xiàn)了這種編碼方法——公鑰密碼學(xué)，但他們一直將其保密。

不同類型的公開密鑰加密法創(chuàng)建和共享臨時口令的方式各不相同，一般都會使用數(shù)學(xué)函數(shù)來混合秘密數(shù)字。函數(shù)就像一臺機(jī)器，輸入數(shù)字、攪動數(shù)字，然后吐出新的數(shù)字。公鑰密碼學(xué)中使用的函數(shù)非常特殊，它們既要能輕松混合數(shù)字，又要讓數(shù)字很難被混合。

非對稱加密技術(shù)又稱公鑰加密技術(shù)，因能在公開場合共享密碼而得名。

例如，RSA密碼術(shù)就是基于乘法函數(shù)及其相反的因數(shù)分解。通過乘法混合數(shù)字對計(jì)算機(jī)來說相對容易，即使數(shù)字非常大。但如果數(shù)字很大，撤銷乘法或因數(shù)分解就非常困難。要解密用RSA創(chuàng)建的密碼，需要對一個大數(shù)進(jìn)行因數(shù)分解。最好的方法是過濾掉許多數(shù)字，找到其中的特定組合——這需要計(jì)算機(jī)花費(fèi)很長的時間。

肖爾算法

1994年，時任美國貝爾實(shí)驗(yàn)室研究科學(xué)家的應(yīng)用數(shù)學(xué)家彼得·肖爾發(fā)現(xiàn)，量子計(jì)算機(jī)可以破解任何用RSA或迪菲-赫爾曼加密的代碼。

肖爾參加過一個關(guān)于使用量子計(jì)算機(jī)解決具有周期性或重復(fù)性結(jié)構(gòu)的數(shù)學(xué)問題的講座，這讓他想起了“離散對數(shù)”問題。對數(shù)函數(shù)是指數(shù)函數(shù)的倒數(shù)。例如，在方程2x=16中找到x。通常情況下，求對數(shù)很容易，但離散對數(shù)問題是用另一種算術(shù)形式計(jì)算對數(shù)。在這種算術(shù)形式中，人們像在時鐘上一樣繞圈計(jì)數(shù)。

正如RSA是基于因數(shù)分解，迪菲-赫爾曼是基于離散對數(shù)問題。計(jì)算機(jī)科學(xué)家普遍認(rèn)為，經(jīng)典計(jì)算機(jī)無法快速找到離散對數(shù)，但肖爾找到了在量子計(jì)算機(jī)上實(shí)現(xiàn)這一目標(biāo)的方法。隨后，他又運(yùn)用類似的邏輯，證明了如何使用量子計(jì)算機(jī)快速找到大數(shù)因數(shù)。這些解決方案被稱為肖爾算法。

不過，肖爾并沒有想象過為真正的量子計(jì)算機(jī)編程，他只是在黑板和紙上做數(shù)學(xué)題。畢竟，量子計(jì)算機(jī)在當(dāng)時似乎還是遙不可及的未來。但他的算法卻對公鑰密碼學(xué)產(chǎn)生了重大影響，因?yàn)榱孔佑?jì)算機(jī)可以利用它破解目前使用的幾乎所有密碼系統(tǒng)。