《應(yīng)用密碼學(xué)》課件第2章

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

2.1.1代替密碼

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

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

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

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

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

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

多表代替密碼由LeonBattista于1568年發(fā)明，在美國南北戰(zhàn)爭期間由聯(lián)軍使用。盡管他們?nèi)菀灼谱g（特別是在計算機(jī)的幫助下），許多商用計算機(jī)保密產(chǎn)品還是使用這種密碼形式。這種密碼的周期與文本一樣長，它也是很容易被破譯的。2.1.2換位密碼

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

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

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

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

在上世紀(jì)20年代，人們發(fā)明了各種機(jī)械加密設(shè)備用來自動進(jìn)行加密，大多數(shù)是基于轉(zhuǎn)輪的概念，機(jī)械轉(zhuǎn)輪用線連起來完成通常的密碼代替。

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

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

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

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

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

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

明碼字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ

密碼字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

明文：veni,vidi，vjdj，vici

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

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

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

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

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

仿射密碼是一種替換密碼，它也是用一個字母來替換另一個字母。記Z26={0,1,2,3,…,25}分別表示26個字母，選擇k使得k與26互質(zhì)，那么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關(guān)于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)其中，所有的運(yùn)算都是在Z26中。容易驗證d(c(p))=15(7p+3)-19(mod26)=p+45-19(mod26)=p。加密明文：hot首先轉(zhuǎn)化這三個字母分別為數(shù)字7、14和19，然后加密：密文串為：AGX。2.5維吉尼亞密碼技術(shù)

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

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

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

密鑰：21421914172142191417214219

密文：CITXWJCSYBHNJVML

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

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

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

解：明文friday對應(yīng)的編碼為：5，17，8，3，0，24

密文pacfku對應(yīng)的編碼為：15，16，2，5，10，20

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

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

為了保證信息的保密性，抗擊密碼分析，保密系統(tǒng)應(yīng)當(dāng)滿足下述要求：

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

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

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

④系統(tǒng)便于實現(xiàn)和使用。英文中的統(tǒng)計是有規(guī)律的：

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

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

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

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