第2章古典密碼技術(shù)1

第1章密碼學(xué)概述 第2章傳統(tǒng)密碼技術(shù)

第3章分組密碼第4章公鑰密碼體制第5章散列函數(shù)與消息鑒別第6章數(shù)字簽名技術(shù)第7章密鑰管理技術(shù)第8章身份鑒別技術(shù)第9章序列密碼第10章密碼技術(shù)應(yīng)用附錄課程主要內(nèi)容第2章傳統(tǒng)密碼技術(shù)

本章主要內(nèi)容替代密碼

置換密碼轉(zhuǎn)輪機密碼

古典密碼的統(tǒng)計分析

單表替代密碼分析多表替代密碼分析

第2章傳統(tǒng)密碼技術(shù)2.1替代密碼(代換密碼）替代是古典密碼中用到的最基本的處理技巧之一

；代換：將明文字母替換為其他字母，數(shù)字或符號。如果把明文看成是二進制的序列的話，那么代換就是用密文位串來替代明文位串。單表替代：用一個替代表決定代換規(guī)則單字母替代：明文的一個字符用相應(yīng)的一個密文字符代替，如Caesar密碼多字母替代：明文中的字符映射到密文空間的字符還依賴于他在上下文中的位置，如Hill密碼，Playfair密碼多表替代：代換規(guī)則由多個代換表組成周期：如維吉尼亞（Vigenere）密碼，轉(zhuǎn)子機（rotorMachine）非周期：一次一密（Onetimepadding)第2章傳統(tǒng)密碼技術(shù)第2章傳統(tǒng)密碼技術(shù)2.1.1單表替代密碼 單表替代密碼對明文中的所有字母都使用一個固定的映射（明文字母表到密文字母表）。設(shè)A＝{a0,a1,…,an-1}為包含了n個字母的明文字母表；

B＝{b0,b1,…,bn-1}為包含n個字母的密文字母表，單表替代密碼使用了A到B的映射關(guān)系：

f：A→B，f(ai)＝bj

一般情況下，f

是一一映射，以保證加密的可逆性。

加密變換過程就是將明文中的每一個字母替換為密文字母表的一個字母。而單表替代密碼的密鑰就是映射f或密文字母表。

下面給出幾種典型的單表替代密碼。第2章傳統(tǒng)密碼技術(shù)一般單表替代密碼 明文空間M和密文空間C都是26個英文字母的集合，密鑰空間

K={π：Z26→Z26|π是置換}，是所有可能置換的集合。對任意π∈K，定義:

加密變換：eπ(m)=π(m)=c

解密變換：dπ(c)=π-1(c)=m，

π-1是π的逆置換。

【例2.1】設(shè)置換π的對應(yīng)關(guān)系如下：abcdefghijklmnopqrstuvwxyzqwertyuiopasdfghjklzxcvbnm

試用單表替代密碼以π為密鑰對明文消息message加密，然后寫出逆置換，并對密文解密。解：以π為密鑰用單表替代密碼對明文消息message加密，所得密文消息為：π(m)π(e)π(s)π(s)π(a)π(g)π(e)=dtllqut

2.1.1單表替代密碼（續(xù)）π第2章傳統(tǒng)密碼技術(shù)

一般單表替代密碼算法特點：密鑰空間K很大，|K|=26!=4×1026，破譯者窮舉搜索計算不可行，1微秒試一個密鑰，遍歷全部密鑰需要1013

年。移位密碼體制是替換密碼體制的一個特例，它僅含26個置換做為密鑰空間。密鑰π不便記憶。針對一般替換密碼密鑰π不便記憶的問題，又衍生出了各種形式單表替代密碼。移位密碼

把26個英文字母與整數(shù)0，1，2，…，25一一對應(yīng)，如表2.1所示。

2.1.1單表替代密碼（續(xù)）表2.1字母數(shù)字映射表第2章傳統(tǒng)密碼技術(shù)加密變換，E={E:Z26→Z26,Ek(m)=m+k(mod26)|

m∈M,k∈K}解密變換，D={D:Z26→Z26,Dk(c)=c－k(mod26)|

c∈C,k∈K}

解密后再把Z26中的元素轉(zhuǎn)換成英文字母。

顯然，移位密碼是前面一般單表替代密碼的一個特例。當(dāng)移位密碼的密鑰k=3時，就是歷史上著名的凱撒密碼（Caesar）。根據(jù)其加密函數(shù)特點，移位密碼也稱為加法密碼。2.1.1單表替代密碼（續(xù)）愷撒密碼

