今年8月的時(shí)候，美國(guó)國(guó)家安全局（NSA）在其網(wǎng)頁(yè)上更新了一段不起眼的內(nèi)容，他們計(jì)劃對(duì)現(xiàn)在政府和軍方加密數(shù)據(jù)的方式更新，以期能夠阻擋來(lái)自量子計(jì)算機(jī)的攻擊。NSA的發(fā)言人表示，量子計(jì)算機(jī)能夠帶來(lái)更新更強(qiáng)的計(jì)算能力，顯然現(xiàn)有的安全措施和加密方式無(wú)法承受來(lái)自這種設(shè)備的攻擊。如果要嚴(yán)密保護(hù)國(guó)家系統(tǒng)的安全的話，那么他們需要在這一方向取得顯著發(fā)展。

量子計(jì)算機(jī)對(duì)于過(guò)去的人而言聽(tīng)起來(lái)就像是遙遠(yuǎn)的神話，但現(xiàn)在人們普遍認(rèn)為在5到30年內(nèi)它就將成為現(xiàn)實(shí)。通過(guò)不斷探索量子物理的法則，不管是NSA的絕密檔案、銀行記錄還是郵箱密碼，這種機(jī)器能夠解密現(xiàn)在世界上絕大多數(shù)“機(jī)密”的數(shù)據(jù)。在意識(shí)到這可能的威脅后，密碼學(xué)家們正在量子計(jì)算機(jī)大范圍使用以前，抓緊開(kāi)發(fā)能夠防止量子破譯的方案。

現(xiàn)在看來(lái)，最可行的方案是基于格的數(shù)學(xué)方案（mathematicsoflattices）。這種方案有效性在于，要在一個(gè)擁有幾百空間維度的格中找出隱藏的信息非常難，除非你知道那條秘徑。

但是去年十月，英國(guó)政府通訊總部（GCHQ）的密碼專家發(fā)表論文指出，即便是最有效的格方案也面臨著安全問(wèn)題。這些發(fā)現(xiàn)意味著，在以效率為目標(biāo)發(fā)展了幾十年后，這種高效暴露出了安全風(fēng)險(xiǎn)。專家們通過(guò)簡(jiǎn)化他們方案中的格，導(dǎo)致這些方案更容易受到攻擊。

基于上面所述的問(wèn)題，一些密碼專家從去年開(kāi)始都在做實(shí)驗(yàn)，看哪些基于格的方案會(huì)被量子計(jì)算機(jī)打破，而哪些至少對(duì)于現(xiàn)在而言又是安全的。對(duì)于編寫密碼和破解密碼的專家而言，這就是一場(chǎng)貓鼠游戲。當(dāng)解碼員沉默的時(shí)候，編碼員為了效率會(huì)放松方案的安全性，有時(shí)候，其結(jié)果就是導(dǎo)致安全越過(guò)了那條紅線。

公開(kāi)的秘密

在談?wù)撨@一話題前，我們需要先對(duì)現(xiàn)在的加密方式有一個(gè)了解。事實(shí)上，當(dāng)你每次訪問(wèn)以“HTTPS”開(kāi)頭的鏈接時(shí)，你都會(huì)發(fā)送和接收加密的信息，而這一安全的網(wǎng)絡(luò)交易方式使用了基于加密技術(shù)的公共密鑰。這一創(chuàng)造性的發(fā)明始于上個(gè)世紀(jì)70年代，而在此前，密碼技術(shù)基本就是政府和間諜之間的比賽。通常而言，參與信息傳遞的人，例如一個(gè)人和他的對(duì)接人之間如果想要偷偷交流的話，要事先約定一個(gè)暗號(hào)或者“鑰匙”。而公共密鑰的技術(shù)則可以讓任何人給其他人發(fā)送一組加密信息，不管是否有人在偷聽(tīng)，只有指定的接受人可以解密，即使參與的人一開(kāi)始并沒(méi)有串通好。

在公鑰加密技術(shù)中，人們通過(guò)一些數(shù)學(xué)技巧來(lái)保證數(shù)據(jù)的安全性，一些數(shù)學(xué)問(wèn)題解答起來(lái)容易，但是要用逆向工程解碼則很難。例如，要計(jì)算機(jī)計(jì)算兩個(gè)質(zhì)數(shù)的乘積很容易，但是如果給計(jì)算機(jī)一個(gè)數(shù)，要它解出組成這個(gè)數(shù)的質(zhì)因子，則可能要花費(fèi)很多時(shí)間。在基于質(zhì)數(shù)分解的方案中，這個(gè)質(zhì)數(shù)就是某人并不與他人共享的“私鑰”。而質(zhì)數(shù)的乘積則是“公鑰”，公開(kāi)分發(fā)。當(dāng)某人用公鑰來(lái)加密信息時(shí)，只有這個(gè)擁有私鑰的人才能夠解密信息。

