2.2 傳統密碼技術

以上討論了密碼技術的基本概念，本節將對傳統密碼學的典型方法進行簡要的論述和總結，使讀者對密碼學的全貌有一個完整的印象，理解現代密碼學產生的背景，為今后比較傳統密碼學和現代密碼學，研究和改進現代密碼系統的途徑打下基礎。

2.2.1 換位密碼

換位密碼根據一定的規則重新安排明文字母，使之成為密文。常用的換位密碼有兩種，一種是列換位密碼，另一種是周期換位密碼。下面給出兩個例子，分別說明它們的工作情況。

【例2-1】 假定有一個密鑰是type的列換位密碼，我們把明文can you believe her寫成4行4列矩陣，如表2-1所示。

按照密鑰type所確定的順序，按列寫出該矩陣中的字母，就得出密文：

YEVR NBEE COLE AUIH

【例2-2】 假設有一個周期是4的換位密碼，其密鑰是i=1，2，3，4的一個置換f（i）=3，4，2，1。明文同上例，加密時先將明文分組，每組4個字母，然后根據密鑰所規定的順序變換如下：

2.2.2 代替密碼

代替密碼就是明文中每一個字符被替換成密文中的另一個字符，接收者對密文進行逆替換就恢復出明文來。在經典的密碼學中，有以下幾種類型的代替密碼。

1．簡單代替密碼（Simple Substitution Cipher）

簡單代替密碼就是將明文字母表M中的每個字母用密文字母表C中的相應字母來代替。這一類密碼包括移位密碼、乘數密碼、仿射密碼、多項式代替密碼以及密鑰短語密碼等。加密前一般首先要對字母表中的每個字母按照其位置進行編號，如用0，1，2，…，25分別表示英文字母a，b，c，…，z。

（1）移位密碼

將明文字母表M的字母右移k個位置并對明文字母表長度q取模得到密文字母，是最簡單的一類代替密碼，其加密變換可表示為：e_k（m）=（k+m）modq=c，解密變換為：d_k（c）=（m-k）modq=m。其中，q為字母表M的長度，m為明文字符在字母表M中的位置，c為密文字母在字母表C中的位置。移位密碼就是對英文26個字母進行移位代替的密碼，其中q=26。這種密碼又被稱為愷撒密碼，因為古羅馬的愷撒曾使用過k=3時的這種密碼。例如，使用愷撒密碼加密，可將明文university加密成密文qlyhuvlwb。

（2）乘數密碼

將明文字母乘以密鑰k并對q取模得到密文字母。加密過程可表示為：

e_k（m）=kmmodq=c

其中，k和q為互素的，這樣字母表中的字母會產生一個復雜的剩余集合。若k和q不互素，則會有一些明文字母被加密成相同的密文字母，而且不是所有的字母都會出現在密文字母表中。

（3）仿射密碼

明文字母經過線性變換得到密文字母，加密的形式為：

e_k（m）=（k₁m+k₂）modq=c

其中，要求k₁和q是互素的，理由同上。

簡單代替密碼由于使用從明文到密文的單一映射，所以明文中單字母出現頻率分布與密文中相同，可以很容易地通過使用字母頻率分析法進行破譯。

2．多名或同音代替密碼（Homophonic Substitution Cipher）

在同音代替中，一個明文字母表的字母a，可以變換為若干個密文字母f（a），稱為同音字母，因此，從明文到密文的映射f的形式是f：A→2C，其中，A和C分別為明文和密文的字母表。

【例2-3】 假定一個同音代替密碼的密鑰是一段短文，該文及其中各個單詞的編號如下所示。

（1）Canada's large land mass and

（6）Scattered population make efficient communication

（11）a necessity.Extensive railway，road

（16）and other transportation systems，as

（21）well as telephone，telegraph，and

（26）cablenetworks，have helped to

（31）link communities and have played

（36）a vital part in the

（41）country's development for future

在上表中，每一個單詞的首字母都和一個數字對應，例如字母C與數字1，10，26，32，41對應；字母M和數字4，8對應，加密時可以用與字母對應的任何一個數字代替字母。例如，如果明文為I Love her forever，則密文可能是：

39 2 17 37 9 28 9 14 43 17 14 13 37 13 14

