第2章古典密碼學(xué)2.1單表替換密碼2.2多表替換密碼2.3置換密碼

密碼學(xué)大致可分為古典密碼學(xué)(ClassicCryptography)和現(xiàn)代密碼學(xué)(ModernCryptog_x0002_raphy)。

古典密碼學(xué)按照操作方式可分為兩大類:替換密碼和置換密碼。替換密碼就是將每個(gè)明文字母用一個(gè)對(duì)應(yīng)的密文字母進(jìn)行替代。

置換密碼則是將明文字母的順序打亂,明文字母本身并沒(méi)有改變。

替換密碼進(jìn)一步又可分為兩種加密方法:單表替換密碼和多表替換密碼。單表替換密碼就是明文字母與密文字母一一對(duì)應(yīng),只有一種映射關(guān)系;在多表替換密碼中,同一個(gè)明文字母可能被替換為多個(gè)不同的密文字母。古典密碼的分類如圖2.1所示。

圖2.1古典密碼分類

2.1單表替換密碼

2.1.1凱撒密碼(CaesarCipher)凱撒密碼最早是古羅馬軍事統(tǒng)帥蓋烏斯·尤利烏斯·凱撒在作戰(zhàn)中用于傳遞秘密信息,是一種典型的單表替換加密方法。密文字母和明文字母的對(duì)應(yīng)關(guān)系通過(guò)ASCII碼表中的固定偏移來(lái)得到。加密時(shí)將明文字母替換為與之對(duì)應(yīng)的密文字母即可。凱撒密碼的加解密方式對(duì)應(yīng)的數(shù)學(xué)語(yǔ)言描述如下。

凱撒密碼的加解密方式對(duì)應(yīng)的數(shù)學(xué)語(yǔ)言描述如下。

·定義:x,y,k∈Z26;

·加密:Ek（x）=x+kmod26;

·解密:Dk（y）=y-kmod26。

其中,x、y

分別表示明文字母、密文字母在ASCII碼表中的排列序號(hào),例如,字母“A”的序號(hào)是0,字母“B”的序號(hào)是1,字母“Z”的序號(hào)是25,k

表示密鑰(偏移量)。

凱撒密碼的密文字母和明文字母之間的映射關(guān)系如圖2.2所示。由圖可知,明文字母“A”被映射為密文字母“D”,明文字母“B”被映射為密文字母“E”,明文字母“X”被映射為密文字母“A”。也就是說(shuō),密文字母和明文字母之間偏移3個(gè)字母。模(mod)26運(yùn)算使得映射形成閉環(huán)。

圖2.2凱撒密碼的明密文映射關(guān)系

凱撒密碼加密算法的Python實(shí)現(xiàn)代碼如下:

1.importstring

2.

defCaesar_encryption(plaintext:string,key:int)->string:

3.

reflection=list(enumerate(string.ascii_lowercase))

4.

cipher=″″

5.

plaintext=plaintext.lower().replace(″″,″″)

6.foriinplaintext:

7.

cipher+=reflection[(ord(i)-ord(″a″)+key)%26][1]

8.returncipher

2.1.2關(guān)鍵詞密碼(KeywordCipher)

構(gòu)造關(guān)鍵詞密碼包含以下兩個(gè)步驟:

(1)選擇一個(gè)關(guān)鍵詞作為密鑰,將關(guān)鍵詞里的字母去重以后構(gòu)成一個(gè)集合。例如,關(guān)鍵詞“hello”構(gòu)成的集合是{h,e,l,o}(從左到右依次從關(guān)鍵詞中取出每個(gè)字母)。

(2)將關(guān)鍵詞寫(xiě)在字母表的下方(最左邊),并將字母表中的其他字母按標(biāo)準(zhǔn)ASCII碼表順序填補(bǔ)剩余的位置。

例如,選擇關(guān)鍵詞“crypto”,建立對(duì)應(yīng)的明文和密文的映射關(guān)系,如圖2.3所示。

圖2.3關(guān)鍵詞密碼的明密文映射關(guān)系

2.1.3仿射密碼(AffineCipher)

