量子計算時代的安全加密算法研究

王 東 李春平 張淑榮

（廣東白云學院，廣東 廣州 510450）

1 引言

云安全是保護云計算數據和基礎設施的一套機制。它用于保護用戶的數據完整性、身份驗證和機密性。云安全涉及數據存儲和傳輸安全，其中，密碼學是保障云計算安全的重要方法。量子計算基于量子物理原理，例如疊加和糾纏[1]，在量子計算中，僅僅增加幾個額外的量子比特就可帶來處理能力的指數級飛躍，將當前計算條件下需一萬年的處理時間縮短為幾分鐘[2]。因此，量子計算機因其超高速的迭代加密密鑰和破解密鑰能力已成為云安全的主要威脅。本文對量子計算機對云安全以及當前的數據加密技術的影響進行展望，并提出針對量子計算機的安全加固方案。

2 傳統加密算法

作為云安全的重要組成部分，密碼學是一種大規模的分布式計算模型，在資源共享過程中保證信息的安全性和隱私性。目前使用的兩種類型的密碼系統是：對稱密碼體系和非對稱密碼體系。對稱密鑰算法(SKA)是單密鑰加密，SKA使發送方和接收方擁有相同的密鑰來加密和解密數據。目前常見的兩種類型的SKA是：分組密碼和流密碼。分組密碼使用密鑰在電子數據塊中對特定長度的比特流進行加密。系統將數據存儲在其內存中，在加密過程中檢索完整的塊[3]。云計算中使用的主要的SKA加密方法包括DES、Triple-DES、AES和河豚算法。例如，Amazon Web Services (AWS)、Google AES 128）均為應用于數據存儲的加密技術。非對稱密鑰算法(AKA)使用公鑰加密發送給接收方的消息，使用私鑰在接收端解密信息。接收者是其私鑰的唯一持有者。在非對稱加密系統中，每個接收者都擁有自己的解密密鑰（私鑰），接收方生成加密密鑰（公鑰）。通常，受信任的第三方參與確定特定公鑰的所有者[4]。云計算中使用的一些流行的SKA技術包括：RSA、DSA、橢圓曲線技術等。

3 量子計算

量子計算是近幾年來興起的計算科學領域的研究熱點之一。量子計算機中的量子位可以處于疊加狀態，這意味著量子同時保持“開”或“關”狀態，由于量子位于這兩種狀態之間的某個光譜上，而不僅僅是“開”或“關”兩種狀態。量子比特可以糾纏在一起。同時，兩個粒子可以連接在一起，即使它們在物理上是分開的。量子計算機的行為方式與普通計算機完全不同，量子計算機的量子力學算法研究成為一門新學科。

3.1 易受量子算法影響的加密系統

密碼學是目前確保電子郵件、密碼或金融交易安全的主要認證識別手段，量子計算具有快速運算的能力，其已成為當前密碼學的嚴重威脅。許多研究人員透露，量子計算機能夠通過計算或嘗試所有密鑰方式，快速破解密碼密鑰。此外，黑客亦會利用持續優化的量子算法破解當前通信的安全加密算法。例如：Peter Shor的算法幫助量子機器找到整數的質因數；Lov Grover的算法幫助量子計算機迭代可能的排列。

3.1.1 Shor算法

Shor算法是Peter Shor于1994年發明的。2001年，IBM使用具有Shor算法的七量子位量子計算機將15分解為3和5，實現了量子計算機破解現有加密方法的初步嘗試。非對稱密碼學使用素數分解作為其安全性的基礎。素數分解是一項艱巨的任務，在普通計算機中僅靠窮盡計算很難在短期內實現破解。由于Shor算法可以快速解決素整數分解或離散對數問題[5]，配備了Shor算法的量子計算機可以破解現代非對稱加密系統。

3.1.2 Lov Grover算法

1996年，Lov Grover發明了一種基于量子技術的數據庫搜索算法，并在傳統電腦中搭建了快速搜索引擎。對稱加密算法的設計模式和密鑰長度是衡量加密系統安全性的重要指標，如：AES系統，密鑰長度為18的AES算法目前被普遍采用。借助量子計算機，Lov Grover算法能加速處理并將128位密鑰轉換為64位密鑰的量子計算等效項并實現對AES加密系統的快速破解。在這種情況下，量子計算用于搜索未排序的數據庫。搜索未排序的數據庫需要線性搜索，這需要O(N)時間，但Lov Grover算法僅需一半的搜索時間便可在含有N個條目的亂序數據庫中檢索出某一特定條目。Lov Grover算法將對稱密碼的復雜度從O(N)降低到O(N/2)，這使得當前對稱密碼學的加密機制很容易被破解。

4 量子算法破解加密

4.1 Shor算法和非對稱加密(RSA)

