今年8月的時候，美國國家安全局（NSA）在其網頁上更新了一段不起眼的內容，他們計劃對現在政府和軍方加密數據的方式更新
，以期能夠阻擋來自量子計算機的攻擊。NSA的(de)發(fa)言(yan)人(ren)表(biao)示(shi)，量(liang)子(zi)計(ji)算(suan)機(ji)能(neng)夠(gou)帶(dai)來(lai)更(geng)新(xin)更(geng)強(qiang)的(de)計(ji)算(suan)能(neng)力(li)，顯(xian)然(ran)現(xian)有(you)的(de)安(an)全(quan)措(cuo)施(shi)和(he)加(jia)密(mi)方(fang)式(shi)無(wu)法(fa)承(cheng)受(shou)來(lai)自(zi)這(zhe)種(zhong)設(she)備(bei)的(de)攻(gong)擊(ji)。如(ru)果(guo)要(yao)嚴(yan)密(mi)保(bao)護(hu)國(guo)家(jia)係(xi)統(tong)的(de)安(an)全(quan)的(de)話(hua)

，那(na)麼(me)他(ta)們(men)需(xu)要(yao)在(zai)這(zhe)一(yi)方(fang)向(xiang)取(qu)得(de)顯(xian)著(zhu)發(fa)展(zhan)。

量子計算機對於過去的人而言聽起來就像是遙遠的神話，但現在人們普遍認為在5到30年內它就將成為現實。通過不斷探索量子物理的法則

，不管是NSA的絕密檔案、銀行記錄還是郵箱密碼
，這種機器能夠解密現在世界上絕大多數“機密”的數據。在意識到這可能的威脅後，密碼學家們正在量子計算機大範圍使用以前，抓緊開發能夠防止量子破譯的方案。

現在看來，最可行的方案是基於格的數學方案（mathematicsoflattices）。這種方案有效性在於
，要在一個擁有幾百空間維度的格中找出隱藏的信息非常難
，除非你知道那條秘徑。

但是去年十月，英國政府通訊總部（GCHQ）的(de)密(mi)碼(ma)專(zhuan)家(jia)發(fa)表(biao)論(lun)文(wen)指(zhi)出(chu)，即(ji)便(bian)是(shi)最(zui)有(you)效(xiao)的(de)格(ge)方(fang)案(an)也(ye)麵(mian)臨(lin)著(zhe)安(an)全(quan)問(wen)題(ti)。這(zhe)些(xie)發(fa)現(xian)意(yi)味(wei)著(zhe)
，在(zai)以(yi)效(xiao)率(lv)為(wei)目(mu)標(biao)發(fa)展(zhan)了(le)幾(ji)十(shi)年(nian)後(hou)，這(zhe)種(zhong)高(gao)效(xiao)暴(bao)露(lu)出(chu)了(le)安(an)全(quan)風(feng)險(xian)。專(zhuan)家(jia)們(men)通(tong)過(guo)簡(jian)化(hua)他(ta)們(men)方(fang)案(an)中(zhong)的(de)格(ge)，導(dao)致(zhi)這(zhe)些(xie)方(fang)案(an)更(geng)容(rong)易(yi)受(shou)到(dao)攻(gong)擊(ji)。

基(ji)於(yu)上(shang)麵(mian)所(suo)述(shu)的(de)問(wen)題(ti)，一(yi)些(xie)密(mi)碼(ma)專(zhuan)家(jia)從(cong)去(qu)年(nian)開(kai)始(shi)都(dou)在(zai)做(zuo)實(shi)驗(yan)，看(kan)哪(na)些(xie)基(ji)於(yu)格(ge)的(de)方(fang)案(an)會(hui)被(bei)量(liang)子(zi)計(ji)算(suan)機(ji)打(da)破(po)，而(er)哪(na)些(xie)至(zhi)少(shao)對(dui)於(yu)現(xian)在(zai)而(er)言(yan)又(you)是(shi)安(an)全(quan)的(de)。對(dui)於(yu)編(bian)寫(xie)密(mi)碼(ma)和(he)破(po)解(jie)密(mi)碼(ma)的(de)專(zhuan)家(jia)而(er)言(yan)
，這(zhe)就(jiu)是(shi)一(yi)場(chang)貓(mao)鼠(shu)遊(you)戲(xi)。當(dang)解(jie)碼(ma)員(yuan)沉(chen)默(mo)的(de)時(shi)候(hou)
，編(bian)碼(ma)員(yuan)為(wei)了(le)效(xiao)率(lv)會(hui)放(fang)鬆(song)方(fang)案(an)的(de)安(an)全(quan)性(xing)，有(you)時(shi)候(hou)
，其(qi)結(jie)果(guo)就(jiu)是(shi)導(dao)致(zhi)安(an)全(quan)越(yue)過(guo)了(le)那(na)條(tiao)紅(hong)線(xian)。

