第2章古典密碼體制2.1古典密碼學中的基本運算2.2隱寫術2.3移位密碼技術2.4仿射密碼技術2.5維吉尼亞密碼技術2.6弗納姆密碼技術2.7希爾密碼技術2.8古典密碼體制的安全性分析2.1古典密碼學中的基本運算

2.1.1代替密碼

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

（1）簡單代替密碼，或單字母密碼：就是明文的一個字符用相應的一個密文字符代替。

簡單代替密碼是很容易破譯的，因為它沒有把明文的不同字母的出現頻率掩蓋起來。在好的密碼分析者重構明文之前，所有的密文都由25個英文字母組成，可以使用頻率分析方法破譯這類密碼。（2）多名碼代替密碼：它與簡單代替密碼系統相似，唯一的不同是單個字符明文可以映射成密文的幾個字符之一，例如A可能對應于5、13、25或56，“B”可能對應于7、19、31或42，等等。

多名碼代替密碼早在1401年就由DuchyMantua公司使用，這些密碼比簡單代替密碼更難破譯，但仍不能掩蓋明文語言的所有統計特性，用已知明文攻擊，破譯這種密碼非常容易。（3）多字母代替密碼：字符塊被成組加密，例如“AB”可能對應于“RT”，“ABB”可能對應于“SLL”等。

多字母代替密碼是字母成組加密，普萊費爾在1854年發明了這種密碼。在第一次世界大戰中英國人就采用這種密碼。

（4）多表代替密碼：由多個簡單的代替密碼構成，例如，可能有5個被使用的不同的簡單代替密碼，單獨的一個字符用來改變明文的每個字符的位置。

多表代替密碼由LeonBattista于1568年發明，在美國南北戰爭期間由聯軍使用。盡管他們容易破譯（特別是在計算機的幫助下），許多商用計算機保密產品還是使用這種密碼形式。這種密碼的周期與文本一樣長，它也是很容易被破譯的。2.1.2換位密碼

在換位密碼中，明文的字母保持相同，但順序被打亂了。在簡單的縱行換位密碼中，明文以固定的寬度水平地寫在一張圖表紙上，密文按垂直方向讀出（如圖2－1所示），解密就是將密文按相同的寬度垂直地寫在圖表紙上，然后水平地讀出明文。圖2－1縱行換位密碼

由于密文字符與明文字符相同，對密文的頻數分析將揭示出每個字母和英語有相似的或然值。這給了密碼分析者很好的線索，他就能夠用各種技術去決定字母的準確順序，以得到明文。密文通過二次換位密碼極大地增強了安全性。甚至有更強的換位密碼，但使用計算機幾乎都能破譯。

在第一次世界大戰中，德國人所用的ADFGVX密碼就是一種換位密碼與簡單的代替密碼的組合。在那個時代它是一個非常復雜的算法，但被法國密碼分析家GeorgePainvin所破譯。

雖然許多現代密碼也使用換位法，但由于它對存儲空間要求很大，有時還要求消息為某個特定的長度，因而比較麻煩。代替密碼要常用得多。2.1.3轉輪機

在上世紀20年代，人們發明了各種機械加密設備用來自動進行加密，大多數是基于轉輪的概念，機械轉輪用線連起來完成通常的密碼代替。

轉輪機有一個鍵盤和一系列轉輪，每個轉輪是字母的任意組合，有26個位置，并且完成一種簡單代替。例如：一個轉輪可能被用線連起來以完成用“F”代替“A”，用“U”代替“B”，用“L”代替“C”等等，而且轉輪的輸出栓連接到相鄰的輸入栓上。

例如，在四個轉輪的密碼機中，第一個轉輪可能用“F”代替“A”，第二個轉輪可能用“Y”代替“F”，第三個轉輪可能用“E”代替“Y”，第四個轉輪可能用“C”代替“E”，“C”應該是輸出密文。那么當轉輪移動后，下一次代替將不同了。為使機器更安全，可把幾種轉輪和移動的齒輪結合起來。因為所有轉輪以不同的速度移動，n個轉輪的機器的周期是26n。為進一步阻止密碼分析，有些轉輪機在每個轉輪上還有不同的位置號。圖2－2是一個具有三個轉輪機器的簡略圖，其中，轉輪c1是慢轉輪，c2是中轉輪，c3是快轉輪。這里，每個轉輪具有4個輸入和4個輸出。初始狀態如圖(a)所示，這時，轉輪的輸入a、b、c、d分別對應輸出的D、C、B、A。第一次擊鍵后，快轉輪c3往下轉動一個位置，這時的設置如圖(b)所示，轉輪的輸入a、b、c、d分別對應輸出的D、A、C、B。同理，第二次擊鍵和第三次擊鍵后轉輪的設置分別如圖(c)和圖(d)所示。注意這三次擊鍵中轉輪和慢轉輪都沒有轉動。如果再擊鍵一次，即第四次擊鍵，這時快轉輪轉動一個位置，回復到最初的設置，而同時中轉輪也會往下轉動一個位置，慢轉輪則保持不動。直到第17次擊鍵，慢轉輪才開始轉動一次。也就是說，對于轉輪c3的每個完整旋轉，轉輪c2旋轉一個引腳位置，而對于c2轉輪的每個完整旋轉，轉輪c1旋轉一個引腳位置。因此，該簡略圖的機器周期是4×4×3=48，即有48種不同的替代字母可供使用。圖2－2具有連線的三轉輪簡略機器

