面對量子霸權(quán)，公鑰加密將形同虛設(shè)

Roger A.Grimes　陳琳華

量子計(jì)算機(jī)的進(jìn)步意味著只需要再過幾年時(shí)間它們就能夠破解所有的公鑰加密。每個(gè)秘密都將大白于天下的那一天已經(jīng)離我們不遠(yuǎn)了。

十多年前，我正在進(jìn)行關(guān)于量子加密的介紹性演講，正如我之前多次做過的演講一樣。我介紹了量子物理學(xué)、量子計(jì)算機(jī)和量子密碼學(xué)的基本概念。我當(dāng)時(shí)以一個(gè)展望作為結(jié)語結(jié)束了那次演講，那就是當(dāng)量子計(jì)算成為主流時(shí)，我們當(dāng)前依賴于難以求解的大質(zhì)數(shù)方程加密的大部分秘密都將會(huì)立刻被破解。

自從Whitfield Diffie、Mark Hellman和Ralph Merkle于1976年在他們開創(chuàng)性的論文《密碼學(xué)中的新方向》中披露這一概念以來，大多數(shù)秘密都受到了某種形式的非對稱加密保護(hù)，比如RSA、SSL、TLS和HTTPS。然而，我們所談?wù)摰拇蠖鄶?shù)網(wǎng)站、數(shù)字簽名下載、在線金融交易、VPN、智能卡和大多數(shù)無線網(wǎng)絡(luò)，所有的這些都能夠立即被量子計(jì)算機(jī)所破解。

當(dāng)今的安全通信都基于一個(gè)事實(shí)，那就是傳統(tǒng)數(shù)字計(jì)算機(jī)不容易分解涉及大質(zhì)數(shù)的多因子方程。如果量子計(jì)算機(jī)具備了這種能力，那么對于采取上述方式加密的任何秘密而言，游戲都結(jié)束了。

從理論上講，世界上大多數(shù)的強(qiáng)國都在記錄和存儲(chǔ)全球大部分加密的網(wǎng)絡(luò)流量以便將來解密，等待即將到來的那一天。屆時(shí)美國將能夠閱讀俄羅斯和中國的絕密通信，反之亦然。我差不多八年前在專欄中就曾經(jīng)提到過這種威脅。

回到我多年前的那次演講：在演講結(jié)束時(shí)的提問環(huán)節(jié)，有人問我，量子計(jì)算機(jī)還有多長時(shí)間就能夠破解所有秘密。我的回答是“10年。大多數(shù)量子物理專家都認(rèn)為只有10年時(shí)間了?！碑?dāng)我走出講臺(tái)后，業(yè)界知名人士Bruce Schneier走了過來。正如他那貌似漫不經(jīng)心的步伐一樣，他隨口問了我一句，“你口中的10年到底是多久？”

我給出的10年這個(gè)答案是說可能至少10年時(shí)間。Bruce讓我意識(shí)到我們都不知道確切的答案。量子物理學(xué)界流傳的一個(gè)笑話是量子計(jì)算機(jī)總是在10年后出現(xiàn)。

量子計(jì)算機(jī)的工作原理

現(xiàn)在來看，不再需要10年了。據(jù)劍橋量子計(jì)算（CQC）商業(yè)發(fā)展科學(xué)主管兼理論物理學(xué)家Mark Jackson博士稱，我們現(xiàn)在可能只需要四到五年的時(shí)間就可迎來量子計(jì)算，在某些領(lǐng)域或有限的商業(yè)應(yīng)用當(dāng)中，例如量子化學(xué)，甚至可能在2021年中期就會(huì)出現(xiàn)。什么東西發(fā)生了變化？我們現(xiàn)在的許多量子計(jì)算機(jī)、設(shè)備和軟件雖然設(shè)計(jì)的足夠巧妙并且十分有用，但是卻沒有被稱為“糾錯(cuò)”的東西。

