量子之矛—後量子計算時代你的系統還安全嗎？

• 2019 年 12 月 11 日
• 筆記

Google在今年的3月份，推出一款72個量子比特的通用量子計算機Bristlecone，實現了1%的錯誤率，性能超越了IBM去年11月份發佈的 50位量子比特的量子計算機。這一成果引起人們廣泛的熱議和討論，按此速度的發展，量子計算機的計算能力將大大得到提升。對於人工智能（AI）領域來說，這是一大福音；而對於網絡與信息安全領域來說，卻是一個不折不扣的壞消息。舉一個直觀的例子：破解一個RSA密碼系統，用當前最大、最好超級計算機需要花1025 年（而宇宙的年齡為1.38×1010 年），但用一個具有足夠量子比特的量子計算機進行破解，在不到1秒內即可完成。眾所周知，RSA公鑰加密系統廣泛應用於電子政務、電子銀行、電子交易和操作系統等。曾經認為十分安全的加密系統在量子計算機面前，卻似乎不堪一擊。

量子計算機真的可以實現嗎？量子時代的到來，你的系統還安全嗎？如果不安全，有什麼好的防範措施？帶着這些問題，我們一一進行解讀和介紹。建議閱讀用時5-8分鐘。

一、 什麼是量子計算機？

在介紹量子計算機前，先明確量子計算 (Quantum Computation) 這個概念。所謂量子計算，就是利用量子態的疊加性和糾纏性（傳送門：轉變思維，打開量子的大門）進行信息的運算和處理，其最顯著優勢在於「操作的並行性」，即對N個疊加態的量子信息進行一次變換，相當於對N個量子信息同時進行操作。

而什麼是量子計算機（Quantum Computer）呢？所謂量子計算機，它是指具有量子計算能力的物理設備。不同於傳統計算機，量子計算機用來存儲數據的對象是量子比特；不同於傳統計算機，量子計算機用使用量子邏輯門進行信息操作，如對單個量子操作的邏輯門：泡利-X門，泡利-Y門，泡利-Z門和Hadamard門等；對兩個量子操作的雙量子邏輯門：受控非門CNOT，受控互換門SWAP等等。

這些量子的邏輯門的操作可以看做一種矩陣變換，即乘以幺正矩陣（可看做正交矩陣從實數域推廣到複數域）的過程。圖1以Hadamard門為例，表述了對量子態∣0〉的形象操作過程。

圖 1量子門的操作示意圖

由圖可知，Hadamard門可以將一個量子態變成兩個量子態的疊加狀態。形象地說，貓生的狀態通過Hadamard門轉換成生和死的疊加態（概率為狀態幅度的平方，概率各為50%）。這種性質十分有用，是實現並行計算基礎，可以將N個輸入數據轉換成一個疊加的量子態，一次量子計算操作，相當於進行了N個數據操作，即實現了N次的並行，後文提到的量子算法正是利用這些量子邏輯門的變換特性。其他量子邏輯門的幺正矩陣有所不同，但操作也類似，這裡不做贅述。

此外，量子計算機用使用的量子邏輯門是可逆的；而傳統計算機的邏輯門一般是不可逆的。前者操作後產生的能量耗散，而後者進行幺正矩陣變換可實現可逆計算，它幾乎不會產生額外的熱量，從而解決能耗上的問題。與傳統的計算機相同的是，量子計算機的理論模型仍然是圖靈機。不同的是，量子計算目前並沒有操作系統，代替用量子算法進行控制，這決定了目前的量子計算機並不是通用的計算機，而屬於某種量子算法的專用計算機。量子計算機和傳統計算機的比較結果如表1所示。

表1 量子計算機VS 傳統計算機

量子計算機的工作原理流程如圖2所示。它主要的過程如下：

(1) 選擇合適的量子算法，將待解決問題編程為適應量子計算的問題。

(2) 將輸入的經典數據製備為量子疊加態。

(3) 在量子計算機中，通過量子算法的操作步驟，將輸入的量子態進行多次幺正操作 ，最終得到量子末態。

(4) 對量子末態進行特殊的測量，得到經典的輸出結果。

