導讀：你可能認為量子計算機還屬于科幻範疇，但近幾十年它就有可能變成現實，而其超強的計算機能力也會對現有的加密技術構成威脅。那有沒有加密方法能抵禦量子計算機攻擊呢？連線的這篇文章就對此做了科普，并指出這不僅是技術問題，更需要安全與效率的平衡。
今年8月的時候，美國國家安全局（nsa）在其網頁上更新了一段不起眼的内容，他們計劃對現在政府和軍方加密資料的方式更新，以期能夠阻擋來自量子計算機的攻擊。nsa的發言人表示，量子計算機能夠帶來更新更強的計算能力，顯然現有的安全措施和加密方式無法承受來自這種裝置的攻擊。如果要嚴密保護國家系統的安全的話，那麼他們需要在這一方向取得顯著發展。
量子計算機對于過去的人而言聽起來就像是遙遠的神話，但現在人們普遍認為在5到30年内它就将成為現實。通過不斷探索量子實體的法則，不管是nsa的絕密檔案、銀行記錄還是郵箱密碼，這種機器能夠解密現在世界上絕大多數“機密”的資料。在意識到這可能的威脅後，密碼學家們正在量子計算機大範圍使用以前，抓緊開發能夠防止量子破譯的方案。
現在看來，最可行的方案是基于格的數學方案（mathematics of lattices）。這種方案有效性在于，要在一個擁有幾百空間次元的格中找出隐藏的資訊非常難，除非你知道那條秘徑。但是去年十月，英國政府通訊總部（gchq）的密碼專家發表論文指出，即便是最有效的格方案也面臨着安全問題。這些發現意味着，在以效率為目标發展了幾十年後，這種高效暴露出了安全風險。專家們通過簡化他們方案中的格，導緻這些方案更容易受到攻擊。
基于上面所述的問題，一些密碼專家從去年開始都在做實驗，看哪些基于格的方案會被量子計算機打破，而哪些至少對于現在而言又是安全的。對于編寫密碼和破解密碼的專家而言，這就是一場貓鼠遊戲。當解碼員沉默的時候，編碼員為了效率會放松方案的安全性，有時候，其結果就是導緻安全越過了那條紅線。
公開的秘密
在談論這一話題前，我們需要先對現在的加密方式有一個了解。事實上，當你每次通路以“https”開頭的連結時，你都會發送和接收加密的資訊，而這一安全的網絡交易方式使用了基于加密技術的公共密鑰。這一創造性的發明始于上個世紀70年代，而在此前，密碼技術基本就是政府和間諜之間的比賽。通常而言，參與資訊傳遞的人，例如一個人和他的對接人之間如果想要偷偷交流的話，要事先約定一個暗号或者“鑰匙”。而公共密鑰的技術則可以讓任何人給其他人發送一組加密資訊，不管是否有人在偷聽，隻有指定的接受人可以解密，即使參與的人一開始并沒有串通好。
在公鑰加密技術中，人們通過一些數學技巧來保證資料的安全性，一些數學問題解答起來容易，但是要用逆向工程解碼則很難。例如，要計算機計算兩個質數的乘積很容易，但是如果給計算機一個數，要它解出組成這個數的質因子，則可能要花費很多時間。在基于質數分解的方案中，這個質數就是某人并不與他人共享的“私鑰”。而質數的乘積則是“公鑰”，公開分發。當某人用公鑰來加密資訊時，隻有這個擁有私鑰的人才能夠解密資訊。
有兩個公鑰加密方案自上世紀70年代以來廣為應用：一個是基于質因子的rsa方案，另一個是基于離散算法的diffie-hellman方案。雖然這兩種方案并不是說一定就無法破解，但是沒人能夠找到高效計算出結果的方法。如果要用計算機将特定長度的公鑰進行計算出來，可能要花費數年的時間。是以，這兩種方案成了保護網際網路資訊的力盾。不過它們帶來的這份安全，似乎已快來到了終結之時。
shor的算法
計算機難以短時計算出結果這一神話在1994年被打破，當時at&t;的研究人員peter shor提出了一種理論，他認為未來的量子計算機會具有破解算法的能力。
在普通計算機中，資訊以比特的形式存儲。比特存在兩種狀态中的一種，即0或者1，而計算機的計算能力與比特數量相稱。但是在量子計算機中，資料是用量子位方式存儲的，資料存儲格式既可以是0也可以是1。由于大量的量子位，使得其中可以存在大量可能的組合形式和可能的個體狀态。是以随着量子位數量的上升，量子計算機的計算能力會以指數級的方式增長。
基于此，量子計算機比普通計算機會具有更強的運算能力。然而要開發出其潛力，還必須同時找到一個合适的算法，能夠充分利用這種同時存在的狀态，即得到正确的解答。80年代量子計算機被提出來以後，超過10多年間都沒有什麼有用的算法出現，這個領域似乎前途暗淡。
變化發生于1994年，shor提出了一個量子計算機算法，能夠高效破解了質因子和離散算法，也就是說打破了rsa加密方法和diffie-hellman密鑰交換理論。于是一瞬間，人們對量子計算機的興趣一下子燃燒了起來。随着shor的算法揭示出了量子計算機進階的運算能力後，世界範圍内的研究人員争相進行研究，試圖找出破譯的方式。而與之相對應的是，密碼編譯專家們也在競相賽跑，提出量子計算機無法攻破的方案。最後他們發現，格似乎是一個不錯的選擇。
迷失在格裡
其實同rsa加密方案類似，理論上來說，計算質數的乘積很容易，但是求解質因子很難，基于格的安全加密方案也取決于，讓計算機迷失在一個500維的格中有多難。不同的是，在格方案中，私鑰與格點相關，而公鑰則與空間中的特定位置有聯系。
除了一開始的驚豔，這種加密方案卻發展遲緩。80年代的時候，這種方案的公鑰都太長，交換資料需要海量的位元組空間。為了提高效率，密碼學家不得不簡化潛在的格。在一個普通的格中，格點是由計算一組向量的線性組合得出。給這些向量配置設定一個模式，使得算出來的結果簡單化，則相關的密鑰也更短。但這帶來的問題是，簡化方案使得人們可以從公鑰中推論出私鑰，進而破壞這個方案。因而，格對于密碼學來說，又成了災難的代名詞。
随着時間的前進，一些密碼學專家仍然在不斷完善格。1995年的時候，一些專家提出了一種基于“環狀”的格，可以産生在任意方向旋轉的向量。這個名為ntru的方案極其高效，甚至比老的rsa和diffie-hellman方案更高效。盡管沒有證據表明這種方案就是一定安全的，但20年過去了還沒有人能破解它，證明某種程度上還是具有安全性的。
格的前景自1997年以後變得明朗起來，ibm的研究人員提出第一種較好的加密方案，這種加密方案名為learning with errors（lwe），意即伴随誤差學習，由于要找到最近的通用格要很長時間，因而可以抵抗來自量子計算機的攻擊。基于理想格下，他們開發出了一個更行之有效的方案。
什麼是lwe方案
在2005年，oded regev基于lwe問題提出了一種加密方案，他證明這個方案解決起來很難，因而比較安全。這個方案的基本思路是這樣的：
首先選擇任何一個奇數，并且不要告訴任何一個其他人，這就是你的私鑰。然後把它乘上任何一個數，再加上一個小的偶數。重複多次，得到一系列的數，這些數就是你的私鑰，然後再把它們告訴别人。 現在，如果有誰想給你發資訊，如0或1，首先這個人随機地在你的公鑰裡選擇一半的數，把它們加起來。然後如果要發送0，他們就把資料加起來然後發給你。如果要發送1的話，就把資料加1并發給你。之後你想要解碼這段資料的話，隻要用你的私鑰求出這個和數的商。如果餘數是偶數的話，這個資訊就是0。如果是奇數，則為1。
再一次，人們似乎又要在安全和效率間進行權衡。魚和熊掌不可兼得，lwe方案雖然更加通用并且安全性更高，但它的效率較低。研究人員在這個方向上，還在不斷探索，之後提出了一些其他方案。
貓鼠遊戲
不僅科研人員在開發基于格的加密方案，gchq的人員也在做同樣的事。他們使用數論開發除了名為soliloquy的方案，把公鑰的大小從一個包含大量資料的矩陣降為僅僅是一個質數。把它量化到格裡而言，則是産生一個非常短的矩陣。然而，這種方案的便利也正是其緻命之處。
在他們釋出的論文中可以看出，他們雖然發明出了這種方案，但是在2013年後又棄用了，原因是他們發現量子攻擊可以把這個加密方案攻破。雖然這篇論文隻是對攻擊草草描繪了一下，但是給人們留下了無限的疑問：其他的格方案是不是也會受到影響？似乎在追求效率的同時，安全的紅線随時也被越過。問題是，這條安全的警戒線到底該放在哪裡？
gchq的團隊并沒有找出多少細節，而僅僅是覺得有很強的證據證明，這種攻擊會被開發出來，因而就推論soliloquy不适用于現實。于是密碼學家們花了差不多一年來了解soliloquy攻擊的範圍，此後研究人員發現，這種攻擊竟然隻需要一台普通的電腦就可以實作。
除了soliloquy以外，他們的發現還表明，其他基于理想格的方案，構造單獨短向量的方法也可以被攻破，而基于一般格的方案，如ring-lwe和ntru則不受影響。用研究人員的話來說，似乎想要把這些技術轉化成有效的方案還有一些技術上的難題，需要更深的研究。
就安全和效率的對稱性而言，密碼學家過于傾向效率這一邊。在他們給政府和銀行等機構尋找最好的抵禦量子攻擊的時候，soliloquy這樣的攻擊迫使他們重新審視過去，回到那些可能沒有那麼有效率，但是更加穩固的方案。對于一個方案而言，在效率和安全性這兩條相反的道路上，還是需要研究人員仔細權衡。
原文釋出時間為：2015-09-26
本文來自雲栖社群合作夥伴“大資料文摘”，了解相關資訊可以關注“bigdatadigest”微信公衆号