古典密碼術

譚亦夫 宋培非 李子臣

人類文明發展到使用語言和文字后，就產生了保密通信和身份認證問題，這是密碼學的主要任務。古典密碼學與其說是一門科學，不如說更像是一門藝術，它們反映出古人的高超智慧和絕妙想象力，并且蘊涵了現代密碼學思想的萌芽。1949年，信息論的創始人香農（Shannon）發表了名為《保密系統的通信理論》的文章，為密碼技術的研究奠定了理論基礎，由此密碼學成了一門科學。而在此之前的編碼方法被稱為古典密碼學。

古希臘“天書”

大約在公元前700年，古希臘軍隊用一種叫作Scytale的圓木棍來進行保密通信。其使用方法是：把長帶子狀羊皮紙纏繞在圓木棍上，然后在上面寫字；解下羊皮紙后，上面只有雜亂無章的字符，只有再次以同樣的方式纏繞到同樣粗細的棍子上，才能看出所寫的內容。

這種Scytale圓木棍也許是人類最早使用的文字加密解密工具，據說主要是古希臘城邦中的斯巴達人在使用它，所以又被叫作“天書”。

斯巴達棒的加密原理屬于密碼學中的“移位法”（Transition）加密，因為它通過改變文本中字母的閱讀順序來達到加密的目的。

古羅馬愷撒密碼

公元100多年前，古羅馬的執政官和軍隊統帥愷撒發明了一種把所有的字母按字母表順序循環移位的文字加密方法。例如，當規定按字母表順移3位的話，那么a就寫成d，b寫成e，c寫成f，…，x寫成a，y寫成b，z寫成c。

比如，Knowledge is power（知識就是力量），就寫成：NQRZOHGJHLVSRZHU。

從密碼學的角度來看，愷撒加密法屬于“單字母表替換”加密，而且替換的規則很簡單。然而，愷撒加密的思想對于西方古典密碼學的發展有較大影響。事實上，直到第二次世界大戰結束，西方所使用的加密方法大多屬于“字母表替換”加密，只是替換的規則越來越復雜而已。

歐洲加密術

替換加密就是把普通信文中的文字符號替換成其他文字符號以達到加密的目的，其替換規則只有合法的通信者知道。西方國家大都使用拼音文字，只有二十幾個字母和幾個標點符號，文字符號較少，所以很適合用替換法加密。如上文提到的愷撒密碼，就是一種替換加密。加密過程就是按照愷撒密碼字母替換表替換，把每一個明文字母替換成密文行中相應的一個字母。

這種加密方法具有“明密異同性”，利用頻率分析法可以破解。

于是，從15世紀中葉起，歐洲人開始研究設計“多字母表替換加密”方法，即明文中同一個字母在不同的位置上會有不同的替換符號。其中最有名的當屬維吉尼亞密碼（Vigenère Cipher）。它主要使用一張字母矩陣表，其中第一行是任意給定的字母表，第二行是第一行左循環移一位，最后一位的字母移至第一位，而形成的字母替換表。第三行又是第二行左循環移一位，以下各行以此類推。加密時，對于明文中的同一個字母，當其第一次出現時，使用表的第一行來替換，第二次出現時使用第二行替換，以此類推。如果該字母出現次數已超過矩陣的行數，則回到第一行繼續下去。解密同加密一樣，也是從上到下逐行進行。

維吉尼亞密碼后來出現過多種改進和變形。其中一種變形就是，由密鑰確定密文所在的行，明文確定明文所在列，在加密方陣中，行和列的交叉就是相應的明文。

例如：密鑰k=best，明文m=data security，密文C=EELTTIUNSMLR。

維吉尼亞加密過程中，一個明文字母根據在明文中出現的順序或者密鑰的不同，會有多種變化，最多能有26種變化。而愷撒密碼加密與明文字母的順序沒有關系，只有一種變換。所以愷撒密碼是“單表密碼體制”，而維吉尼亞密碼是“多表密碼體制”。顯然，多表加密比單表加密復雜許多，因此其破解難度也加大許多。自從維吉尼亞加密術出現以后，多表加密成為歐洲人最常用的加密方法。