圖2量子計算機工作原理流程圖[1]

迄今為止，科學家用來嘗試實現量子計算機的硬件系統有許多種，包括液態核磁共振、離子阱、線性光學、超導、半導體量子點等。其中，超導和半導體量子點由於可集成度高，容錯性好等優點，目前被認為是實現量子計算機的兩種可能方案。

加拿大量子計算公司D-Wave於2011年5月11日正式發佈了全球第一款商用型量子計算機「D-Wave One」。隨後，一些信息科技公司和高校紛紛研究和開發量子計算機。IBM在2017年11月份發佈的 50位量子比特的量子計算機；Google在2018年3月份宣布研製出72比特量子計算機，提高了量子比特數量，提高計算能力。

需要說明的是，多個比特的量子計算在現實的環境中實現起來十分困難。因為它要求所有的量子比特都持續處於一種「相干態」，而這種特殊狀態通常僅能維持幾百毫秒，隨着量子比特的數量以及與環境相互作用的可能性增加，這個挑戰將變得越來越大。因此，實際的量子計算過程中非常容易發生量子比特錯誤。量子編碼的目的正是為了糾錯。由於量子的不可克隆原理和存在多種量子態的原因，傳統的編碼理論不再適用。它成為實現多個量子的計算機亟待解決的一大難點。IBM的50比特和Google的72比特指的是邏輯比特的數量，而一個邏輯比特它會由多個物理的量子比特編碼而成。

二、量子算法—量子計算機的靈魂

可以說，沒有量子算法就沒有高並行的量子計算機。量子算法控制量子計算機的具體計算步驟。在量子算法的研究中，出現了兩個里程碑式的算法：Shor算法和Grove算法，它們對傳統密碼算法產生較大的影響。

1Shor算法—分解大整數，破解RSA

大整數素因子分解難題指的是：將兩個大的質因子p1,p2相乘容易，N =p1×p2，但將它們相乘的結果N分解為兩個素因子十分困難。經典算法求解該問題時計算複雜度會隨着問題的規模指數增長，目前最有效的傳統求解方法複雜度為O (exp[n1/3 (log n)2/3])，其中n表示N的位數。眾所周知，RSA公鑰密碼正是基於這樣的一個數學難題。

1994年，應用數學家Shor 提出了一個實用的量子算法，通常稱為Shor算法。它的出現使得大整數分解問題在量子計算機中在多項式時間內解決成為可能，它計算複雜度僅為 O (n2(log n)(log log n))。顯然，相比經典算法，Shor算法相當於進行了指數加速。算法主要思想是將整數質因子分解問題轉化為求解量子傅里葉變換的周期，將多個輸入製備為量子態疊加，進行並行處理和操作，從而到到了量子加速的目的。

在實際應用中， 2001年，IBM公司的研究小組首次在開發的核磁共振 (Nuclear magnetic resonance，NMR) 量子計算機中使用Shor算法，成功將15分解成3×5，這一成果引起業界廣泛的關注和討論。理論上，一旦更多量子比特的量子計算機研究成功，對於1000位大整數，採用 Shor算法可以在不到1秒內即可進行素因子分解，而採用傳統計算機分解需要1025年。由此可見在量子計算機面前，現有的公開密鑰 RSA體系不再安全。

2Grover算法—對稱密碼安全性減半

搜索問題指的是從N個未分類的元素中尋找出某個特定的元素。對於該問題，經典算法逐個地進行搜尋，直到找到滿足的元素為止，平均需要N /2，時間複雜度為O (N )。

1996年，計算機科學家Grover在提出一個量子搜索算法，通常稱為Grover算法。採用該量子算法進行搜索僅需π/4×√N次次，複雜度為O (√N )。相比傳統算法，它進行了二次加速，再次體現了量子計算並行帶來的高效優勢。舉一個直觀的例子，若要從有着100萬個號碼的電話本中找出某個人的號碼。經典方法是逐個地進行搜索，平均需要搜索50萬次才能找到正確的號碼。而採用Grover的量子算法，它會首先將100萬個號碼製備為量子疊加態。然後在製備的量子疊加態上通過反覆執行量子操作的迭代，每一次迭代，它將放大正確的態（尋找的電話號碼）的概率，同時減少非正確的態的概率。當進行π/4×√100×104 ≈785次後，正確態的概率接近於1，此時去測量，可以正確態的結果，從而得到查找的電話號碼。