公開的秘密

在談論這一話題前
，我們需要先對現在的加密方式有一個了解。事實上，當你每次訪問以“HTTPS”kaitoudelianjieshi

，nidouhuifasonghejieshoujiamidexinxi

，erzheyianquandewangluojiaoyifangshishiyonglejiyujiamijishudegonggongmiyao。zheyichuangzaoxingdefamingshiyushanggeshiji70年(nian)代(dai)
，而(er)在(zai)此(ci)前(qian)，密(mi)碼(ma)技(ji)術(shu)基(ji)本(ben)就(jiu)是(shi)政(zheng)府(fu)和(he)間(jian)諜(die)之(zhi)間(jian)的(de)比(bi)賽(sai)。通(tong)常(chang)而(er)言(yan)，參(can)與(yu)信(xin)息(xi)傳(chuan)遞(di)的(de)人(ren)，例(li)如(ru)一(yi)個(ge)人(ren)和(he)他(ta)的(de)對(dui)接(jie)人(ren)之(zhi)間(jian)如(ru)果(guo)想(xiang)要(yao)偷(tou)偷(tou)交(jiao)流(liu)的(de)話(hua)，要(yao)事(shi)先(xian)約(yue)定(ding)一(yi)個(ge)暗(an)號(hao)或(huo)者(zhe)“鑰匙”。而er公gong共gong密mi鑰yao的de技ji術shu則ze可ke以yi讓rang任ren何he人ren給gei其qi他ta人ren發fa送song一yi組zu加jia密mi信xin息xi，不bu管guan是shi否fou有you人ren在zai偷tou聽ting

，隻zhi有you指zhi定ding的de接jie受shou人ren可ke以yi解jie密mi，即ji使shi參can與yu的de人ren一yi開kai始shi並bing沒mei有you串chuan通tong好hao。

在zai公gong鑰yao加jia密mi技ji術shu中zhong，人ren們men通tong過guo一yi些xie數shu學xue技ji巧qiao來lai保bao證zheng數shu據ju的de安an全quan性xing，一yi些xie數shu學xue問wen題ti解jie答da起qi來lai容rong易yi，但dan是shi要yao用yong逆ni向xiang工gong程cheng解jie碼ma則ze很hen難nan。例li如ru

，要yao計ji算suan機ji計ji算suan兩liang個ge質zhi數shu的de乘cheng積ji很hen容rong易yi，但dan是shi如ru果guo給gei計ji算suan機ji一yi個ge數shu
，要yao它ta解jie出chu組zu成cheng這zhe個ge數shu的de質zhi因yin子zi
，則ze可ke能neng要yao花hua費fei很hen多duo時shi間jian。在zai基ji於yu質zhi數shu分fen解jie的de方fang案an中zhong，這zhe個ge質zhi數shu就jiu是shi某mou人ren並bing不bu與yu他ta人ren共gong享xiang的de“私鑰”。而質數的乘積則是“公鑰”，公開分發。當某人用公鑰來加密信息時，隻有這個擁有私鑰的人才能夠解密信息。

有兩個公鑰加密方案自上世紀70年代以來廣為應用：一個是基於質因子的RSA方案，另一個是基於離散算法的Diffie-Hellman方(fang)案(an)。雖(sui)然(ran)這(zhe)兩(liang)種(zhong)方(fang)案(an)並(bing)不(bu)是(shi)說(shuo)一(yi)定(ding)就(jiu)無(wu)法(fa)破(po)解(jie)，但(dan)是(shi)沒(mei)人(ren)能(neng)夠(gou)找(zhao)到(dao)高(gao)效(xiao)計(ji)算(suan)出(chu)結(jie)果(guo)的(de)方(fang)法(fa)。如(ru)果(guo)要(yao)用(yong)計(ji)算(suan)機(ji)將(jiang)特(te)定(ding)長(chang)度(du)的(de)公(gong)鑰(yao)進(jin)行(xing)計(ji)算(suan)出(chu)來(lai)，可(ke)能(neng)要(yao)花(hua)費(fei)數(shu)年(nian)的(de)時(shi)間(jian)。因(yin)此(ci)，這(zhe)兩(liang)種(zhong)方(fang)案(an)成(cheng)了(le)保(bao)護(hu)互(hu)聯(lian)網(wang)信(xin)息(xi)的(de)力(li)盾(dun)。不(bu)過(guo)它(ta)們(men)帶(dai)來(lai)的(de)這(zhe)份(fen)安(an)全(quan)，似(si)乎(hu)已(yi)快(kuai)來(lai)到(dao)了(le)終(zhong)結(jie)之(zhi)時(shi)。

Shor的算法

計算機難以短時計算出結果這一神話在1994年被打破，當時AT&T的研究人員PeterShor提出了一種理論
，他認為未來的量子計算機會具有破解算法的能力。

