【導(dǎo)讀】可能大多數(shù)人都認為量子計算機屬于科幻技術(shù),但是專家告訴你近幾十年量子計算機將有可能實現(xiàn),屆時超強的計算機能力勢必會對加密技術(shù)造成威脅,那么有沒有一種加密技術(shù)能夠抵御量子計算機的形成的威脅?本文再次為你解析,加密技術(shù)抵御量子計算機,不僅涉及到技術(shù)問題,還涉及到安全與效率的問題。
今年8月的時候,美國國家安全局(NSA)在其網(wǎng)頁上更新了一段不起眼的內(nèi)容,他們計劃對現(xiàn)在政府和軍方加密數(shù)據(jù)的方式更新,以期能夠阻擋來自量子計算機的攻擊。NSA的發(fā)言人表示,量子計算機能夠帶來更新更強的計算能力,顯然現(xiàn)有的安全措施和加密方式無法承受來自這種設(shè)備的攻擊。如果要嚴密保護國家系統(tǒng)的安全的話,那么他們需要在這一方向取得顯著發(fā)展。
量子計算機對于過去的人而言聽起來就像是遙遠的神話,但現(xiàn)在人們普遍認為在5到30年內(nèi)它就將成為現(xiàn)實。通過不斷探索量子物理的法則,不管是NSA的絕密檔案、銀行記錄還是郵箱密碼,這種機器能夠解密現(xiàn)在世界上絕大多數(shù)“機密”的數(shù)據(jù)。在意識到這可能的威脅后,密碼學(xué)家們正在量子計算機大范圍使用以前,抓緊開發(fā)能夠防止量子破譯的方案。
現(xiàn)在看來,最可行的方案是基于格的數(shù)學(xué)方案(mathematicsoflattices)。這種方案有效性在于,要在一個擁有幾百空間維度的格中找出隱藏的信息非常難,除非你知道那條秘徑。
但是去年十月,英國政府通訊總部(GCHQ)的密碼專家發(fā)表論文指出,即便是最有效的格方案也面臨著安全問題。這些發(fā)現(xiàn)意味著,在以效率為目標(biāo)發(fā)展了幾十年后,這種高效暴露出了安全風(fēng)險。專家們通過簡化他們方案中的格,導(dǎo)致這些方案更容易受到攻擊。
基于上面所述的問題,一些密碼專家從去年開始都在做實驗,看哪些基于格的方案會被量子計算機打破,而哪些至少對于現(xiàn)在而言又是安全的。對于編寫密碼和破解密碼的專家而言,這就是一場貓鼠游戲。當(dāng)解碼員沉默的時候,編碼員為了效率會放松方案的安全性,有時候,其結(jié)果就是導(dǎo)致安全越過了那條紅線。
公開的秘密
在談?wù)撨@一話題前,我們需要先對現(xiàn)在的加密方式有一個了解。事實上,當(dāng)你每次訪問以“HTTPS”開頭的鏈接時,你都會發(fā)送和接收加密的信息,而這一安全的網(wǎng)絡(luò)交易方式使用了基于加密技術(shù)的公共密鑰。這一創(chuàng)造性的發(fā)明始于上個世紀(jì)70年代,而在此前,密碼技術(shù)基本就是政府和間諜之間的比賽。通常而言,參與信息傳遞的人,例如一個人和他的對接人之間如果想要偷偷交流的話,要事先約定一個暗號或者“鑰匙”。而公共密鑰的技術(shù)則可以讓任何人給其他人發(fā)送一組加密信息,不管是否有人在偷聽,只有指定的接受人可以解密,即使參與的人一開始并沒有串通好。
在公鑰加密技術(shù)中,人們通過一些數(shù)學(xué)技巧來保證數(shù)據(jù)的安全性,一些數(shù)學(xué)問題解答起來容易,但是要用逆向工程解碼則很難。例如,要計算機計算兩個質(zhì)數(shù)的乘積很容易,但是如果給計算機一個數(shù),要它解出組成這個數(shù)的質(zhì)因子,則可能要花費很多時間。在基于質(zhì)數(shù)分解的方案中,這個質(zhì)數(shù)就是某人并不與他人共享的“私鑰”。而質(zhì)數(shù)的乘積則是“公鑰”,公開分發(fā)。當(dāng)某人用公鑰來加密信息時,只有這個擁有私鑰的人才能夠解密信息。
有兩個公鑰加密方案自上世紀(jì)70年代以來廣為應(yīng)用:一個是基于質(zhì)因子的RSA方案,另一個是基于離散算法的Diffie-Hellman方案。雖然這兩種方案并不是說一定就無法破解,但是沒人能夠找到高效計算出結(jié)果的方法。如果要用計算機將特定長度的公鑰進行計算出來,可能要花費數(shù)年的時間。因此,這兩種方案成了保護互聯(lián)網(wǎng)信息的力盾。不過它們帶來的這份安全,似乎已快來到了終結(jié)之時。
Shor的算法
計算機難以短時計算出結(jié)果這一神話在1994年被打破,當(dāng)時AT&T的研究人員PeterShor提出了一種理論,他認為未來的量子計算機會具有破解算法的能力。
在普通計算機中,信息以比特的形式存儲。比特存在兩種狀態(tài)中的一種,即0或者1,而計算機的計算能力與比特數(shù)量相稱。但是在量子計算機中,數(shù)據(jù)是用量子位方式存儲的,數(shù)據(jù)存儲格式既可以是0也可以是1。由于大量的量子位,使得其中可以存在大量可能的組合形式和可能的個體狀態(tài)。因此隨著量子位數(shù)量的上升,量子計算機的計算能力會以指數(shù)級的方式增長。
基于此,量子計算機比普通計算機會具有更強的運算能力。然而要開發(fā)出其潛力,還必須同時找到一個合適的算法,能夠充分利用這種同時存在的狀態(tài),即得到正確的解答。80年代量子計算機被提出來以后,超過10多年間都沒有什么有用的算法出現(xiàn),這個領(lǐng)域似乎前途暗淡。
變化發(fā)生于1994年,Shor提出了一個量子計算機算法,能夠高效破解了質(zhì)因子和離散算法,也就是說打破了RSA加密方法和Diffie-Hellman密鑰交換理論。于是一瞬間,人們對量子計算機的興趣一下子燃燒了起來。隨著Shor的算法揭示出了量子計算機高級的運算能力后,世界范圍內(nèi)的研究人員爭相進行研究,試圖找出破譯的方式。而與之相對應(yīng)的是,密碼編譯專家們也在競相賽跑,提出量子計算機無法攻破的方案。最后他們發(fā)現(xiàn),格似乎是一個不錯的選擇。
迷失在格里
其實同RSA加密方案類似,理論上來說,計算質(zhì)數(shù)的乘積很容易,但是求解質(zhì)因子很難,基于格的安全加密方案也取決于,讓計算機迷失在一個500維的格中有多難。不同的是,在格方案中,私鑰與格點相關(guān),而公鑰則與空間中的特定位置有聯(lián)系。
除了一開始的驚艷,這種加密方案卻發(fā)展遲緩。80年代的時候,這種方案的公鑰都太長,交換數(shù)據(jù)需要海量的字節(jié)空間。為了提高效率,密碼學(xué)家不得不簡化潛在的格。在一個普通的格中,格點是由計算一組向量的線性組合得出。給這些向量分配一個模式,使得算出來的結(jié)果簡單化,則相關(guān)的密鑰也更短。但這帶來的問題是,簡化方案使得人們可以從公鑰中推論出私鑰,從而破壞這個方案。因而,格對于密碼學(xué)來說,又成了災(zāi)難的代名詞。
隨著時間的前進,一些密碼學(xué)專家仍然在不斷完善格。1995年的時候,一些專家提出了一種基于“環(huán)狀”的格,可以產(chǎn)生在任意方向旋轉(zhuǎn)的向量。這個名為NTRU的方案極其高效,甚至比老的RSA和Diffie-Hellman方案更高效。盡管沒有證據(jù)表明這種方案就是一定安全的,但20年過去了還沒有人能破解它,證明某種程度上還是具有安全性的。
格的前景自1997年以后變得明朗起來,IBM的研究人員提出第一種較好的加密方案,這種加密方案名為LearningWithErrors(LWE),意即伴隨誤差學(xué)習(xí),由于要找到最近的通用格要很長時間,因而可以抵抗來自量子計算機的攻擊?;诶硐敫裣?,他們開發(fā)出了一個更行之有效的方案。
什么是LWE方案
在2005年,OdedRegev基于LWE問題提出了一種加密方案,他證實這個方案解決起來很難,因而比較安全。這個方案的基本思路是這樣的:
首先選擇任何一個奇數(shù),并且不要告訴任何一個其他人,這就是你的私鑰。然后把它乘上任何一個數(shù),再加上一個小的偶數(shù)。重復(fù)多次,得到一系列的數(shù),這些數(shù)就是你的私鑰,然后再把它們告訴別人。
現(xiàn)在,如果有誰想給你發(fā)信息,如0或1,首先這個人隨機地在你的公鑰里選擇一半的數(shù),把它們加起來。然后如果要發(fā)送0,他們就把數(shù)據(jù)加起來然后發(fā)給你。如果要發(fā)送1的話,就把數(shù)據(jù)加1并發(fā)給你。之后你想要解碼這段數(shù)據(jù)的話,只要用你的私鑰求出這個和數(shù)的商。如果余數(shù)是偶數(shù)的話,這個信息就是0。如果是奇數(shù),則為1。
再一次,人們似乎又要在安全和效率間進行權(quán)衡。魚和熊掌不可兼得,LWE方案雖然更加通用并且安全性更高,但它的效率較低。研究人員在這個方向上,還在不斷探索,之后提出了一些其他方案。
貓鼠游戲
不僅科研人員在開發(fā)基于格的加密方案,GCHQ的人員也在做同樣的事。他們使用數(shù)論開發(fā)除了名為Soliloquy的方案,把公鑰的大小從一個包含大量數(shù)據(jù)的矩陣降為僅僅是一個質(zhì)數(shù)。把它量化到格里而言,則是產(chǎn)生一個非常短的矩陣。然而,這種方案的便利也正是其致命之處。
在他們發(fā)布的論文中可以看出,他們雖然發(fā)明出了這種方案,但是在2013年后又棄用了,原因是他們發(fā)現(xiàn)量子攻擊可以把這個加密方案攻破。雖然這篇論文只是對攻擊草草描繪了一下,但是給人們留下了無限的疑問:其他的格方案是不是也會受到影響?似乎在追求效率的同時,安全的紅線隨時也被越過。問題是,這條安全的警戒線到底該放在哪里?
GCHQ的團隊并沒有找出多少細節(jié),而僅僅是覺得有很強的證據(jù)證明,這種攻擊會被開發(fā)出來,因而就推論Soliloquy不適用于現(xiàn)實。于是密碼學(xué)家們花了差不多一年來了解Soliloquy攻擊的范圍,此后研究人員發(fā)現(xiàn),這種攻擊竟然只需要一臺普通的電腦就可以實現(xiàn)。
除了Soliloquy以外,他們的發(fā)現(xiàn)還表明,其他基于理想格的方案,構(gòu)造單獨短向量的方法也可以被攻破,而基于一般格的方案,如Ring-LWE和NTRU則不受影響。用研究人員的話來說,似乎想要把這些技術(shù)轉(zhuǎn)化成有效的方案還有一些技術(shù)上的難題,需要更深的研究。
就安全和效率的對稱性而言,密碼學(xué)家過于傾向效率這一邊。在他們給政府和銀行等機構(gòu)尋找最好的抵御量子攻擊的時候,Soliloquy這樣的攻擊迫使他們重新審視過去,回到那些可能沒有那么有效率,但是更加穩(wěn)固的方案。對于一個方案而言,在效率和安全性這兩條相反的道路上,還是需要研究人員仔細權(quán)衡。
相關(guān)閱讀:
安全性設(shè)計如何選擇可靠的隨機數(shù)加密方案?
詳細解析嵌入式加密工作原理
工業(yè)計算機的主板該如何選型?有哪些竅門?