[科普中國(guó)]-量子保密通信：認(rèn)清李鬼與李逵

導(dǎo)讀：后量子密碼術(shù)是個(gè)活躍的研究領(lǐng)域，但沒(méi)有在原理層面證明任何一個(gè)公鑰密碼體制可以抵抗量子計(jì)算機(jī)甚至經(jīng)典計(jì)算機(jī)。量子密碼術(shù)是目前唯一能從原理上證明安全性的密碼體制。京滬干線(xiàn)建設(shè)的初衷來(lái)自金融部門(mén)對(duì)現(xiàn)有安全體系的不滿(mǎn)，未來(lái)的建設(shè)也將在國(guó)家戰(zhàn)略的指引下，堅(jiān)持用戶(hù)至上和穩(wěn)步推進(jìn)的原則。公眾對(duì)量子通信應(yīng)該有正確的概念，分清李逵和李鬼，杜絕資本和輿論炒作，才有利于這個(gè)行業(yè)健康發(fā)展。

2017年9月29日，世界首條量子保密通信干線(xiàn)“京滬干線(xiàn)”正式開(kāi)通。這是中國(guó)繼2016年8月16日發(fā)射世界第一顆量子科學(xué)實(shí)驗(yàn)衛(wèi)星“墨子號(hào)”后，在量子保密通信領(lǐng)域的又一項(xiàng)重大進(jìn)展。對(duì)于京滬干線(xiàn)的介紹，可以參見(jiàn)我的文章《解讀量子通信京滬干線(xiàn)，包你懂》（https://mp.weixin.qq.com/s/30ucPReX9Z7gI1SmIcINog）。

我的前輩朋友、加州大學(xué)洛杉磯分校（UCLA）物理系研究員徐令予，在退休后很關(guān)心中國(guó)科技各個(gè)領(lǐng)域的發(fā)展，近年來(lái)在觀(guān)察者網(wǎng)和科學(xué)網(wǎng)等媒體寫(xiě)了許多文章，介紹和評(píng)論的領(lǐng)域十分廣泛，遍及量子信息、航天、天文望遠(yuǎn)鏡、人工光合作用、太陽(yáng)能發(fā)電、無(wú)人駕駛等等（http://www.guancha.cn/XuLingyu）。包括我在內(nèi)的讀者們從中學(xué)到了很多東西，也對(duì)美國(guó)的社會(huì)動(dòng)態(tài)增加了很多了解。對(duì)于各個(gè)具體科學(xué)問(wèn)題，即使意見(jiàn)不是完全一致（例如對(duì)于500米口徑射電望遠(yuǎn)鏡FAST），我們也可以看出徐老師對(duì)故鄉(xiāng)和同胞的眷戀，對(duì)此都抱有深深的敬意。雖然我和徐老師尚未謀面，不過(guò)在網(wǎng)絡(luò)上已經(jīng)做過(guò)不少交流，可以稱(chēng)為忘年交了，對(duì)此我深感榮幸。

因此，當(dāng)我看到徐老師2017年10月31日發(fā)表在觀(guān)察者網(wǎng)的文章《炒作量子通信工程，連潘建偉都擔(dān)心》（http://www.guancha.cn/XuLingyu/2017_10_31_432886_s.shtml）時(shí)，認(rèn)為這是一篇值得仔細(xì)研究的文章。此文在開(kāi)頭祝賀了京滬干線(xiàn)開(kāi)通后，側(cè)重點(diǎn)就急轉(zhuǎn)直下，主要篇幅放在給量子保密通信潑冷水降溫上。

為什么說(shuō)這是急轉(zhuǎn)直下呢？因?yàn)樾炖蠋熞郧暗脑S多文章，是對(duì)量子保密通信的科普和支持，例如《為什么發(fā)展量子密鑰技術(shù)已刻不容緩》（http://www.guancha.cn/XuLingyu/2016_08_19_371818.shtml）、《為什么說(shuō)外國(guó)無(wú)法破解中國(guó)量子密鑰技術(shù)》（http://www.guancha.cn/Science/2016_08_16_371382.shtml）、《反對(duì)高鐵的邏輯，要用到量子通信上了？》（http://www.guancha.cn/XuLingyu/2016_08_26_372499.shtml）。從這些文章中摘幾段：

“量子計(jì)算機(jī)的研發(fā)進(jìn)展是各強(qiáng)國(guó)的最高機(jī)密，媒體上的報(bào)道真真假假千萬(wàn)信不得，很有可能用以破譯的專(zhuān)用量子計(jì)算機(jī)已經(jīng)接近完工，這決不是危言聳聽(tīng)，密碼世界從來(lái)是波詭云譎、莫測(cè)高深。即使按專(zhuān)家們保守的預(yù)測(cè)，量子計(jì)算機(jī)的實(shí)際應(yīng)用也許還要等十到十五年，但尋找新的密碼系統(tǒng)，特別是開(kāi)發(fā)密鑰分配的新技術(shù)已經(jīng)刻不容緩，因?yàn)樾录夹g(shù)從開(kāi)發(fā)到系統(tǒng)的建立和實(shí)用也需要時(shí)日，所以我們已經(jīng)到了最危險(xiǎn)的時(shí)刻！”（《為什么發(fā)展量子密鑰技術(shù)已刻不容緩》）

“有必要再次強(qiáng)調(diào)：與其它密碼技術(shù)不同，量子密鑰分配技術(shù)從原理上保證密鑰配送是絕對(duì)安全的，量子通信是穩(wěn)定可靠的，加速發(fā)展量子通信是十分必要的，因?yàn)楝F(xiàn)有密碼系統(tǒng)已經(jīng)到了最危險(xiǎn)的時(shí)刻。工程實(shí)施中一定會(huì)有許多的問(wèn)題，但原理與實(shí)施是完全不同的兩個(gè)概念，畢竟實(shí)施中的技術(shù)問(wèn)題可以逐步解決，不可破譯的原理才是該項(xiàng)技術(shù)具有發(fā)展前途的根本保證，它使我們對(duì)量子密鑰分配技術(shù)的將來(lái)充滿(mǎn)了信心?！保ā斗磳?duì)高鐵的邏輯，要用到量子通信上了？》）

以上這些說(shuō)法，我都十分贊同。而在《炒作量子通信工程，連潘建偉都擔(dān)心》一文中，徐老師的結(jié)論卻似乎翻了個(gè)個(gè)：

“開(kāi)發(fā)量子保密技術(shù)為的是應(yīng)對(duì)未來(lái)可能發(fā)生的危機(jī)，但這種危機(jī)離我們?nèi)允值剡b遠(yuǎn)，即使危機(jī)真的降臨，改進(jìn)升級(jí)后的經(jīng)典密碼系統(tǒng)應(yīng)該足以應(yīng)付危局。量子密碼技術(shù)并非是對(duì)抗危機(jī)的唯一選擇，它很有可能僅是一枚永遠(yuǎn)也使用不上的備胎?！?/p>

有意思，大反轉(zhuǎn)啊！當(dāng)然，徐老師在此文中一再聲明：“對(duì)量子保密通信技術(shù)作前瞻性科學(xué)研究應(yīng)該大力支持，我的這個(gè)態(tài)度始終也不會(huì)改變?！辈贿^(guò)對(duì)工程的態(tài)度，看起來(lái)徐老師是反轉(zhuǎn)了。

類(lèi)似的觀(guān)點(diǎn)我早就看到過(guò)，但那些并不值得認(rèn)真對(duì)待，因?yàn)橹挥袀€(gè)結(jié)論，沒(méi)有論證過(guò)程。而徐老師就不一樣了，無(wú)論他寫(xiě)什么話(huà)題，持什么觀(guān)點(diǎn)，總是會(huì)舉出不少“干貨”，無(wú)論正方反方都可以從中得到新的信息。在這篇文章中，最大的干貨是一篇標(biāo)題為《后量子RSA》（“post-quantum RSA”）的論文（https://eprint.iacr.org/2017/351.pdf），徐老師向大家介紹了這篇論文，把它作為經(jīng)典密碼術(shù)已經(jīng)夠用的重要證據(jù)。