單表替換加密的另一種形式是仿射密碼。它是凱撒密碼的升級(jí),大大提高了暴力破解的難度。在仿射密碼中,將字母表中的字母從左至右分別賦予0~25之間的數(shù)字,即字母“A”用0表示,字母“B”用1表示,依次類推,最后一個(gè)字母“Z”用25表示。仿射密碼由一對(duì)密鑰(a,b)構(gòu)成,其中a、b

的取值范圍是0~25之間的整數(shù)。

仿射密碼加解密對(duì)應(yīng)的數(shù)學(xué)描述如下。

·定義:x,y,a,b∈Z26;

·加密:Ek(x)=ax+bmod26;

·解密:Dk(y)=a-1(y-b)mod26。

需要說(shuō)明的是,密鑰a的選擇是有限制條件的。a

要求滿足gcd(a,26)=1,此處gcd表示計(jì)算最大公約數(shù)。在解密仿射密碼的時(shí)候,需要求解a

的逆a-1,然而a-1

存在需要滿足a

與模數(shù)26互素。因此,gcd(a,26)=1式子成立,實(shí)際上就是尋找與26互素的數(shù)字。滿足此條件的所有a為

【例2-1】

首先選取密鑰為(9,13),然后選取明文為“GOD”。將“GOD”按照字母序號(hào)轉(zhuǎn)換成對(duì)應(yīng)的數(shù)字6、14、3。

利用仿射密碼的加密函數(shù)生成密文:

根據(jù)序號(hào)15、9、14對(duì)應(yīng)的字母可知密文是“PJO”。

仿射密碼對(duì)應(yīng)的Python實(shí)現(xiàn)代碼如下:

2.1.4單表替換密碼分析

單表替換密碼的特點(diǎn)是明文字母與密文字母的映射關(guān)系是固定的。而在英語(yǔ)中,每個(gè)字母都有自身的一些特性,例如,字母出現(xiàn)的頻率、出現(xiàn)的位置,與其他字母的組合關(guān)系等。因此,明文字母被替換成為相應(yīng)的密文字母以后,它本身的特性會(huì)在密文中保留并有所體現(xiàn)。

1.頻率分析

英文字母出現(xiàn)的頻率統(tǒng)計(jì)是最容易捕獲到的信息。在標(biāo)準(zhǔn)英語(yǔ)中,字母“e”出現(xiàn)的頻率最高,字母“z”出現(xiàn)的頻率則最低,如圖2.4所示。當(dāng)然,頻率分析也需要一定數(shù)量的密文來(lái)做支撐,密文數(shù)量越多,頻率分析越準(zhǔn)確。

圖2.4英語(yǔ)文本中的字母頻數(shù)統(tǒng)計(jì)直方圖

如果依靠字母出現(xiàn)的頻率無(wú)法破解明密文的映射關(guān)系,還可以進(jìn)一步利用字母出現(xiàn)的位置信息和字母之間的相鄰關(guān)系作為猜測(cè)的依據(jù)。例如,在標(biāo)準(zhǔn)英語(yǔ)中,“th”“he”“er”的字母組合是經(jīng)常出現(xiàn)的,而“hx”“yz”則幾乎沒(méi)有。除此之外,通過(guò)對(duì)英語(yǔ)單詞的統(tǒng)計(jì)分析,發(fā)現(xiàn)英文單詞存在以下有用信息:

(1)字母“r”與不同的字母組成的字母對(duì)比其他字母多;

(2)元音字母組成的兩個(gè)字母對(duì)中,“ea”的數(shù)量最多;

(3)字母“n”前面80%是元音字母,例如“-on”“-un”“-in”等;

(4)字母“h”經(jīng)常出現(xiàn)在字母“e”前面,幾乎不出現(xiàn)在其后面。

【例2-2】

密碼破解者Eve截獲了一串密文(已知是替換密碼):

oknqdbqmoq{kag_tmhq_xqmdzqp_omqemd_qzodkbfuaz}

其中,每個(gè)字母出現(xiàn)的次數(shù)如下:

顯然,字母“q”出現(xiàn)的頻率最高,因此可以大膽猜測(cè)字母“q”很可能映射的是字母“e”。字母“q”到字母“e”的距離是12,所以猜測(cè)替換密碼的密鑰是12。根據(jù)上述信息進(jìn)行破解,可得到明文:

頻率分析除了可以用來(lái)猜測(cè)明密文的映射關(guān)系,通常還是我們判斷破解后的字符串是否是有語(yǔ)言意義的明文的重要依據(jù)。由于明文一定是一個(gè)完整的有意義的句子,所以它的每個(gè)字母對(duì)應(yīng)頻率相加后的數(shù)值一定是最大的。

因此,在使用暴力破解的時(shí)候,不妨將每一組破解出來(lái)的明文分別按照頻率打分(將破解出來(lái)的明文的每個(gè)字母頻率相加),那么分?jǐn)?shù)最高的明文分組就是我們想要的真正明文了。以下給出了計(jì)分函數(shù)和對(duì)應(yīng)的自動(dòng)判斷凱撒密碼密鑰的Python代碼實(shí)現(xiàn):

2.卡方統(tǒng)計(jì)(Chi-squaredStatistics)分析

卡方統(tǒng)計(jì)量是指數(shù)據(jù)的概率分布與所選擇的預(yù)期或假設(shè)分布之間差異的度量,由英國(guó)統(tǒng)計(jì)學(xué)家Pearson在1900年提出。如果兩種分布相同,那么其卡方統(tǒng)計(jì)量就等于零;否則,兩種分布差異越大,其卡方統(tǒng)計(jì)量也越大?？ǚ浇y(tǒng)計(jì)量的計(jì)算公式如下:

其中,Ci

表示某個(gè)字母(a~z)出現(xiàn)的次數(shù),注意不是概率;Ei

表示某個(gè)字母期望(或者理論上應(yīng)該)出現(xiàn)的次數(shù)。

假設(shè)有密文是采用凱撒密碼加密的,密文如下:

按照卡方統(tǒng)計(jì)量的計(jì)算公式,需要計(jì)算兩個(gè)統(tǒng)計(jì)量。一個(gè)是每個(gè)字母應(yīng)該出現(xiàn)的理論次數(shù),這可以利用英文字母的理論出現(xiàn)頻率乘以上述密文長(zhǎng)度來(lái)得到。例如,對(duì)于字母“a”,其出現(xiàn)概率是0.082,上述密文長(zhǎng)度為162個(gè)字符,因此期望字母“a”出現(xiàn)的次數(shù)就是162×0.082=13.284次。另一個(gè)是每個(gè)字母的實(shí)際出現(xiàn)次數(shù),通過(guò)對(duì)上述密文中每個(gè)字母的計(jì)數(shù)就可以得到。

例如,上述密文中字母“a”出現(xiàn)了18次,因此對(duì)于字母“a”,其對(duì)應(yīng)的卡方統(tǒng)計(jì)量是:

對(duì)所有的26個(gè)字母重復(fù)上述過(guò)程,就可以得到最終的該字符串所對(duì)應(yīng)的卡方統(tǒng)計(jì)量,大約等于1634.09。為了找到正確的解密密鑰,逐一使用每個(gè)密鑰對(duì)密文進(jìn)行解密,然后對(duì)解密得到的明文計(jì)算卡方統(tǒng)計(jì)量,最小值對(duì)應(yīng)的密鑰應(yīng)該就是真正的密鑰。以下是上述密文的計(jì)算過(guò)程,如圖2.5所示。

圖2.5卡方統(tǒng)計(jì)量用于密碼分析

2.2多表替換密碼

2.2.1Vigenere密碼維吉尼亞(Vigenere)密碼是對(duì)關(guān)鍵詞密碼的升級(jí),其核心就是所謂的多個(gè)替換表。在前面的單表替換中,明文字母和密文字母之間的映射是固定的,例如,“A”永遠(yuǎn)被替換成“D”;但是,在維吉尼亞密碼中,字母“A”可能被替換成其他任何一個(gè)字母,具體替換成哪個(gè)字母,取決于密鑰。

【例2-3】

有

密

鑰

關(guān)

鍵

詞“THINK”,明

文“THISISTHEPLAINTEXT”,那

