數學中的戰爭，戰爭中的數學——漫談密碼（1）

作者：@Banana9

作為本專欄的首篇文章，我實在是有點誠惶誠恐。我本人才疏學淺，貨真價值的學渣，要論專業程度肯定是不值一提，只是平時各類知識都走馬觀花，故事性還是有一點的。我本人並非從事密碼學方向的研究，只是數年前選修過一門課程，如有錯誤，敬請指正。由於篇幅限制，當然最主要還是水平有限，本文主要講古典密碼，不展開討論DES、RSA這樣的現代密碼。

其實在密碼學領域，密碼不能作為一個獨立的概念，對應的定義稱為「密碼體制（Cryptosystem）」，它包括5個要素：明文的編碼集合，密文的編碼集合、密鑰、加密規則、解密規則。以英文為例，明文和密文的編碼集合都是A-Z（通常不分大小寫），或者擴展一下加上幾個標點符號。加密和解密規則通俗地講就是加解密的方法，密鑰就是在加密和解密過程中分別與明文和密文進行運算的元素。

最早的密碼大概是「凱撒密碼」，因為據說被凱撒使用過而得名。凱撒密碼的加密方法非常簡單，把每個字元用其後的第三（當然也可以用其他數字）個字元替換，如果數到字母表末尾了就從頭開始。如果把凱撒密碼用在英文上，那麼WEWONTHEWAR的加密結果就是ZIZRQWKIZDU，收到消息的一方解密的時候再向前推三個字元就行。這種密碼如果知道了加密方法的話解密當然非常簡單，把所有字元同時向前推，推到結果有意義的時候就是明文。

凱撒密碼之後就出現了較為複雜的替換加密，基本原理就是把語句中的每一個字元用其他的字元映射，比如A用M替換，B用D替換……解密的時候則反過來，其實就是中學數學裡學的一一映射。這種加密破解起來雖然有一定的難度，但依然是有漏洞的——比如說在英文的應用中，e、a、s、t這些字母是最常用的，也就是說在明文中，它們的出現次數通常也是最多的，那麼在密文中出現頻率較高的字元，很大概率對應的就是這些字母，用這些常見字母的排列一個個去試，如果能解密出有意義的字元串，那麼這時候用的解密映射很可能就是對的，多花點時間總能試出來。替換密碼有很多變種，也都存在這種問題。因此到了20世紀之後，替換密碼在戰爭中應用已經很少了。不幸的是，抗戰時期的國軍部分單位有的還使用這種密碼，密碼本是啥樣子呢，大家中考高考從漢字數字代碼表里找過自己名字對應的4位數吧，就那個樣子。這種密碼基本上被日本人一破一個準，因此二戰時期美英很多時候情報都不跟凱申公共享，因為告訴了老蔣差不多就等於告訴了日本人。至於我黨對蔣的情報工作，那都是直接看的明文，當然這就屬於另一個話題了。

替換加密是不是就徹底不安全了呢？也不見得，電視劇《潛伏》里，余則成和組織聯繫用的也是替換密碼，密碼體制——這裡通俗地稱作密碼本，就是他手裡的那本書。為什麼同樣的密碼體制，國軍用就不安全，tg用就安全了？第一因為這套密碼可能只有他一個人用，而每個情報員用的密碼是不一樣的，可選的範圍又如此廣闊，就算被截聽到信號，破譯方也很難確定對應的是哪套密碼本；第二，因為只有一個人用，更換代價非常小，因此可以經常換；第三畢竟每天就那麼點消息，通信量很少，跟作戰通信完全不在一個量級，而替換密碼的破譯是需要一定的密文數量來支撐的，否則也沒法找常出現的字元啊。

替換加密可以算作一種「單字碼加密」，意思是每個字母在密文中對應的字母始終是恆定的。為了克服單字碼加密體制的缺點，多字碼加密應運而生，顧名思義，就是加密後明文字元可能對應不同的密文字元。維吉尼亞密碼是一種簡單的多字碼加密，基本原理是用一個字元串與明文的同長度子串做某種運算。比如上面的WEWONTHEWAR，如果密鑰是2467的話，就把明文分成一個個4字元長的子串，然後把每個子串中的四個字元分別向後推2、4、6、7，這樣明文中的W在密文中對應的就是不同的字元。然而維吉尼亞密碼也不是完美的，舉例來說，如果某個字元串出現了多次，那麼它也有可能是常見片語，而它們之間的間隔，都是密鑰長度的整數倍（抱歉我沒辦法用更通俗的語言詳細解釋這個原理），這樣就可以推出密鑰的長度，接下來密文中的一部分就可以單獨提取出來，使用替換密碼的破譯方法來進行分析，除此之外還有其他的破譯方法。那維吉尼亞密碼怎樣才能安全呢？那隻能讓密鑰的長度跟明文一樣，而且每次加密都換密鑰，才能完全避免這種缺陷，這種密碼就不叫維吉尼亞密碼了，叫Vernam密碼。那Vernam密碼算不算是完美的密碼體制呢？算啊，絕對算啊，根本沒法破譯，可是問題來了——你怎麼把密鑰交給信息接收者呢？

所以Vernam的密碼雖然在理論上完美，但在實踐中不實用，不可能廣泛應用。

說起多字碼加密，不得不提它的兩個經典的應用案例。第一個是大名鼎鼎的Enigma密碼機，作為德國二戰時期使用的軍用密碼機，Enigma可算是古典密碼史上的巔峰之作，Enigma的詳細機制我也不甚了了，但是作為一種多字碼加密，Enigma的密鑰長度可以達到驚人的10的16次方，這就讓傳統的破譯方法失去了意義。Enigma在二戰時期讓盟軍吃盡了苦頭，等到1941年英國海軍捕獲了德國的U-110潛艇，在繳獲的Enigma密碼機和密碼本的幫助下，才真正破解了Enigma，在此之前連計算機之父圖靈拿它都沒辦法。有個非常著名的戰爭片《獵殺U-571》講的就是類似的事情，雖然不甚符合史實，但不影響電影本身的精彩程度，推薦觀看。

第二個就是大名鼎鼎的《十二宮殺手》了。被稱為「黃道十二宮殺手」的神秘殺人犯在上世紀60年代連續作案，並在1974年前給媒體寄送了4份密文，其中3份至今還沒解開，這一系列案件後來被改編為著名的懸疑電影《十二宮殺手》。下面這幅圖就是電影里的截圖，右邊那堆符號就是密文，看這個架勢，很可能用的就是長度足夠的維吉尼亞密碼甚至是Vernam密碼，考慮到密文數量如此之少，而密鑰長度可能很長，這些密碼很可能無法破解了。

至於電影嘛，滿滿的負能量，因此也推薦各位觀看

隨著計算機的發明和應用，新的現代密碼體制逐漸替代了舊的古典密碼，如今我們也只能在電影里回味一下古典密碼的餘韻了。無論是古典密碼還是現代密碼，最核心的部分都是數學，加密一方要做的就是讓破譯者做盡量多的數學運算才能破解，而破譯者要做的就是找到更好的方法來盡量降低破解運算的複雜度。密碼是數學中的戰爭，是戰爭中的數學，只有在對抗中，通過加密和解密的鬥智，密碼才有它獨特的魅力。當然，我們這些凡人只能跪在數學的山腳下，仰望天才們在越來越高的海拔鬥法。隨著量子計算的發展和對現代密碼體制的挑戰，這個海拔必然越來越高，讓我們期待現行密碼體制也失去效用的那天，好好看一看人類的智慧，究竟能達到一個怎樣的高度。