徐老師把這篇20頁(yè)的論文發(fā)給了我，最近我仔細(xì)研讀了一番。我的專(zhuān)業(yè)是理論與計(jì)算化學(xué)，量子力學(xué)是這門(mén)學(xué)科的基礎(chǔ)之一，所以我對(duì)量子力學(xué)還算是比較熟悉，但是對(duì)信息科學(xué)的了解就很有限了。至于密碼學(xué)這門(mén)需要大量數(shù)學(xué)技巧的學(xué)科，我更是門(mén)外漢。不過(guò)，經(jīng)過(guò)研讀，加上一些專(zhuān)家朋友的幫助，我想我還是理解了《后量子RSA》的基本框架。

這篇文章確實(shí)很有趣，提出了一種比現(xiàn)在通行的RSA密碼體系更加能夠抵抗量子計(jì)算機(jī)的改進(jìn)版RSA。但在理論層面，這個(gè)進(jìn)步只是把“完全不安全”（敵方破解幾乎跟合法用戶(hù)解密一樣快）提升到了“稍微有點(diǎn)安全可言”（破解的速度低于加密解密的速度），遠(yuǎn)遠(yuǎn)沒(méi)有達(dá)到正統(tǒng)的安全標(biāo)準(zhǔn)（破解的計(jì)算量指數(shù)增長(zhǎng)）。更重要的是，這個(gè)進(jìn)步跟“量子密碼術(shù)為什么有價(jià)值”的大圖景完全無(wú)關(guān)。這樣的進(jìn)步再來(lái)一萬(wàn)個(gè)，也不會(huì)使經(jīng)典密碼術(shù)變得無(wú)懈可擊，不會(huì)使量子密碼術(shù)變成多此一舉。其實(shí)作者們也完全沒(méi)有這個(gè)意思，原文對(duì)這個(gè)成果的自我評(píng)估是很準(zhǔn)確的，徐老師似乎對(duì)這篇論文有些誤讀。其中一個(gè)誤讀是，把“2的100次方的量子比特操作”看成了“2的100次方的量子比特”，由此引申出來(lái)的評(píng)論自然也都失準(zhǔn)了。

徐老師文章中的論據(jù)，除了《后量子RSA》之外，還有其他的。不過(guò)在我看來(lái)，有一些比較明確的錯(cuò)誤（“硬傷”），還有一些比較“軟”的可商榷之處。其中最硬的錯(cuò)誤，是認(rèn)為有些公鑰密碼體系已經(jīng)在原理上被證明不可能被量子計(jì)算機(jī)破解了。實(shí)際上，人們還沒(méi)有證明任何一個(gè)公鑰密碼體系不可能被經(jīng)典計(jì)算機(jī)破解，又怎么可能得到更強(qiáng)的結(jié)果，證明它不可能被量子計(jì)算機(jī)破解呢？

一個(gè)公鑰密碼體制可以抵抗某種算法的攻擊（包括量子算法），不等于能從原理上證明其安全性，因?yàn)楹笳呤且C明它可以抵抗任何已知和未知算法的攻擊。而至今唯一能從原理上嚴(yán)格證明安全性的密碼體制，就是量子密碼術(shù)。這是量子密碼術(shù)與所有的公鑰密碼體制之間的根本差別。

在一篇文章里見(jiàn)到這么多可商榷之處，對(duì)于低水平的作者來(lái)說(shuō)很常見(jiàn)，對(duì)于徐老師來(lái)說(shuō)很罕見(jiàn)。我感覺(jué)這篇文章徐老師寫(xiě)得比較急促，大概是心里對(duì)另外一些事感到焦慮，一些科學(xué)之外的事。我跟徐老師溝通，徐老師告訴我，被最近某公司人身威脅科學(xué)家的事件刺痛了，最擔(dān)憂(yōu)的是騙子傷了眾人的心，最后政府光火把臟水連同孩子一起潑出去，所以希望理性降溫。這就可以理解了。對(duì)于如何保持量子通信領(lǐng)域的健康發(fā)展，我也將在本文中談?wù)勎业挠^(guān)點(diǎn)，以及我了解的一線(xiàn)工作者的看法。公眾、投資者和潛在的用戶(hù)明白了這些基本圖景，也將有利于抵制資本與媒體的炒作，促進(jìn)量子通信行業(yè)健康發(fā)展。

以上是一個(gè)總體的介紹。下面我來(lái)具體說(shuō)明各個(gè)要點(diǎn)，以及借這個(gè)機(jī)會(huì)，解釋一個(gè)基本問(wèn)題：量子密碼術(shù)的價(jià)值究竟在哪里？

一，什么是量子密碼術(shù)？

描述微觀(guān)世界基本物理規(guī)律的理論，叫做量子力學(xué)，它跟相對(duì)論是目前已知的兩大基礎(chǔ)物理理論。量子力學(xué)出現(xiàn)后，我們就把描述宏觀(guān)世界的牛頓力學(xué)稱(chēng)為經(jīng)典力學(xué)，它可以理解為量子力學(xué)在宏觀(guān)情況下的近似。

1980年代以來(lái)，量子力學(xué)跟信息科學(xué)交叉，產(chǎn)生了一門(mén)新的學(xué)科“量子信息”。這門(mén)學(xué)科的目的，就是利用量子力學(xué)的特性，實(shí)現(xiàn)傳統(tǒng)信息科學(xué)中實(shí)現(xiàn)不了的功能，例如永遠(yuǎn)不會(huì)被破解的保密方法（就是后面要解釋的量子密碼術(shù)）、科幻電影中的“傳送術(shù)”（它的專(zhuān)業(yè)名稱(chēng)叫做“量子隱形傳態(tài)”）。

《星際迷航》中的傳送術(shù)

**經(jīng)典的信息科學(xué)包括通信和計(jì)算兩大主題，量子信息的研究?jī)?nèi)容同樣也可以分成兩大塊：量子通信和量子計(jì)算。**這兩大子領(lǐng)域里又各自有若干具體應(yīng)用，剛才說(shuō)的量子密碼術(shù)和量子隱形傳態(tài)都屬于量子通信，而量子計(jì)算中的重要應(yīng)用包括量子因數(shù)分解和量子搜索等等。下面這個(gè)圖，可以表示量子信息這門(mén)學(xué)科的脈絡(luò)。

量子信息學(xué)科內(nèi)容

我寫(xiě)過(guò)不少量子信息的科普文章，目前最全面的一篇是應(yīng)新浪科技之邀寫(xiě)的《你完全可以理解量子信息》（http://tech.sina.com.cn/d/2017-08-31/doc-ifykpysa2199081.shtml）。讀者如果想知道量子力學(xué)有哪些可以用于信息科學(xué)的特點(diǎn)，量子信息的這些應(yīng)用做的是什么事，以及為什么能做到，請(qǐng)去參閱這篇長(zhǎng)文。

許多媒體在報(bào)道“量子通信”如何如何的時(shí)候，指的實(shí)際是量子密碼術(shù)，即量子通信的一部分而非全部。量子密碼術(shù)又被稱(chēng)為“量子保密通信”或者“量子密鑰分發(fā)”，無(wú)論從哪個(gè)名字，你都可以一眼看出，它是一種保密的方法，不是有些媒體胡思亂想的超時(shí)空傳輸之類(lèi)。

**量子密碼術(shù)實(shí)際做的是什么事情呢？簡(jiǎn)短的回答是：不通過(guò)信使，讓通信雙方直接分享密鑰。**打個(gè)比方，就是《紅燈記》中的李玉和下崗了，地下黨和游擊隊(duì)不通過(guò)他就直接獲得了同一套密電碼。

《紅燈記》

怎么做到的？有若干種技術(shù)方案，都稱(chēng)為某某協(xié)議，包括BB84協(xié)議、E91協(xié)議、B92協(xié)議、誘騙態(tài)協(xié)議等等。由于篇幅所限，本文對(duì)這些方案不能詳細(xì)解釋。有興趣的讀者，請(qǐng)參閱《你完全可以理解量子信息》中的相關(guān)內(nèi)容（http://mp.weixin.qq.com/s/kKLd5_YbjI765qBvuSFB4A）。