有兩個(gè)公鑰加密方案自上世紀(jì)70年代以來(lái)廣為應(yīng)用：一個(gè)是基于質(zhì)因子的RSA方案，另一個(gè)是基于離散算法的Diffie-Hellman方案。雖然這兩種方案并不是說(shuō)一定就無(wú)法破解，但是沒(méi)人能夠找到高效計(jì)算出結(jié)果的方法。如果要用計(jì)算機(jī)將特定長(zhǎng)度的公鑰進(jìn)行計(jì)算出來(lái)，可能要花費(fèi)數(shù)年的時(shí)間。因此，這兩種方案成了保護(hù)互聯(lián)網(wǎng)信息的力盾。不過(guò)它們帶來(lái)的這份安全，似乎已快來(lái)到了終結(jié)之時(shí)。

Shor的算法

計(jì)算機(jī)難以短時(shí)計(jì)算出結(jié)果這一神話在1994年被打破，當(dāng)時(shí)AT&T的研究人員PeterShor提出了一種理論，他認(rèn)為未來(lái)的量子計(jì)算機(jī)會(huì)具有破解算法的能力。

在普通計(jì)算機(jī)中，信息以比特的形式存儲(chǔ)。比特存在兩種狀態(tài)中的一種，即0或者1，而計(jì)算機(jī)的計(jì)算能力與比特?cái)?shù)量相稱。但是在量子計(jì)算機(jī)中，數(shù)據(jù)是用量子位方式存儲(chǔ)的，數(shù)據(jù)存儲(chǔ)格式既可以是0也可以是1。由于大量的量子位，使得其中可以存在大量可能的組合形式和可能的個(gè)體狀態(tài)。因此隨著量子位數(shù)量的上升，量子計(jì)算機(jī)的計(jì)算能力會(huì)以指數(shù)級(jí)的方式增長(zhǎng)。

基于此，量子計(jì)算機(jī)比普通計(jì)算機(jī)會(huì)具有更強(qiáng)的運(yùn)算能力。然而要開(kāi)發(fā)出其潛力，還必須同時(shí)找到一個(gè)合適的算法，能夠充分利用這種同時(shí)存在的狀態(tài)，即得到正確的解答。80年代量子計(jì)算機(jī)被提出來(lái)以后，超過(guò)10多年間都沒(méi)有什么有用的算法出現(xiàn)，這個(gè)領(lǐng)域似乎前途暗淡。

變化發(fā)生于1994年，Shor提出了一個(gè)量子計(jì)算機(jī)算法，能夠高效破解了質(zhì)因子和離散算法，也就是說(shuō)打破了RSA加密方法和Diffie-Hellman密鑰交換理論。于是一瞬間，人們對(duì)量子計(jì)算機(jī)的興趣一下子燃燒了起來(lái)。隨著Shor的算法揭示出了量子計(jì)算機(jī)高級(jí)的運(yùn)算能力后，世界范圍內(nèi)的研究人員爭(zhēng)相進(jìn)行研究，試圖找出破譯的方式。而與之相對(duì)應(yīng)的是，密碼編譯專家們也在競(jìng)相賽跑，提出量子計(jì)算機(jī)無(wú)法攻破的方案。最后他們發(fā)現(xiàn)，格似乎是一個(gè)不錯(cuò)的選擇。

迷失在格里

其實(shí)同RSA加密方案類似，理論上來(lái)說(shuō)，計(jì)算質(zhì)數(shù)的乘積很容易，但是求解質(zhì)因子很難，基于格的安全加密方案也取決于，讓計(jì)算機(jī)迷失在一個(gè)500維的格中有多難。不同的是，在格方案中，私鑰與格點(diǎn)相關(guān)，而公鑰則與空間中的特定位置有聯(lián)系。

除了一開(kāi)始的驚艷，這種加密方案卻發(fā)展遲緩。80年代的時(shí)候，這種方案的公鑰都太長(zhǎng)，交換數(shù)據(jù)需要海量的字節(jié)空間。為了提高效率，密碼學(xué)家不得不簡(jiǎn)化潛在的格。在一個(gè)普通的格中，格點(diǎn)是由計(jì)算一組向量的線性組合得出。給這些向量分配一個(gè)模式，使得算出來(lái)的結(jié)果簡(jiǎn)單化，則相關(guān)的密鑰也更短。但這帶來(lái)的問(wèn)題是，簡(jiǎn)化方案使得人們可以從公鑰中推論出私鑰，從而破壞這個(gè)方案。因而，格對(duì)于密碼學(xué)來(lái)說(shuō)，又成了災(zāi)難的代名詞。

隨著時(shí)間的前進(jìn)，一些密碼學(xué)專家仍然在不斷完善格。1995年的時(shí)候，一些專家提出了一種基于“環(huán)狀”的格，可以產(chǎn)生在任意方向旋轉(zhuǎn)的向量。這個(gè)名為NTRU的方案極其高效，甚至比老的RSA和Diffie-Hellman方案更高效。盡管沒(méi)有證據(jù)表明這種方案就是一定安全的，但20年過(guò)去了還沒(méi)有人能破解它，證明某種程度上還是具有安全性的。