Shor算法可用于破解非對稱密碼系統。例如，RSA加密系統通常使用一對密鑰：一個公鑰和一個私鑰。公鑰用于加密消息，只能使用私鑰解密。私鑰是兩個大素數p和q。這些數字相乘得到RSA算法的公鑰N。將私鑰相乘以計算公鑰是一項輕松的任務，但幾乎不可能將公鑰分解為私鑰。Shor的算法使分解變得更容易。它以一個隨機數g開頭。歐幾里得算法用于尋找g和N的最大公約數，其中N是公鑰。當g是N的一個因子或與N共享一個因子的情況下：找到N的最大公約數是一個素因子，比如q，然后找到另一個因子將是N除以q的簡單數學問題。但在g和N互質的情況下，可猜測一個隨機數g。隨機數g具有N因子的概率可以通過以下數學事實來增加：如果兩個數字a和b互質，則gp=m*b+ 1 ，可表示為：

這時gp/2 + 1與N共享一個因子，并且最大公約數(gp/2 + 1,N)將給出N的素因子。但要計算最大公約數(gp/2 + 1,N) ，需要找到周期p。am(modb)表示兩個相對素數，其中m = 0，1，2……依此類推[6]，給出了一個周期性的余數序列。這可以使用下面的數字2a(mod 15)看出：

2amod 15 20mod 15 21mod 15 22mod 15 23mod 15 24mod 15 Output 1 2 4 8 1

在這里，余數在間隔4之后重復。因此，周期是4。而針對復雜情況，特別是那些516位或以上的數字運算，采用傳統的計算機很難在有效時間內得到解。但借助量子計算的手段，計算速度得到飛速提升。Shor的量子計算算法可以將隨機的、很難被猜測到的g轉換為gp/2 + 1 ，其與N共享一個因子的概率很高，其中p是重復周期。對于那些516位或更多的數字，量子計算機可以通過疊加輸入的方法在短短幾分鐘內完成運算。首先取輸入條件：1＞+2＞+3＞+...并通過輸入條件提高初始數的冪并給出輸出：g1＞+g2＞+g3＞+...，這是初始化數字對輸入數字的冪。這些疊加被傳遞到另一臺量子計算機中。第二臺量子計算機計算gx(modN)并給出具有g的冪的余數疊加的輸出結果，并用gx(modN)得出該余數，其運算過程如下：

針對上面給出的g=2和N=15的例子，第二臺量子計算機得出的輸出結果是：

此時，計算結果在周期4之后出現重復。類似地，對于較大的數字N和g，其運算結果會在周期p之后出現重復。如果采用所有可能的冪的疊加來測量余數，那么量子計算機會給出可能的余數r的一種結果作為輸出。雖然沒有得到最終的解，但量子計算機中的狀態疊加減少到僅產生余數r的g的冪，這個冪結果以p為周期重復，并將余數保留在疊加中。這種疊加可以被視為具有周期p和頻率f的波。疊加的頻率可以使用量子傅里葉變換計算（QFT）給出單個量子態作為輸出( 1/p)。在p值已知的情況下，可以將猜測從g提高到gp/2 + 1 ，再次取(gp/2 + 1,N)的最大公約數，得出N的質因數之一，再通過將N除以p，得出另一個素因子[7]。此時，采用Shor算法的量子計算機就實現了對非對稱加密算法的破解。

4.2 Lov Grover對稱密碼算法

配備Grover算法的量子計算機可迅速破解對稱密鑰算法(AES)。基于Grover算法的量子搜索算法可以在O(n1)中搜索關鍵空間，其包含一個二次加速。例如，對于n位對稱密碼算法，量子計算機重在破解2n個可能的方式。研究表明，量子計算機采用Grover算法后，針對AES128位加密系統，攻擊時間可減少到264次，而對于AES-256位對稱加密系統，攻擊時間則減少到2128次。Grover算法的目的不僅是搜索密鑰數據庫，而且是將其描述為反相函數。假設我們有一個函數y=f(x) ，Grover的算法計算已知y的x的解。此時，求解反函數相當于在數據庫中搜索出給定值y的x解，采用Grover算法的量子計算機在破解AES加密系統時極大地縮短了時間。

5 量子計算時代的密碼學

量子計算機憑借其快速的計算機能力，結合相應的算法，已對現有基于傳統密碼學的云安全產生了威脅，但當前部署應用量子計算機的綜合成本很高，目前雖然已有在云端部署量子計算服務的實例，但距離量子計算的廣泛商用化還相距甚遠[8]。由于早期的量子計算服務可能會通過云部署，因此云安全最迫切需要創建一個抗量子的安全系統。這種安全系統需要利用量子計算所具有的運算優勢，將云安全的水平提升到更高的高度。新興的量子密碼學學說提出了構建量子計算分發量子密鑰的密碼系統，并被看作是量子計算時代的安全解決方案。

5.1 量子密碼學