這里有一點(diǎn)值得強(qiáng)調(diào)。**許多科普作品說(shuō)量子密碼術(shù)離不開(kāi)“量子糾纏”（你八成聽(tīng)說(shuō)過(guò)這個(gè)詞），但這個(gè)說(shuō)法是錯(cuò)誤的！**一線(xiàn)工作者都知道它錯(cuò)，而媒體仍然整天這么說(shuō)，——可能他們覺(jué)得量子糾纏這個(gè)詞比較高大上，讀者聽(tīng)了以后暈頭的程度直接上升三級(jí)。實(shí)際情況是，量子密碼術(shù)有若干種實(shí)現(xiàn)方案，有些用到量子糾纏，有些不用量子糾纏。量子糾纏是個(gè)可選項(xiàng)，而不是必要條件。

不僅如此，量子糾纏其實(shí)還是個(gè)很少被選中的可選項(xiàng)。量子糾纏是一種多粒子體系的現(xiàn)象，而對(duì)于實(shí)驗(yàn)來(lái)說(shuō)，操縱一個(gè)粒子肯定比操縱多個(gè)粒子容易。量子密碼術(shù)可以通過(guò)發(fā)射和接收單個(gè)光子實(shí)現(xiàn)，所以，絕大多數(shù)量子密碼術(shù)的實(shí)驗(yàn)都是用單光子方案做的，這樣達(dá)到的效果更好。有些文章通過(guò)批評(píng)量子糾纏來(lái)批評(píng)量子密碼術(shù)，這其實(shí)就是被那些說(shuō)量子密碼術(shù)必須用到量子糾纏的媒體給忽悠了，屬于無(wú)的放矢。

二，量子密碼術(shù)為什么有價(jià)值？

不通過(guò)信使，讓通信雙方直接分享密鑰，這顯然是個(gè)非常奇妙的能力，是以前想象不到的。不過(guò)，這個(gè)能力有什么樣的意義？這就需要從密碼學(xué)的基本框架講起了。

**把明文變換成密文，需要兩個(gè)元素：變換的規(guī)則和變換的參數(shù)。前者是編碼的算法，后者是密鑰。**密碼學(xué)的一個(gè)基本原則是，在設(shè)計(jì)算法時(shí)，你必須假設(shè)敵人已經(jīng)知道了算法和密文，唯一不知道的就是密鑰。

用一個(gè)比喻來(lái)說(shuō)，密碼學(xué)的攻防就好比魔王追公主（魔王：“你喊吧，喊破喉嚨也不會(huì)有人來(lái)救你的！”破喉嚨：“公主，我來(lái)救你！”）。魔王知道公主運(yùn)動(dòng)的規(guī)則，但不知道公主運(yùn)動(dòng)的參數(shù)。魔王的目標(biāo)是在這種前提下追上公主，公主的目標(biāo)是在這種前提下擺脫魔王。

我們經(jīng)常說(shuō)，沒(méi)有完美的東西。但在理論的層面上，這話(huà)其實(shí)不對(duì)。**有一種很簡(jiǎn)單的密碼體系，就具有“完美的安全性”（perfect security）。**這里的“完美安全”是個(gè)信息論的術(shù)語(yǔ)，意思是攻擊方無(wú)論有多強(qiáng)的計(jì)算能力，都不可能從密文中得出任何信息。

這話(huà)聽(tīng)著似乎很玄，實(shí)際的意思卻很簡(jiǎn)單。假如你要傳一比特的信息（即0和1這兩個(gè)數(shù)中的一個(gè)），密鑰也有兩個(gè)選擇：0和1。算法非常簡(jiǎn)單：如果密鑰為0，那么密文就等于明文，即把0變成0，把1變成1；如果密鑰為1，那么密文就是0和1中不同于明文的那個(gè)數(shù)，即把0變成1，把1變成0。學(xué)過(guò)二進(jìn)制的同學(xué)們知道，這個(gè)算法就是“模為2的加法”?，F(xiàn)在如果你告訴敵人密文是0，那么他能得到什么呢？什么都得不到！他唯一可說(shuō)的，是明文有一半的可能是0，一半的可能是1。但這是句廢話(huà)，因?yàn)槿绻芪氖?，這句話(huà)同樣也成立。他不看密文就知道這一點(diǎn)，看了以后也不能增加任何新知識(shí)，所以這個(gè)密碼體系就是不可破譯的，具有完美的安全性。

當(dāng)然，這是個(gè)最簡(jiǎn)單的例子，只適用于明文長(zhǎng)度為1比特、只傳輸一次的情況。把這個(gè)辦法推廣到更長(zhǎng)的明文長(zhǎng)度、更多次的傳輸，需要滿(mǎn)足三個(gè)條件。哪三個(gè)條件呢？**一，密鑰的長(zhǎng)度跟明文一樣；二，密鑰是一串隨機(jī)的字符串；三，每傳送一次密文后都更換密鑰，即“一次一密”。滿(mǎn)足這三個(gè)條件的密鑰叫做“一次性便箋”（one-time pad）。**信息論的創(chuàng)始人香農(nóng)（Claude E. Shannon）從數(shù)學(xué)上證明了：密鑰如果滿(mǎn)足這三個(gè)條件，通信就是完美安全的。這個(gè)定理可以稱(chēng)為“系統(tǒng)的安全保密性定理”。

香農(nóng)

一次性便箋保密的實(shí)質(zhì)，是讓密文跟明文完全沒(méi)有關(guān)聯(lián)，任何的密文都以相等的概率對(duì)應(yīng)相同長(zhǎng)度的任何的明文。好比你問(wèn)一群村民：“李向陽(yáng)在哪里？”所有人都回答：“我就是李向陽(yáng)！”在魔王追公主的故事中，就好比公主下一步可以跳到任何地方，“瞻之在前，忽焉在后”，完全無(wú)法預(yù)測(cè)。這讓魔王怎么玩？魔王：“算你狠！破喉嚨，你把公主帶走吧！”破喉嚨：“公主已經(jīng)上天了，我也找不著她……”

這么說(shuō)起來(lái)，保密的問(wèn)題已經(jīng)解決了？

其實(shí)沒(méi)有！

**真正的難題在于，怎么讓雙方共享密鑰？**在量子密碼術(shù)出現(xiàn)之前，密鑰需要第三方的信使來(lái)傳遞。而信使可能被抓（如《紅燈記》中的李玉和），也可能叛變（如《紅巖》中的甫志高），這麻煩就大了?，F(xiàn)在甚至都有技術(shù)可以遠(yuǎn)程讀出未通電的硬盤(pán)里的數(shù)據(jù)，傳送密鑰這活越來(lái)越不好干了！

甫志高

因此，在很長(zhǎng)時(shí)間內(nèi)，一次性便箋保密法的意義主要是在理論上，用來(lái)證明完全保密的系統(tǒng)是存在的，而實(shí)踐意義很小。道理很明顯：一次性便箋密鑰跟你要傳輸?shù)拿魑囊粯娱L(zhǎng)，如果你能安全地傳輸這么多的密鑰，那用這個(gè)信道直接傳輸明文不就得了？不就是因?yàn)闆](méi)有這么安全的信道，才需要發(fā)展保密方法嗎？這就好像周星馳的電影《國(guó)產(chǎn)凌凌漆》里那個(gè)“有光照才會(huì)發(fā)光的手電筒”，成了一個(gè)一本正經(jīng)的笑話(huà)。

你看，只要拿另外一只電筒照著它，它就亮了

魔王長(zhǎng)出一口氣：來(lái)來(lái)來(lái)，公主，我們重回賽場(chǎng)！