字母表：(密碼本）密文：ABCDEFGHIJKLMNOPQRSTUVWXYZ明文：xyzabcdefghijklmnopqrstuvw

i：0123456789……..加密算法：C=E（p）=（p+3）mod（26）解密算法：P=D（C）=（C-3）mod（26）破譯以下密文：密文：PHHWPHDIWHOWKHSDUWB明文：meetmeaftertheparty 第2章傳統(tǒng)密碼技術(shù)2.1.1單表替代密碼（續(xù)）K=3第2章傳統(tǒng)密碼技術(shù)2.1.1單表替代密碼（續(xù)）是替換密碼的一個特例加密函數(shù)的形式為：

K={(k1，k2)|k1，k2∈Z26，gcd(k1，26)=1}

對任意m∈M，c∈C，k=(k1，k2)∈K，加密變換為：c=Ek(m)=k1m+k2(mod26)解密變換為：

m=Dk(c)=k1－1(c－k2)(mod26)仿射密碼第2章傳統(tǒng)密碼技術(shù)【例2.3】設(shè)明文消息為china，密鑰試用仿射密碼對其進行加密，然后再進行解密。解：利用擴展的歐幾里德算法（參見附錄A.1.2）可計算出

加密變換為：

解密變換為：

明文消息對應(yīng)的數(shù)字依次為2，7，8，13，0，用仿射密碼對明文進行加密如下：

2.1.1單表替代密碼（續(xù)）第2章傳統(tǒng)密碼技術(shù)密文消息為unwpc。而解密過程如下：

即恢復(fù)明文消息為china。

仿射密碼要求gcd(k1,26)=1，否則就會有多個明文字母對應(yīng)一個密文字母的情況。由于與26互素的整數(shù)有12個，故仿射密碼密鑰空間大小為|K|=12×26=312。

若將仿射密碼的加密函數(shù)換為多項式函數(shù)時，即為多項式密碼。密鑰短語密碼

選用一個英文短語或單詞串作為密鑰，去掉其中重復(fù)的字母得到一個無重復(fù)字母的字符串，然后再將字母表中的其它字母依次寫于此字母串后，就可構(gòu)造出一個字母替代表。如密鑰為key時，替代表如表2.2所示。2.1.1單表替代密碼（續(xù)）第2章傳統(tǒng)密碼技術(shù)

表2.2密鑰為key的單表替代密碼

當(dāng)選擇上面的密鑰進行加密時，若明文為“china”，則密文為“yfgmk”。顯然，不同的密鑰可以得到不同的替換表。2.1.2多表替代密碼單表替代密碼表現(xiàn)出明文中單字母出現(xiàn)的頻率分布與密文中相同，多表替代密碼使用從明文字母到密文字母的多個映射來隱藏單字母 出現(xiàn)的頻率分布，每個映射是簡單替代密碼中的一對一映射,多表替 代密碼將明文字母劃分為長度相同的消息單元，稱為明文分組，對 明文成組地進行替代，同一個字母有不同的密文，改變了單表替代 密碼中密文的唯一性，使密碼分析更加困難。

第2章傳統(tǒng)密碼技術(shù)多表替代密碼的特點是使用了兩個或兩個以上的替代表。著名的維吉尼亞密碼和Hill密碼等均是多表替代密碼。1.維吉尼亞密碼維吉尼亞密碼是最古老而且最著名的多表替代密碼體制之一，與位移密碼體制相似，但維吉尼亞密碼的密鑰是動態(tài)周期變化的。該密碼體制有一個參數(shù)n。在加解密時，同樣把英文字母映射為0－25的數(shù)字再進行運算，并按n個字母一組進行變換。明文空間、密文空間及密鑰空間都是長度為n的英文字母串的集合，因此可表示

加密變換定義如下：設(shè)密鑰k=(k1,k2,…,kn),明文m=(m1,m2,…,mn),加密變換為：

其中ci=(mi+ki)(mod26)，i=1,2,…,n

Ek(m)=(c1,c2,…,cn),對密文c=(c1,c2,…,cn),解密變換為：

Dk(c)=(m1,m2,…,mn),其中mi=(ci

－ki)(mod26)，i=1,2,…,n2.1.2多表替代密碼（續(xù)）第2章傳統(tǒng)密碼技術(shù)【例2.4】設(shè)密鑰k=cipher，明文消息appliedcryptosystem，試用維吉尼亞密碼對其進行加密，然后再進行解密。解：由密鑰k=cipher，得n=6，密鑰對應(yīng)的數(shù)字序列為(2，8，15，7，4，17)。然后將明文按每6個字母進行分組，并轉(zhuǎn)換這些明文字母為相應(yīng)的數(shù)字，再用模26加上對應(yīng)密鑰數(shù)字，其加密過程如表2.3所示。

表2.3密鑰為cipher的維吉尼亞密碼加密過程

密文為：cxtsmvfkgftkqanzxvo。解密使用相同的密鑰，但用模26的減法代替模26加法，這里不再贅述。2.1.2多表替代密碼（續(xù)）第2章傳統(tǒng)密碼技術(shù)

置換密碼又稱為換位密碼；置換密碼通過改變明文消息各元素的相對位置，但明文消息元素本身的取值或內(nèi)容形式不變；在前面的替代密碼中，則可以認(rèn)為是保持明文的符號順序，但是將它們用其它符號來替代；置換密碼是把明文中各字符的位置次序重新排列來得到密文的一種密碼體制。下面再給出幾種典型的置換密碼算法。2.2置換密碼(PermutationCipher)第2章傳統(tǒng)密碼技術(shù)2.2置換密碼最簡單的例子是柵欄技術(shù)：明文：meetmeaftertheparty寫為：mematrhpryetefeteat密文：mematrhpry

etefeteat第2章傳統(tǒng)密碼技術(shù)2.2置換密碼

列置換密碼把消息一行一行的寫出，然后按列讀取，但把列的次序打亂，列的次序就是密鑰；密鑰：

4312567明文：

attackpostponeduntiltwoamxyz密文：ttnaaptmtsuoaodwcoixknlypetz第2章傳統(tǒng)密碼技術(shù)2.2置換密碼例：設(shè)m=6，設(shè)置密鑰置換：加密的密鑰置換解密的密鑰置換123456351642K=123456361524K-1=明文組中的第5個字符與第4個字符進行置換對明文cryptography進行加密，首先將明文分成6個字母長的明文組：crypto|graphy；然后將每個明文組按密鑰置換K重新排列：加密的密鑰置換123456351642K=cryptoytcopr（crypto）K=graphyahgypr（graphy）K==YTCOPR=AHGYPR第2章傳統(tǒng)密碼技術(shù)2.2置換密碼用編號表示內(nèi)部引線的三轉(zhuǎn)輪機(a)初始情況 （b）經(jīng)過一次按鍵后的情況第2章傳統(tǒng)密碼技術(shù)2.3轉(zhuǎn)輪機第2章傳統(tǒng)密碼技術(shù)2.4傳統(tǒng)密碼的統(tǒng)計分析在對密碼進行安全分析時，一般假設(shè)密碼分析者知道密碼體制，這就是Kerckhoffs假設(shè)，密碼分析重點在獲取密鑰。移位密碼、仿射密碼、維吉尼亞密碼、置換密碼等對己知明文攻擊都是非常脆弱的。即使用惟密文攻擊，大多數(shù)古典密碼體制都容易被攻破。大多數(shù)古典密碼體制都不能很好隱藏明文消息的統(tǒng)汁特征。下面就針對單表替代密碼、多表替代密碼和Hill密碼來介紹利用英文語言的統(tǒng)計特征和密碼特點，運用惟密文攻擊或已知明文攻擊等方式破譯古典密碼的基本方法。第2章傳統(tǒng)密碼技術(shù)2.4.1單表替代密碼分析

本質(zhì)上，密文字母表是明文字母表的一種排列。但企圖使用計算機窮舉一切密鑰來破譯密鑰詞組替代密碼也是計算不可行的。窮舉不是攻擊密碼的惟一方法，密碼分析者便可利用語言的統(tǒng)計特性進行分析。如果明文語言的這種統(tǒng)計特性在明文中有所反映，密碼分析者便可通過分析明文和密文的統(tǒng)計規(guī)律而破譯密碼。通過對大量英文語言的研究可以發(fā)現(xiàn)，每個字母出現(xiàn)的頻率不一樣，e出現(xiàn)的頻率最高。如果所統(tǒng)計的文獻足夠長，便可發(fā)現(xiàn)各字母出現(xiàn)的頻率比較穩(wěn)定。如表2.4所示（表中字母出現(xiàn)頻率為字母出現(xiàn)次數(shù)除以文本字母總數(shù)）。第2章傳統(tǒng)密碼技術(shù)表2.426個英文字母出現(xiàn)頻率統(tǒng)計表

2.4.1單表替代密碼分析（續(xù)）字母出現(xiàn)頻率字母出現(xiàn)頻率a0.0856n0.0707b0.0139o0.0797c0.0279p0.0199d0.0378q0.0012e0.1304r0.0677f0.0289s0.0607g0.0199t0.1045h0.0528u0.0249i0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m