量子計(jì)算機(jī)可以憑借其獨(dú)特的工作原理“秒殺”傳統(tǒng)的數(shù)字計(jì)算機(jī)。顯然，量子計(jì)算機(jī)依賴于量子力學(xué)（這里涉及的主題太大并且十分復(fù)雜），但簡而言之，這就是優(yōu)勢。數(shù)字計(jì)算機(jī)是二進(jìn)制的，其中央處理單元（CPU）內(nèi)的每個(gè)晶體管或邏輯門同一時(shí)刻只能保持一種“狀態(tài)”，是“開”還是“關(guān)”，是否通電，是“1”還是“0”。這就是所謂的二進(jìn)制。

量子計(jì)算機(jī)的基礎(chǔ)是量子比特。每個(gè)量子比特可以同時(shí)處于兩個(gè)狀態(tài)。因此，一個(gè)量子比特相當(dāng)于兩個(gè)二進(jìn)制邏輯門。當(dāng)引入它們后，量子比特會(huì)呈指數(shù)級增長。兩個(gè)量子比特可以同時(shí)保持四種狀態(tài)，三個(gè)量子比特可以同時(shí)保持八種狀態(tài)，依此類推。

一臺(tái)普通的量子計(jì)算機(jī)就可能會(huì)破解我們之前所有采用公鑰/私鑰對加密的秘密，但是這個(gè)過程需要有效的糾錯(cuò)。

量子計(jì)算機(jī)將在何時(shí)1.2何種方式破解公鑰加密

為了讓量子計(jì)算成為現(xiàn)實(shí)，我們已經(jīng)等待了很長時(shí)間。到底有多久呢？至少可以追溯到1959年Richard Feynman博士就此進(jìn)行的演講。不過許多量子計(jì)算專家將Peter Shor博士在1994年公布的算法視為量子計(jì)算的真正開端。

Shor的算法表明，基于量子的計(jì)算可快速破解大多數(shù)傳統(tǒng)形式的非對稱加密。二十多年后，量子計(jì)算的光明前景（和威脅）幾乎近在眼前。不僅僅是理論模型，而是出現(xiàn)了一些能夠工作的量子計(jì)算機(jī)、軟件、網(wǎng)絡(luò)和其他通信設(shè)備。

最大的挑戰(zhàn)之一是讓量子比特保持足夠的穩(wěn)定和足夠長的時(shí)間，在嚴(yán)肅的計(jì)算中不會(huì)出錯(cuò)。我會(huì)在下面的介紹中使用非技術(shù)術(shù)語“完美”和“不完美”來描述量子比特的這一品質(zhì)。美國德克薩斯大學(xué)奧斯汀分校量子信息中心主任兼計(jì)算機(jī)科學(xué)教授Scott Aarenson稱：“要破解公鑰加密，實(shí)際上需要成千上萬的‘邏輯或‘編碼量子比特。而在現(xiàn)實(shí)世界中，由于糾錯(cuò)以及現(xiàn)有容錯(cuò)方案的龐大需求，對高品質(zhì)的物理量子比特的需求很容易就會(huì)上升至百萬級。”

那么我們在量子計(jì)算生命周期中已經(jīng)處于哪個(gè)階段了？按照J(rèn)ackson博士的說法，量子計(jì)算機(jī)僅需要49個(gè)完美的量子比特就可以勝過傳統(tǒng)的二進(jìn)制計(jì)算機(jī)。這就是被大家熟知的“量子優(yōu)勢”，這將是量子計(jì)算機(jī)最終超越二進(jìn)制計(jì)算機(jī)的關(guān)鍵節(jié)點(diǎn)。這一時(shí)刻的意義與IBM深藍(lán)超級計(jì)算機(jī)在1997年擊敗世界象棋冠軍加里·卡斯帕羅夫時(shí)一樣。

為了破解當(dāng)前大多數(shù)公鑰加密，量子計(jì)算機(jī)需要至少4000個(gè)完美的量子比特，如果量子比特不完美，那么所需的數(shù)量將會(huì)翻上許多倍。那么我們距離完美的4000個(gè)量子比特還有多遠(yuǎn)？這個(gè)問題的答案要取決于你問誰。Jackson博士認(rèn)為，我們將在未來五年制造出擁有4000個(gè)完美量子比特的量子計(jì)算機(jī)。雖然他有一些證據(jù)支持他的這一說法，但是我們距離4000個(gè)完美的量子比特還非常遙遠(yuǎn)。