密碼學(xué)家們也不會(huì)輕易地狗帶，他們開(kāi)辟了另外一個(gè)戰(zhàn)場(chǎng)，叫做“公鑰密碼體制”。公鑰的意思，就是這個(gè)密鑰是向全世界公開(kāi)的，所有人都可以看到。還有一個(gè)私鑰，只在接收方（以下稱(chēng)為B）手里有，發(fā)送方（以下稱(chēng)為A）手里沒(méi)有。用公鑰可以加密，但不能解密，用私鑰才能解密。因此，A把明文用公鑰加密后，公開(kāi)傳給B，別人截獲了沒(méi)有私鑰無(wú)法竊密，而B(niǎo)拿到了就可以解密。公鑰密碼體制也常常被稱(chēng)作“非對(duì)稱(chēng)密碼體制”，因?yàn)殡p方手里的密鑰不一樣多。而雙方共享同一套密鑰的方法就叫做“對(duì)稱(chēng)密碼體制”，一次性便箋就是其中的一種。

公鑰密碼體制的關(guān)鍵在于：通過(guò)某些數(shù)學(xué)操作可以方便地從公鑰得到私鑰，但從公鑰卻很難得到私鑰。也就是說(shuō)，有些數(shù)學(xué)問(wèn)題沿著一個(gè)方向操作很容易，沿著相反的方向操作卻非常困難，“易守難攻”。

因數(shù)分解就是一個(gè)典型例子。把兩個(gè)質(zhì)數(shù)相乘得到一個(gè)合數(shù)，是很容易的，而把一個(gè)合數(shù)分解成質(zhì)因數(shù)的乘積，例如291,311 = 523 × 557（到下一節(jié)你就會(huì)明白為什么舉這個(gè)例子），就難得多了。

讓我們想想，如何分解一個(gè)數(shù)字N。最容易想到的算法，是從2開(kāi)始往上，一個(gè)一個(gè)地試驗(yàn)?zāi)芊裾齆，一直到N的平方根為止。如果N用二進(jìn)制表示是個(gè)n位數(shù)，即N約等于2的n次方，那么嘗試的次數(shù)大致就是2的n/2次方。指數(shù)上出現(xiàn)n，這就麻煩了，這叫做“指數(shù)增長(zhǎng)”。學(xué)過(guò)微積分的同學(xué)們明白，指數(shù)增長(zhǎng)是一種極快的增長(zhǎng)，比n的任何多項(xiàng)式都快。比如說(shuō)，2的n次方比n的10000次方增長(zhǎng)得還要快。沒(méi)有學(xué)過(guò)微積分的同學(xué)也不要頭暈，看看下面的圖就可以明白這個(gè)意思。

指數(shù)增長(zhǎng)的威力。指數(shù)函數(shù)雖然在最初落后，但很快勢(shì)不可擋地超越了線(xiàn)性函數(shù)和三次方函數(shù)，而且越到后面把它們甩得越遠(yuǎn)

在多項(xiàng)式之間比較，當(dāng)然是次數(shù)越高增長(zhǎng)得越快，例如n的三次方比二次方快，二次方比一次方快。但在計(jì)算機(jī)科學(xué)中，多項(xiàng)式內(nèi)部的這個(gè)差別并不太重要，它們只是定量的差別（醫(yī)生，我覺(jué)得我還可以搶救一下），而指數(shù)增長(zhǎng)與多項(xiàng)式增長(zhǎng)的差別是定性的差別（同志，放棄治療吧……）。因此，**計(jì)算機(jī)科學(xué)中把計(jì)算量多項(xiàng)式增長(zhǎng)的問(wèn)題稱(chēng)為“可解的”（tractable），把計(jì)算量指數(shù)增長(zhǎng)的問(wèn)題稱(chēng)為“不可解的”（intractable）。**不可解的意思并不是計(jì)算機(jī)不能算，而是計(jì)算量增長(zhǎng)得太快，通過(guò)擴(kuò)大問(wèn)題的規(guī)模，很快就能達(dá)到“用全世界的計(jì)算機(jī)算幾十億年都無(wú)法得出結(jié)果”的程度。

當(dāng)然，你可以尋找效率更高的算法。對(duì)于因數(shù)分解，人們發(fā)展了很多種比“一個(gè)個(gè)試”聰明得多的算法。但到目前為止，這些算法的計(jì)算量仍然都是指數(shù)增長(zhǎng)的。

1978年，基于因數(shù)分解的困難性，三位密碼學(xué)家李維斯特（Ron Rivest）、薩莫爾（Adi Shamir）和阿德曼（Leonard Adleman）發(fā)明了“RSA密碼體系”（這個(gè)名字是他們的首字母縮寫(xiě)），這是現(xiàn)在世界上最常用的公鑰密碼體系之一。

RSA密碼體系的三位發(fā)明者

除了RSA之外，還有許多其他的公鑰密碼體系。無(wú)論哪種，基本思想都是一樣的，安全性來(lái)自某個(gè)數(shù)學(xué)問(wèn)題的困難性?；氐侥跖c公主的比喻，現(xiàn)在公主不是滿(mǎn)世界亂跳了，而是按照某種確定的規(guī)則前進(jìn)。魔王以前是完全無(wú)從追起，而現(xiàn)在有可能追上公主了，只要解出某個(gè)數(shù)學(xué)問(wèn)題就行。但是這個(gè)數(shù)學(xué)問(wèn)題的計(jì)算量是指數(shù)增長(zhǎng)的，通過(guò)擴(kuò)大問(wèn)題的規(guī)模，很容易就使解題所需的時(shí)間變得不可思議的長(zhǎng)（指的是計(jì)算題，不是五點(diǎn)共圓這種證明題）。魔王：為什么一定要解數(shù)學(xué)題，我們來(lái)比寫(xiě)詩(shī)吼不吼?。?/p>

公鑰密碼體系是個(gè)偉大的發(fā)明，但它達(dá)到完美的安全性了嗎？顯然沒(méi)有，因?yàn)橥昝腊踩缘囊馑际菬o(wú)論敵方有多強(qiáng)的計(jì)算能力都不能破解。魔王：跟你說(shuō)解數(shù)學(xué)題不好了嘛，我先來(lái)念兩句詩(shī)……

在這個(gè)前提下，如果我們退一步，把計(jì)算量指數(shù)增長(zhǎng)作為僅次于完美安全的第二級(jí)別安全性，那也可以接受。但在這個(gè)臺(tái)階上，問(wèn)題又來(lái)了：你怎么能保證對(duì)這個(gè)數(shù)學(xué)問(wèn)題，不會(huì)發(fā)現(xiàn)多項(xiàng)式計(jì)算量的算法呢？

實(shí)際上，計(jì)算機(jī)科學(xué)中的一大難題就是：我們可以證明，計(jì)算量指數(shù)增長(zhǎng)的問(wèn)題有很多，然而，我們幾乎無(wú)法確定任何一個(gè)具體的問(wèn)題屬于這一類(lèi)！

包括因數(shù)分解在內(nèi)，目前公鑰密碼體制用到的所有數(shù)學(xué)問(wèn)題都是這樣，無(wú)法排除哪天有人提出破解算法的可能。因此，密碼學(xué)處于一種無(wú)止境的軍備競(jìng)賽對(duì)抗之中，一方提出更強(qiáng)的攻擊算法，另一方提出更強(qiáng)的保密算法，無(wú)限地循環(huán)下去。

算法的進(jìn)步和硬件的進(jìn)步，迫使許多公鑰密碼體系一再升級(jí)。例如RSA推薦使用的質(zhì)數(shù)長(zhǎng)度，就在不斷增加。即使你升級(jí)了，也只能保護(hù)新的數(shù)據(jù)，許多歷史數(shù)據(jù)還是可以被破解的，這又是一重頭疼。

以上這些，都是基于對(duì)公開(kāi)算法的討論。但是，只有學(xué)術(shù)界才會(huì)把破解的消息公開(kāi)。**在實(shí)際的軍事、政治、經(jīng)濟(jì)對(duì)抗中，對(duì)手如果破解了你的密碼，會(huì)讓你知道嗎？**偷襲珍珠港的策劃者山本五十六是因?yàn)樾谐绦孤?，飛機(jī)被美國(guó)擊落而死的，難道美國(guó)會(huì)告訴日本“我已經(jīng)破解了你的密碼”嗎？

在拍攝此照片幾小時(shí)后，山本五十六就被擊斃

