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

王 東 李春平 張淑榮

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

1 引言

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

2 傳統(tǒng)加密算法

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

3 量子計算

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

3.1 易受量子算法影響的加密系統(tǒng)

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

3.1.1 Shor算法

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

3.1.2 Lov Grover算法

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

4 量子算法破解加密

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

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

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

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

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

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

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

4.2 Lov Grover對稱密碼算法

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

5 量子計算時代的密碼學

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

5.1 量子密碼學

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

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

5.2 量子計算的局限性

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

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

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

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

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

6 量子計算時代密碼學發(fā)展方向

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

6.1 基于格的密碼學

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

6.2 基于多變量的密碼學

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

6.3 基于哈希的密碼學

基于哈希的密碼學是一種量子認證密碼方案，其廣泛用于驗證文檔的數(shù)字簽名中。LamportDiffie或Winternitz等數(shù)字簽名與基于簽名的RSA不同，基于散列的密碼學產(chǎn)生的簽名僅供一次性使用，它不受Shor算法等量子攻擊的影響，即使使用量子計算機，要破解加密哈希函數(shù)也很困難。在后量子時代，基于散列的密碼學因其對抗量子算法的魯棒性而被寄予厚望?；谏⒘械募用芤殉蔀楝F(xiàn)有RSA和ECDSA的合理替代方案，在不久的將來基于散列的加密很可能會被廣泛采用。

6.4 基于代碼的密碼學

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

7 結(jié)論

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