2018年3月，谷歌公布了一臺(tái)擁有72個(gè)不完美量子比特的計(jì)算機(jī)。谷歌目前的量子計(jì)算機(jī)每執(zhí)行200次計(jì)算就會(huì)出一次錯(cuò)誤。當(dāng)每秒進(jìn)行數(shù)十億次計(jì)算時(shí)，這么高的錯(cuò)誤率將是一場災(zāi)難。在全世界范圍內(nèi)，在制造更穩(wěn)定的量子計(jì)算機(jī)的投入上沒有數(shù)千萬億美元也至少有數(shù)百萬億美元。部分人認(rèn)為如今達(dá)到4000個(gè)完美量子比特所需付出的努力已經(jīng)不再像以前那樣令人望而生畏了。

直接從事量子計(jì)算機(jī)研發(fā)的Jackson博士稱：“我們在短短一年內(nèi)就已經(jīng)從9個(gè)量子比特發(fā)展到了72個(gè)量子比特，所以我們在今后的五年內(nèi)獲得4000個(gè)量子比特并不是一個(gè)瘋狂的想法。鑒于美國政府已經(jīng)在幾個(gè)月前最終決定參與進(jìn)來，我認(rèn)為這個(gè)時(shí)間只是一個(gè)保守的估計(jì)?！?/p>

更多知識(shí)淵博的人依然認(rèn)為我們?nèi)詿o法知道會(huì)在何時(shí)取得用于破解公鑰加密的突破性成就。Schneier長期撰寫關(guān)于量子密碼學(xué)的文章。當(dāng)?shù)弥@一時(shí)間是5年時(shí)，他說：“我不相信這一說法。沒人知道前面還有什么不可預(yù)料的問題?！?/p>

Aaronson博士也對此持懷疑態(tài)度。他在文章中寫道：“如果這種情況在五年內(nèi)發(fā)生，我會(huì)感到十分驚訝。我不是說這不可能，但我認(rèn)為它們需要更長的時(shí)間。如果谷歌、IBM或其他公司在三到五年內(nèi)成功地制造出了擁有70個(gè)量子比特的量子計(jì)算機(jī)，或是它們能夠在一些（主要是人工）任務(wù)中開始超越經(jīng)典計(jì)算機(jī)，我會(huì)對此感到非常高興。即便如此，由于糾錯(cuò)和現(xiàn)有容錯(cuò)方案的龐大需求，它們還遠(yuǎn)不能威脅到公鑰密碼技術(shù)，因?yàn)檫@很容易導(dǎo)致對高品質(zhì)的物理量子比特的需求上升至數(shù)百萬量級?！?/p>

顯然，對于量子計(jì)算機(jī)何時(shí)能夠破解公鑰加密，大家各執(zhí)一詞，但是這已經(jīng)不再是科幻小說中的虛構(gòu)內(nèi)容了。

雖然美國國家安全局（NSA）也尚未承認(rèn)很快就會(huì)實(shí)現(xiàn)量子突破，不過他們已經(jīng)認(rèn)為現(xiàn)在是時(shí)候開始著手準(zhǔn)備了。具體說來，在他們的一份常見問題解答中曾提到，“NSA認(rèn)為現(xiàn)在時(shí)機(jī)已經(jīng)成熟……量子計(jì)算正在不斷取得進(jìn)展……NSA正在尋求與所有的NSA供應(yīng)商和運(yùn)營商一起實(shí)施基于標(biāo)準(zhǔn)的抗量子破解的密碼技術(shù)以保護(hù)他們的數(shù)據(jù)和通信?！?/p>

新興的量子計(jì)算行業(yè)