早就有一位長(zhǎng)者說(shuō)過(guò)：你們啊，naive！悶聲發(fā)大財(cái)才是墜吼的！

用《三體》的語(yǔ)言說(shuō)，你無(wú)法判斷對(duì)方是否破解了你的密碼，這就構(gòu)成了“猜疑鏈”。用美國(guó)前國(guó)防部長(zhǎng)拉姆斯菲爾德的語(yǔ)言說(shuō)，最可怕的就是“未知的未知”。

拉姆斯菲爾德和“未知的未知”

在量子密碼術(shù)出現(xiàn)之前，永遠(yuǎn)的猜疑、無(wú)盡的升級(jí)和不時(shí)的泄密是我們不得不忍受的代價(jià)。畢竟，一次性便箋是個(gè)中看不中用的銀樣镴槍頭，真正能用的最好的保密方法就是公鑰密碼體制了。

我的朋友、著名科普作家“奧卡姆剃刀”是一位通信專(zhuān)家，他有一個(gè)親身經(jīng)歷的故事（https://www.wukong.com/question/6471509815406362893/）：

“那是一個(gè)涉密的科研項(xiàng)目，我們團(tuán)隊(duì)發(fā)明了一種三重MARS加密算法，我們認(rèn)為比上級(jí)配發(fā)的傳統(tǒng)加密方法更安全。

由于密碼算法的使用必須得到國(guó)家和軍隊(duì)某委員會(huì)的批準(zhǔn)，因此我們向他們提出了鑒定申請(qǐng)，結(jié)果卻被駁回。

我對(duì)此不服，給他們說(shuō)：你們憑什么認(rèn)為我這個(gè)算法不夠安全，有本事你們破解試試？

他們的回答是：我們沒(méi)本事破解，但不代表敵人沒(méi)本事破解，你給我證明下敵人無(wú)法破解。

然后我就懵逼了，最后只能繼續(xù)使用上級(jí)配發(fā)的加密算法，這樣即使出了問(wèn)題也沒(méi)我的責(zé)任。

加密算法就是這樣，你很難證明它安全，也很難證明它不安全。

加密算法的強(qiáng)度依賴(lài)的是數(shù)學(xué)難題的難度，即使是大家公認(rèn)的極難解決的數(shù)學(xué)難題，也備不住躲在陰暗角落的某個(gè)天才數(shù)學(xué)家已經(jīng)破解，而數(shù)學(xué)問(wèn)題的破解就如同窗戶(hù)紙一樣，一捅破就全完了。

很可能敵方已經(jīng)據(jù)此設(shè)計(jì)了完美的破解方法，這種可能雖然可能性極小，但終歸無(wú)法杜絕！因此，在傳遞絕密信息時(shí)，誰(shuí)都不敢拍胸脯保證，只能去賭概率，這是令人非常非常痛苦的！”

現(xiàn)在，我們的主角出場(chǎng)了。量子密碼術(shù)，改變了密碼攻防的基本格局。

我就是美貌與智慧并重，英雄與俠義的化身：唐伯虎

不通過(guò)信使，讓通信雙方直接分享密鑰，這意味著什么呢？意味著原本只具有理論意義的一次性便箋保密法起死回生了，變成一個(gè)可以實(shí)用的方法了！這種保密方法，封死了通過(guò)數(shù)學(xué)破解密碼的可能性！

因此，“奧卡姆剃刀”在講完上面那個(gè)故事之后，結(jié)論是（https://www.wukong.com/question/6471509815406362893/）：

“而量子通信解決了這個(gè)問(wèn)題，它從理論和實(shí)踐上都證明了不可破解，令人把懸著的心放回肚里，這是上千年密碼術(shù)的重大突破，功莫大焉！”

回到魔王與公主的比喻，現(xiàn)在公主又變成了滿(mǎn)世界亂跳，而且這次可以放心大膽地這么做了！魔王徹底失去了追上公主的希望，無(wú)論他的計(jì)算能力再?gòu)?qiáng)都無(wú)濟(jì)于事。因?yàn)椋@壓根就不是計(jì)算的事兒。

魔王：算你狠，我舉白旗還不行嗎？我看看還有沒(méi)有其他的辦法……

量子密碼術(shù)的出現(xiàn)，并不意味著信息安全的問(wèn)題已經(jīng)完全解決了。最明顯的，策反情報(bào)人員這一招就仍然存在。我的朋友、美國(guó)新墨西哥大學(xué)數(shù)學(xué)與統(tǒng)計(jì)系助理教授黃宏年博士認(rèn)為**，現(xiàn)在網(wǎng)絡(luò)安全體系最大的弱點(diǎn)并不在于密碼，在這方面增強(qiáng)不能解決主要問(wèn)題。**現(xiàn)在的操作系統(tǒng)過(guò)于復(fù)雜，許多地方用溢出攻擊等粗淺的手段就可以攻破。

我的理解是，信息安全問(wèn)題是個(gè)很長(zhǎng)的鏈條，量子密碼術(shù)只是保證了其中一個(gè)環(huán)節(jié)的安全，即密鑰分享和密文傳送這一環(huán)，敵方仍然可以去攻擊其他的環(huán)節(jié)。但是，能保證一個(gè)環(huán)節(jié)的安全已經(jīng)是相當(dāng)重大的進(jìn)步了，至少你泄密時(shí)可以排除這方面的問(wèn)題，集中排查其他方面。正如中國(guó)工程院院士鄔江興所說(shuō)：中國(guó)的網(wǎng)絡(luò)安全幾乎是“裸奔”，量子密碼術(shù)給它穿上了一條內(nèi)褲。

**如果你問(wèn)我，量子密碼術(shù)有什么缺點(diǎn)？最明顯的，就是慢。**由于密鑰是通過(guò)單光子的發(fā)射和接收產(chǎn)生的，條件十分苛刻，所以生成密鑰的速度目前都是在每秒多少k的量級(jí)。在一次性便箋加密中，明文跟密鑰一樣長(zhǎng)，所以傳輸信息的速度就等于生成密鑰的速度。每秒不到一兆的速度就像回到了撥號(hào)上網(wǎng)用“貓”的時(shí)代，只能傳送少量最重要的文本。如果用AES、DES之類(lèi)不等長(zhǎng)加密的對(duì)稱(chēng)密碼算法（用一段密鑰加密一個(gè)長(zhǎng)得多的文件），速度倒是上去了，但又有可能被數(shù)學(xué)破解了。此外，量子密碼術(shù)的成本應(yīng)該也不低，雖然我沒(méi)有具體數(shù)據(jù)。

除了慢和貴之外，作為一個(gè)新技術(shù)，量子密碼術(shù)的問(wèn)題想必還有許多。不過(guò)我既不是工程專(zhuān)家，也沒(méi)有打算自學(xué)成一個(gè)工程專(zhuān)家（估計(jì)學(xué)也學(xué)不成），我的興趣主要在理論方面，因此對(duì)我來(lái)說(shuō)，最重要的是：**量子密碼術(shù)的安全性是能在原理層面證明的，而目前其他的密碼體系都不能。**這就是量子密碼術(shù)無(wú)可替代的價(jià)值。

由此還可以引出一點(diǎn)值得強(qiáng)調(diào)的：量子密碼術(shù)從來(lái)沒(méi)有說(shuō)要完全代替?zhèn)鹘y(tǒng)的密碼術(shù)。作為一個(gè)新生事物，量子密碼術(shù)不是一上來(lái)就宣布“這個(gè)魚(yú)塘我承包了”（正經(jīng)的科技工作者不會(huì)這樣說(shuō)話(huà)的），而是“我有這樣一個(gè)能力，可能對(duì)保密有用，歡迎大家一塊來(lái)討論，看看什么地方能用上”。你可以列舉一千個(gè)不適合用量子密碼術(shù)的地方，這都沒(méi)問(wèn)題，但只要有一個(gè)地方適合用量子密碼術(shù)，就算是進(jìn)步了。用了量子密碼術(shù)，也不意味著排斥經(jīng)典密碼術(shù)，雙方完全可以結(jié)合使用，取長(zhǎng)補(bǔ)短。

這個(gè)魚(yú)塘我承包了

