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

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

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

——編者

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

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

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

“量子年”時鐘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

揀選加密“基石”

新算法何以青睞格理論

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

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

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

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

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

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

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

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

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

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

密碼代際切換

“后量子”時代即將開啟

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

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

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

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

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

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

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

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

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

>>>延伸閱讀

密碼發(fā)展簡史

愷撒密碼

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

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

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

上世紀三四十年代的機械加密裝置

對稱加密技術

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

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

公鑰密碼學

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

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

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

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

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

肖爾算法

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

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

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

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