3．多表代替密碼（Polyalphabetic Substitution Cipher）

大多數多表代替密碼是周期代替密碼，當周期為1時，就是單表代替密碼。多表代替密碼的種類很多，這里只介紹其中的Vigenere密碼和游動鑰密碼。

在Vigenere密碼中，用戶鑰是一個有限序列k=（k₁，k₂，k₃，…，k_d），我們可以通過周期性（周期為d）將k擴展為無限序列k_i，其中Ki=K（imodd），1≤i≤∞，從而得到工作鑰K=（K₁，K₂，K₃，…）。

如果用Ф和θ分別表示密文和明文字母，則Vigenere密碼的變換公式為

Ф≡（θ+k_i）（modn）

該密碼體制有一個參數n。在加解密時，同樣把英文字母映射為0～25的數字再進行運算，并按n個字母一組進行變換。明文空間、密文空間及密鑰空間都是長度為n的英文字母串的集合。

【例2-4】 在用戶鑰為cat的Vigenere密碼（周期為3）中，加密明文Vigenere cipher的過程如下（n=26）：

在這個例子中，每個三字母組中的第一個、第二個和第三個字母分別移動（mod 26）2個、0個和19個位置。

游動鑰密碼是一種非周期性的Vigenere密碼，它的密鑰和明文信息一樣長，而且不重復。

【例2-5】 假定一個游動鑰密碼的密鑰是美國1776年7月4日發布的獨立宣言，從第一段開始，因此，明文the object of …

4．多字母代替密碼（Polygram Substitution Cipher）

多字母代替密碼即明文中的字符塊成組被加密。這里介紹一種第一次世界大戰使用過的二字母組代替密碼（P1ayfair密碼），它的密鑰是由25個英文字母（J被除去）組成的五階方陣，如表2-2所示。

每一對明文字母m₁和m₂，都根據以下五條規則進行加密。

1）若m₁和m₂在密鑰方陣中的同一行，則密文字母C₁和C₂分別是m₁和m₂右邊字母（第一列看作在第五列的右邊）。

2）若m_l和m₂在同一列，則C₁和C₂分別是m₁和m₂下邊的字母（第一行看作在第五行的下邊）。

3）若m₁和m₂在密鑰方陣中的不同行和列，密文字母C₁和C₂分別是以m₁和m₂為頂點組成的長方形中的另兩個頂點，其中C₁和m₁、C₂和m₂分別在同一行。

4）若m₁=m₂，則在m₁和m₂之間插進一個無效字母，例如x。

5）若明文信息共有奇數個字母，則在明文末尾附加一個無效字母。

【例2-6】 用Playfair密碼加密明文bookstore，有：

2.2.3 轉輪機

20世紀20年代，出現了轉輪密碼，而由德國發明家亞瑟·謝爾比烏斯發明的Enigma密碼機最為著名。它主要由經電線相連的鍵盤、轉子和顯示器組成，轉子本身也集成了26條線路（如圖2-2所示中顯示了6條），把鍵盤的信號對應到顯示器不同的小燈上去。在圖2-2中可以看到，如果按下a鍵，那么燈B就會亮，這意味著a被加密成了B。同樣可以看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果在鍵盤上依次鍵入cafe（咖啡），顯示器上就會依次顯示DBCE，這是最簡單的加密方法之一——簡單替換密碼。

不僅僅如此，因為當鍵盤上一個鍵被按下時，相應的密文在顯示器上顯示，然后轉子的方向就自動地轉動一個字母的位置（在圖中就是轉動1/6圈，而在實際中轉動1/26圈）。如圖2-3所示，它表示了連續鍵入3個b的情況。

當第一次鍵入b時，信號通過轉子中的連線，燈A亮起來，放開鍵后，轉子轉動一格，各字母所對應的密碼就改變了；第二次鍵入b時，它所對應的字母就變成了C；同樣地，第三次鍵入b時，燈E閃亮。

為使機器更安全，可以把幾種轉輪和移動的齒輪結合起來。因為所有轉輪以不同的速度移動，n個轉輪的機器的周期是26n。為進一步阻止密碼分析，有些轉輪機在每個轉輪上還有不同的位置號。

