面對量子霸權，公鑰加密將形同虛設

Roger A.Grimes　陳琳華

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

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

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

當今的安全通信都基于一個事實，那就是傳統數字計算機不容易分解涉及大質數的多因子方程。如果量子計算機具備了這種能力，那么對于采取上述方式加密的任何秘密而言，游戲都結束了。

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

回到我多年前的那次演講：在演講結束時的提問環節，有人問我，量子計算機還有多長時間就能夠破解所有秘密。我的回答是“10年。大多數量子物理專家都認為只有10年時間了。”當我走出講臺后，業界知名人士Bruce Schneier走了過來。正如他那貌似漫不經心的步伐一樣，他隨口問了我一句，“你口中的10年到底是多久？”

我給出的10年這個答案是說可能至少10年時間。Bruce讓我意識到我們都不知道確切的答案。量子物理學界流傳的一個笑話是量子計算機總是在10年后出現。

量子計算機的工作原理

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

量子計算機可以憑借其獨特的工作原理“秒殺”傳統的數字計算機。顯然，量子計算機依賴于量子力學（這里涉及的主題太大并且十分復雜），但簡而言之，這就是優勢。數字計算機是二進制的，其中央處理單元（CPU）內的每個晶體管或邏輯門同一時刻只能保持一種“狀態”，是“開”還是“關”，是否通電，是“1”還是“0”。這就是所謂的二進制。

量子計算機的基礎是量子比特。每個量子比特可以同時處于兩個狀態。因此，一個量子比特相當于兩個二進制邏輯門。當引入它們后，量子比特會呈指數級增長。兩個量子比特可以同時保持四種狀態，三個量子比特可以同時保持八種狀態，依此類推。

一臺普通的量子計算機就可能會破解我們之前所有采用公鑰/私鑰對加密的秘密，但是這個過程需要有效的糾錯。

量子計算機將在何時1.2何種方式破解公鑰加密

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

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

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

那么我們在量子計算生命周期中已經處于哪個階段了？按照Jackson博士的說法，量子計算機僅需要49個完美的量子比特就可以勝過傳統的二進制計算機。這就是被大家熟知的“量子優勢”，這將是量子計算機最終超越二進制計算機的關鍵節點。這一時刻的意義與IBM深藍超級計算機在1997年擊敗世界象棋冠軍加里·卡斯帕羅夫時一樣。

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

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

直接從事量子計算機研發的Jackson博士稱：“我們在短短一年內就已經從9個量子比特發展到了72個量子比特，所以我們在今后的五年內獲得4000個量子比特并不是一個瘋狂的想法。鑒于美國政府已經在幾個月前最終決定參與進來，我認為這個時間只是一個保守的估計。”

更多知識淵博的人依然認為我們仍無法知道會在何時取得用于破解公鑰加密的突破性成就。Schneier長期撰寫關于量子密碼學的文章。當得知這一時間是5年時，他說：“我不相信這一說法。沒人知道前面還有什么不可預料的問題。”

Aaronson博士也對此持懷疑態度。他在文章中寫道：“如果這種情況在五年內發生，我會感到十分驚訝。我不是說這不可能，但我認為它們需要更長的時間。如果谷歌、IBM或其他公司在三到五年內成功地制造出了擁有70個量子比特的量子計算機，或是它們能夠在一些（主要是人工）任務中開始超越經典計算機，我會對此感到非常高興。即便如此，由于糾錯和現有容錯方案的龐大需求，它們還遠不能威脅到公鑰密碼技術，因為這很容易導致對高品質的物理量子比特的需求上升至數百萬量級。”

顯然，對于量子計算機何時能夠破解公鑰加密，大家各執一詞，但是這已經不再是科幻小說中的虛構內容了。

雖然美國國家安全局（NSA）也尚未承認很快就會實現量子突破，不過他們已經認為現在是時候開始著手準備了。具體說來，在他們的一份常見問題解答中曾提到，“NSA認為現在時機已經成熟……量子計算正在不斷取得進展……NSA正在尋求與所有的NSA供應商和運營商一起實施基于標準的抗量子破解的密碼技術以保護他們的數據和通信。”

新興的量子計算行業

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

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

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

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

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

這場競賽是一場國際性的競爭。人們普遍認為，即使沒有處于領先地位，中國也具有很強的競爭力。正如Jackson博士所說，“他們非常重視這方面的研究，并且幾乎沒有任何預算限制。”中國在前段時間已經宣稱使用衛星完成了量子通信實驗。

劍橋量子計算（CQC）

CQC成立于4年前，當時投資重點開始從大學實驗室轉移到了微軟、谷歌和IBM等大企業。CQC積極參與設計了一系列提升量子計算機效率的工具。最近他們設計并測試了一種全新的加密設備，理論上可提供牢不可破的保護。

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

Jackson博士稱，與傳統的圖形處理單元（GPU）負責處理密集的圖形負載一樣，傳統的數字處理器單元（NPU）負責處理常規數字計算機的繁重數學負載，QPU負責處理量子負載。

CQC的編譯器會將傳統數字計算機的工作負載交給普通的CPU，將量子計算需求交給QPU，然后再將各自的處理結果重新合成為通用輸出流。Jackson博士稱：“你不需要急于淘汰你的數字電腦，我們仍然需要它們。”這是一個好消息，因為我想知道我們將如何攜帶需要超低溫環境的計算機。

可驗證的隨機數生成器

CQC還設計了一些硬件，其中包括“可驗證的”量子隨機數生成器。傳統的數字計算機從未能夠生成過真正的隨機數，因為從機制上說就是不可能的。傳統計算機由非常穩定且可自然預測的石英時鐘驅動，這些時鐘可確定CPU將在何時以及以何種速度將信息存入和取出CPU寄存器。每個時鐘周期都是固定的。這意味著任何傳統隨機數生成器背后的最終“真實數據來源”是可預測的（即不是真正隨機的）。

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

美國國家標準與技術研究院（NIST）在2018年4月出版的《自然》雜志上討論了對真正隨機數生成器的需求。結果證明量子計算實際上非常擅長生成經過驗證的隨機數。最早的可驗證的量子隨機數生成器的體積非常龐大且速度相當慢。

隨機數如何在后量子世界中保護密碼

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

誰最在意獲取這類真正的隨機數呢？任何希望在量子計算打破傳統加密方法后保護數據和信息的人。這其中包括政府、科技企業以及需要保護其寶貴的知識產權、研究和信息的公司。

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

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