量子密碼系統使用光子攜帶量子密鑰，光子充當無法復制或更改的移動粒子。量子密碼學的安全性依賴于光子的這一特性，使其在當前技術條件下不可攻破。量子密碼學最重要的部分是量子密鑰分發（QKD）。量子密鑰分發是使用經過身份驗證的通信通道來建立密鑰的過程，使用一系列光子通過光纜將數據從發送方傳輸到接收方[9]。目前，很有希望取得成功的量子密鑰分發的系統是BB84協議。在BB84協議中，量子位用于編碼信息，光子用于攜帶該信息。

量子密鑰分發對竊聽具有很強的魯棒性，考慮到光子狀態在被復制或篡改時會發生變化，發送方可以檢測到這種變化并向接收方發送新密鑰以重新加密發送信息。量子密鑰分發還可以創建一個具有量子彈性的安全和通信生態系統，因此即使使用量子計算機也很難破解基于量子的密碼系統[10]。

5.2 量子計算的局限性

傳統計算機需要數年才能完成的計算工作量對于量子計算機而言僅需要很短的時間，但量子計算機因其自身的計算特性存在著一些不穩定性和局限性影響了量子計算機的大規模應用[11]：

(1)基于量子的密碼學需要在發送者和接收者之間建立一個量子通道，在當前的通信網絡中還沒有這種量子通道。

(2)量子計算機對噪聲失真和環境影響極其敏感，對運算結果影響很大。

(3)量子計算在當前還處于運算論證和演示階段，量子計算自身的脫散問題造成信息難以被存儲。

(4)量子計算尚缺乏容錯、糾錯等機制，本身造成的錯誤率難以預測和發現。

6 量子計算時代密碼學發展方向

盡管量子計算機以目前的能力可能無法破解當今所有的密碼系統，但量子計算正在快速發展，新型的匹配算法正不斷被推出。Shor和Grover的算法已被證實對當前密碼系統造成了顯著的威脅。量子計算機在計算時間和應對復雜任務方面的能力要遠遠優于傳統的超級計算機。但目前適配量子計算機的算法還不多，例如：多重解決方案的問題還不能被量子計算機有效解決[12]。當前，主要有四種量子密碼系統的研發引領著量子計算的發展方向。

6.1 基于格的密碼學

基于格的密碼學具有抵抗數百萬量子位的容錯通用量子計算機的密碼破解能力。與RSA不同，基于格的加密方案不是乘以素數，而是采用乘法矩陣。最短向量問題(SVP)是一個NP-hard問題，其目標是在格中找到最小的非零向量。基于格的密碼系統的安全性依賴于難以解決的格系統內的坐標[11]。目前，用于求解最短向量問題需要在多種方案中求最優解，而量子計算機無法通過多種解決方案快速解決問題。

6.2 基于多變量的密碼學

基于多變量的密碼學是一種采用公鑰密碼的加密系統，它使用有限域上的多變量方程系統作為其公共映射。其安全性取決于有限域上的二次多項式方程的NP硬度。多元加密方案目前是簡單的矩陣加密方案，解密過程僅由線性系統的解組成。多元密碼系統也可用于數字簽名，UOV和Rainbow方案是代表例子。

6.3 基于哈希的密碼學

基于哈希的密碼學是一種量子認證密碼方案，其廣泛用于驗證文檔的數字簽名中。LamportDiffie或Winternitz等數字簽名與基于簽名的RSA不同，基于散列的密碼學產生的簽名僅供一次性使用，它不受Shor算法等量子攻擊的影響，即使使用量子計算機，要破解加密哈希函數也很困難。在后量子時代，基于散列的密碼學因其對抗量子算法的魯棒性而被寄予厚望。基于散列的加密已成為現有RSA和ECDSA的合理替代方案，在不久的將來基于散列的加密很可能會被廣泛采用。

6.4 基于代碼的密碼學

基于代碼的密碼算法采用糾錯碼進行加密和解密。發送方和接收方通過嘈雜的信道進行通信。發送方通過噪聲信道向接收方發送編碼消息，接收方在另一端使用糾錯碼對消息進行解碼。將來，隨著基于代碼的密碼學的廣泛使用，解碼過程將耗時更久。基于代碼的密碼系統的典型代表例子是McEliece密碼系統[13]，因其復雜性較低，它可以用于量子計算的加密密鑰交換，也可實現快速加密和解密數據。

7 結論

量子計算時代終將到來，它將與計算機網絡通信和人工智能等既有學科一起對世界產生深遠影響。當前，以非對稱算法和對稱算法為代表的傳統密碼學在量子計算面前暴露出了安全的脆弱性。量子計算具有高效破解傳統加密算法的技術條件。在量子計算方面，有研究顯示出結合了Shor算法和Grover算法的量子計算機具有快速破解AES和DES等云計算常用的對稱加密系統的能力[14]。本文對相關的科研成果進行了梳理，重點介紹了Shor和Lov Grover算法。以量子密碼學為代表的量子安全伴隨著量子計算的發展而發展，隨著量子加密的實現，量子密碼學將帶來深遠的技術革命，并將密碼學的發展提升到一個新的高度。