么密鑰-明文關(guān)系如圖2.6所示。

由圖2.6可知,同是明文中的字母“T”,會(huì)和不同的密鑰字母進(jìn)行替換。例如,第一個(gè)明文字母T與密鑰字母“T”配對(duì),而第七個(gè)明文字母“T”則與密鑰字母“H”配對(duì)。另外,由于密鑰長(zhǎng)度一般都比明文短,因此密鑰會(huì)被重復(fù)使用。

圖2.6關(guān)鍵詞的密鑰-明文關(guān)系

建立密鑰與明文對(duì)之間的映射關(guān)系需要維吉尼亞表,如圖2.7所示。圖2.7Vigenere表

維吉尼亞表的映射關(guān)系:密鑰字母確定表的行,明文字母確定表的列。例如,當(dāng)密鑰字母為“H”,明文字母為“T”時(shí),對(duì)應(yīng)的密文輸出為“A”。通過(guò)查詢維吉尼亞表,可得到圖2.6所對(duì)應(yīng)的明文和密鑰對(duì)應(yīng)的密文,如圖2.8所示。

圖2.8Vigenere加密示例

維吉尼亞密碼加密方式對(duì)應(yīng)的數(shù)學(xué)描述如下。

·替換表:π=π-π2…πd;

·密鑰:k=(k1k2…kd)∈Zdq;

·加密:ci+nd=Eki(mi+nd)=mi+nd

+kimodq。

其中,d

是密鑰長(zhǎng)度,明文m

按照密鑰長(zhǎng)度d

進(jìn)行分組,n

為分組數(shù)-1,密鑰中的每個(gè)字母ki（i=1,…,d

確定對(duì)應(yīng)的替換表πi,就是第i+nd

個(gè)明文字母的偏移。

Vigenere密碼的Python實(shí)現(xiàn)代碼如下:

2.2.2希爾密碼

希爾(Hill)密碼是一種基于矩陣運(yùn)算的替換密碼,由LesterS.Hill在1929年發(fā)明。希爾密碼同樣將每個(gè)字

母

按

照

字

母

順

序

轉(zhuǎn)

換

為0~25之

間

的

數(shù)字:“A”=0,“B”=1,

“C”=2,…,然后將明文用n

維向量來(lái)表示,再將這個(gè)n

維向量與n×n

的加密矩陣相乘,對(duì)計(jì)算結(jié)果進(jìn)行模26運(yùn)算后輸出密文向量。

Hill密碼加解密方式對(duì)應(yīng)的數(shù)學(xué)描述如下。

·明文分組:m=(m1,m2,…,mL)T;

·加密:c≡Kmmodq;

·解密:m≡K-1cmodq。

其中,K

是L×L

階滿秩矩陣,L是每個(gè)明文分組的長(zhǎng)度。當(dāng)K

是單位方陣時(shí),Hill密碼就退化為Vigenere密碼。值得注意的是,用來(lái)加密的矩陣K

并不是隨意選取的,它需要滿足GCD(|K|,26)=1的條件。接下來(lái)通過(guò)實(shí)例進(jìn)一步理解Hill密碼加解密的過(guò)程。

1.加密過(guò)程

【例2-4】

指定明文“cat”,分組長(zhǎng)度為3,明文按照字母表順序編號(hào)為(2,0,19),計(jì)算希爾加密密文。

建立明文向量:

設(shè)置加密矩陣K

為

檢驗(yàn)加密矩陣是否可逆,即

加密過(guò)程:

所以,得到的密文是“fin”。

2.解密過(guò)程

先根據(jù)加密矩陣求逆矩陣:

將逆矩陣與密文相乘:

通過(guò)以上方式解密便得到明文“cat”。

2.2.3PlayFair密碼

PlayFair密碼是一種一次替換兩個(gè)字母(Digram)的密碼,其加密算法如下。

(1)選取一個(gè)關(guān)鍵詞作密鑰,除去重復(fù)出現(xiàn)的字母后,依次將密鑰的字母填入5×5的矩陣內(nèi),然后在剩下的矩陣單元中依A~Z的順序加入尚未出現(xiàn)過(guò)的英文字母。由于5×5的矩陣只能容納25個(gè)字母,可以將字母“Q”去除,或?qū)⒆帜浮癐”和字母“J”視為同一字母。