用不用量子密碼術(shù)的選擇權(quán)，當(dāng)然在于用戶(hù)。如果你對(duì)保密的要求高于一切，那么量子密碼術(shù)是你的好選擇。如果你沒(méi)有高價(jià)值的秘密需要保護(hù)，那有什么理由像某些企業(yè)宣傳的那樣，花很高的成本去追逐“量子小鎮(zhèn)”之類(lèi)的噱頭呢？

三、量子計(jì)算機(jī)對(duì)這幅圖景有什么影響？

基本的回答是：非本質(zhì)的影響。你看，我前面說(shuō)了那么多，壓根就沒(méi)提到“量子計(jì)算機(jī)”這個(gè)詞嘛！

傳統(tǒng)計(jì)算機(jī)的基本單元是比特（bit），指的是一個(gè)體系有且僅有兩個(gè)可能的狀態(tài)，往往用0和1來(lái)表示。而量子計(jì)算機(jī)的基本單元是量子比特（quantum bit，縮寫(xiě)為qubit或qbit），指的是一個(gè)體系可以處于兩個(gè)狀態(tài)|0>和|1>以及它們的任何疊加態(tài)a|0> + b|1>。這里的|>叫做狄拉克符號(hào)，在其中填入數(shù)字或文字，就可以表示量子狀態(tài)。

做一個(gè)比喻：**經(jīng)典比特是“開(kāi)關(guān)”，只有開(kāi)和關(guān)兩個(gè)狀態(tài)，而量子比特是“旋鈕”，有無(wú)窮多個(gè)狀態(tài)。**因此，量子計(jì)算機(jī)可以做到所有的經(jīng)典計(jì)算機(jī)可以做的事，還有可能做到一些經(jīng)典計(jì)算機(jī)做不了的事。

這里需要強(qiáng)調(diào)一點(diǎn)，常有文章把量子計(jì)算機(jī)描寫(xiě)成無(wú)所不能，都快成神了，這是重大的誤解。量子計(jì)算機(jī)仍然是需要算法的，而只對(duì)于某些特定的問(wèn)題，人們才設(shè)計(jì)出了超越經(jīng)典計(jì)算機(jī)的算法。因此，量子計(jì)算機(jī)不是因?yàn)槠毡樾缘乃愕每?，所以干什么都比?jīng)典計(jì)算機(jī)強(qiáng)，而是針對(duì)某些特定的問(wèn)題算得快，只在這些問(wèn)題上比經(jīng)典計(jì)算機(jī)強(qiáng)。

到目前為止，人類(lèi)找到的這樣的問(wèn)題并不是很多。但在這為數(shù)不多的能夠讓量子計(jì)算機(jī)大展拳腳的問(wèn)題中，其中一個(gè)恰恰就是——因數(shù)分解。

前面說(shuō)對(duì)因數(shù)分解，迄今還沒(méi)有能在多項(xiàng)式時(shí)間內(nèi)分解的算法，但那指的是經(jīng)典計(jì)算機(jī)。1994年，肖爾（Peter Shor）發(fā)明了一種量子算法，把因數(shù)分解的計(jì)算量減少到了多項(xiàng)式級(jí)別。這是一個(gè)革命性的進(jìn)步！分解300位和5000位的數(shù)字，量子算法會(huì)把所需時(shí)間從15萬(wàn)年減到不足1秒鐘，從50億年減到2分鐘！在理論上，RSA已經(jīng)被量子計(jì)算機(jī)攻克了！

不過(guò)這只是理論上，因?yàn)檎嬲苡玫牧孔佑?jì)算機(jī)還沒(méi)有造出來(lái)。到目前為止，在實(shí)驗(yàn)上分解的最大的數(shù)是291,311 = 523 × 557，是由中國(guó)科學(xué)技術(shù)大學(xué)的杜江峰院士和彭新華教授等人在2017年實(shí)現(xiàn)的。這離分解上千位的密碼還遠(yuǎn)著呢。

量子計(jì)算機(jī)是當(dāng)前全世界的科研熱門(mén)。許多研究機(jī)構(gòu)和企業(yè)在激烈地競(jìng)爭(zhēng)，紛紛放出風(fēng)來(lái)要在近年內(nèi)實(shí)現(xiàn)“量子制霸”，實(shí)際意思就是前面說(shuō)的，對(duì)于某些問(wèn)題超越現(xiàn)有的經(jīng)典計(jì)算機(jī)。有發(fā)展的眼光的人，都會(huì)關(guān)注這方面的消息。

顯然，量子計(jì)算的進(jìn)步，增加了人們對(duì)量子密碼術(shù)的需求。但是，如果沒(méi)有量子因數(shù)分解算法，甚至壓根沒(méi)有量子計(jì)算機(jī)的概念，量子密碼術(shù)是不是就沒(méi)有價(jià)值了呢？

當(dāng)然不是！

量子密碼術(shù)的基本價(jià)值來(lái)自它的完美安全性，這是其他任何密碼體系都沒(méi)有做到的。無(wú)論計(jì)算技術(shù)有沒(méi)有進(jìn)步，這個(gè)價(jià)值始終存在。量子因數(shù)分解或者任何其他的計(jì)算技術(shù)進(jìn)步，只是起到錦上添花或者說(shuō)“補(bǔ)一刀”的作用，對(duì)這個(gè)基本圖景并沒(méi)有影響。

徐令予老師在文章中說(shuō)：

“為什么要開(kāi)發(fā)量子保密通信技術(shù)？因?yàn)閺睦碚撋现v，如果未來(lái)量子計(jì)算機(jī)建成，如果建成的量子計(jì)算機(jī)有足夠的Qbit和足夠的穩(wěn)定性，那么今天密碼系統(tǒng)中的公鑰密碼RSA有可能被破解?！?/p>

根據(jù)以上的分析，我們知道這個(gè)理解是錯(cuò)誤的。實(shí)際上，最早的量子密碼術(shù)協(xié)議BB84是在1984年發(fā)明的，而量子因數(shù)分解算法是在10年之后的1994年發(fā)明的。難道在1994年之前，人們會(huì)覺(jué)得BB84協(xié)議沒(méi)有意義嗎？

四、《后量子RSA》說(shuō)了些什么？

徐老師在文章中對(duì)這篇論文的介紹是：

“數(shù)月前出現(xiàn)這樣一篇論文：‘后量子時(shí)代的RSA’[2]，該文發(fā)表后被多家相關(guān)雜志轉(zhuǎn)載和引用，這些文章給出的共同結(jié)論是：目前使用的非對(duì)稱(chēng)性密碼RSA不會(huì)因?yàn)榱孔佑?jì)算機(jī)的出現(xiàn)而消亡?！?/p>

如前所述，經(jīng)過(guò)饒有興味的研讀之后，我大致理解了此文的框架。此文的四位作者Daniel J. Bernstein、Nadia Heninger、Paul Lou、Luke Valenta（以下簡(jiǎn)稱(chēng)為BHLV）表現(xiàn)出了很強(qiáng)的數(shù)學(xué)功力和創(chuàng)意，令我十分敬佩。那么，BHLV實(shí)際說(shuō)了些什么呢？

他們說(shuō)的是：目前版本的RSA在量子算法面前不堪一擊，他們提出了一種改進(jìn)的版本，在某種意義上可以對(duì)抗已知的量子算法。

在什么意義上呢？合法用戶(hù)加密解密也是需要計(jì)算量的，而肖爾的量子算法強(qiáng)大到了這種程度：破解RSA跟合法用戶(hù)解密幾乎一樣快，具體而言，計(jì)算量都大約是n的平方（n是要分解的那個(gè)合數(shù)的二進(jìn)制位數(shù)）。對(duì)RSA密碼體系來(lái)說(shuō)，這簡(jiǎn)直是輸?shù)眠B底褲都快沒(méi)有了。

