王 東 李春平 張淑榮

（廣東白云學(xué)院，廣東 廣州 510450）

1 引言

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

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

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

3 量子計(jì)算

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

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

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

3.1.1 Shor算法

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

3.1.2 Lov Grover算法

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

4 量子算法破解加密

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

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

這時(shí)gp/2 + 1與N共享一個(gè)因子，并且最大公約數(shù)(gp/2 + 1,N)將給出N的素因子。但要計(jì)算最大公約數(shù)(gp/2 + 1,N) ，需要找到周期p。am(modb)表示兩個(gè)相對素?cái)?shù)，其中m = 0，1，2……依此類推[6]，給出了一個(gè)周期性的余數(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之后重復(fù)。因此，周期是4。而針對復(fù)雜情況，特別是那些516位或以上的數(shù)字運(yùn)算，采用傳統(tǒng)的計(jì)算機(jī)很難在有效時(shí)間內(nèi)得到解。但借助量子計(jì)算的手段，計(jì)算速度得到飛速提升。Shor的量子計(jì)算算法可以將隨機(jī)的、很難被猜測到的g轉(zhuǎn)換為gp/2 + 1 ，其與N共享一個(gè)因子的概率很高，其中p是重復(fù)周期。對于那些516位或更多的數(shù)字，量子計(jì)算機(jī)可以通過疊加輸入的方法在短短幾分鐘內(nèi)完成運(yùn)算。首先取輸入條件：1＞+2＞+3＞+...并通過輸入條件提高初始數(shù)的冪并給出輸出：g1＞+g2＞+g3＞+...，這是初始化數(shù)字對輸入數(shù)字的冪。這些疊加被傳遞到另一臺量子計(jì)算機(jī)中。第二臺量子計(jì)算機(jī)計(jì)算gx(modN)并給出具有g(shù)的冪的余數(shù)疊加的輸出結(jié)果，并用gx(modN)得出該余數(shù)，其運(yùn)算過程如下：

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

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

4.2 Lov Grover對稱密碼算法

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

5 量子計(jì)算時(shí)代的密碼學(xué)

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

5.1 量子密碼學(xué)

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

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

5.2 量子計(jì)算的局限性

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

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

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

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

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

6 量子計(jì)算時(shí)代密碼學(xué)發(fā)展方向

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

6.1 基于格的密碼學(xué)

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

6.2 基于多變量的密碼學(xué)

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

6.3 基于哈希的密碼學(xué)

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

6.4 基于代碼的密碼學(xué)

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

7 結(jié)論

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