最著名的轉輪裝置是恩尼格馬(Enigma)。恩尼格馬在第二次世界大戰期間由德國人使用。其基本原理由歐洲的ArthurScherbius和ArvidGerhardDamn發明，它由ArthurScherbius在美國申請了專利。德國人為了戰時使用，大大地加強了基本設計。

恩尼格馬有三個轉輪，從五個轉輪中選擇。轉輪機中有一塊稍微改變明文序列的插板，有一個反射輪導致每個轉輪對每一個明文字母操作兩次。像恩尼格馬那樣復雜的密碼，在第二次世界大戰期間都被破譯了。波蘭密碼小組最早破譯了德國的恩尼格馬，并告訴了英國人。德國人在戰爭進行過程中修改了他們的密碼。英國人繼續對新的方案進行分析，并成功地繼續進行了破譯。在破譯恩尼格馬過程中，英國科學家圖靈（Turing）做出了杰出的貢獻。 2.2隱寫術

隱寫術在希臘語中就是“秘密”+“書寫”的意思，它是將秘密信息隱藏于非秘密或者不太秘密的信息中的方法。傳統的隱寫術有：使用顯隱墨水，修改公共文本的約定，使用代碼字，寫藏頭詩，用小針在選擇的字符上刺小的針眼，在手寫的字符之間留下細微差別，在打印字符上用鉛筆作記號，等等，這些方法古代就已經出現了，遠早于電子／計算機密碼技術。最近，人們在圖像中隱藏秘密消息，用圖像的每個字節的最不重要的比特代替消息比特。但是圖像并沒有怎么改變（大多數圖像標準規定的顏色等級比人類眼睛能夠覺察到的要多得多），秘密消息卻能夠在接收端剝離出來。比如一張照片，在計算機中用24比特來描述每一個像素的顏色。如果把每個像素的24比特中最次要比特拿出來存放另外的文件，人的眼睛是分辨不出來隱藏了文件的照片與原來的照片有什么區別的。用這種方法可在大小為1024×1024字節的灰色刻度圖片中存儲64KB的消息。同樣道理，我們也可以把聲音文件和視頻文件中最次要比特拿出來存放要隱藏的文件。 2.3移位密碼技術

將密碼用于軍事用途的第一個文件記載是愷撒著的《高盧記》。愷撒描述了他如何將密信送到正處在被圍困、瀕臨滅亡的西塞羅。其中羅馬字母被替換成希臘字母使得敵人根本無法看懂信息。蘇托尼厄斯在公元二世紀寫的《愷撒傳》中對愷撒用過的其中一種替換密碼作了詳細的描寫。愷撒只是簡單地把信息中的每一個字母用字母表中的該字母后的第三個字母代替。這種密碼替換通常叫做愷撒移位密碼，或簡單地說，叫愷撒密碼。愷撒密碼是一種簡單的移位密碼，它把字母表中的每個字母用該字母后面的第三個字母來代替。例如“a”將變成“D”，“b”將變成“E”，“c”將變成“F”等。在字母表的最后，移位將重新折回，形成一個循環，“x”將變成“A”，“y”將變成“B”，“z”將變成“C”。能夠列出所有可能性定義如下所示的變換：

明碼字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ

密碼字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

明文：veni,vidi，vjdj，vici

密文：yhql,ylgl，ymgm,ylfl（veni，vidi，vici，“我來，我見，我征服”是儒勒·愷撒征服本都王法那西斯后向羅馬元老院宣告的名言）

現在，為每個字母分配一個數值（如a=0、b=1等），對每個明文字母p，用密文字母C代替，則愷撒密碼的加密算法可表示為：C=E(p)=(p+3)mod

26而解密算法則可表示為：p=D(C)=(C-3)mod26若攻擊者熟知該加密系統，則破譯截取的密文的唯一障礙就只是推算實際移位值所花費的時間。由于字母移位解密是由接收方完成，萬一加密方法泄露，對攻擊者來說解密就變得跟接收方解密一樣容易。為了改進愷撒密碼系統，我們可以通過加進一個附加的秘密，使得攻擊者必須付出比接收方大得多的工作量才能解密。也即明文的發送方和接收方事先協商好一個密鑰。該密鑰代表在當前環境下字母移位的位數（從1到25），而不像前面愷撒密碼系統那樣所有情況下都向前和向后移動3位。