傳統(tǒng)的RSA是把兩個(gè)質(zhì)數(shù)相乘。BHLV提出，通過(guò)一系列數(shù)學(xué)技巧（快速的乘法以及隨機(jī)生成質(zhì)數(shù)的方法等等），可以把加密解密的計(jì)算量都控制在正比于n，然后把非常多的質(zhì)數(shù)相乘，使得n非常大，就可以讓破解的計(jì)算量顯著地超過(guò)加密解密的計(jì)算量。簡(jiǎn)而言之，就是把加密解密的計(jì)算量（n）降低到了破解的計(jì)算量（n的平方）之下。他們把這種改進(jìn)版RSA稱(chēng)為后量子RSA。

呃……原來(lái)我們說(shuō)的是，破解的計(jì)算量指數(shù)增長(zhǎng)才算安全?，F(xiàn)在標(biāo)準(zhǔn)降得這么低，破解的計(jì)算量比加密解密增長(zhǎng)得快就算安全，——這幾乎是可以定義的最低級(jí)別的安全性了。

原文對(duì)此說(shuō)得很清楚：

“Post-quantum RSA does not qualify as secure under old-fashioned security definitions requiring asymptotic security against polynomial-time adversaries. However, post-quantum RSA does appear to provide a reasonable level of concrete security.”

【翻譯：在老派的安全性定義下，即面對(duì)多項(xiàng)式時(shí)間敵手時(shí)的漸近安全性的定義下，后量子RSA沒(méi)有達(dá)到安全的標(biāo)準(zhǔn)。然而，后量子RSA看起來(lái)確實(shí)提供了一個(gè)合理水平的具體的安全性。】”

后面還有一個(gè)更具體的解釋?zhuān)?/p>

“Note that, for theoretical purposes, it is possible that (1) there are no public-key encryption systems secure against polynomial-time quantum adversaries but (2) there are public-key encryption systems secure against, e.g., essentially-linear-time quantum adversaries. Post-quantum RSA is a candidate for the second category.”

【翻譯：請(qǐng)注意，對(duì)于理論的目的，以下兩點(diǎn)是有可能的：(1) 沒(méi)有任何公鑰密碼體系在多項(xiàng)式時(shí)間的量子敵手的面前是安全的；但是(2)有公鑰密碼體系在比如說(shuō)基本上是線(xiàn)性時(shí)間的量子敵手的面前是安全的。后量子RSA是第二類(lèi)的一個(gè)候選者?！俊?/p>

如果你看不懂，我來(lái)簡(jiǎn)單解釋一下。給定問(wèn)題的規(guī)模n，如果你允許量子計(jì)算機(jī)運(yùn)行對(duì)n的任意高階多項(xiàng)式的時(shí)間，那么大概所有的公鑰密碼體系都會(huì)被擊敗。而如果你只允許量子計(jì)算機(jī)運(yùn)行n的時(shí)間，那么就可能有公鑰密碼體系扛得住。后量子RSA是后一類(lèi)中的一個(gè)候選者。為什么只說(shuō)是候選者，而不是直接就是呢？因?yàn)槟銦o(wú)法保證人們不發(fā)展出新的量子算法甚至是經(jīng)典算法，在n的時(shí)間內(nèi)破解后量子RSA。

從破解跟解密一樣快，改進(jìn)到加密解密比破解快，這個(gè)進(jìn)步好比贏(yíng)回了一條底褲?；蛘哌@么說(shuō)：一個(gè)低手跟一個(gè)高手下圍棋，從分先到讓先，到倒貼目，到讓二子，到讓三子，一路被打得降級(jí)，現(xiàn)在提高了棋藝，在讓三子的情況下贏(yíng)了一盤(pán)，回到了讓二子。這當(dāng)然可喜可賀，不過(guò)如果把這理解成他可以跟高手分庭抗禮，甚至超過(guò)了高手，那就大錯(cuò)特錯(cuò)了。

用網(wǎng)絡(luò)語(yǔ)言說(shuō)：BHLV對(duì)RSA使用挽尊卡，為RSA挽回了尊嚴(yán)！效果：密碼術(shù)經(jīng)驗(yàn)+5。

挽尊卡

對(duì)于后量子RSA的價(jià)值，原文有一個(gè)生動(dòng)的比喻：

“RSA has enough flexibility to survive the advent of quantum computers — beaten, bruised, and limping, perhaps, but not dead.”

【翻譯：RSA有足夠的柔韌性來(lái)挺過(guò)量子計(jì)算機(jī)的來(lái)臨——被打擊，被挫傷，一瘸一拐地走，都有可能，但不是死亡?！俊?/p>

再來(lái)看看BHLV用什么樣具體的例子演示后量子RSA。目前常用的RSA是用兩個(gè)質(zhì)數(shù)相乘，每個(gè)質(zhì)數(shù)用二進(jìn)制表示是1024位或2048位。他們生成了2的31次方（2,147,483,648，即大約21億）個(gè)質(zhì)數(shù)，每個(gè)質(zhì)數(shù)用二進(jìn)制表示有2的12次方（即4096）位。這21億個(gè)質(zhì)數(shù)乘起來(lái)，得到了2的43次方（8,796,093,022,208，即大約8.8萬(wàn)億）長(zhǎng)度的一個(gè)密鑰，也就是1 T字節(jié)長(zhǎng)度的一個(gè)數(shù)字。想想看1 T容量足夠放下多少部電影，現(xiàn)在居然只是用來(lái)存放一個(gè)數(shù)字！

處理如此巨大的數(shù)字，加密解密當(dāng)然也很不容易。生成21億個(gè)隨機(jī)的質(zhì)數(shù)，花費(fèi)了一個(gè)1400核的機(jī)群4個(gè)月的時(shí)間?？雌饋?lái)這是最耗時(shí)間的一步，后邊的質(zhì)數(shù)相乘、加密、解密等步驟，花費(fèi)的時(shí)間都是以天計(jì)，而不是以月計(jì)的。徐老師的文章說(shuō)“費(fèi)時(shí)一共為五天”，大概是只看了其中的一步。

根據(jù)BHLV的估算，肖爾的量子算法分解這個(gè)1 T字節(jié)長(zhǎng)度的數(shù)字，需要的量子比特操作數(shù)是2的100次方。2的43次方平方就得到2的86次方了，再考慮到其他一些細(xì)節(jié)，2的100次方是可以理解的。徐老師在這里似乎出現(xiàn)了一個(gè)硬傷，把量子比特操作的數(shù)目看成了量子比特的數(shù)目，然后以此為根據(jù)做了一番討論：

“假設(shè)量子計(jì)算機(jī)已經(jīng)建成，再假設(shè)量子計(jì)算機(jī)的量子位（Qbit）可以無(wú)限擴(kuò)展，進(jìn)一步假設(shè)該量子計(jì)算機(jī)的運(yùn)行成本與現(xiàn)在通用電子計(jì)算機(jī)的成本可以相比，用這樣一臺(tái)超級(jí)想象出來(lái)的量子計(jì)算機(jī)來(lái)破解長(zhǎng)度為T(mén)erabyte（太字節(jié)，等于1024 GB）的RSA非對(duì)稱(chēng)密鑰需要量子計(jì)算機(jī)的Qbit為2^100（2的100次方）。

2^100是一個(gè)什么概念？這個(gè)數(shù)大于我們星球上所有生物細(xì)胞的總數(shù)！而今天為了建成兩位數(shù)Qbit的量子計(jì)算機(jī)，專(zhuān)家們已經(jīng)弄得焦頭爛額，多年來(lái)一籌莫展。當(dāng)然使用長(zhǎng)度為T(mén)erabyte的RSA公鑰確實(shí)也有點(diǎn)離譜，但論文作者在今日的電子計(jì)算機(jī)上產(chǎn)生了這樣的公鑰，并用它來(lái)加密和解密，費(fèi)時(shí)一共為五天。按目前的技術(shù)水平，長(zhǎng)度為T(mén)erabyte的RSA公鑰雖然并不實(shí)用，至少還是可以實(shí)現(xiàn)的，但是還在紙上的量子計(jì)算機(jī)即使明天就建成，要破解這樣的RSA公鑰也無(wú)一線(xiàn)希望?！?/p>