在普通計算機中，信息以比特的形式存儲。比特存在兩種狀態中的一種，即0或者1，而計算機的計算能力與比特數量相稱。但是在量子計算機中
，數據是用量子位方式存儲的，數據存儲格式既可以是0也可以是1。youyudaliangdeliangziwei，shideqizhongkeyicunzaidaliangkenengdezuhexingshihekenengdegetizhuangtai。yincisuizheliangziweishuliangdeshangsheng，liangzijisuanjidejisuannenglihuiyizhishujidefangshizengchang。

基(ji)於(yu)此(ci)，量(liang)子(zi)計(ji)算(suan)機(ji)比(bi)普(pu)通(tong)計(ji)算(suan)機(ji)會(hui)具(ju)有(you)更(geng)強(qiang)的(de)運(yun)算(suan)能(neng)力(li)。然(ran)而(er)要(yao)開(kai)發(fa)出(chu)其(qi)潛(qian)力(li)，還(hai)必(bi)須(xu)同(tong)時(shi)找(zhao)到(dao)一(yi)個(ge)合(he)適(shi)的(de)算(suan)法(fa)
，能(neng)夠(gou)充(chong)分(fen)利(li)用(yong)這(zhe)種(zhong)同(tong)時(shi)存(cun)在(zai)的(de)狀(zhuang)態(tai)，即(ji)得(de)到(dao)正(zheng)確(que)的(de)解(jie)答(da)。80年代量子計算機被提出來以後，超過10多年間都沒有什麼有用的算法出現，這個領域似乎前途暗淡。

變化發生於1994年
，Shor提出了一個量子計算機算法

，能夠高效破解了質因子和離散算法，也就是說打破了RSA加密方法和Diffie-Hellman密鑰交換理論。於是一瞬間
，人們對量子計算機的興趣一下子燃燒了起來。隨著Shor的de算suan法fa揭jie示shi出chu了le量liang子zi計ji算suan機ji高gao級ji的de運yun算suan能neng力li後hou，世shi界jie範fan圍wei內nei的de研yan究jiu人ren員yuan爭zheng相xiang進jin行xing研yan究jiu
，試shi圖tu找zhao出chu破po譯yi的de方fang式shi。而er與yu之zhi相xiang對dui應ying的de是shi，密mi碼ma編bian譯yi專zhuan家jia們men也ye在zai競jing相xiang賽sai跑pao，提ti出chu量liang子zi計ji算suan機ji無wu法fa攻gong破po的de方fang案an。最zui後hou他ta們men發fa現xian，格ge似si乎hu是shi一yi個ge不bu錯cuo的de選xuan擇ze。

迷失在格裏

其實同RSA加密方案類似
，理論上來說，計算質數的乘積很容易，但是求解質因子很難
，基於格的安全加密方案也取決於，讓計算機迷失在一個500維的格中有多難。不同的是，在格方案中，私鑰與格點相關，而公鑰則與空間中的特定位置有聯係。

除了一開始的驚豔，這種加密方案卻發展遲緩。80niandaideshihou，zhezhongfangandegongyaodoutaichang，jiaohuanshujuxuyaohailiangdezijiekongjian。weiletigaoxiaolv
，mimaxuejiabudebujianhuaqianzaidege。zaiyigeputongdegezhong，gedianshiyoujisuanyizuxiangliangdexianxingzuhedechu。geizhexiexiangliangfenpeiyigemoshi
，shidesuanchulaidejieguojiandanhua
，zexiangguandemiyaoyegengduan。danzhedailaidewentishi
，jianhuafanganshiderenmenkeyiconggongyaozhongtuilunchusiyao
，congerpohuaizhegefangan。yiner，geduiyumimaxuelaishuo
，youchenglezainandedaimingci。

隨著時間的前進，一些密碼學專家仍然在不斷完善格。1995年的時候

，一些專家提出了一種基於“環狀”的格，可以產生在任意方向旋轉的向量。這個名為NTRU的方案極其高效，甚至比老的RSA和Diffie-Hellman方案更高效。盡管沒有證據表明這種方案就是一定安全的
，但20年過去了還沒有人能破解它
，證明某種程度上還是具有安全性的。

格的前景自1997年以後變得明朗起來，IBM的研究人員提出第一種較好的加密方案
，這種加密方案名為LearningWithErrors（LWE），yijibansuiwuchaxuexi，youyuyaozhaodaozuijindetongyonggeyaohenchangshijian
，yinerkeyidikanglaiziliangzijisuanjidegongji。jiyulixianggexia

，tamenkaifachuleyigegengxingzhiyouxiaodefangan。

什麼是LWE方案

在2005年，OdedRegev基於LWE問題提出了一種加密方案，他證實這個方案解決起來很難
，因而比較安全。這個方案的基本思路是這樣的：