越來越多的企業(yè)和組織，至少有44個(gè)已知實(shí)體正在嘗試制造量子計(jì)算機(jī)。4家全球知名的美國企業(yè)谷歌、IBM、英特爾和微軟均參與其中。與此同時(shí)，越來越多的初創(chuàng)公司似乎也在不斷取得進(jìn)展。Jackson博士的公司CQC作為其中的一員，目前正與谷歌和IBM等公司展開合作。

雖然許多企業(yè)正在使用相似的技術(shù)，但還是有少數(shù)企業(yè)正在使用他們自己的方法，也有一些公司在同時(shí)使用多種方法以期在競爭中成為贏家。在過去的幾個(gè)月里，IBM和谷歌均已經(jīng)成立了業(yè)務(wù)開發(fā)部門，這表明他們的重點(diǎn)已經(jīng)從理論轉(zhuǎn)向了商用。

另外，許多企業(yè)競相投入數(shù)十億美元的現(xiàn)象也非常重要。當(dāng)許多企業(yè)和國家開始為此投入大量資金時(shí)，必然會(huì)出現(xiàn)殺手級應(yīng)用。以云計(jì)算為例。多年來，云只是一個(gè)深受懷疑的流行詞，如今情況已經(jīng)完全發(fā)生了改變。量子計(jì)算機(jī)也是一樣。

常用的量子計(jì)算方法包括超導(dǎo)、離子阱和馬約拉納費(fèi)米子法。超導(dǎo)和離子阱是目前產(chǎn)生量子比特最多的方法。但超導(dǎo)需要非常低的溫度，這個(gè)溫度接近絕對零度（接近-460F或-273C），且產(chǎn)生的量子比特非常脆弱且不穩(wěn)定。

微軟使用不太成熟的馬約拉納費(fèi)米子法。目前，這種方法產(chǎn)生的量子比特比其他方法要少，但似乎更不易碎。Jackson博士形容馬約拉納費(fèi)米子法就像編辮子一樣。它們可以被外部環(huán)境推擠，但它們的量子狀態(tài)會(huì)保持不變。他說：“如果我們能夠讓它們大規(guī)模地工作，那么這種方法無疑將會(huì)勝出，但我們對它們知之甚少。”

這場競賽是一場國際性的競爭。人們普遍認(rèn)為，即使沒有處于領(lǐng)先地位，中國也具有很強(qiáng)的競爭力。正如Jackson博士所說，“他們非常重視這方面的研究，并且?guī)缀鯖]有任何預(yù)算限制。”中國在前段時(shí)間已經(jīng)宣稱使用衛(wèi)星完成了量子通信實(shí)驗(yàn)。

劍橋量子計(jì)算（CQC）

CQC成立于4年前，當(dāng)時(shí)投資重點(diǎn)開始從大學(xué)實(shí)驗(yàn)室轉(zhuǎn)移到了微軟、谷歌和IBM等大企業(yè)。CQC積極參與設(shè)計(jì)了一系列提升量子計(jì)算機(jī)效率的工具。最近他們設(shè)計(jì)并測試了一種全新的加密設(shè)備，理論上可提供牢不可破的保護(hù)。

CQC擁有名為“t|ket！”的專利量子編程語言和編譯器。Jackson博士稱這種語言有點(diǎn)類似c語言。其編譯器與平臺(tái)無關(guān)，適用于所有基于眾多不同平臺(tái)的量子計(jì)算機(jī)。它們可以在傳統(tǒng)的數(shù)字CPU和新的量子處理單元（QPU）之間分配計(jì)算工作。

Jackson博士稱，與傳統(tǒng)的圖形處理單元（GPU）負(fù)責(zé)處理密集的圖形負(fù)載一樣，傳統(tǒng)的數(shù)字處理器單元（NPU）負(fù)責(zé)處理常規(guī)數(shù)字計(jì)算機(jī)的繁重?cái)?shù)學(xué)負(fù)載，QPU負(fù)責(zé)處理量子負(fù)載。