(2)把要加密的明文分隔為兩個(gè)字母一組。若組內(nèi)的字母相同,將字母“X”(或“Q”)插入兩字母之間,重新分組(例如,HELLO將分成HELXLO)。若最后只剩下一個(gè)字母,可以補(bǔ)一個(gè)字母“X”。

(3)針對(duì)每一組的兩個(gè)字母,按照以下規(guī)則找到對(duì)應(yīng)的替換密文字母:

·若兩個(gè)字母在矩陣中的同一行,分別取這兩個(gè)字母右側(cè)的字母(若字母在最右側(cè),則取該行最左側(cè)的字母);

·若兩個(gè)字母在矩陣中的同一列,分別取這兩個(gè)字母下方的字母(若字母在最下方,則取該列最上方的字母);

·若兩個(gè)字母不在同一行或同一列,則應(yīng)在矩陣中找出另外兩個(gè)對(duì)角字母,使這四個(gè)字母組成一個(gè)長(zhǎng)方形的四個(gè)角。

取關(guān)鍵詞密鑰為“playfairexample”,得加密矩陣,如圖2.9所示,其中上面兩行是密鑰去重以后的結(jié)果。圖2.9PlayFair加密矩陣

2.2.4多表替換密碼分析

維吉尼亞這類多表密碼的分析重點(diǎn)在于確定加密密鑰的長(zhǎng)度,一旦確定密鑰長(zhǎng)度,就可以利用加密時(shí)密鑰重復(fù)使用這一特性,把多表密碼分析問(wèn)題降為單表密碼分析問(wèn)題。密鑰長(zhǎng)度確定主要有兩種方法,分別是卡西斯基(Kasiski)方法和重合指數(shù)方法。

1.Kasiski方法

該方法的原理基于密鑰的重復(fù)部分和明文中的重復(fù)部分進(jìn)行加密運(yùn)算導(dǎo)致密文中也會(huì)產(chǎn)生重復(fù)的部分,如圖2.10所示。

圖2.10Kasiski方法原理

考慮

明

文

字

符

串“CRYPTOISSHORTFORCRYPTOGRAPHY”以及加密密鑰“ABCD”,按照維吉尼亞加密算法,加密結(jié)果如圖2.11所示。圖2.11維吉尼亞加密

Kasiski方法的整個(gè)計(jì)算過(guò)程如下:

(1)找出密文中所有重復(fù)出現(xiàn)的字符串;

(2)計(jì)算相同字符串之間的距離;

(3)找出上述距離的公因子;

(4)上述公因子有可能就是密鑰的長(zhǎng)度。

2.重合指數(shù)方法

重合指數(shù)(IndexofCoincidence)是另一種估計(jì)密鑰長(zhǎng)度的方法,它是各個(gè)字母頻數(shù)分布平坦(凹凸)程度的度量(MeasureofRoughness,MR)。對(duì)于標(biāo)準(zhǔn)英語(yǔ)的各個(gè)字母頻數(shù)分布,我們前面已經(jīng)看到是凹凸不平的,或者說(shuō)有高峰有低谷,而經(jīng)過(guò)類似多表加密以后的密文字符分布,則可能要平滑得多,甚至是均勻分布的。

由MR的定義,對(duì)于平坦分布,所有的字母有相同的概率,那就是1/26(大

約0.0385)。那么,每個(gè)字母出現(xiàn)的概率與平坦分布下的概率差為pi-(1/26)。例如,對(duì)于字母“E”,其概率之差為pE-(1/26)=0.127-0.0385=0.0885。所有字母的概率差平方和為

由于每個(gè)字母的概率相比1/26有正有負(fù),因此上式可采用平方來(lái)計(jì)算MR。展開(kāi)上式得到MR計(jì)算公式如下:

【例2-5】

根據(jù)不同加密算法的IC取值范圍,考慮以下明文:

各個(gè)字母的頻數(shù)如圖2.12所示。