其實(shí)原文是“2100 qubit operations”，不是“2100 qubits”。這個(gè)錯(cuò)誤的性質(zhì)，相當(dāng)于認(rèn)為一個(gè)量子比特只能操作一次，然后就報(bào)廢了。這當(dāng)然是不對(duì)的。因此，拿2的100次方去跟細(xì)胞的總數(shù)相比，跟專(zhuān)家想建成多少位的量子計(jì)算機(jī)相比，都對(duì)錯(cuò)號(hào)了。

BHLV對(duì)2的100次方這個(gè)數(shù)字，僅僅是說(shuō)它“驚人”（astonishing），沒(méi)有像徐老師這樣做這么多引申。這確實(shí)是一個(gè)非常大的數(shù)，但能不能說(shuō)量子計(jì)算機(jī)做不了這么多操作呢？這話(huà)誰(shuí)都不敢說(shuō)。至于將來(lái)算法改進(jìn)，在更短時(shí)間內(nèi)破解后量子RSA的可能性，自然也無(wú)法排除。因此，后量子RSA正如BHLV所言，提供的是“一個(gè)合理水平的具體的安全性”，還是“看起來(lái)確實(shí)提供了”，而不是能夠令理論家滿(mǎn)意的安全性水平，更不是完美的安全性。

**五、**如何理解后量子密碼學(xué)？

徐老師的文章中有這樣一段：

“再讓我們看看密碼學(xué)界最近的動(dòng)態(tài)，請(qǐng)先看下圖：密碼學(xué)界已經(jīng)明確把公鑰密碼系統(tǒng)分成兩大類(lèi)，左列中都是目前常用的公鑰密碼，它們是‘量子可破’的，即理論上在量子計(jì)算機(jī)攻擊下是不安全的（事實(shí)上也并非如此，見(jiàn)注解[2]）。圖中右列的幾種公鑰密碼系統(tǒng)被列為‘量子不可破’，它們從原理上被證明是不可能被量子計(jì)算機(jī)破解的，因而它們又被稱(chēng)為后量子時(shí)代的密碼系統(tǒng)。”

公鑰密碼系統(tǒng)的分類(lèi)

有些公鑰密碼系統(tǒng)已經(jīng)從原理上被證明是不可能被量子計(jì)算機(jī)破解的？我必須說(shuō)，這話(huà)是錯(cuò)誤的。實(shí)際上，**對(duì)于任何一個(gè)公鑰密碼系統(tǒng)，人們連它不會(huì)被經(jīng)典計(jì)算機(jī)破解都還沒(méi)有證明，又怎么可能證明它不會(huì)被量子計(jì)算機(jī)破解？**如果有人做出一個(gè)這樣的證明，那立刻會(huì)成為計(jì)算機(jī)科學(xué)界以至整個(gè)科學(xué)界最轟動(dòng)的消息，圖靈獎(jiǎng)什么的都不在話(huà)下。

徐老師在自己以前的文章《反對(duì)高鐵的邏輯，要用到量子通信上了？》（http://www.guancha.cn/XuLingyu/2016_08_26_372499.shtml）中，同樣引用了這個(gè)圖，而在那里的敘述是：

“再讓我們看看密碼學(xué)術(shù)界的動(dòng)態(tài)，請(qǐng)先看下圖：密碼學(xué)界已經(jīng)明確把公鑰密碼系統(tǒng)分成兩大類(lèi)，左列中都是目前常用的公鑰密碼，全被打入‘量子可破’的死域。

圖中右列確有幾種公鑰密碼理論方法被列為‘量子不可破’。但是請(qǐng)注意：1）它們只是目前還未被攻破，并非被證明‘量子不可破’。2）它們?nèi)繘](méi)有進(jìn)入實(shí)用階段，甚至未進(jìn)入應(yīng)用初期開(kāi)發(fā)階段，很可能最后根本沒(méi)有實(shí)用價(jià)值?！?/p>

其實(shí)徐老師以前的這個(gè)說(shuō)法，是完全正確的！

我再來(lái)多解釋幾句。后量子（post-quantum）、量子安全（quantum-secure）或者抗量子（quantum resistant）的密碼體系，這幾個(gè)術(shù)語(yǔ)表達(dá)的都是同樣的意思：能夠抵抗量子計(jì)算機(jī)的密碼體系。這是個(gè)活躍的研究領(lǐng)域，我對(duì)這個(gè)領(lǐng)域的研究者也是十分尊敬的。不過(guò)，目前這個(gè)領(lǐng)域的成果都是這種模式：我嚴(yán)格證明問(wèn)題A的難度跟問(wèn)題B相當(dāng)，而大家普遍相信問(wèn)題B對(duì)量子計(jì)算機(jī)來(lái)說(shuō)非常困難（這只是個(gè)猜想，不是證明），所以可以相信問(wèn)題A對(duì)量子計(jì)算機(jī)也非常困難。**結(jié)果是，證明了若干個(gè)猜想之間的等價(jià)性，但沒(méi)有證明任何一個(gè)猜想。**因此，后量子密碼學(xué)的基本格局跟傳統(tǒng)密碼學(xué)是一樣的，都是無(wú)止境的貓捉老鼠、魔王追公主的競(jìng)賽。

六、金融業(yè)現(xiàn)有的密碼體制已經(jīng)足夠安全了嗎？

徐老師的文章里提到：

“那么金融行業(yè)，特別是銀行系統(tǒng)是否會(huì)享受到量子通信干線(xiàn)的優(yōu)越性呢？很可惜答案是否定的。量子計(jì)算機(jī)有可能破解RSA這類(lèi)非對(duì)稱(chēng)密鑰，而對(duì)于基于復(fù)雜邏輯運(yùn)算的對(duì)稱(chēng)密鑰體制根本就沒(méi)有威脅?，F(xiàn)在所有金融行業(yè)（包括銀行）采用的都是對(duì)稱(chēng)密鑰體制，這個(gè)標(biāo)準(zhǔn)在由中國(guó)人民銀行頒布的PBOC里有詳細(xì)的描述[3]。

銀行系統(tǒng)密鑰分發(fā)要用到RSA這類(lèi)非對(duì)稱(chēng)密鑰只有初始化的第一次，之后采用的都是對(duì)稱(chēng)密鑰。其實(shí)初始化都未必會(huì)用到RSA，任何能夠安全地將初始化密鑰分發(fā)到密鑰分發(fā)管理中心的手段都可以采用，畢竟只需要做一次的事情，麻煩一些也無(wú)所謂。我估計(jì)，銀行與其它金融系統(tǒng)對(duì)量子保密通信是沒(méi)有多少興趣的，哪怕你有天大本事明天就變出一臺(tái)幾萬(wàn)Qbit的量子計(jì)算機(jī)，他們?nèi)耘f會(huì)是‘量子圍困萬(wàn)千重，我自巋然不動(dòng)?！?/p>

其實(shí)這個(gè)估計(jì)有點(diǎn)主觀(guān)了。京滬干線(xiàn)建設(shè)的基本動(dòng)機(jī)之一，就是金融部門(mén)不滿(mǎn)足于現(xiàn)有的密碼體系（詳細(xì)闡述見(jiàn)下一節(jié)）。

例如徐老師描述的這種體系，其安全性歸根結(jié)底依賴(lài)于最初存的那些對(duì)稱(chēng)密鑰。對(duì)稱(chēng)密鑰有多長(zhǎng)，能夠安全傳輸?shù)男畔⒘烤褪嵌啻?。這樣又回到信使可靠性的問(wèn)題了。如果密鑰長(zhǎng)期不換，失竊的風(fēng)險(xiǎn)就越來(lái)越大。而如果要及時(shí)更換，又頻繁地需要信使?？傊?，做到一次一密非常困難。相比之下，量子密碼術(shù)天然就是一次一密的，因?yàn)槊荑€可以等到有信息要傳輸時(shí)現(xiàn)場(chǎng)生成，這個(gè)優(yōu)越性很明顯。

這里還可以引申一下。我在講RSA的時(shí)候，經(jīng)常有人問(wèn)：如果我把所有的兩個(gè)幾千位質(zhì)數(shù)相乘的乘積存起來(lái)，不就可以破解RSA嗎？回答是：當(dāng)然可以