本文整理自Gilles Brassard教授的演講。
視頻
【墨子沙龍】Secrecy in a Quantum Word ——Gilles Brassard_騰訊視頻
圖文
我的報告主要是告訴大家，量子現象是如何改變我們在保密通信中的加密和解密方式的。
首先允許我給大家介紹一些密碼學的內容。密碼學長久以來都是兩個角色之間的爭鬥，加密者和破譯者。這種鬥爭已經持續了很長的時間了。比如說，這個叫做密碼棒的東西，至少已經問世2500年之久了。 它是密碼學最早的見證者之一。可能有其他的東西比它更早。所以說密碼學是一個古老的話題，在很長的時間內它都是一門藝術，但是現在變成了科學。
密碼棒圖片來源：維基百科
在今天的報告裡，我們最關心的事情是：事實上，我們住在一個量子的世界中。Artur已經告訴我們一些關於量子的含義。事實上，我們確實住在一個量子的世界。這對於加密者來說是好事嗎？或者換一種說法，量子的世界對加密者和破譯者哪一個更好？和經典世界相比，有哪些東西發生了改變？當然，還有一個更重要的問題，在這個問題誕生之初人們就各執一詞：誰將會獲勝，加密者還是破譯者？
我想先介紹一位科學家、詩人兼小說家，Edgar Allan Poe。他是一位19世紀的美國小說家和詩人，據我所知他沒有任何的科學研究背景。而且我還知道他是一位非常優秀的自學成才的非專業破譯密碼學家。事實上，他寫了一本叫做The Gold-Bug的小說，這本書是他最有名的著作之一。Poe講了這樣的一個故事，一個名叫William Legrand的人，他在森林中發現了這個看起來非常奇怪的手稿，他不知道這是什麼。他想如果他透過光線來觀察它，可能會有一些事情發生。因此他把這張羊皮紙靠近火光，想透過火光觀察它。出乎他意料的是，當他把它靠得離火焰很近的時候，密文出現了。
William Legrand意識到這些文字一定和海盜寶藏的埋藏地點有關。他是怎麼解密這段密文的呢？他解密的過程是一個非常精彩的故事，作者大約用了10頁的文字來解釋William Legrand如何破譯一段這樣的密文。這個故事十分有趣，許多現實世界的密碼學家在他們小的時候都讀到了這個故事，他們紛紛被密碼學的藝術之美所吸引，進而成長為真正的密碼學家，尤其是弗裡德曼先生。
我們再回到這個故事，William Legrand已經有了這樣的密文。首先要做的事是統計每個字符出現的次數。我們得到了這個結果——字符“8”是出現最頻繁的。在大多數西方語言中，包括英語，出現次數最頻繁的字母是“e”。因此William Legrand認為“8”就代表字母“e”。字符“4e;”出現了很多次。因為假設原文是英文，所以這必定是單詞“the”。“the”是由3個字母構成並且以“e”結尾的、出現最頻繁的單詞。所以很可能“；”代表“t”，“4”代表“h”。在經過10頁文字的推導後，他得到了結論——‘;’代表‘t’，‘4’代表 ‘h’，‘8’代表 ‘e’，等等。
The Gold-Bug 中密文和明文的對應關係
我們按照對應關係來替換掉密文中的字符——隨便說一句，這叫做密鑰，在密碼學中，密鑰是明文和密文之間相互轉換的工具，William Legrand通過推理找到了密鑰。密文經過變換後，我們就會得到明文。這樣看起來就可以理解了。現在他需要把空格加在這段文字裡。當加入空格後，我們得到了一段文字，看起來好像仍然不知所云。因為在這個時候，你需要在一定程度上去猜它是什麼含義。最後他在當天就找到了寶藏，很棒。
The Gold-Bug 中的明文
Poe並不是第一個找到破解密文方法的人。這種加密方法是將每個字母替換為另一個符號。用密碼學的術語叫作“單碼替換法”。並不是Poe發明了破解單碼替換法的方法，而是Al-Kindi。Al-Kindi也有多重身份，他在相當長的一生中寫了300本書。尤其是他寫了一本書，介紹瞭如何破譯加密的信息。在這本書裡，Al-Kindi解釋瞭如何解碼，如何破譯Poe書中提到的那種類型的密碼。你可能會認為這個工作是所有密碼學或者說密碼破譯的起源，然而並不是。這本書有一部分遺失，直到距今不久才被發現。所以在歷史上它並沒很大的影響力，這是一件令人遺憾的事。
那麼，究竟誰會獲勝呢？是加密者還是解密者？Poe是怎麼認為的呢？Poe有一個非常清晰的觀點，他篤信破譯者將會是最後的贏家：“可以全面斷言，人類的創造力還不足以創造出人類不能破譯的密碼。”換句話說，不論你是一個多麼聰明的加密者，總會有一個比你更聰明的破譯者。可能需要一段時間，但是你終將被一個足夠聰明的破譯者擊敗。Poe十分堅信這一點，因為他本身在破譯密碼上就有非常高的造詣。他於1841年在一本奇特的雜誌上寫下了以上的話語，請注意1841年，因為在當時有一個這樣的密碼，通常被認為是Vigenère在1586年在他的書《數字的密寫》中提出的。在1586年，Vigenère提出了一種加密方式，直到Poe的論點誕生時，它都沒有被破解。事實上，Poe是在1841年寫下這個論點，而Vigenère在1586年寫下這本書（但可以明確的是，在1553年這種加密方式就已經誕生了），直到Poe寫下這個論點時，它都始終沒有被破譯，而Poe非常確信破譯者終將會獲勝。但是這個加密方式十分強大，持續了將近300年沒人能夠破解。Poe怎麼也想不到的是，僅僅在他發表這個論點幾年後，Babbage就破解了它。這個加密方式存在了301年後才被打破。但是它最終確實被破譯了，所以可能Poe還是對的。
所以Poe所說的破譯者終將獲勝是正確的嗎？在我回答他是否是正確的之前，我要先告訴你一些關於密碼學的內容。回到密碼的產生上來，有兩個問題。其中一個就是如何獲得一串共享密鑰。如果有兩個人，名字通常用Alice和Bob表示。Alice和Bob想要秘密的進行通信。如果他們想要使用Poe故事裡的單碼替換法，他們需要知道密鑰是什麼。通信的雙方需要用共享的密鑰，一個用來進行加密，另一人則用來進行解密。所以怎麼獲得共享的密鑰是產生密碼時要考慮的一個主要問題。另一個問題是怎麼使用密鑰。我們在Poe的小說裡看到一種使用方式。但是應該有別的途徑，有更好的方法，比如像Vigenère那樣。所以第一個問題我們把它叫做密鑰的建立問題，第二個問題是在加密和解密過程中如何使用密鑰。加密的意思是將明文轉換為密文，解密的意思是將密文翻譯成明文——在你擁有密鑰的情況下。讓我們首先關注第二個問題，在我們已經有密鑰的情況下怎麼使用它。
我們已經見過一個現成的例子了。在The Gold-Bug中，一種使用密鑰的方式是將明文中的字母按照密鑰中的對應關係依次替換。這樣就得到了密文。一旦你有了密文，如果你也有密鑰，你可以反過來將每個字符一一替換成明文，這樣就重新得到了明文。這是一種在你擁有密鑰的情況下使用密鑰的方法。但是這並不好，因為在9世紀 Al-Kindi就已經破解了它。
讓我們看看是否有更好的方法。再次強調，這不是一個好方法。它只適用於初學者。Vigenère的方案在長達300年的時間內都很好，但是它最終還是被破解了。還有恩尼格瑪密碼機。恩尼格瑪是一臺德國人在二戰中使用的機器，萬幸的是它被破譯了，這也不是個好方案。在15年甚至更長的時間裡，美國政府想要使用一個叫做DES（Data Encryption Standard,即數據加密標準）的加密系統——它起源於1977年，但是後來也都放棄了。之後美國政府提出了“高級加密標準”，它是由比利時人發明的。美國政府舉行了一個競賽，鼓勵人們提出取代DES的新方案。有許許多多的方案，最終勝出的是兩個比利時人。他們發明了一套叫做Rigndael的系統，後來被美國政府重命名為AES。這就是現在的標準，已經使用了將近20年，還沒有人聲稱找到破解它的方法。這很好，但是我們沒有一個嚴格的證明。它的安全性我們不得而知，但是可能它是安全的。
有另一種加密方式誕生於19世紀，叫做“一次一密”。大多數人認為它是被Vernam或者 Mauborgne在20世紀發明的，但不是，應當更早，“一次一密”是1882年被一位銀行家發明的。“一次一密”是一種加密和解密信息的方式，它是無條件安全的。無條件安全的意思是說，如果竊聽者得到了編碼信息，也就是密文，他不能夠獲得任何明文的信息。除非有一些信息的洩露，比如說有幾個字符。但是除此之外，嚴格的講，在你沒有密鑰的情況下，不能通過攔截密文來獲取信息。而且，即使你有無盡的計算能力和最尖端的技術也是無法破譯的。如果你熟悉公鑰密碼學，你會知道它並不能保證無條件安全——公鑰密碼在有足夠計算能力的情況下總是可以被破解的。我所說的完美的安全性可以抵抗各種破解技術，我們可以證明“一次一密”擁有所有這些特性，它可以做到無條件安全。20世紀中葉，Shannon證明了這種加密算法的安全性，但是它卻在更晚的時間被髮明出來。
請允許我簡單介紹一下“一次一密”的工作原理。Alice和Bob是想要通信的雙方，他們共享密鑰，並且其他人無法獲知它。Alice想要給Bob發送信息，她通過手裡的信息和密鑰，對信息進行了簡單的加密，獲得她要發送給Bob的密文。“一次一密”的理論說的是，竊聽者在沒有密鑰的情況攔截密文，那麼他將不會得到任何明文的信息。Bob手持密鑰和密文，簡單地把它們摞在一起，就得到一段清晰的文字。再次強調，這種加密算法是絕對安全的。
在故事的最後，我們已經有了一種完美的加密和解密方式，我們為什麼還要用別的方案呢？我們為什麼還在浪費時間研究量子密碼學或者一些其他的加密方式呢？是因為這裡存在一個問題——你需要大量的密鑰。對每一比特的信息，你都需要一比特的密鑰進行加密。這是很不方便的。不過，在對於安全需求很高的情景，我們使用這種加密算法是合理的。比如說，在冷戰時期，赫魯曉夫和肯尼迪之間的通話就使用了這種方式。赫魯曉夫和肯尼迪之間的通信叫做“紅色電話”，實際上電話並不是紅色的，而且他們之間的通話也不是通過電話。但是至少，赫魯曉夫和肯尼迪在冷戰期間的秘密通信是通過“一次一密”的方式完成的。
現在的問題是一次性密碼本是怎麼在兩個領導人之間傳遞的？這個密碼本首先在華盛頓或者莫斯科產生，哪裡都可以。然後這串完全隨機的比特被保存在磁帶上，這種方式在那個年代已經有了。這個磁帶被保存在一個外交公文包裡，外交官牢牢掌控著。外交官會乘坐飛機把密鑰親手交給對方。這種級別安全性的通信需求不太普遍的情況下，這種方式是很好的。但是在當代，當任意兩個人想要秘密的通信時，這種方式就沒有意義了。
還有另外的一個問題，密鑰是怎麼建立的。我們知道了怎麼使用密鑰。現在讓我們談談如何建立密鑰。實際上有3種方式可以實現密鑰建立。Alice和Bob可以使用一個可信的第三方，就像赫魯曉夫和肯尼迪之間的公文包。這種方法已經應用在現實生活中，讓我們更深入地研究一些其他方法。
我們可以使用基於計算複雜度的計算安全性。Artur剛剛已經談到了，或者我們可以使用量子理論。出乎你的意料，我將更多的介紹一些計算安全性的內容，因為它有一段非常有趣的歷史。從定義出發，計算安全性對密鑰的保護是基於這一前提：竊聽者沒有足夠的計算能力破解它。所以從定義來說，它就不是無條件安全的。在計算時間充足的條件下總可以破解它。
密鑰建立是指， Alice和Bob一開始沒有共享的密鑰，他們想要建立一個。他們要做什麼呢？他們要通過一個信道進行交流。這是一個公共信道，公共的意思是這個信道對於竊聽是沒有任何保護措施的，你可能會對此感到震驚。但是信道是驗證過的，意思是Alice知道來自Bob的一切信息，反之亦然，信息在傳遞過程中沒有被修改。我們假設他們用這樣的驗證過的公共信道進行通信。在經過一些通信後，他們將相同的信息作為密鑰。他們都有相同的一串字符，被用來作為密鑰。更神奇的是，有一個全程竊聽的人，他想要獲取密鑰，但是他卻做不到。如果你沒見過這個現象，這聽起來就像是黑魔法一樣。這兩個人一開始沒有密鑰，他們各自做一些計算，然後進行通信，有一個人全程竊聽，在最後，他們可以得到密鑰，而竊聽全部通信過程的人卻不知道密鑰是什麼。聽起來像是黑魔法，不過我們知道如何在一些對於計算能力的假設下做到這一點。
現在來看它的發展歷史。大多數人認為這種方法首先由Whitfield Diffie和Martin Hellman在1976年發明。那一年誕生了一篇非常有名的文章——《密碼學的新方向》。一年後，Rivest, Shamir, Adleman從Diffie和Hellman的工作出發，發展出了著名的RSA加密系統。RSA在世界範圍內的安全網絡中廣泛應用。大約在同時，McEliece也提出了另一個實現Diffie和Hellman想法的途徑。這是我們通常所認為的發展歷史。
但是事實上，在Diffie和Hellman之前2年，Merkle就有了和他們幾乎相同的想法。Hellman是斯坦福一位非常有名的教授，Diffie是一位非常出色的學生，他們有能力推動這個想法的發展。而Merkle就位於隔壁的伯克利，但是沒有人能夠理解他在幹什麼，所以非常不幸，他在1974年的想法在1978年才得以發表。這就是真正的事實——Merkle先於Diffie和Hellman提出RSA想法。但是實際上，RSA是在更早些的時候被Clifford Cocks提出的。他在英國特勤局工作，他發明了它卻不能告訴其他人。實際上，Cocks的工作是基於Ellis的。Eillis是我們能瞭解到的極限，除非還有一些別的人突然從石頭縫裡蹦出來。我們目前為止知道，Ellis是第一個認為可能可以基於一些計算假設實現密鑰建立的人。這只是個瘋狂的想法，但是他不知道怎麼能讓它實現。當Cocks進入特情局時，他們給他一張桌子。他無所事事。因此他們遞給他一張Ellis在3年前寫的一份草稿。他在讀過後感到十分有趣。那天晚上他回到家，由於不在特勤局的高牆之內時，是不允許寫任何東西的，至少是任何和工作有關的東西，所以他就一直躺在床上，不被允許使用紙和筆等等一系列物品。就在那一晚，他發明了RSA加密系統。第二天早上他早早來到辦公室，你能想象的到，他把他的想法記錄下來並且來驗證它是否可行，結果成功了。這就是基於計算假設的密鑰建立的歷史。
你還記得我們的問題吧？我們所居住的量子世界改變了這一切。請允許我告訴你一些關於加密者、破譯者和通信信道的內容。加密者是經典的，意味著他們只有經典計算機，他們不懂量子理論。或者他們有一臺量子計算機，就像Artur之前談到的。破譯者可以是經典的或者量子的，Alice和Bob之間的信道也可以是經典或者量子的。這給我們提供了多種組合的可能。
特別地，如果每個人都是經典的，那麼從一開始我們就置身於一個經典的環境中。我們有許多經典條件下的人。這樣的場景從2500年前開始就存在，比如說前面說的故事就發生在一個經典的世界中。在經典世界中，我們每天都在大量的、數以百萬計的使用Diffie-Hellman和RSA這些方案來建立密鑰，並保證整個互聯網框架的安全性。
如果破譯者有量子計算機會發生什麼？我們把這個稱為後量子密碼學，是說加密者還只是經典的但是破譯者可以使用量子計算機。在這種情形下，有一種分解大數的方案，它是由Peter Shor提出的，他也是2018量子墨子獎的獲獎者之一。Shor發現量子計算機可以有效地分解大數，也可以有效地提取離散對數，而這兩點正是RSA和Diffie-Hellman算法所依賴的，甚至包括橢圓曲線加密算法也是如此。要完成這兩件事，你需要一個量子計算機，而一旦你擁有，一切將迎刃而解。
另一個重要的量子算法是Grover算法。如果你有一個函數，對於N個點，只有一個點的結果為1，其他的均為0。你想要找到這個滿足f(x) = 1的點。如果用經典的方法來找這個點，我們除了嘗試不同的輸入以外別無他法，不管是隨機試還是逐個試。這樣平均下來需要嘗試半數的點才能找到。所以在經典的情形下，你需要調用N/2次函數f才可以找到x。Grover發現了一種依託量子計算機的算法，你可以只需根號N次的調用就可以找到。這種算法十分出色。Shor算法可以使我們的運算速度比在經典計算機上有指數級的提升，而Grover的算法相比經典只有平方量級的提升，但是它卻擁有非常廣泛的應用——任何搜索問題都可以應用Grover算法進行加速。
無論什麼情況，讓我們回到密鑰建立問題。如果我們給竊聽者一臺量子計算機，量子竊聽者將會改變這一切。我沒有說明Merkle系統是如何工作的。但是一旦你掌握了Grover算法，Merkle系統就被破解了。所以說Grover破解了Merkle。Shor算法對離散對數的提取破解了Diffie-Hellman，而對大數的分解破解了RSA；是Cocks發明了RSA，Shor破解了Cocks。沒人知道如何用量子計算機破解McEliece。從一開始我們就使用Diffie-Hellman和RSA真的是個災難。如果使用的是McEliece，我們今天將會是安全的。但是不幸的是，整個密碼學框架都仰仗於Diffie-Hellman或 RSA的安全性，一旦量子計算機被髮明，這個框架將會瞬間崩塌。我們只有使用McEliece，今天才不會如此窘迫。選擇RSA和Diffie-Hellman的原因之一是因為McEliece需要更長的密鑰——不是更多的計算，而是更長的密鑰，MB量級的密鑰；而對於Diffie-Hellman和RSA，kB量級的密鑰就足夠。在當時——1980年代早期，也可能是1970年代末期，我們已經想到我們未來可能將會有手持加密設備，如智能卡，如果需要MB量級的密鑰，加密設備的體積會大到一隻手拿不下的地步。這在當時是顯然的，雖然今天看來，MB是非常小的。無論如何，我們在當時做了最好的決定，但是現在我們不得不面對這一切。
如果加密者是量子的，那麼就有可能挽救今天的局面。但是如果加密者是量子，那就意味著Alice和Bob現在擁有了量子計算機。可能量子計算機將會使得Alice和Bob實現安全的密鑰建立來抵禦量子的攻擊者。不幸的是，現在還做不到。到目前為止，量子計算看起來對破譯者更有優勢。Poe很高興，加密者很惆悵。
總的來說，在經典信道中，RSA 和 Diffie-Hellman可以抵抗經典攻擊者。我們不能完全證明這一點，但是它看起來是安全的。而它對於量子攻擊者來說是不安全的。所以量子看起來對於加密者是件壞事。還記得我們的問題嗎？量子理論對於加密者是好事還是壞事？答案看起來像是後者。但是McEliece可能是安全的，因此我們還有一些別的可能。另外在當時還發展了一些其他的方案。比如一些叫做New Hope和Frodo等的完全經典的加密系統。他們可能可以抵抗量子計算的攻擊。
我的報告接近尾聲了，但是我還想告訴你們一些在擁有量子信道後發生的故事，它又使得一切變得不一樣。事實上，甚至不需要加密者是量子的，他們只需要一個小的干涉。Alice和Bob之間的信道變成量子的，將會發生什麼？Alice和Bob可以是經典的，他們只需要一個小小的量子干涉，不需要其他的。這並不像說的那麼容易，而是需要一批科學家傾其一生來實現。但是這比實現量子計算機要容易得多。我們做的這一切叫做量子密碼術。
我想向你們介紹一個人，Stephen Wiesner，他是第一個考慮將量子效應引入密碼學中的人。Wiesner在1968年寫下了這篇文章，很不幸的是，它在很長一段時間內都沒能發表。在這篇文章中，Wiesner提出了量子鈔票的概念。量子鈔票只是一個量子力學的想法，它是把量子理論用於信息學和密碼學的最早的想法之一。Wiesner的想法是如此具有革命性，以至於這篇文章被雜誌退回了。他沒有繼續發展他的想法，而把它放進了抽屜裡。幸運的是，Wiesner把他的想法告訴了Bennett，他最好的朋友之一；Bennett用筆記錄了下來。在1970年，他用“量子信息理論”來命名這些筆記，可能這就是“量子信息理論”這幾個詞的誕生。他想向人們分享Wiesner的想法，但是沒有成功，沒人聽他的。
直到有一天我在波多黎各的聖胡安游泳，有個瘋狂的人遊向我，並且向我講述了Wiesner的想法——量子鈔票。當我們游回岸邊時，我們至少在腦海中構建好了我們的第一篇文章。長話短說，不管怎樣，是Wiesner的想法促進了量子密鑰分發和量子密碼學的誕生。
基於這個想法，我們可以以偏振光子的形式發送信息來抵禦竊聽者。因為這些光子無法被可靠地區分，所以任何竊聽都將會產生可被探測的錯誤。所以如果Alice以偏振光子的形式發送信息給Bob，有一個竊聽者在他們的信道上而使得信息發生篡改，Bob將收到不同於Alice的信息，這就是量子密碼學基本的想法。除此以外，我們可以用它來建立密鑰。在你擁有字母對照表後，密鑰就可以在“一次一密”中使用。這就是竊聽保護，這就是量子密碼學。
1984年，我們把這個想法發表在印度舉辦的一個會議的公報中，這就是熟知的BB84。我們實現了無條件保密的信息傳遞。無論竊聽者掌握何種技術和計算能力，它都是安全的，這就是無條件的定義。因此，誰將會獲勝？Poe錯了，加密者將會獲勝。當然，這種無條件安全的通信已經實現了。
我想說中國是目前為止在量子密碼學的實現中走在最前列的國家。謝謝潘建偉，他也獲得了2019年的量子墨子獎，但他今天只介紹演講者而不做報告。中國在量子密鑰分發的應用領域是處於國際領先的。你們還發射了一顆叫“墨子號”的衛星，和這個獎的名字相同，好巧！
“墨子號”可以被用來在遙遠的兩地之間建立密鑰。首個由量子密碼學加密的視頻電話，是於幾年前在奧地利科學院院長Anton Zeilinger和中國科學院院長白春禮之間進行的。他們的視頻電話很令人興奮，因為這是人類歷史上最安全的視頻通話。當然，周圍到處都是吵鬧的記者。
北京和維也納之間的量子通信
現在有覆蓋全球的量子衛星方案。Poe錯了。這是真的嗎？可能並不是。因為有量子黑客的存在。量子黑客沒有破譯量子密碼學。他們只是阻止量子密碼學的實現。量子密碼是安全的，但是完美的實現它有一定的難度。Vadim Markov，首屈一指的量子黑客，他在尋找實現量子密碼的漏洞上有著非凡的天分。他隨身帶著一個完美的量子黑客的公文包環遊世界，看他通過機場的安檢是一件有趣的事情。他時不時地會破譯一些實際的量子密碼系統。
Poe究竟是不是對的？實際上，在長達2500年的時間內，密碼學是數學家之間的一場戰役，最近這場戰役漸漸轉移到了工程師之間，因為有許多量子密碼方案在理論上都是完美的。你不僅需要工程師，也需要像潘建偉這樣的科學家來盡最大可能地實現量子密碼，還有一些其他的工程師比如Markov來試圖破譯它。所以爭鬥的中心已經由數學轉移到了工程學。Poe到底是不是對的？是量子黑客總是可以破壞量子密碼的實現，還是我們可以建造一些量子密碼使得量子黑客再也不能攻擊它？換句話說，貓和老鼠的遊戲還沒有結束。
現在給我的報告做個總結。我們住在量子的世界中，這對於加密者是壞事還是好事？答案是：我不知道。歷史將會說明一切，但是現在我還不知道。當然，我希望加密者將會贏，想出方法來更好地實現量子密碼使得Markov不能破解它，但是這還沒有得到證明。
謝謝大家!
關於“墨子沙龍”
墨子沙龍是由中國科學技術大學上海研究院主辦、上海市浦東新區科學技術協會及中國科大新創校友基金會協辦的公益性大型科普論壇。沙龍的科普對象為對科學有濃厚興趣、熱愛科普的普通民眾，力圖打造具有中學生學力便可以瞭解當下全球最尖端科學資訊的科普講壇。