CQC的編譯器會(huì)將傳統(tǒng)數(shù)字計(jì)算機(jī)的工作負(fù)載交給普通的CPU，將量子計(jì)算需求交給QPU，然后再將各自的處理結(jié)果重新合成為通用輸出流。Jackson博士稱：“你不需要急于淘汰你的數(shù)字電腦，我們?nèi)匀恍枰鼈??！边@是一個(gè)好消息，因?yàn)槲蚁胫牢覀儗⑷绾螖y帶需要超低溫環(huán)境的計(jì)算機(jī)。

可驗(yàn)證的隨機(jī)數(shù)生成器

CQC還設(shè)計(jì)了一些硬件，其中包括“可驗(yàn)證的”量子隨機(jī)數(shù)生成器。傳統(tǒng)的數(shù)字計(jì)算機(jī)從未能夠生成過真正的隨機(jī)數(shù)，因?yàn)閺臋C(jī)制上說就是不可能的。傳統(tǒng)計(jì)算機(jī)由非常穩(wěn)定且可自然預(yù)測的石英時(shí)鐘驅(qū)動(dòng)，這些時(shí)鐘可確定CPU將在何時(shí)以及以何種速度將信息存入和取出CPU寄存器。每個(gè)時(shí)鐘周期都是固定的。這意味著任何傳統(tǒng)隨機(jī)數(shù)生成器背后的最終“真實(shí)數(shù)據(jù)來源”是可預(yù)測的（即不是真正隨機(jī)的）。

傳統(tǒng)計(jì)算機(jī)中的隨機(jī)性實(shí)際上是在某種程度上近似于隨機(jī)性。缺乏真正的隨機(jī)性將導(dǎo)致許多以隨機(jī)生成數(shù)字為開始的加密解決方案被破解。因此我們不僅需要真正的隨機(jī)數(shù)生成器，還需要驗(yàn)證它們是否真正隨機(jī)才能完全信任它們。

美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）在2018年4月出版的《自然》雜志上討論了對真正隨機(jī)數(shù)生成器的需求。結(jié)果證明量子計(jì)算實(shí)際上非常擅長生成經(jīng)過驗(yàn)證的隨機(jī)數(shù)。最早的可驗(yàn)證的量子隨機(jī)數(shù)生成器的體積非常龐大且速度相當(dāng)慢。

隨機(jī)數(shù)如何在后量子世界中保護(hù)密碼

CQC已經(jīng)研發(fā)了一款名為IronBridge的基于硬件的原型單元，大小與VCR相當(dāng)，預(yù)計(jì)每秒可產(chǎn)生大約400萬個(gè)隨機(jī)比特。它們足以投入商業(yè)使用支持加密協(xié)議，提供量子安全。所有這些數(shù)字都被貝爾不等式驗(yàn)證為真正隨機(jī)的。

誰最在意獲取這類真正的隨機(jī)數(shù)呢？任何希望在量子計(jì)算打破傳統(tǒng)加密方法后保護(hù)數(shù)據(jù)和信息的人。這其中包括政府、科技企業(yè)以及需要保護(hù)其寶貴的知識(shí)產(chǎn)權(quán)、研究和信息的公司。

在差不多二十年前，我曾經(jīng)說過量子“審判日”到來的那一天距我們還有10年時(shí)間，當(dāng)時(shí)這種想法就如同飛行汽車和水下城市的想法一樣看似遙不可及。我和其他人也并不真正相信它們會(huì)很快到來。

但是今天，它們比以往任何時(shí)候都更接近我們。我們已經(jīng)有了可運(yùn)行的量子計(jì)算機(jī)，量子比特的數(shù)量也正在快速增長。它們已不再是一個(gè)被炒作起來的自日夢。強(qiáng)國和大大小小的公司正在努力在剩余的少數(shù)問題上取得實(shí)質(zhì)性進(jìn)展。這些只是一個(gè)時(shí)間問題，而現(xiàn)在是時(shí)候開始評估量子計(jì)算的到來時(shí)間了，這一時(shí)間已經(jīng)縮短到了幾個(gè)月或幾年而不再是幾十年。