首(shou)先(xian)選(xuan)擇(ze)任(ren)何(he)一(yi)個(ge)奇(qi)數(shu)，並(bing)且(qie)不(bu)要(yao)告(gao)訴(su)任(ren)何(he)一(yi)個(ge)其(qi)他(ta)人(ren)，這(zhe)就(jiu)是(shi)你(ni)的(de)私(si)鑰(yao)。然(ran)後(hou)把(ba)它(ta)乘(cheng)上(shang)任(ren)何(he)一(yi)個(ge)數(shu)，再(zai)加(jia)上(shang)一(yi)個(ge)小(xiao)的(de)偶(ou)數(shu)。重(zhong)複(fu)多(duo)次(ci)
，得(de)到(dao)一(yi)係(xi)列(lie)的(de)數(shu)，這(zhe)些(xie)數(shu)就(jiu)是(shi)你(ni)的(de)私(si)鑰(yao)，然(ran)後(hou)再(zai)把(ba)它(ta)們(men)告(gao)訴(su)別(bie)人(ren)。

現在，如果有誰想給你發信息，如0或1
，首先這個人隨機地在你的公鑰裏選擇一半的數

，把它們加起來。然後如果要發送0，他們就把數據加起來然後發給你。如果要發送1的話
，就把數據加1並發給你。之後你想要解碼這段數據的話，隻要用你的私鑰求出這個和數的商。如果餘數是偶數的話，這個信息就是0。如果是奇數，則為1。

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

貓鼠遊戲

不僅科研人員在開發基於格的加密方案，GCHQ的人員也在做同樣的事。他們使用數論開發除了名為Soliloquy的de方fang案an

，把ba公gong鑰yao的de大da小xiao從cong一yi個ge包bao含han大da量liang數shu據ju的de矩ju陣zhen降jiang為wei僅jin僅jin是shi一yi個ge質zhi數shu。把ba它ta量liang化hua到dao格ge裏li而er言yan，則ze是shi產chan生sheng一yi個ge非fei常chang短duan的de矩ju陣zhen。然ran而er
，這zhe種zhong方fang案an的de便bian利li也ye正zheng是shi其qi致zhi命ming之zhi處chu。

在他們發布的論文中可以看出，他們雖然發明出了這種方案
，但是在2013年nian後hou又you棄qi用yong了le，原yuan因yin是shi他ta們men發fa現xian量liang子zi攻gong擊ji可ke以yi把ba這zhe個ge加jia密mi方fang案an攻gong破po。雖sui然ran這zhe篇pian論lun文wen隻zhi是shi對dui攻gong擊ji草cao草cao描miao繪hui了le一yi下xia，但dan是shi給gei人ren們men留liu下xia了le無wu限xian的de疑yi問wen：其他的格方案是不是也會受到影響？似乎在追求效率的同時，安全的紅線隨時也被越過。問題是，這條安全的警戒線到底該放在哪裏？

GCHQ的團隊並沒有找出多少細節
，而僅僅是覺得有很強的證據證明，這種攻擊會被開發出來，因而就推論Soliloquy不適用於現實。於是密碼學家們花了差不多一年來了解Soliloquy攻擊的範圍，此後研究人員發現，這種攻擊竟然隻需要一台普通的電腦就可以實現。

除了Soliloquy以外，他們的發現還表明，其他基於理想格的方案，構造單獨短向量的方法也可以被攻破
，而基於一般格的方案，如Ring-LWE和NTRU則不受影響。用研究人員的話來說

，似乎想要把這些技術轉化成有效的方案還有一些技術上的難題，需要更深的研究。

就安全和效率的對稱性而言，密碼學家過於傾向效率這一邊。在他們給政府和銀行等機構尋找最好的抵禦量子攻擊的時候，Soliloquy這(zhe)樣(yang)的(de)攻(gong)擊(ji)迫(po)使(shi)他(ta)們(men)重(zhong)新(xin)審(shen)視(shi)過(guo)去(qu)
，回(hui)到(dao)那(na)些(xie)可(ke)能(neng)沒(mei)有(you)那(na)麼(me)有(you)效(xiao)率(lv)，但(dan)是(shi)更(geng)加(jia)穩(wen)固(gu)的(de)方(fang)案(an)。對(dui)於(yu)一(yi)個(ge)方(fang)案(an)而(er)言(yan)，在(zai)效(xiao)率(lv)和(he)安(an)全(quan)性(xing)這(zhe)兩(liang)條(tiao)相(xiang)反(fan)的(de)道(dao)路(lu)上(shang)，還(hai)是(shi)需(xu)要(yao)研(yan)究(jiu)人(ren)員(yuan)仔(zai)細(xi)權(quan)衡(heng)。

相關閱讀：

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