德國人為了戰時使用，大大加強了其基本設計。軍用的Enigma密碼機有3個轉輪，因此只有在26×26×26=17576個字母后才會重復原來的編碼。同時還在3個轉輪的一側加了1個反射器，導致每個轉輪對每一個明文字母操作兩次，結構如圖2-4所示。

但如此復雜的密碼機在第二次世界大戰中還是被破解了。首先是波蘭人利用德軍電報中前幾個字母的重復出現，破解了早期的Enigma密碼機，而后又將破譯的方法告訴了法國人和英國人。英國人在計算機理論之父——圖靈的帶領下，通過尋找德國人在密鑰選擇上的失誤，并成功奪取德軍的部分Enigma密碼機的密碼本，獲得密鑰，以及進行選擇明文攻擊等手段，破解出相當多非常重要的德軍情報。

2.2.4 一次一密密碼

1917年，Joseph Mauborgne少校和AT&T公司的Gilbert Vernam發明了一次一密亂碼本的加密方案。通常，一次一密亂碼本是一個大的不重復的真隨機密鑰字母集，這個密鑰字母集被寫在幾張紙上，并一起粘成一個亂碼本，它最初用于電傳打字機。發方用亂碼本中的每一密鑰字母準確地加密一個明文字符。加密是明文字符和一次一密亂碼本密鑰字符的模26加法。

每個密鑰僅對一個消息使用一次。發方對所發的消息加密，然后銷毀亂碼本中用過的一頁或用過的磁帶部分。收方有一個同樣的亂碼本，并依次使用亂碼本上的每個密鑰去解密密文的每個字符。收方在解密消息后銷毀亂碼本中用過的一頁或用過的磁帶部分。新的消息則用亂碼本中新的密鑰加密。

例如，如果消息是ONETIMEPAD，而取自亂碼本的密鑰序列是TBFRGFARFM，那么密文就是IPKLPSFHGQ，因為

（O+T）mod 26=I

（N+B）mod 26=P

（E+F）mod 26=K

…

如果竊聽者不能得到用來加密消息的一次一密亂碼本，這個方案是完全保密的。由于給出的密文消息相當于同樣長度的任何可能的明文消息，且每一密鑰序列都是等概率的（記住，密鑰是以隨機方式產生的），破譯者沒有任何信息用來對密文進行密碼分析，密鑰序列也可能是POYYAEAAZX，解密出來是SALMONEGGS，或密鑰序列為BXFGBMTMXM，解密出來的明文為GREENFLUID。

由于明文消息是等概率的，所以密碼分析者沒有辦法確定哪一個明文消息是正確的。隨機密鑰序列異或一非隨機的明文消息將產生完全隨機的密文消息，即便現代的高速計算機對此也無能為力。

使用一次一密亂碼本需要注意以下幾點。

1）密鑰字母必須隨機產生。對這種方案的攻擊主要是針對用來產生密鑰序列的方法。偽隨機數發生器通常只有非隨機性，所以不能用于產生隨機密鑰序列。采用真隨機源，它才是安全的。

2）密鑰序列不能重復使用。如果密碼分析者有多個密鑰重疊的密文，那么即使你用多兆字節的亂碼本，他也能重構明文。分析者可以把每排密文移來移去，并計算每個位置的適配量。如果排列正確，則適配的比例會突然升高（準確的百分比與明文的語種有關）。從這一點來說，密碼分析是容易的，它類似于重合指數法，只不過用兩個“周期”，所以千萬別重復使用密鑰序列。

一次一密亂碼本的想法很容易推廣到二進制數據的加密，只需用由二進制數字組成的亂碼本代替由字母組成的密亂碼本，用異或代替一次一密亂碼本的明文字符加法即可。解密時用同樣的亂碼本對密文異或，其他保持不變。這種方法現在主要用于高度機密的低帶寬信道，而在高速寬帶通信信道上工作還有很大的困難：密鑰比特必須隨機，密鑰序列的長度要等于消息的長度，并且絕不能重復使用；必須準確地復制兩份隨機數比特，且銷毀已經使用過的比特：要確保發方和收方完全同步，一旦收方有一比特的偏移（或者一些比特在傳送過程中丟失了），消息就變成了亂碼；如果某些比特在傳送中出現差錯，則這些比特就不能正確地解密。因此，盡管一次一密亂碼本不能破譯，但只能局限于某些應用。