暴力窮舉對稱密碼 (如DES/AES等) 的正確密鑰，可以看做一個搜索過程。假設AES的密鑰長度為128位，破解該密碼使用普通的窮舉方法需要大約2128次；而使用Grover算法，卻只需大約264次。由此看來，對稱密碼的安全性在Grover算法下，可以看做其密鑰長度減半。

三、應對措施—抗量子密碼體制

量子計算的快速發展，對當前廣泛成熟使用的經典密碼算法，特別是非對稱密碼算法（如RSA和ECC等）產生了極大的威脅和挑戰，表2列出對三種不同密碼算法的影響，下面進行解釋和說明[3]：

(1) 所有基於整數分解和離散對數上的非對稱密碼體制都是不安全的。如RSA、EEC算法，它們在多項式時間內可以破解。那麼當前主流的公鑰加密、數字簽名算法將不再安全。

(2) 分組密碼和序列密碼的安全性將降低為原來密鑰長度的1/2。為了抵抗這種攻擊，對稱加密算法通過增加密鑰長度（2倍密鑰長度）即可。

(3) Hash 算法的安全性降低為原來的2/3。

表2 量子計算對傳統密碼的影響

為了抵抗量子計算的攻擊，人們提出抗量子密碼體制，也稱為後量子密碼體制(Post-Quantum Cryptography)，即在量子計算機出現之後仍然安全的密碼體制。它主要包含基於 Hash的密碼體制、基於編碼的密碼體制、基於格的密碼體制和基於多變量的密碼體制。具體抗量子密碼體制類型及典型算法如表3所示。

表3抗量子密碼體制及其具體算法

目前，美國和歐洲正在大力對其投入研究，並快速推動其實用化。2015 年8月，美國國家安全局 NSA 宣布將當前美國政府所使用的「密碼算法 B 套件」進行安全性升級，用於2015年至抗量子密碼算法標準正式發佈的空窗期，並最終過渡到抗量子密碼算法。2016 年秋到2017年11月，NIST面向全球公開徵集抗量子密碼算法，計划進行 3~5年的密碼分析工作，預計在 2022年到2023年，完成抗量子密碼標準算法起草並發佈。

四、總結

目前的量子計算機仍然存在諸多問題，如現實中難以達到理想的條件（操作環境無法達到絕對零攝氏度或存在量子噪聲），量子態的操作十分脆弱，通常只能維持幾百毫秒，錯誤難以避免。另外，由於量子不可克隆的特性，導致傳統的糾錯編碼不再適用，這限制量子比特數量的快速增加。然而，量子理論和量子計算機快速的發展表明未來實現高性能的、完整的量子計算機成為可能。量子計算時代的到來，勢必對傳統密碼造成了強大的衝擊。特別是RSA和ECC為代表公鑰密碼，這將直接威脅到PKI（公鑰基礎設施）體系的根基。不僅你的計算機系統不再安全，你的每一封電子郵件也許可以輕易解密，甚至你的電子網銀的金錢將很容易被竊取。為了應對這種威脅與衝擊，我們需要做到的是未雨綢繆，提前設計和研究出安全性更高可以抵抗量子計算攻擊的密碼算法——抗量子密碼體制。

如果您想對量子信息技術有進一步的了解，歡迎查看原文，閱讀我們的報告《漫談量子信息技術：量子通信與量子計算》。

參考文獻：

[1] 郭光燦，張昊，王琴. 量子信息技術發展概況[J]. 南京郵電大學學報(自然科學版), 2017, 37(3):1-14.

[2] 韓永建. 量子計算原理及研究進展[J]. 科技導報, 2017, 35(23): 70-75.

[3] 劉文瑞. 抗量子計算攻擊密碼體制發展分析[J]. 通信技術，2017, 50(5): 1054-1059.

內容編輯：物聯網安全實驗室 陳磊 責任編輯：肖晴