破譯古典密碼

公元7世紀開始興盛的阿拉伯民族是最早系統總結并使用密碼分析方法的民族。

1987年，科學家發現了肯迪約在公元850年寫的《解碼手冊》。

書中關于密碼分析的描述如下：如果我們已經知道了一份密文所使用的語言，要破解它的一種方法是找一份用同樣語言寫的明文，大約有一頁紙的長度。然后統計其中每個字母出現的次數，把出現頻率最高的字母叫作“第一”，出現頻率次高的字母叫作“第二”，以此類推，直到數完明文中所有的字母。然后再看要破解的那份密文，同樣對其中的符號做頻率排序。我們找到出現頻率最高的那個符號并把它替換為上述的“第一”字母，找到出現頻率次高的符號并把它替換為“第二”字母，找到再次高的符號并替換為“第三”字母，直到數完密文中的所有符號。這是歷史上最早的研究用頻率分析法破解密碼的文獻，比西方的同類文獻早了大約300年。基于字母和單詞的統計學特性的頻率分析方法一直是破解密碼最基本和最常用的方法。

例如，已知經愷撒密碼加密過的密文：

HQGHDYRUWRVHHWKHJRRGLQHYHUBVLWXDWLRQ

統計得出“H”是出現次數最多的字母，頻率為0.194。

根據英文中字母出現概率的統計數據，字母“e”出現概率最高，為0.127。

那么，密文字母H的明文就應該是e，H對應的數字為7，e對應的數字為4，于是根據愷撒密碼加密規則：C=m+k（mod26），其中：C為密文，m為明文，k為密鑰。可以得出密鑰k=3，將密文中的字母向右移3位，就可得到明文。解密后得出明文：Endeavor to see the good in every situation（努力在每個情況下看到好的一面）。

第二次世界大戰中的密碼戰，是當時敵對雙方最優秀的科學大腦和最先進的科技之間的生死較量，但究其所依據的加密原理，仍然是替換和移位，破解原理是基于字母和單詞的頻率分析，只是復雜的程度不同而已。當然，肯迪的方法只能破解較原始的單表替換加密方法，對于較復雜的多表替換加密方法是無能為力的。然而，對于多表古典密碼體制，利用密文的重合指數方法和密文中字母統計規律相結合，同樣可以破譯。

練習題

本文結束之前，為了增加讀者的興趣，給大家出一個小小練習題。已知維吉尼亞密碼加密過的密文LRGPMIVZFMKIPAWK，密鑰為best，那么它的明文是什么？（答案在本期找）

（責任編輯/劉京 美術編輯/胡美巖）

知識鏈接：

中國古代密碼

從古到今，軍隊歷來是使用密碼最頻繁的地方，因為保護己方秘密并洞悉敵方秘密是克敵制勝的重要條件。中國古代有著豐富的軍事實踐和發達的軍事理論，其中不乏巧妙、規范和系統的保密通信和身份認證方法。

1.兵書《六韜》中的“陰符”和“陰書”

“陰符”和“陰書”中的“陰”顯然是指“機密”，“符”是指“符號”，也有編碼的意思；而古文中的“書”是指“信件”或“文件”。所以，按照字面意義理解，“陰符”和“陰書”就是后來密碼學中的“加密后的信息”或“密文”，其加密的方法，相當于現代密碼學中變換的代替或移位。

2.虎符和信牌

虎符、信牌和符契，都具有驗證身份的作用。其中“符”字本義是指古代朝廷下命令的憑證；部首的“竹”表明最早的“符”是用竹子做的。“符”通常做成兩部分，使用時一分為二，驗證時合二為一；只有同一符的兩部分才能完美地合在一起；這就是常用詞“符合”的來歷。近代間諜史上，常有人把紙幣鈔票一撕為二，作為接頭聯絡的工具，其原理同“符”。現代密碼學中，運用公鑰-私鑰體系進行身份認證的方法也與“符”相通。