根據(jù)IC計(jì)算公式可以得到其重合指數(shù)為0.068101,其中出現(xiàn)次數(shù)最多的六個(gè)字母依次是“ETIOAS”,該重合指數(shù)值接近理想的英語(yǔ)統(tǒng)計(jì)結(jié)果0.0686。

圖2.12明文字母頻數(shù)統(tǒng)計(jì)

接下來(lái)對(duì)上述明文進(jìn)行凱撒加密(密鑰=3),得到的密文如下:

上述密文中各個(gè)字母對(duì)應(yīng)的頻數(shù)如圖2.13所示。

圖2.13凱撒密文字母頻數(shù)統(tǒng)計(jì)

比較圖2.12和圖2.13,可以發(fā)現(xiàn)凱撒加密后的密文字符統(tǒng)計(jì)是明文字符的統(tǒng)計(jì)移位三個(gè)位置的結(jié)果。上述結(jié)果可以從加密公式b=(a+k)mod26得到印證,字母“a”出現(xiàn)的次數(shù)和對(duì)應(yīng)的字母“b”出現(xiàn)的次數(shù)相同。顯然根據(jù)圖2.13的統(tǒng)計(jì)計(jì)算得到的IC值也和明文的相同,等于0.068101。

最后,對(duì)明文進(jìn)行維吉尼亞加密,并同樣統(tǒng)計(jì)密文中各個(gè)字母的出現(xiàn)次數(shù),如圖2.14所示。

圖2.14凱撒密文字母頻數(shù)統(tǒng)計(jì)

根據(jù)上述各個(gè)字母的統(tǒng)計(jì)情況得到其IC值為0.041989。根據(jù)上述明文字符串、凱撒密文字符串和維吉尼亞密文字符串的IC值,大致可以得到IC值和密鑰長(zhǎng)度的關(guān)系,如表2.1所示。

另外,由于隨機(jī)字符串的ICRandom=0.038466是最小的,或者說(shuō)IC值越小則可以認(rèn)為測(cè)試的字符串越隨機(jī)。而標(biāo)準(zhǔn)英文字符串ICEnglish=0.0686,也就是說(shuō)IC值越接近ICEnglish,測(cè)試字符串越有可能是標(biāo)準(zhǔn)的英文文本。

假設(shè)監(jiān)聽(tīng)者Eve截獲了以下密文消息:

Eve可以假設(shè)密鑰長(zhǎng)度為7,則可以把密文按列編寫(xiě)如下:

然后Eve單獨(dú)提取每列字符串,計(jì)算其IC值。如果密鑰大小恰好與假定的列數(shù)相同,Eve計(jì)算每

列

的

重

合

指

數(shù),它

應(yīng)

該

在0.067左

右;如

果

說(shuō)

選

錯(cuò)

了

列

數(shù),其

重

合

指

數(shù)

應(yīng)

該

在0.0385左右。利用這個(gè)特性,Eve可以較好地在IC值和密鑰長(zhǎng)度之間建立聯(lián)系,準(zhǔn)確地獲取維吉尼亞密鑰的長(zhǎng)度。

一旦確定維吉尼亞密碼的密鑰長(zhǎng)度,那么破解維吉尼亞密碼就簡(jiǎn)化為單表替換密碼分析問(wèn)題,可以使用前述的暴力破解或者頻率分析方法進(jìn)行破解。

2.3置

換

密

碼

2.3.1柵欄密碼假如Alice想把明文“thisisatest”發(fā)送給Bob,可通過(guò)柵欄密碼對(duì)明文進(jìn)行加密,如圖2.15所示。明文字母被安排在鋸齒形的圖案中,尺寸是3,讀寫(xiě)方向是按行讀取。由此得出的密文是“tiehsstsiat”。Bob獲得密文后,按照相同的圖案和讀寫(xiě)方向便可以恢復(fù)明文。

圖2.15柵欄(RailFence)密碼

2.3.2列置換方法

把明文分割為一定長(zhǎng)度的分組,長(zhǎng)度等于d。定義一種置換1到d

的整數(shù)的方法F,然后按照方法F

對(duì)每個(gè)分組進(jìn)行置換,此時(shí)的密鑰就是(d,F)。

舉例:將明文字母