“量子年”時(shí)鐘目前被設(shè)置在2030年4月14日，其對(duì)應(yīng)的是通用量子計(jì)算機(jī)可以攻破公鑰加密技術(shù)的預(yù)計(jì)日期。
本文來(lái)自文匯網(wǎng)，作者：章珂/整理編譯。
在網(wǎng)絡(luò)信息傳輸過(guò)程中，公鑰密碼算法是最重要的技術(shù)保障，也是互聯(lián)網(wǎng)時(shí)代網(wǎng)絡(luò)信息安全的基石。然而，隨著量子計(jì)算機(jī)技術(shù)的迅猛發(fā)展，公鑰加密技術(shù)正面臨巨大安全威脅。為了提醒人們關(guān)注這一巨大隱患，數(shù)字安全專家設(shè)立了“量子年”時(shí)鐘，其代表的量子計(jì)算機(jī)攻破現(xiàn)代密碼技術(shù)的日期正在不斷提前。
站在這場(chǎng)新技術(shù)變革的邊緣，發(fā)展“后量子密碼”變得刻不容緩。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院自2016年12月起發(fā)出后量子密碼學(xué)標(biāo)準(zhǔn)化流程的公開征集，今年將有三種新算法標(biāo)準(zhǔn)投入使用，各類系統(tǒng)將開始向后量子密碼技術(shù)切換。不過(guò)，問(wèn)題似乎還未就此解決。科學(xué)家仍在不懈努力，希望“量子年”危機(jī)能像“千年蟲”危機(jī)一樣順利渡過(guò)。
——編者
如果有一臺(tái)計(jì)算機(jī)，能在眨眼間解決當(dāng)今速度最快的超級(jí)計(jì)算機(jī)也無(wú)法解決的數(shù)學(xué)問(wèn)題；如果有一種技術(shù)，可以讓觀察者透過(guò)墻壁看到墻后的事物，或者看到最黑暗的海洋世界深處，還可以在構(gòu)建完全不可攻破的網(wǎng)絡(luò)的同時(shí)，破解對(duì)手最機(jī)密的數(shù)據(jù)——這就是量子計(jì)算機(jī)和量子技術(shù)。今后幾十年甚至幾個(gè)世紀(jì)內(nèi)，它們將重新界定全球信息技術(shù)的未來(lái)。
當(dāng)這一天到來(lái)，當(dāng)前廣泛使用的加密技術(shù)將在量子計(jì)算機(jī)面前不堪一擊。為此，全世界的數(shù)字安全專家都在關(guān)注“量子年”（Years to Quantum，Y2Q）時(shí)鐘，它指向的時(shí)間對(duì)應(yīng)的是通用量子計(jì)算機(jī)可以攻破非對(duì)稱加密技術(shù)（現(xiàn)代密碼學(xué)的一種重要加密形式）的預(yù)計(jì)日期。
非對(duì)稱加密技術(shù)又稱公鑰加密技術(shù)，因能在公開場(chǎng)合共享密碼而得名。這種加密技術(shù)可以保證網(wǎng)上購(gòu)物時(shí)信用卡的安全，也可確保手機(jī)軟件更新來(lái)自手機(jī)公司而非黑客。但是，量子計(jì)算機(jī)會(huì)讓目前廣泛使用的公鑰加密技術(shù)形同虛設(shè)。
“量子年”時(shí)鐘
傳統(tǒng)密碼“最后期限”將至
云安全聯(lián)盟（CSA）量子安全工作組聯(lián)合主席布魯諾·胡特納說(shuō)，如果明天就有一臺(tái)量子計(jì)算機(jī)出現(xiàn)，那所有人都將無(wú)法找到一種安全的方式在一起交談，“這確實(shí)非常嚴(yán)重”。
胡特納是Y2Q時(shí)鐘的創(chuàng)造者之一。Y2Q時(shí)鐘的命名是為了紀(jì)念那個(gè)可能導(dǎo)致計(jì)算機(jī)崩潰但最終在技術(shù)人員努力下得以避免的Y2K（千年蟲）危機(jī)。這一危機(jī)之所以得以天衣無(wú)縫地順利渡過(guò)，主要是因?yàn)槠髽I(yè)和政府都在抓緊時(shí)間，及時(shí)修復(fù)了“千年蟲”。
與“千年蟲”危機(jī)不同的是，沒(méi)有人確切知道，足以打破現(xiàn)有密碼標(biāo)準(zhǔn)的量子計(jì)算機(jī)何時(shí)才能研制成功。目前，Y2Q時(shí)鐘的結(jié)束日期被設(shè)置在2030年4月14日。但這只是一個(gè)猜測(cè)，胡特納說(shuō)，“Y2Q時(shí)鐘是一個(gè)提醒，有助于引起人們的關(guān)注。”
實(shí)際上，對(duì)保密有長(zhǎng)期需求的政府及相關(guān)機(jī)構(gòu)來(lái)說(shuō)，真正的“最后期限”會(huì)比Y2Q時(shí)鐘設(shè)定的早很多年到來(lái)——如果今天發(fā)送的加密數(shù)據(jù)被存儲(chǔ)起來(lái)，那么未來(lái)的量子計(jì)算機(jī)就可追溯性地解密這些信息。
美國(guó)密歇根大學(xué)的計(jì)算機(jī)科學(xué)家克里斯-佩克特說(shuō)，如果一些信息需要保密20年，破解這種加密技術(shù)的量子計(jì)算機(jī)可能在20年內(nèi)出現(xiàn)，那么現(xiàn)在為這些信息加密時(shí)，就不得不考慮這個(gè)問(wèn)題了。
正是預(yù)見(jiàn)到了這種威脅，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）于2016年12月發(fā)起了公開競(jìng)賽，征集“后量子”或“抗量子”密碼學(xué)方案——這些密碼可以在目前使用的計(jì)算機(jī)上運(yùn)行，但卻可以強(qiáng)大到連量子計(jì)算機(jī)也無(wú)法破解。
經(jīng)過(guò)四輪提交和評(píng)審，NIST最終于2022年7月選定了四種算法作為“后量子密碼學(xué)”標(biāo)準(zhǔn)化流程的成果，其中公鑰封裝機(jī)制為CRYSTALS—Kyber，數(shù)字簽名方案為CRYSTALS—Dilithium、FALCON和SPHINCS+。NIST正在與研究人員合作，將獲獎(jiǎng)算法標(biāo)準(zhǔn)化，以便程序員可以此為基礎(chǔ)，研發(fā)能夠抵御量子計(jì)算機(jī)的密碼技術(shù)。
專家們確信，它們肯定都是非常難以破解的，但誰(shuí)也不能保證未來(lái)的量子計(jì)算機(jī)不會(huì)破解它們。
經(jīng)典計(jì)算機(jī)運(yùn)行的是一長(zhǎng)串0和1，被稱為“比特”，而量子計(jì)算機(jī)使用的是可以處于疊加狀態(tài)的“量子比特”——通過(guò)在0和1這兩種狀態(tài)之間徘徊，量子計(jì)算機(jī)能夠以比經(jīng)典計(jì)算機(jī)快得多的速度執(zhí)行某些任務(wù)。
現(xiàn)在的量子計(jì)算機(jī)看起來(lái)就像巨大的金色吊燈一樣懸掛在天花板上——令人印象深刻，但功能卻還不夠強(qiáng)大?？茖W(xué)家們只能控制數(shù)量不多的量子比特進(jìn)行計(jì)算。2012年，英國(guó)布里斯托爾大學(xué)的研究人員利用量子計(jì)算機(jī)推算出21是7的3倍。
盡管如此，許多專家還是認(rèn)為，足以破解目前使用最廣泛的RSA和迪菲-赫爾曼這兩種加密算法的量子計(jì)算機(jī)，將在未來(lái)幾十年內(nèi)問(wèn)世，不過(guò)時(shí)間線還不確定。
第六屆進(jìn)博會(huì)中國(guó)館展出的可編程量子計(jì)算系統(tǒng)——祖沖之號(hào)，未來(lái)量子計(jì)算機(jī)將強(qiáng)大得多，能破解目前廣泛使用的公鑰密碼。本報(bào)記者張伊辰攝
對(duì)于需要與量子計(jì)算機(jī)“趕時(shí)間”的密碼學(xué)家來(lái)說(shuō)，這種不確定性令人擔(dān)憂。IBM公司的雷-哈里尚卡爾說(shuō)，幾乎每個(gè)行業(yè)都會(huì)涉及到信息保密和安全。比如，醫(yī)療公司需要確保他們醫(yī)學(xué)研究的數(shù)據(jù)安全，而電力公司則必須保護(hù)電網(wǎng)免受黑客攻擊，“而最壞的情況是，這些系統(tǒng)一旦遭受量子計(jì)算機(jī)攻擊，它們就會(huì)完全暴露”。
揀選加密“基石”
新算法何以青睞格理論
每一種公鑰密碼學(xué)都會(huì)以一個(gè)困難的數(shù)學(xué)問(wèn)題為基礎(chǔ)。為了確保密碼系統(tǒng)不受未來(lái)量子計(jì)算機(jī)的影響，研究人員在設(shè)計(jì)后量子密碼時(shí)，需要使用那些即使量子計(jì)算機(jī)也無(wú)法在合理時(shí)間內(nèi)破解的難題。
NIST發(fā)起的征集要求所提交的方案必須是可以在標(biāo)準(zhǔn)計(jì)算機(jī)上廣泛實(shí)施的公鑰加密算法，從而能夠替代目前的RSA和迪菲-赫爾曼算法。NIST的數(shù)學(xué)家陳莉莉表示，這種新型密碼必須滿足人們?cè)谠S多不同網(wǎng)絡(luò)系統(tǒng)和設(shè)備上都能互相交流的需求。
在征集所規(guī)定的第一輪截止日2017年11月前，研究人員共提交了82份不同方案。此后一年，研究人員對(duì)這些算法進(jìn)行了測(cè)試，NIST專家從中選出了26種算法在2019年1月進(jìn)入下一輪測(cè)試。
在NIST的測(cè)試過(guò)程中，研究人員會(huì)試圖從候選算法中不斷找出漏洞。有一種候選算法使用了“基于同源性”的加密技術(shù)，這種技術(shù)已經(jīng)被研究了十年，似乎很有前途。但兩位研究人員注意到，利用一個(gè)已經(jīng)被確認(rèn)25年的數(shù)學(xué)定理就能破解這種算法——他們使用一臺(tái)筆記本電腦，僅花了一個(gè)小時(shí)就完成了破解。
在被選出的四種算法中，有三種基于的都是格理論。CRYSTALS-Kyber的作者之一、IBM公司的瓦迪姆·柳巴舍夫斯基認(rèn)為，選擇格理論作為后量子密碼算法基礎(chǔ)很自然，因?yàn)?ldquo;20多年來(lái)，人們一直在以各種形式研究這個(gè)問(wèn)題”。
在格理論中，格點(diǎn)是由點(diǎn)組成的重復(fù)陣列，其中最簡(jiǎn)單的格子看起來(lái)就像一塊釘板——圓點(diǎn)排列在一個(gè)正方形網(wǎng)格中。數(shù)學(xué)家認(rèn)為，這種“格”是由兩條基本線構(gòu)成的：等長(zhǎng)的垂直線和水平線。
假設(shè)有人在一張紙上畫了兩條線，并告訴你這兩條線是網(wǎng)格的組成部分，然后再在紙上某處畫一個(gè)點(diǎn)，你能找出離那個(gè)點(diǎn)最近的格點(diǎn)嗎？
或許在一張紙這樣的二維平面上最終可以找到，但如果將這個(gè)點(diǎn)放在三維空間中呢？人類的視覺(jué)想象力一般僅限于三維空間，但數(shù)學(xué)家卻可以描述數(shù)百維的網(wǎng)格。在這些網(wǎng)格中，要找到最近的點(diǎn)是非常困難的。
研究人員利用這種巨型網(wǎng)格構(gòu)建密碼系統(tǒng)。例如，在一個(gè)1000維的網(wǎng)格中，從這些點(diǎn)中選擇一個(gè)點(diǎn)，這個(gè)點(diǎn)的精確位置代表秘密信息，然后從這個(gè)點(diǎn)開始一點(diǎn)點(diǎn)移動(dòng)，浮出網(wǎng)格，進(jìn)入環(huán)境空間。你可以在不泄露秘密點(diǎn)位置的情況下公開分享新位置——尋找附近的網(wǎng)格點(diǎn)是一道非常難的數(shù)學(xué)題。
幾十年來(lái)，計(jì)算機(jī)科學(xué)家一直在研究這類問(wèn)題，并相信它們很難解決。但在設(shè)計(jì)新算法時(shí)，密碼學(xué)家還需要考慮安全性之外的許多其他問(wèn)題，并在這些問(wèn)題間取得平衡，例如兩臺(tái)計(jì)算機(jī)需要交換的信息量以及加密和解密信息所需的計(jì)算難度。在這方面，基于格理論的密碼學(xué)非常出色。有學(xué)者調(diào)侃說(shuō)，格理論之于新型密碼學(xué)就像一位“金發(fā)女郎”戀人——沒(méi)什么太差，也沒(méi)什么太好，一切都在合理的點(diǎn)上。
密碼代際切換
“后量子”時(shí)代即將開啟
然而，沒(méi)有人能保證基于格理論的加密技術(shù)永遠(yuǎn)安全。為了防止數(shù)學(xué)基礎(chǔ)研究上某次根本性突破使得“抗量子”密碼全線覆滅，密碼學(xué)家需要使用各種類型的算法。
NIST的競(jìng)賽征集為數(shù)字簽名算法設(shè)立了一個(gè)類別。數(shù)字簽名算法可以保證信息是由誰(shuí)發(fā)送的，并且沒(méi)有被修改過(guò)。美國(guó)加州蒙特雷海軍研究生院的密碼學(xué)家布里塔·黑爾解釋，加密算法回答的是“我可以知道沒(méi)有其他人會(huì)讀到這個(gè)信息”，而數(shù)字簽名回答的是“我能相信這些數(shù)據(jù)沒(méi)有被修改過(guò)”。
目前廣泛使用的加密系統(tǒng)可能在量子計(jì)算機(jī)面前不堪一擊。
此次，NIST選擇將三種數(shù)字簽名算法標(biāo)準(zhǔn)化，其中有兩種基于格理論。然而，如此嚴(yán)重依賴單一類型的數(shù)學(xué)問(wèn)題是有風(fēng)險(xiǎn)的。首先，沒(méi)人能保證數(shù)學(xué)家最終不會(huì)破解它。其次，它也沒(méi)有給用戶提供任何選擇余地——或許另一種加密技術(shù)更契合他們的特定需求。出于以上這些原因，NIST希望標(biāo)準(zhǔn)化方案可以拓展到基于格理論以外的其他數(shù)學(xué)基石上。
即使是已經(jīng)被選中進(jìn)行標(biāo)準(zhǔn)化的算法，也需要不斷調(diào)整。德國(guó)馬普安全與隱私研究所的彼得·施瓦貝是CRYSTALS-Kyber的創(chuàng)建者之一。第一輪提交后，研究人員發(fā)現(xiàn)該算法有一個(gè)小問(wèn)題，隨后作者就把它解決了。在下一輪競(jìng)賽中，作者又找到了一些方法來(lái)對(duì)算法進(jìn)行微調(diào)。
去年8月，NIST正式發(fā)布了三種入選算法的標(biāo)準(zhǔn)化草案，第四種算法FALCON的標(biāo)準(zhǔn)化草案則會(huì)在今年發(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ī)之間就無(wú)法相互對(duì)話。”柳巴舍夫斯基說(shuō)。
這些標(biāo)準(zhǔn)制定后，每個(gè)計(jì)算機(jī)系統(tǒng)都將開始向后量子加密技術(shù)切換。各大軟件公司也得開始升級(jí)相關(guān)產(chǎn)品的協(xié)議，不少硬件設(shè)備也需要更換。
整個(gè)社會(huì)系統(tǒng)要完成向后量子加密技術(shù)的過(guò)渡，可能需要很多年。在此之前，任何使用舊式加密技術(shù)發(fā)送的信息都有可能被未來(lái)的量子計(jì)算機(jī)讀取。你期望的保密時(shí)限是多久？或許，“量子年”時(shí)鐘忽然就提醒你“密碼過(guò)期了”。
延伸閱讀
密碼發(fā)展簡(jiǎn)史
愷撒密碼
迄今已知人類最早使用的密碼形式，是一種用來(lái)替換文字中字母的密碼。羅馬愷撒大帝在消息傳遞中，用羅馬字母表中相隔三個(gè)位置的字母來(lái)替換原文字母。在英語(yǔ)中，這意味著“a”變成“d”，“b”變成“e”，以此類推，將字母按字母表順序移動(dòng)三個(gè)位置即可。
愷撒密碼的替換方案有無(wú)窮無(wú)盡的變化。比如，上課傳紙條的孩子們可以自己創(chuàng)造規(guī)則，把“a”換成心形，把“b”換成星形等等。這樣，即使紙條被老師沒(méi)收，也不會(huì)輕易泄露同學(xué)之間的小秘密。
破解此類密碼相對(duì)容易，只需逆向操作即可解密。密碼破譯者通?？赏ㄟ^(guò)比較不同符號(hào)與常見(jiàn)英文文本中字母的出現(xiàn)頻率，來(lái)破解復(fù)雜一些的替換方案。
上世紀(jì)三四十年代的機(jī)械加密裝置
對(duì)稱加密技術(shù)
現(xiàn)代密碼學(xué)的黃金標(biāo)準(zhǔn)，即高級(jí)加密標(biāo)準(zhǔn)（AES），在愷撒加密方法的基礎(chǔ)上進(jìn)行了大幅擴(kuò)展。它通過(guò)反復(fù)替換條目和像洗撲克牌一樣洗牌來(lái)擾亂信息。要解密信息，就必須通過(guò)撤銷每次洗牌和替換來(lái)解碼。計(jì)算機(jī)是根據(jù)一套精確的指令來(lái)洗牌的，例如“將第二個(gè)條目移到第五個(gè)位置”，計(jì)算機(jī)只需在解密時(shí)反向執(zhí)行指令“將第五個(gè)條目移到第二個(gè)位置”即可。
AES的加密和解密程序是對(duì)稱的，就像朝相反方向擰鑰匙來(lái)鎖門和開鎖一樣。直到20世紀(jì)70年代，對(duì)稱加密技術(shù)一直是唯一的加密技術(shù)。它有一個(gè)很大的局限性，即在交換任何信息之前，發(fā)送方和接收方需要就加密和解密的程序達(dá)成一致，可以當(dāng)面交換，也可通過(guò)可信的單獨(dú)通信方式交換。
公鑰密碼學(xué)
1974年，美國(guó)加州大學(xué)伯克利分校的本科生拉爾夫·默克爾提出了一個(gè)設(shè)想中的系統(tǒng)：在這個(gè)系統(tǒng)中，兩個(gè)人完全在公開場(chǎng)合交換信息，而且總是假定有人在監(jiān)聽(tīng)。能否建立一個(gè)編碼和解碼方案，在這種公開通信場(chǎng)景中發(fā)送秘密信息，即使其他人閱讀到這些信息也無(wú)法解密？
當(dāng)時(shí)，默克爾的設(shè)想被一位專家以“想法不切實(shí)際”為由否決了。然而，僅僅幾年后，幾篇數(shù)學(xué)論文實(shí)現(xiàn)了默克爾的設(shè)想。其中提出的兩種算法被稱為迪菲-赫爾曼（Diffie-Hellman）和RSA（該算法三位創(chuàng)造者的姓氏Rivest、Shamir、Adleman的縮寫），它們?cè)诂F(xiàn)代通信中幾乎無(wú)處不在。事實(shí)上，在默克爾的課堂設(shè)想之前，英國(guó)情報(bào)組織的研究人員就已經(jīng)發(fā)現(xiàn)了這種編碼方法——公鑰密碼學(xué)，但他們一直將其保密。
不同類型的公開密鑰加密法創(chuàng)建和共享臨時(shí)口令的方式各不相同，一般都會(huì)使用數(shù)學(xué)函數(shù)來(lái)混合秘密數(shù)字。函數(shù)就像一臺(tái)機(jī)器，輸入數(shù)字、攪動(dòng)數(shù)字，然后吐出新的數(shù)字。公鑰密碼學(xué)中使用的函數(shù)非常特殊，它們既要能輕松混合數(shù)字，又要讓數(shù)字很難被混合。
非對(duì)稱加密技術(shù)又稱公鑰加密技術(shù)，因能在公開場(chǎng)合共享密碼而得名。
例如，RSA密碼術(shù)就是基于乘法函數(shù)及其相反的因數(shù)分解。通過(guò)乘法混合數(shù)字對(duì)計(jì)算機(jī)來(lái)說(shuō)相對(duì)容易，即使數(shù)字非常大。但如果數(shù)字很大，撤銷乘法或因數(shù)分解就非常困難。要解密用RSA創(chuàng)建的密碼，需要對(duì)一個(gè)大數(shù)進(jìn)行因數(shù)分解。最好的方法是過(guò)濾掉許多數(shù)字，找到其中的特定組合——這需要計(jì)算機(jī)花費(fèi)很長(zhǎng)的時(shí)間。
肖爾算法
1994年，時(shí)任美國(guó)貝爾實(shí)驗(yàn)室研究科學(xué)家的應(yīng)用數(shù)學(xué)家彼得·肖爾發(fā)現(xiàn)，量子計(jì)算機(jī)可以破解任何用RSA或迪菲-赫爾曼加密的代碼。
肖爾參加過(guò)一個(gè)關(guān)于使用量子計(jì)算機(jī)解決具有周期性或重復(fù)性結(jié)構(gòu)的數(shù)學(xué)問(wèn)題的講座，這讓他想起了“離散對(duì)數(shù)”問(wèn)題。對(duì)數(shù)函數(shù)是指數(shù)函數(shù)的倒數(shù)。例如，在方程2x=16中找到x。通常情況下，求對(duì)數(shù)很容易，但離散對(duì)數(shù)問(wèn)題是用另一種算術(shù)形式計(jì)算對(duì)數(shù)。在這種算術(shù)形式中，人們像在時(shí)鐘上一樣繞圈計(jì)數(shù)。
正如RSA是基于因數(shù)分解，迪菲-赫爾曼是基于離散對(duì)數(shù)問(wèn)題。計(jì)算機(jī)科學(xué)家普遍認(rèn)為，經(jīng)典計(jì)算機(jī)無(wú)法快速找到離散對(duì)數(shù)，但肖爾找到了在量子計(jì)算機(jī)上實(shí)現(xiàn)這一目標(biāo)的方法。隨后，他又運(yùn)用類似的邏輯，證明了如何使用量子計(jì)算機(jī)快速找到大數(shù)因數(shù)。這些解決方案被稱為肖爾算法。
不過(guò)，肖爾并沒(méi)有想象過(guò)為真正的量子計(jì)算機(jī)編程，他只是在黑板和紙上做數(shù)學(xué)題。畢竟，量子計(jì)算機(jī)在當(dāng)時(shí)似乎還是遙不可及的未來(lái)。但他的算法卻對(duì)公鑰密碼學(xué)產(chǎn)生了重大影響，因?yàn)榱孔佑?jì)算機(jī)可以利用它破解目前使用的幾乎所有密碼系統(tǒng)。
文：章珂/整理編譯