用k(1≤k≤25)表示密鑰，則通用的愷撒加密算法可表示為：C=E(p)=(p+k)(mod26而解密算法則可表示為：p=D(C)=(C-3)mod26若攻擊者熟知該加密系統，則破譯截取的密文的唯一障礙就只是推算實際移位值所花費的時間。由于字母移位解密是由接收方完成，萬一加密方法泄露，對攻擊者來說解密就變得跟接收方解密一樣容易。

為了改進愷撒密碼系統，我們可以通過加進一個附加的秘密，使得攻擊者必須付出比接收方大得多的工作量才能解密。也即明文的發送方和接收方事先協商好一個密鑰。該密鑰代表在當前環境下字母移位的位數（從1到25），而不像前面愷撒密碼系統那樣所有情況下都向前和向后移動3位。用k(1≤k≤25)表示密鑰，則通用的愷撒加密算法可表示為：C=E(p)=(p+k)mod26相應地，解密算法可表示為：p=D(C)=(C-k)mod26 2.4仿射密碼技術

仿射密碼是一種替換密碼，它也是用一個字母來替換另一個字母。記Z26={0,1,2,3,…,25}分別表示26個字母，選擇k使得k與26互質，那么k=3、5、7、9、11、15、17、19、21、23、25之一和b∈Z26組成密鑰(k,b)。加密公式：c=ek(p)=k（p+b）(mod26)解密公式：dk(c)=k-1（c-b）(mod26)其中：k-1是k關于26的逆元，即k-1×k＝1(mod26)。例2－1選定(k,b)為（7，3），7－1mod26＝15，那么

加密公式：c=e(p)=(7p+3)(mod26)解密公式：p=15（c-3）(mod26)＝(15c－19)(mod26)其中，所有的運算都是在Z26中。容易驗證d(c(p))=15(7p+3)-19(mod26)=p+45-19(mod26)=p。加密明文：hot首先轉化這三個字母分別為數字7、14和19，然后加密：密文串為：AGX。2.5維吉尼亞密碼技術

即是說，密鑰的第一個字符被加到明文的第1個、第m+1個、第2m+1個、第3m+1個字符上（進行mod26運算），密鑰的第二個字符被加到明文的第2個、第m+2個、第2m+2個、第3m+2個字符上，依此類推。

解密函數Dk和加密函數一樣，只是運算時使用的是減法而不是加法，假設密文Y=(y1，y2，…，yn)，則解密函數為：在實際應用中，為了容易記住密鑰，常常使用英文單詞來充當Vigenere密碼的密鑰。作為一個例子，我們使用密鑰為vector，用數值表示則k=(21，4，2，19，14，17)，來加密明文：hereishowitworks。

加密過程如下描述：用密鑰k來加密明文消息，則第一個明文字符用其后面的第21個字符來代替(即向后移21位)，相應的，第二個明文字符則向后移4位，第三個字符向后移2位，以此類推。當用完密鑰k的最后一位時，又從密鑰的第一位開始，如此循環下去。因此，第7個明文字符被向后移21位，第8個明文字符向后移4位，等等。具體加密過程如下：明文：hereishowitworks

密鑰：21421914172142191417214219

密文：CITXWJCSYBHNJVML

Vigenere密碼的強度在于對每個明文字母有多個密文字母與之相對應，因此該字母的頻率信息是模糊的。實際上，維吉尼亞密碼是一種多表加密算法，在密文的不同位置出現的字符通常不是以同樣的方式加密的，但它是一種周期密碼，如果兩個同樣的字符出現的間隔固定，并且為密鑰長度的倍數，則它們將以同樣的方法進行加密。 2.6弗納姆密碼技術

為了增強Vernam密碼技術的安全性，應該避免密鑰的重復使用。假設我們可以做到：密鑰是真正的隨機序列；密鑰的長度大于或等于明文的長度；一個密鑰只使用一次。那么Vernam密碼技術是經得起攻擊的考驗的。 2.7希爾密碼技術

例2－2設英文字母a,b,c,…,z分別編碼為0,1,2,3,4,…,25。已知Hill密碼中的明文分組長度為2，密鑰K是Z26上的一個二階可逆方陣，假設明文friday所對應的密文為pacfku，試求密鑰K。

解：明文friday對應的編碼為：5，17，8，3，0，24

密文pacfku對應的編碼為：15，16，2，5，10，20

由于n=2（分組長度），所以可以設K為：明文：密文：于是有：(因為C=MKmod26)由此可得所以密鑰K為：

Hill密碼技術可以較好地抗擊統計分析攻擊，但在面對已知明文的攻擊時就很容易被破譯，特別是在已知密鑰矩陣行數的情況下。因此，Hill密碼技術并不安全。 2.8古典密碼體制的安全性分析

為了保證信息的保密性，抗擊密碼分析，保密系統應當滿足下述要求：

①系統即使達不到理論上是不可破的，也應當為實際上不可破的。就是說，從截獲的密文或某些已知的明文—密文對，要決定密鑰或任意明文在計算上是不可行的。

②系統的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。

③加密和解密算法適用于所有密鑰空間中的元素。

④系統便于實現和使用。英文中的統計是有規律的：

①每個單字母中E出現頻率最高，其次是T、A、O、I、N、S、H、R等，V、K、J、X、Q、Z最低。

②雙字母出現頻率最高的有TH，HE的出現頻率低于IN、ER等。

③還有THE、ING等其他規律。2.8.1移位密碼安全性分析

移位密碼是極不安全的（mod26），它可被窮舉密鑰搜索所分析：因為僅有