格的前景自1997年以后變得明朗起來(lái)，IBM的研究人員提出第一種較好的加密方案，這種加密方案名為L(zhǎng)earningWithErrors（LWE），意即伴隨誤差學(xué)習(xí)，由于要找到最近的通用格要很長(zhǎng)時(shí)間，因而可以抵抗來(lái)自量子計(jì)算機(jī)的攻擊?；诶硐敫裣?，他們開(kāi)發(fā)出了一個(gè)更行之有效的方案。

什么是LWE方案

在2005年，OdedRegev基于LWE問(wèn)題提出了一種加密方案，他證實(shí)這個(gè)方案解決起來(lái)很難，因而比較安全。這個(gè)方案的基本思路是這樣的：

首先選擇任何一個(gè)奇數(shù)，并且不要告訴任何一個(gè)其他人，這就是你的私鑰。然后把它乘上任何一個(gè)數(shù)，再加上一個(gè)小的偶數(shù)。重復(fù)多次，得到一系列的數(shù)，這些數(shù)就是你的私鑰，然后再把它們告訴別人。

現(xiàn)在，如果有誰(shuí)想給你發(fā)信息，如0或1，首先這個(gè)人隨機(jī)地在你的公鑰里選擇一半的數(shù)，把它們加起來(lái)。然后如果要發(fā)送0，他們就把數(shù)據(jù)加起來(lái)然后發(fā)給你。如果要發(fā)送1的話，就把數(shù)據(jù)加1并發(fā)給你。之后你想要解碼這段數(shù)據(jù)的話，只要用你的私鑰求出這個(gè)和數(shù)的商。如果余數(shù)是偶數(shù)的話，這個(gè)信息就是0。如果是奇數(shù)，則為1。

再一次，人們似乎又要在安全和效率間進(jìn)行權(quán)衡。魚(yú)和熊掌不可兼得，LWE方案雖然更加通用并且安全性更高，但它的效率較低。研究人員在這個(gè)方向上，還在不斷探索，之后提出了一些其他方案。

貓鼠游戲

不僅科研人員在開(kāi)發(fā)基于格的加密方案，GCHQ的人員也在做同樣的事。他們使用數(shù)論開(kāi)發(fā)除了名為Soliloquy的方案，把公鑰的大小從一個(gè)包含大量數(shù)據(jù)的矩陣降為僅僅是一個(gè)質(zhì)數(shù)。把它量化到格里而言，則是產(chǎn)生一個(gè)非常短的矩陣。然而，這種方案的便利也正是其致命之處。

在他們發(fā)布的論文中可以看出，他們雖然發(fā)明出了這種方案，但是在2013年后又棄用了，原因是他們發(fā)現(xiàn)量子攻擊可以把這個(gè)加密方案攻破。雖然這篇論文只是對(duì)攻擊草草描繪了一下，但是給人們留下了無(wú)限的疑問(wèn)：其他的格方案是不是也會(huì)受到影響？似乎在追求效率的同時(shí)，安全的紅線隨時(shí)也被越過(guò)。問(wèn)題是，這條安全的警戒線到底該放在哪里？

GCHQ的團(tuán)隊(duì)并沒(méi)有找出多少細(xì)節(jié)，而僅僅是覺(jué)得有很強(qiáng)的證據(jù)證明，這種攻擊會(huì)被開(kāi)發(fā)出來(lái)，因而就推論Soliloquy不適用于現(xiàn)實(shí)。于是密碼學(xué)家們花了差不多一年來(lái)了解Soliloquy攻擊的范圍，此后研究人員發(fā)現(xiàn)，這種攻擊竟然只需要一臺(tái)普通的電腦就可以實(shí)現(xiàn)。

除了Soliloquy以外，他們的發(fā)現(xiàn)還表明，其他基于理想格的方案，構(gòu)造單獨(dú)短向量的方法也可以被攻破，而基于一般格的方案，如Ring-LWE和NTRU則不受影響。用研究人員的話來(lái)說(shuō)，似乎想要把這些技術(shù)轉(zhuǎn)化成有效的方案還有一些技術(shù)上的難題，需要更深的研究。

就安全和效率的對(duì)稱性而言，密碼學(xué)家過(guò)于傾向效率這一邊。在他們給政府和銀行等機(jī)構(gòu)尋找最好的抵御量子攻擊的時(shí)候，Soliloquy這樣的攻擊迫使他們重新審視過(guò)去，回到那些可能沒(méi)有那么有效率，但是更加穩(wěn)固的方案。對(duì)于一個(gè)方案而言，在效率和安全性這兩條相反的道路上，還是需要研究人員仔細(xì)權(quán)衡。

相關(guān)閱讀：

安全性設(shè)計(jì)如何選擇可靠的隨機(jī)數(shù)加密方案？
詳細(xì)解析嵌入式加密工作原理
工業(yè)計(jì)算機(jī)的主板該如何選型？有哪些竅門？