【現如今，密碼在工作生活中發揮著越來越重要的作用，登錄帳戶、快捷支付、網上轉帳收帳，都需要它的參與。試想一下，如果某天我們的密碼被不懷好意的人獲取，會帶來什麼樣的後果呢？還有一個值得思考的問題是，現在的加密技術真的已經無懈可擊了嗎？
其實，量子計算的發展就有可能讓現有的加密技術失效。而我們對此束手無策了嗎？牛津大學量子物理博士，騰訊公司歐洲首席代表葛凌，向我們解釋了量子計算對現代密碼學的威脅、量子計算到來的時間，以及最後我們還可能要利用量子力學來應對量子計算對現有密碼學的威脅。】
本文作者：葛凌（牛津大學量子物理博士 騰訊公司歐洲首席代表）
想想我們在自己的手機、筆記本電腦和臺式機等不同的連接設備中存儲的所有私人數據。這些私人數據包括健康狀況這樣的個人信息，銀行帳戶的帳號，各類地址，發給朋友和家人的私人信息，以及與公司業績和財務狀況有關的公司數據。這些數據被公之於眾的話，對個人和公司來說很可能都是災難性的。
我們怎樣保護私人數據的安全？答案就在現代密碼學——這是一種通過加密和解密，讓保護儲存的信息不被可能懷有惡意的第三方獲取的方法。
然而，量子計算近期的發展已經使人們對這些現代密碼學方法的永久安全性提出了質疑。可擴展的量子計算機可以執行一些算法，使我們能夠打破目前在密碼學中使用的部分加密方法——這將有可能把我們的私人數據暴露給第三方。因此，許多人預測，伴隨著現實中量子計算機的到來，我們將在網際網路上失去隱私。
而且，這種危險看起來正步步緊逼。就在去年，量子計算領域有加速之勢，因為幾家主要的科技公司，比如谷歌、英特爾和IBM，都宣布在量子硬體的研發上取得了顯著的進展。一些人樂觀預測，「量子霸權」（量子計算機超越經典計算機的臨界點）將在2018年到來。
量子計算的發展是否真正威脅到在網際網路上我們的數據的一些核心秘密？(更多背景知識，見059期《騰雲》文章《我們為什麼需要量子計算》)
1 肖爾算法：量子計算革命的催化劑
1994年，美國麻省理工學院的彼得·肖爾（Peter Shor）發表了一篇論文，題為《量子計算機上的質因數分解和離散對數的多項式時間算法》（Polynomial Time Algorithms for Prime Factorisation and Discrete Logarithms on a Quantum Computer）。這篇論文被認為是一劑催化劑，催生了一場延續至今的建造量子計算機的競賽。本質上說，通過使用量子平行處理，肖爾算法(Shor’s Algorithm)使量子計算機上的大整數的因式分解比在經典計算中使用已知最快的算法還要快出很多。更精確地說，肖爾算法差不多可以在多項式時間內因式分解N比特整數，與此相比，在經典計算中最有效的算法（稱作廣義數域篩法，縮寫為GNFS）則差不多需要指數時間。這就預示著RSA方法——它的安全性極其依賴於經典計算機因式分解大數N所需的時間——會立即變得不堪一擊，同樣面臨崩潰的還有網際網路上公鑰密碼的主體部分。
在肖爾算法使用量子計算的性質之前，來自經典數論的一些結果已經被用來恰當地處理這個問題。肖爾算法的特別之處在於，它使用模運算中的周期性的概念——對我們要因式分解的數N進行模運算，一個數x必須被自身乘多少次a才能得出答案是1(也就是xamod N =1)。直到這個周期最終將使我們對N進行分解。
確定這個函數的周期正是量子計算的性質發揮作用的地方，特別是準確地引入量子平行處理這一概念。我們使用兩個量子存儲寄存器——第一個被放置在所有a（a的範圍是從0到q，其中q是2的指數倍，並且滿足N2< q < 2N2）的可能值的疊加態上。注意，這個寄存器必須有足夠的量子比特來表示這個大小的整數，比如說，如果N是一個2048比特數（RSA模數的典型大小），那我們就需要大約4000個量子比特。在第一個寄存器中，會用到以N為模的函數xa，而結果會被存儲在第二個寄存器中（在這一步中，我們利用了量子平行處理的性質）。
接下來，第二個寄存器會被測量，這意味著第二個寄存器從疊加態塌縮到某個值k。第一個寄存器也隨之塌縮，和第二個寄存器保持一致——但是對a的每個值，進行相等的疊加使得xamod N = k。最終，一個叫作離散傅立葉變換的運算被應用到第一個寄存器上，接著輸出m就有很大可能性是這個周期的倍數。一旦得到m，在經典計算機上使用一些相關的簡單數論就可以先找到這個周期，然後是N的因式分解。
當肖爾算法成為密碼學（公鑰）最直接的威脅時，其他一些已經發展起來的算法也對對稱式加密產生衝擊。特別是格羅弗算法(Grover’s Algorithm)，這種算法使得量子計算機的使用者只使用0.758 N0.5次運算就可以在N項列表中發現特定的一項。這又是一個量子計算允許的與直覺完全相反卻又強有力的結果。來看看為什麼。想像一下，我們有10000個盒子，並且隨機地把一個物品藏在其中一個盒子裡。如果我們讓某個人去找到這個物品，那麼他們將最多不得不打開所有10000個盒子才能確定找到這個物品（這個物品也許正好被藏在他們決定最後一個打開的盒子裡）。平均來說，我們可能不得不打開盒子數量的一半才能找到被藏起來的物品，也就是找5000次。然而，使用格羅弗算法，我們實際上可以在0.758√N次運算中就找到結果。在這個例子中，這意味著我們找75.8次（0.758 * √10000）就可以找到這個物品！
這種算法的力量與窮舉搜索攻擊有關。正如我們可以回想起來的，窮舉搜索攻擊就是檢查每一個密鑰的單值來看看那個密鑰是否解碼了一條信息。使用格羅弗算法，我們可以極大地加速窮舉搜索攻擊的過程——例如對於一個長度為128比特的密鑰來說，使用格羅弗算法的話，一次窮舉搜索攻擊可以在 √2128= 264次內完成。同樣，一臺可以運行格羅弗算法的量子計算機將意味著某些標準的密鑰長度需要增加，特別是AES 128比特不再被認為是安全的，而是需要AES 256比特的密鑰。
2 量子計算：影響是什麼？何時到來？
RSA算法並不是今天使用的唯一一種公鑰密碼學方法——其他兩種主要的方法是迪菲—海爾曼（Diffie Hellman）算法和被稱為橢圓曲線密碼學的一組方法，這組方法利用了數學的單向函數的類似用途。然而，根據肖爾算法，所有這些方法都是易受攻擊的。在下面的表格裡，美國國家標準與技術研究院（NIST）歸納了量子計算帶來的影響。
如果不去應對這些挑戰，對我們在網際網路上的數據來說，量子計算機的發展將意味著災難性的安全喪失。數字籤名確認我們是誰，密鑰交換協議管理網頁瀏覽器和伺服器之間的安全，它們都會變得不再安全，而且在網際網路上我們也不再能夠安全地進行很多我們今天想當然認為是安全的活動。例如，輸入帳戶信息去購買產品或者服務，收發私人郵件，保守商業數據的秘密，信任我們在網際網路上瀏覽的網頁的內容——所有這些事情都變得不可能。
一個很自然的問題是，我們距離一臺有能力大規模運行肖爾算法或者格羅弗算法的量子計算機有多遠呢？目前，在建最強大的通用量子計算機的數量級在50-72個量子比特之間。而正如我們在討論肖爾算法時看到的那樣，一臺量子計算機大概需要4000個邏輯量子比特才能因式分解一個2048比特的RSA數。
對以上的一個解釋也許是，實際上我們並不處在建造一臺有能力打破目前公鑰密碼學的量子計算機的中期階段（例如2-5年）內。執行肖爾算法所需的量子比特的數量，遠遠超過今天我們製造的最強大的量子計算機的能力，而且肖爾算法大規模的可靠的應用還沒有被展示出來。今天，我們並不清楚諸如量子比特的退相干，和管理噪聲以減少量子系統中的差錯等面臨的挑戰能否被解決。正因為如此，在短期或者中期內建造這樣一臺可規模化的擴展的量子計算機似乎不太現實。
然而，放眼較長的時間（5-20年），忽視量子計算機對於目前的現代密碼學標準的威脅將會是錯誤的。正如美國國家標準與技術研究院的描述：「一些人預測在接下來的20年左右，足夠規模的量子計算機會被製造出來，基本上可以打破目前使用中的所有公鑰方案。在歷史上，我們花了差不多20年時間去配置現代公鑰密碼基礎架構。因此，不論我們能否準確估計量子計算時代到來的時間，我們都必須現在開始準備我們的信息安全系統，使之能夠對抗量子計算。」
3 後量子密碼學和量子保密通信
那麼，在量子計算被引入後，密碼學看起來是怎樣呢？這裡有兩條路徑——後量子密碼學和量子保密通信。
後量子密碼學
後量子密碼學以數學方法為基礎定義了一系列新的密碼學標準，其中主要是針對公鑰密碼學。這些方法很強大，足以抵擋來自量子計算機的攻擊。美國國家標準與技術研究院已經開始著手實施一項計劃來發展這些新的標準。他們將通過一個階段性的招標流程，收集學術界和工業界對新的密碼算法的建議。2018年4月，這個機構組織的一次會議，討論了第一階段提交的建議。然而，標準草案可能在2022-2024年才會被提出。下面介紹一些有潛力的新方法。
基于格點的密碼 (Lattice Based Cryptography)——格點是N維空間中帶有周期性結構的點集，它和N維的有斑點圖案的壁紙有些相似。某些數學上的格點問題被認為解決起來非常困難，比如最短向量問題（Shortest Vector Problem），就是給定一個特定的基矢，然後找出一些最短的非零向量。這樣的格點問題已經被用來作為構建一些密碼學方法的基礎。一項正在研究的方法叫做NTRU，它於1996年被提出，使用12881比特的密鑰去提供標準的128比特密鑰長度具有的安全性。在第一階段中，眾多提交給美國國家標準與技術研究院的方案都是以NTRU的變體（例如NTRU Prime）為基礎，這些方法具有在效率和安全性之間提供一種優質平衡的潛力。
基於編碼的密碼 (Code Based Cryptography)——這類方法是以糾錯碼為基礎的加密系統，最早於1978年被提出，目前已經發展起來，其中最著名的是麥克利斯（McEliece）算法。這些算法以解碼線性代碼的困難為基礎，算法中的私鑰與一個糾錯碼相聯繫，公鑰與加擾版本相聯繫。這些類型的加密方案的密鑰長度往往會長一些，因此令人不免對它們的效率有些擔憂（如果密鑰長度太長，它的儲存和交換會佔用相當多的資源）。
多元多項式 (Multivariant Polynomials)——在有限場上包含多變量多項式的數學問題已經被建議用來作為新的加密方法的基礎。研究人員已經在這個領域內做出幾項嘗試，意圖建立新的加密方法。然而，由於用到的數學複雜度較低，有些方法已經被證明不安全。還有繼續進行的研究關注這些方法是否可以被數字籤名所採用。
基於哈希的籤名 (Hash-Based Signatures)——這是一種提供數字籤名的方法，其中的數字籤名來自一種叫作哈希函數的數學函數的復用。在今天的網際網路上，哈希函數已經作為鑑別碼（MAC’s）的一部分而被廣泛地使用和理解。這些方法通常有小的私鑰和公鑰，籤名生成都很快，但是密鑰生成相對較慢。
一個基於哈希籤名的方案是XMSS，它在2018年6月1日成為在網際網路工程任務組（IETF，該組織管理網際網路上的開放標準）中發表的第一個後量子籤名方案。這份文件的作者強調，「在面對量子計算機時，他們對這個籤名方案的密碼安全性有信心……同時，網際網路上重要部分的安全性也可以依賴於這個方案」。
以上的這些方法依賴於一個相似的方法——它們都使用被認為是非常困難的數學問題作為自身安全性的基礎（與RSA類似）。把量子計算的發展先放到一邊，如果一個數學家能夠發展一種新的數學方法或者技術，可以解決這些「困難的問題」中的一個，比如說大整數N的因式分解，那基於這個問題的加密系統的安全性就只能讓步。2017年2月，著名的以色列密碼學家阿迪·沙米爾（Adi Shamir）表示：「在我所擔心的事情中，量子計算機並不是排在首位的，我認為更有可能發生的是RSA因為一次數學攻擊而崩潰」。因式分解是RSA的基礎，這個問題至少在幾個世紀裡被很多偉大的數學家廣泛研究過，不過仍然沒有被解決。
然而，對於更新的數學挑戰而言，比如支撐某些後量子加密系統的數學問題，我們可能需要更長一些的驗證周期，才能使這個方法成為一個合適的標準並對它充滿信心。或者，量子保密通信這樣嶄新的概念，可能會使得用高深莫測的數學問題來為密碼學服務的觀點顯得有些多餘。
量子保密通信
在量子計算時代裡，第二種實現安全的方法被稱作量子保密通信。它使用了量子力學本身的性質來確保通信的安全，尤其是通過量子密鑰分配（QKD）。其洞見就在於，與其使用數學問題來確保安全，我們更應該使用量子力學的性質來達到目的，其中最值得注意的是量子不確定性和量子糾纏這兩個概念。這裡有兩個主要的被推薦的協議——Prepare & Measurement (P&M)協議和糾纏(Entanglement)協議。
P&M協議使用海森堡不確定性原理——對一個量子態的測量將會以某種方式改變那個狀態。這個概念就是BB84協議背後的思想，該協議由查爾斯·本內特（Charles Bennett）和吉列斯·布拉薩德（Gilles Brassard）於1984年提出。在這個系統裡，我們用單光子的極化來傳輸信息比特，其中接受者和發送者使用極化的方向來確定被傳輸的比特是0還是1。這種方法的安全性來自於這樣一個事實，即如果一個竊聽者攔截並且試著看被傳輸的光子的數值，他們就會以某種方式幹擾光子的模式，而這種幹擾在消息的傳輸之後是可以被測量到的。我們可以用這種方法建立共享密鑰，因而解決了最早給公鑰密碼學以靈感的這個難題。
理論上這樣一個基於量子原理的系統是安全的，然而實際操作上，量子密鑰分配的物理實現曾經被破壞過，也就是在發送者或者接受者不知情的情況下密鑰被攔截過。同時還要注意，在實踐中，光子在最佳光纜上的實際物理傳輸也會不可避免地持續向系統中引入誤差，因此在現實中，一個估計的誤碼率必須和實際的誤碼率相比較，以確定是否有傳輸達不到標準從而提供了較低的安全水平。從技術上講，發射單光子是很有挑戰性的，因此我們使用發射多光子的雷射，但這也使這個系統容易遭受光子數分束（PNS）攻擊的影響。在光子可以傳輸的距離上同樣也存在限制——使用標準光纜的話，目前距離上限大約是100千米，在這個範圍內量子密鑰分配的方法是可行的。目前的數據傳輸速率也很低，在比較短的距離上，每秒幾百比特是有代表性的速率。不過，即便存在這些挑戰，一些實用的、具有商業可行性的量子密鑰分配系統還是已經成功落地，現在一些機構（例如一些瑞士及中國的銀行）正在用這樣的系統進行密鑰交換。
量子密鑰分配機制的第二種類型是基於糾纏協議，由阿圖爾·埃克特（Artur Ekert）最早在1991年提出。在這種被稱為E91的方法中，一個單獨的源發射一對發生量子糾纏的物體，例如一對極化的光子，比如給愛麗絲和鮑勃，其中一個給愛麗絲，另一個給鮑勃，而他們兩個人在地理位置上是分開的。由於糾纏的性質，如果愛麗絲和鮑勃都以某種方式測量這個極化的話，光子會得到相反的結果（例如，愛麗絲測到的是+1，鮑勃測到的是-1）。通過彼此結果相反的光子對中的一個光子，愛麗絲和鮑勃就可以得到一個共享密鑰。
針對竊聽的保護通過使用一個叫作貝爾不等式（Bell’s Inequality）的不等式來完成——根據量子物理的性質，如果粒子保持真正的糾纏，也就是沒有被一個竊聽者攔截，那這個不等式就不成立。
糾纏作為一種量子密鑰分配的實驗方法一直是研究的熱點。值得注意的是，2017年6月，由中國科學技術大學的潘建偉領導的團隊成功演示了光子之間的糾纏。這些光子由在軌道上的衛星發射，而被位於地面上的基站測量，衛星與基站之間相距1200千米。雖然每600萬個從衛星發射的光子中只有1個能夠被基站探測到，目前實現量子密鑰分配還不足夠，但是這個實驗受人矚目之處在於它證明了「鬼魅般的超距作用」——愛因斯坦如此描述量子糾纏。這個團隊未來的研究計劃包括通過更長的光子流分發實際的量子密鑰到中國的基站。
4 量子力學將可能挽救現代密碼學
人類不同個體之間希望保持信息的私密這一願望，同語言本身一樣古老，而這個願望所面臨的最根本的挑戰也存在了相同長的時間。兩個人如何商定一個安全的溝通方法，比如說給物品以特別的詞語或代號，或者某種共享密鑰，使得雙方可以彼此理解對方的意思，但是第三方卻做不到？伴隨著數位技術對我們生活的方方面面的侵入，這些問題之於我們自身安全感的重要性無疑在增加——現在我們想使我們的隱私不被我們的各類連接設備觸及幾乎不可能，因此正確地保護信息的安全就變得非常重要。
現代密碼學已經發展出有效、安全的標準和方法，來促進人與人之間對信息的共享，但是這種共享仍然有其脆弱性。一方面，儘管量子計算機的發展似乎在短期內可能性較低，但是卻也使重新考慮和加強這些標準成為必要。快速完成美國國家標準與技術研究院提出的旨在發展安全的後加密算法的計劃是非常重要的，從而安全地升級目前網絡協議的安全性。另一方面，繼續信賴困難的數學問題作為加密系統的基礎，限制了我們對這些系統充滿十足的信心——因為當明天我們醒來的時候，一位聰明的數學家可能已經很好地解決了這些問題。
於是，量子保密通信提供了一種有力的保證，利用量子力學的固有性質來保障安全性，克服了現代加密方法面對數學攻擊時的脆弱性。量子密鑰分配，例如來自衛星的糾纏極化光子，通過量子糾纏和海森堡不確定性原理這樣的基礎量子物理原理來保護通信免於遭到竊聽。它的願景極具吸引力，並且已經開始實驗驗證。
所以，儘管現代密碼學受到來自量子力學的威脅，但最終挽救它的可能也是量子力學。
密碼已與我們的工作生活密不可分，密碼的洩露就意味著個人隱私的洩露，你覺得個人應該如何保護自己的隱私呢？歡迎留言告訴我們~