量子密碼術為什么有價值？

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

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

用一個比喻來說，密碼學的攻防就好比魔王追公主（魔王：“你喊吧，喊破喉嚨也不會有人來救你的！”破喉嚨：“公主，我來救你！”）。魔王知道公主運動的規(guī)則，但不知道公主運動的參數(shù)。魔王的目標是在這種前提下追上公主，公主的目標是在這種前提下擺脫魔王。

我們經(jīng)常說，沒有完美的東西。但在理論的層面上，這話其實不對。有一種很簡單的密碼體系，就具有“完美的安全性”（perfect security）。這里的“完美安全”是個信息論的術語，意思是攻擊方無論有多強的計算能力，都不可能從密文中得出任何信息。

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

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

香農

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

這么說起來，保密的問題已經(jīng)解決了？

其實沒有！

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

甫志高

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

魔王長出一口氣：來來來，公主，我們重回賽場！

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

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

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

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

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

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

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

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

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

除了RSA之外，還有許多其他的公鑰密碼體系。無論哪種，基本思想都是一樣的，安全性來自某個數(shù)學問題的困難性。回到魔王與公主的比喻，現(xiàn)在公主不是滿世界亂跳了，而是按照某種確定的規(guī)則前進。魔王以前是完全無從追起，而現(xiàn)在有可能追上公主了，只要解出某個數(shù)學問題就行。但是這個數(shù)學問題的計算量是指數(shù)增長的，通過擴大問題的規(guī)模，很容易就使解題所需的時間變得不可思議的長（指的是計算題，不是五點共圓這種證明題）。魔王：為什么一定要解數(shù)學題，我們來比寫詩吼不吼啊！

公鑰密碼體系是個偉大的發(fā)明，但它達到完美的安全性了嗎？顯然沒有，因為完美安全性的意思是無論敵方有多強的計算能力都不能破解。

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

實際上，計算機科學中的一大難題就是：我們可以證明，計算量指數(shù)增長的問題有很多，然而，我們幾乎無法確定任何一個具體的問題屬于這一類！

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

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

以上這些，都是基于對公開算法的討論。但是，只有學術界才會把破解的消息公開。在實際的軍事、政治、經(jīng)濟對抗中，對手如果破解了你的密碼，會讓你知道嗎？偷襲珍珠港的策劃者山本五十六是因為行程泄露，飛機被美國擊落而死的，難道美國會告訴日本“我已經(jīng)破解了你的密碼”嗎？

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

用《三體》的語言說，你無法判斷對方是否破解了你的密碼，這就構成了“猜疑鏈”。用美國前國防部長拉姆斯菲爾德的語言說，最可怕的就是“未知的未知”。

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

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

我的朋友、著名科普作家“奧卡姆剃刀”是一位通信專家，他有一個親身經(jīng)歷的故事：

“那是一個涉密的科研項目，我們團隊發(fā)明了一種三重MARS加密算法，我們認為比上級配發(fā)的傳統(tǒng)加密方法更安全。