網(wǎng)絡(luò)安全與保密（第二版）課件：對(duì)稱密碼學(xué)

對(duì)稱密碼學(xué)2.1密碼系統(tǒng)模型2.2古典密碼2.3數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)2.4高級(jí)加密標(biāo)準(zhǔn)(AES)2.5流密碼算法參考文獻(xiàn)思考題

密碼學(xué)是研究數(shù)據(jù)加密、解密以及認(rèn)證的學(xué)科，它包括密碼編碼學(xué)和密碼分析學(xué)兩部分。本章首先介紹密碼學(xué)的一些基礎(chǔ)知識(shí)和幾種古典密碼術(shù)，然后對(duì)現(xiàn)代對(duì)稱密碼算法進(jìn)行討論。

2.1密碼系統(tǒng)模型

在1976年Diffie及Hellman發(fā)表其論文“NewDirectionsinCryptography”[1]之前，所謂的密碼學(xué)就是指對(duì)稱密鑰密碼系統(tǒng)。因?yàn)榧用?解密用的是同一把密鑰，所以也稱為單一密鑰密碼系統(tǒng)。這類算法可謂歷史悠久，從最早的凱撒密碼到目前使用最多的DES密碼算法，以及2000年美國(guó)推出的下一代密碼算法AES[/archive/aes/index.html]都屬于此類密碼系統(tǒng)。

通常一個(gè)密鑰加密系統(tǒng)包括以下幾個(gè)部分：

(1)消息空間M(Message)；

(2)密文空間C(Ciphertext)；

(3)密鑰空間K(Key)；

(4)加密算法E(Encryptionalgorithm)；

(5)解密算法D(Decryptionalgorithm)。

消息空間中的消息M(稱之為明文)通過(guò)由加密密鑰K1控制的加密算法加密后得到密文C。密文C通過(guò)解密密鑰K2控制的解密算法又可恢復(fù)出原始明文M。即：

EK1(M)?=?C

DK2(C)?=?M

DK2(EK1(M))?=?M

在圖2-1的加/解密系統(tǒng)模型中，當(dāng)算法的加密密鑰能夠從解密密鑰中推算出來(lái)，或反之，解密密鑰可以從加密密鑰中推算出來(lái)時(shí)，稱此算法為對(duì)稱算法，也稱秘密密鑰算法或單密鑰算法。稱加密密鑰和解密密鑰不同并且其中一個(gè)密鑰不能通過(guò)另一個(gè)密鑰推算出來(lái)的算法為公開密鑰算法。

在現(xiàn)代密碼學(xué)中，所有算法的安全性都要求是基于密鑰的安全性，而不是基于算法細(xì)節(jié)的安全性。也就是說(shuō)，只要密鑰不公開，即使算法公開并被分析，不知道密鑰的人也無(wú)法理解你所加密過(guò)的消息。圖2-1密鑰加/解密系統(tǒng)模型

2.2古典密碼

在計(jì)算機(jī)出現(xiàn)之前，密碼學(xué)由基于字符的密碼算法構(gòu)成。不同的密碼算法之間互相替代(Substitution)或相互置換(Transposition)，好的密碼算法是結(jié)合這兩種方法，每次進(jìn)行多次運(yùn)算?，F(xiàn)在的計(jì)算機(jī)密碼算法要復(fù)雜的多，但基本原理沒有變化。其重要的變化是算法只對(duì)位而不是字母進(jìn)行變換，也就是字母表長(zhǎng)度從26個(gè)字母變?yōu)?個(gè)字母。大多數(shù)好的密碼算法仍然是以替代和置換作為加密技術(shù)的基本構(gòu)造塊。

2.2.1替代密碼

替代密碼就是明文中的每一個(gè)字符被替換為密文中的另外一個(gè)字符。接收者對(duì)密文進(jìn)行逆替換即可恢復(fù)出明文。在古典密碼學(xué)中有三種類型的替代密碼：?jiǎn)伪硖娲艽a、多表替代密碼和多字母替代密碼。

1．單表替代密碼

所謂的單表替代密碼(Monoalphabetic)就是明文的每一個(gè)字符用相應(yīng)的另外一個(gè)唯一的密文字符代替。最早的密碼系統(tǒng)“凱撒密碼”就是一種單表替代密碼，也是一種移位替代密碼。凱撒密碼是對(duì)英文的26個(gè)字母分別向前移3位，于是可以得到其替代表為明文：abcdefghijklmnopqrstuvwxyz密文：DEFGHIJKLMNOPQRSTUVWXYZABC

例2.1對(duì)明文

顯然，這種密碼系統(tǒng)是不安全的，它非常容易攻破。首先，簡(jiǎn)單的單表替代沒有掩蓋明文不同字母出現(xiàn)的頻率；其次，移位替代的密鑰空間有限，只有25個(gè)密鑰，利用暴力攻擊法很容易破解。因此，替代密碼應(yīng)該有更大的密鑰空間，關(guān)鍵詞(Keyword)密碼就是這樣一種加密方法。

2．關(guān)鍵詞(Keyword)密碼

關(guān)鍵詞加密方法包含兩個(gè)步驟：

(1)選擇一個(gè)關(guān)鍵詞，如果關(guān)鍵詞中包含有重復(fù)的字母，則后續(xù)出現(xiàn)的該字母一律刪除。例如，對(duì)于關(guān)鍵詞“xidian”，則最終使用的詞是“xidan”。

(2)將關(guān)鍵詞寫在字母表的下方，剩下的空間用其余的字母按照字母順序進(jìn)行填寫。

例2.2對(duì)于關(guān)鍵詞“KRYPTOS”，其明文和密文對(duì)照表如下

對(duì)消息“cryptographyiscool”的加密結(jié)果如下

明文：CRYPTOGRAPHYISCOOL

密文：YLXINHSLKIAXBMYHHE

關(guān)鍵詞加密方法的最大安全缺陷在于其很容易受到頻率分析攻擊。明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文：KRYPTOSABCDEFGHIJLMNQUVWXZ

在密碼學(xué)中，所謂的頻率分析是指字母或者字母組合在密文中出現(xiàn)的頻率。許多的古典密碼都可以用這種方法進(jìn)行破解。

頻率分析是基于這樣一個(gè)事實(shí)：在任何一種書面語(yǔ)言中，不同的字母或字母組合出現(xiàn)的頻率各不相同。而且，對(duì)于以這種語(yǔ)言書寫的任意一段文本，都具有大致相同的字母分布特征。比如，在英語(yǔ)中，字母E出現(xiàn)的頻率很高，而X則出現(xiàn)得較少，如圖2-2所示。類似地，ST、NG、TH，以及QU等雙字母組合出現(xiàn)的頻率非常高，NZ、QJ組合則極少。英語(yǔ)中出現(xiàn)頻率最高的12個(gè)字母可以簡(jiǎn)記為“ETAOINSHRDLU”。圖2-2英文字母出現(xiàn)頻率統(tǒng)計(jì)

有了這些信息，我們?cè)倩仡^看看關(guān)鍵詞加密方法的破解：

(1)首先關(guān)鍵詞加密法仍屬于單表替代密碼，這也就意味著，盡管明文中的某個(gè)字母被替換成密文中的某個(gè)字母，但是其統(tǒng)計(jì)頻率并未改變。因此，通過(guò)對(duì)密文中的每個(gè)字母的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)分析，就可以大致判斷明文和密文的對(duì)應(yīng)關(guān)系。例如，密文中出現(xiàn)頻率最高的某個(gè)字母很有可能對(duì)應(yīng)的就是明文字母“E”。

(2)其次可以利用密文的關(guān)鍵詞之后都是按照字母順序排列這一規(guī)律來(lái)進(jìn)一步降低破解難度。

3．仿射加密方法(AffineCipher)

在仿射加密方法中，每個(gè)字母被賦予一個(gè)數(shù)字，例如字母a=0，字母b=1，……，字母z?=?25。加密密鑰為0～25之間的數(shù)字對(duì)(a，b)。

加解密函數(shù)形式分別為

c?=?e(p)?=?(ap?+?b)(mod26)

p?=?d(c)?=?a-1(c?-?b)(mod26)

其中a-1是a的模乘法逆元，也就是滿足

1?=?aa-1modm

模乘法逆元有唯一解的充要條件是a和26(m)的最大公約數(shù)：gcd(a，26)=1。

例2.3下面我們對(duì)明文“AFFINECIPHER”進(jìn)行加密，其中a=5，b=8。整個(gè)加密過(guò)程如下表所示。

由于仿射密碼仍然是一種單表替換密碼，因此它也存在此類密碼所固有的缺陷。前述的頻率分析方法同樣適用。

在考慮加密英文消息時(shí)，m?=?26，此時(shí)總共有286種仿射密碼，其中沒有包含26種簡(jiǎn)單的凱撒密碼。這主要是因?yàn)橥?6互為素?cái)?shù)的數(shù)有12個(gè)，也就是a的取值有12種。每個(gè)a對(duì)應(yīng)的移位取值是26個(gè)，也就是b的值。因此總共有12*26?=?312可能的秘鑰。

該密碼系統(tǒng)的主要弱點(diǎn)在于對(duì)手一旦通過(guò)頻率分析或者蠻力搜索或者猜測(cè)等手段發(fā)現(xiàn)兩個(gè)密文字符所對(duì)應(yīng)的明文字符，他就可以通過(guò)線性解方程得方法來(lái)恢復(fù)秘鑰。而且我們知道a和m必須互為素?cái)?shù)，這也有助于判斷解方程得到的結(jié)果是否正確。

4．多表替代密碼

多表替代密碼是以一系列的(兩個(gè)以上)替代表依次對(duì)明文消息的字母進(jìn)行替代的加密方法。

多表替換加密形式是：其中的每個(gè)明文字母可以被密文中的不同字母來(lái)代替，而每個(gè)密文字母也可以表示多個(gè)明文字母。這種加密法可以干擾字母出現(xiàn)頻率分析法。著名的Vigenere加密法就是其中的一種，它在長(zhǎng)達(dá)三百多年的時(shí)間里都被認(rèn)為是不可破解的。

Vigenere加密過(guò)程如下：

(1)選擇一個(gè)關(guān)鍵詞(例如，“MEC”)。

(2)將關(guān)鍵詞重復(fù)地寫在明文的上方，直至兩者長(zhǎng)度相等。

密文通過(guò)查詢Vigenere表得到。其中關(guān)鍵詞字母確定表的行，明文字母確定表的列，如圖2-3所示。

(3)行與列的交叉處得到對(duì)應(yīng)密文。圖2-3Vigenere替換表

例2.4用關(guān)鍵詞MEC進(jìn)行消息加密。

關(guān)鍵詞 MECMECMECMECMECMECMECM

明文 weneedmoresuppliesfast

密文 IIPQIFYSTQWWBTNUIUREUF

從中，我們可以看到，字母‘e’有時(shí)候被加密成‘I’，有時(shí)候被加密成‘Q’。而且，密文中的Ｉ表示了兩個(gè)不同的明文字母‘w’和‘e’。這種變換特性使得頻率分析方法在此變得無(wú)能為力。顯然，出現(xiàn)頻率很高的字母‘e’被替換成了出現(xiàn)頻率不怎么高的‘I’和‘Q’，而且密文中連續(xù)出現(xiàn)的兩個(gè)相同字母，如‘II’或‘WW’所對(duì)應(yīng)的明文字母并不相同。

當(dāng)然，這并不意味著沒有辦法來(lái)破解Vigenere加密法。幸運(yùn)的是，F(xiàn)rederick

Kasiski通過(guò)觀察發(fā)現(xiàn)：明文中重復(fù)出現(xiàn)的字符串與關(guān)鍵詞密鑰的重復(fù)部分加密會(huì)得到重復(fù)密文字符串，如圖2-4所示。圖2-4Vigenere密碼分析

在上例中，兩次“kiov”之間的距離為9，“nu”之間的距離為6，由此我們可以猜測(cè)這些距離應(yīng)該是密鑰長(zhǎng)度的倍數(shù)，密鑰長(zhǎng)度可能為3。因此密文中重復(fù)字符串之間的距離反映了密鑰重復(fù)的次數(shù)和密鑰的長(zhǎng)度，于是Frederick

Kasiski提出的破解過(guò)程如下：

(1)找出密文中重復(fù)的字符串；

(2)計(jì)算重復(fù)字符串之間的字符數(shù)；

(3)找出從步驟(2)中得到的數(shù)的因子(就是最大公約數(shù))；

(4)該最大公約數(shù)很可能就是關(guān)鍵詞的長(zhǎng)度。

有了關(guān)鍵詞長(zhǎng)度，我們就可以將與關(guān)鍵詞中用同一個(gè)字符替換得到的密文字符集合到一起，這些密文字符的集合就相當(dāng)于一個(gè)單表加密所得到的密文。這樣就可以采用前面提到的頻率分析方法進(jìn)行密碼破解了。對(duì)于上面的例子，把密鑰run中的r字符所對(duì)應(yīng)的密文整合在一起，即kvekvrjvvz…，它們都是由同一個(gè)密鑰加密得到的移位加密密文。所以，一旦得到關(guān)鍵字長(zhǎng)度，破解Vigenere加密法就變成了破解n(關(guān)鍵字長(zhǎng)度為n)個(gè)不同的單表加密問(wèn)題。

對(duì)于關(guān)鍵詞長(zhǎng)度的計(jì)算，美國(guó)密碼學(xué)家William

Friedman提出了基于凹凸度量(MR)的方法。我們知道，英語(yǔ)中每個(gè)字符出現(xiàn)的概率都是不一樣的，繪成頻率分析圖，圖中就有高峰與低谷，單表加密法是沒有辦法改變字母出現(xiàn)的概率的，但是對(duì)于多表加密法，得到的字母頻率圖就變得很平滑。完全平滑的分布就是每個(gè)字母等概率(1/26)出現(xiàn)的情況。凹凸度量是指從文本中選取的字母的實(shí)際概率與從完全平滑的分布中選取該字母的概率之差。

Pa是從密文中選取a字母的概率，那么上述的概率偏差即為(Pa-1/26)2。加平方是為了保證得到的值為正值。Pa為完全偏差，因此a到z所有字母的偏差和為

通過(guò)拆分和取舍，可以將這個(gè)式子簡(jiǎn)化成

對(duì)于某個(gè)密文，如果估算出，那么MR就能確定。由于P2a為從密文中選取字母a的概率，那么就是從全部密文中選取字母的概率和從剩余密文中(即去掉第一個(gè)a字母的密文)中選取字母a的概率的乘積。如果密文中有n個(gè)字母，F(xiàn)a是密文中a字母的個(gè)數(shù)，那么

計(jì)算密文的MR值只依賴于P2a。

由此，WilliamFriedman定義了重合指數(shù)的概念(Index

of

Coincidence，IC)來(lái)分析多表加密法。IC定義為

通過(guò)分析和資料，我們得知單表加密法的IC大概為0.066。完全平滑的文字，其值為0.38，如果IC的值在0.38到0.066之間，就說(shuō)明該密文很可能就是多表加密法。事實(shí)上，通過(guò)圖2-5，我們能得知IC值暗示的多表加密法的密鑰長(zhǎng)度。圖2-5IC值和秘鑰長(zhǎng)度關(guān)系

5．多字母(Polygraphic)替代密碼

多字母替代密碼是每次對(duì)多于1個(gè)字母進(jìn)行替代的加密方法，它的優(yōu)點(diǎn)在于將字母的自然頻度隱蔽或均勻化，從而利于抗統(tǒng)計(jì)分析。

6．Playfair密碼算法

Playfair密碼采用一個(gè)包含密鑰的5?×?5矩陣進(jìn)行加密解密。矩陣首先用去掉重復(fù)字母的密鑰進(jìn)行填充，然后用剩余的字母按照順序進(jìn)行填充。圖2-6給出了密鑰為“playfairexample”的加解密矩陣(注意，I和J被認(rèn)為是同一個(gè)字母)。圖2-6Playfair加解密矩陣

加密消息前，把消息明文按兩個(gè)字母一組進(jìn)行分割，如果這個(gè)兩個(gè)字母相同，則插入一個(gè)空字符，比如‘X’。若明文消息的字母?jìng)€(gè)數(shù)為奇數(shù)時(shí)，將空字母X加在明文的

末端。

對(duì)于每一對(duì)明文m1、m2，其加密規(guī)則如下：

(1)?m1和m2在同一行時(shí)，則密文c1和c2分別是緊靠m1、m2右端的字母。其中第一列看作是最后一列的右方。舉例如下：

(2)若m1和m2在同一列時(shí)，則密文c1和c2分別是緊靠m1、m2下方的字母。其中第一行看作是最后一行的上方。

(3)若m1和m2不在同一行，也不在同一列時(shí)，則密文c1和c2是由m1和m2確定的矩形的其他兩角的字母，并且c1和m1、c2和m2同行。

例2.5首先對(duì)加密消息“Hidethegoldinthetreestump”進(jìn)行預(yù)處理后，得到兩個(gè)字母一組的明文：

HIDETHEGOLDINTHETREXESTUMP

^

通過(guò)利用圖所示的加密矩陣加密后得到的密文如下：

BMODZBXDNABEKUDMUIXMMOUVIF

7．Playfair密碼分析

破解和分析Playfair密碼的第一步就是要確定你所分析的密碼確實(shí)是采用的Playfair加密的。這通?？梢酝ㄟ^(guò)以下特征來(lái)識(shí)別：

(1)密文的字母?jìng)€(gè)數(shù)是偶數(shù)；

(2)原來(lái)在明文中很少出現(xiàn)的一些字母，其在密文中出現(xiàn)的頻率明顯增加；

(3)把密文按照兩個(gè)字母一組進(jìn)行分割，則每組的字母不會(huì)有重復(fù)；

(4)雙圖的頻率分布與明文的頻率分布大致相同。

在具體的密文分析過(guò)程中，可以使用以下特征或者規(guī)則進(jìn)行：

(1)明文中的字母不會(huì)被加密成自己。

(2)明文中逆序的兩個(gè)雙圖加密后的兩個(gè)雙圖同樣也是逆序的。

(3)明文中的每個(gè)字母只能用某5個(gè)字母中的一個(gè)來(lái)加密。

圖2-7給出了Playfair密碼分析的一般過(guò)程。圖2-7playfair密碼分析步驟

2.2.2置換密碼

在置換密碼中，明文和密文的字母保持相同，但順序被打亂了。置換密碼使用的密鑰通常是一些幾何圖形，它決定了明文字母被重新排列的順序和方式。

1．Skytale加密法(天書)

Skytale就是一種加密用的、具有一定粗細(xì)的棍棒或權(quán)杖，如圖2-8所示。

斯巴達(dá)人把皮革或羊皮紙纏繞在特定直徑的木棍上，寫好文字以后再把皮革或羊皮紙解下來(lái)，紙上的字母順序就頓時(shí)歪七扭八，就誰(shuí)也不認(rèn)識(shí)了；只有把皮(紙)帶再一點(diǎn)點(diǎn)卷回與原來(lái)加密的Skytale同樣粗細(xì)的棍棒上后，文字信息逐圈并列在棍棒的表面，才能還原出本來(lái)的意思。圖2-8Skytale天書

實(shí)際上天書就是一種簡(jiǎn)單的縱行置換密碼。明文以固定的寬度水平地寫在一張圖表紙上，密文按垂直方向讀出；解密就是將密文按相同的寬度垂直的寫在圖表紙上，然后水平的讀出明文。

例2.6對(duì)下列明文計(jì)算天書加密結(jié)果

密文：eiffobnsodmlctraeerhmtufyeaanopttirrtrinemiaotaonnodnsosa

在填寫某個(gè)圖表時(shí)，可以采用各種形狀的幾何圖形，如rail-fence(柵欄)加密時(shí)采用對(duì)角線方式寫入，然后按行讀出即可得到密文，如圖2-9所示。圖2-9柵欄密碼

對(duì)應(yīng)的密文如下

WECRLTEERDSOEEFEAOCAIVDEN

圖2-10給出了按照三角形方式填充的加密方法，按列讀取就是對(duì)應(yīng)的密文。圖2-10三角形置換密碼

2．列置換密碼

在列置換密碼中，消息按照固定長(zhǎng)度的行寫入，然后按照某種順序逐列讀出，即可得到密文。行的寬度和列的置換順序由一個(gè)關(guān)鍵詞或者密鑰來(lái)控制。例如，對(duì)于秘鑰“crypto”，總共包含6個(gè)字母，因此加密矩陣有6列。然后秘鑰中各個(gè)字母在字母表中的順序?yàn)椋?、4、6、3、5、2，因此相應(yīng)的列置換順序?yàn)椤?46352”。也就是說(shuō)，密文的第一列仍然是明文矩陣的第一列，而密文的第二列則是明文矩陣的第六列，以此類推。

對(duì)于消息明文“WEAREDISCOVERED.FLEEATONCE.”和密鑰“crypto”，其對(duì)應(yīng)的明文矩陣和置換規(guī)則如圖2-11所示。圖2-11列置換密碼

圖2-11中最后5個(gè)字母稱為空字符，用于填滿矩陣最后一行，這種列置換密碼稱為規(guī)則列置換矩陣。對(duì)于非規(guī)則列置換密碼，矩陣最后一行不進(jìn)行任何填充。

最終的加密結(jié)果為

WIREEDEECUROFOJESEAQEVLNEACDTK

3．置換密碼分析

由于置換密碼并不影響單個(gè)符號(hào)出現(xiàn)的頻率，簡(jiǎn)單的置換可以通過(guò)頻率計(jì)數(shù)進(jìn)行檢測(cè)識(shí)別。如果密文和明文的頻率分布非常接近，那么很有可能該密文是采用置換密碼加密的。置換密碼最容易用文字拼圖游戲進(jìn)行攻擊，也就是不斷交換字母順序，看能不能發(fā)現(xiàn)單詞或者某些短語(yǔ)。這種短語(yǔ)可能泄露某些列置換模式。隨著發(fā)現(xiàn)更多的短語(yǔ)，從而最終找到整個(gè)列置換規(guī)則。

簡(jiǎn)單的置換密碼還容易受到最優(yōu)搜索算法的攻擊，如遺傳算法。因?yàn)殡S著破解出來(lái)的密鑰越來(lái)越接近真實(shí)的密鑰，每一行中合理的，更加接近語(yǔ)法的明文短語(yǔ)越來(lái)越多，越來(lái)越長(zhǎng)，這就為密鑰的搜索提供有用的信息。

2.3數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)

從這一節(jié)開始將介紹幾種對(duì)稱密碼系統(tǒng)。首先介紹一種最通用的計(jì)算機(jī)加密算法—數(shù)據(jù)加密標(biāo)準(zhǔn)DES(DataEncryptionStandard)。

2.3.1分組密碼簡(jiǎn)介

對(duì)稱密碼算法有兩種類型：分組密碼(BlockCipher)和流密碼(StreamCipher)。分組密碼一次處理一塊輸入，每個(gè)輸入塊生成一個(gè)輸出塊，而流密碼對(duì)輸入元素進(jìn)行連續(xù)處理，同時(shí)產(chǎn)生連續(xù)單個(gè)輸出元素。數(shù)據(jù)加密標(biāo)準(zhǔn)DES屬于分組密碼。分組密碼將明文消息劃分成固定長(zhǎng)度的分組，各分組分別在密鑰的控制下變換成等長(zhǎng)度的密文分組。分組密碼的工作原理如圖2-12所示。圖2-12分組密碼工作原理

DES是一種典型的分組密碼，一種將固定長(zhǎng)度的明文通過(guò)一系列復(fù)雜的操作變成同樣長(zhǎng)度的密文的算法。對(duì)DES而言，分組長(zhǎng)度為64位。同時(shí)，DES使用密鑰來(lái)自定義變換過(guò)程，因此算法認(rèn)為只有持有加密所用的密鑰的用戶才能解密密文。密鑰表面上是64位的，然而只有其中的56位被實(shí)際用于算法，其余8位被用于奇偶校驗(yàn)，并在算法中被丟棄。因此，DES的有效密鑰長(zhǎng)度為56位，通常稱DES的密鑰長(zhǎng)度為56位。

與其他分組密碼相似，DES自身并不是加密的實(shí)用手段，而必須以某種工作模式進(jìn)行實(shí)際操作。FIPS—81確定了DES使用的幾種模式[3]。

2.3.2DES算法的描述

DES加密算法如圖2-13所示。圖2-13DES加密算法

初始置換函數(shù)IP

DES對(duì)64位明文分組進(jìn)行操作。首先64位明文分組x經(jīng)過(guò)一個(gè)初始置換函數(shù)IP，產(chǎn)生64位的輸出x0，再將分組x0分成左半部分L0和右半部分R0。即

x0?=??IP(x)?=?L0R0

置換表如表2-1。此表順序?yàn)閺纳系较?，從左至右。如初始置換把明文的第58位換至第1位的位置，把第50位換至第二位。以此類推。

獲取子密鑰Ki

DES加密算法的密鑰長(zhǎng)度為56位，但一般表示為64位，其中每個(gè)第8位用于奇偶校驗(yàn)。在DES加密算法中，要利用用戶提供的64位初始密鑰經(jīng)過(guò)一系列的處理得到K1，K2，…，K16，分別作為1～16輪運(yùn)算的16個(gè)子密鑰?，F(xiàn)在來(lái)看如何獲得這16個(gè)子密鑰。

首先，將64位密鑰去掉8個(gè)校驗(yàn)位，用密鑰置換PC-1置換剩下的56位密鑰；再將56位分成前28位C0和后28位D0。即：PC-1(K56)=C0D0。密鑰置換PC-1如表2-2所示。

綜上所述，整個(gè)子密鑰獲得過(guò)程如圖2-14。圖2-14子密鑰產(chǎn)生

密碼函數(shù)F

密碼函數(shù)F的輸入是32比特?cái)?shù)據(jù)和48比特的子密鑰，其操作步驟如圖2-15所示。圖2-15F(Ri,Ki)計(jì)算

1．?dāng)U展置換(E)

將數(shù)據(jù)的右半部分Ri從32位擴(kuò)展為48位。位選擇函數(shù)(也稱E-盒)如表2-5所示。

2．異或

擴(kuò)展后的48位輸出E(Ri)與壓縮后的48位子密鑰Ki作異或運(yùn)算。

3．S盒替代

將第二步異或得到的48位結(jié)果分成8個(gè)6位的塊，每一塊通過(guò)對(duì)應(yīng)一個(gè)S盒產(chǎn)生一個(gè)4位的輸出。8個(gè)S盒如表2-6所示，注意表中各項(xiàng)采用十六進(jìn)制表示。

S盒的具體置換過(guò)程為：某個(gè)Si盒的6位輸入的第一位和第六位形成一個(gè)2位的二進(jìn)制數(shù)(從0～3)決定對(duì)應(yīng)表中的一行；同時(shí)，輸入的中間4位構(gòu)成4位二進(jìn)制數(shù)(從0～15)對(duì)應(yīng)表中的一列(注意：行和列均從0開始計(jì)數(shù)。)。例如，第8個(gè)S盒的輸入為001011。前后2位形成的二進(jìn)制數(shù)為01，對(duì)應(yīng)第8個(gè)S盒的第1行；中間4位為0101，對(duì)應(yīng)同一S盒的第5列。從表2-6可得S盒8的第1行第5列的數(shù)為3。于是就用0011代替原輸入001011。

4．P盒置換

將8個(gè)S盒的輸出連在一起生成一個(gè)32位的輸出，輸出結(jié)果再通過(guò)置換P。P產(chǎn)生一個(gè)32位的輸出即：F(Ri,Ki)。至此，密碼函數(shù)F的操作就完成了。表2-7為P盒置換。

最后，將P盒置換的結(jié)果與最初的64位分組的左半部分異或，然后左、右半部分交換，接著開始下一輪計(jì)算。

5．函數(shù)F設(shè)計(jì)

函數(shù)F是DES加密的核心。而該函數(shù)又依賴于S盒的設(shè)計(jì)。這也適用于其它的對(duì)稱分組加密算法。下面我們簡(jiǎn)單討論一下有關(guān)F函數(shù)的一些通用設(shè)計(jì)準(zhǔn)則，以及S盒設(shè)計(jì)問(wèn)題。

F的設(shè)計(jì)準(zhǔn)則

函數(shù)F的基本功能就是“擾亂(Confusion)”輸入，因此，對(duì)于F來(lái)說(shuō)其非線性越高越好，也就是說(shuō)，要恢復(fù)F所做的“擾亂”操作越難越好。

其他的設(shè)計(jì)準(zhǔn)則還包括嚴(yán)格雪崩準(zhǔn)則(SAC)和比特獨(dú)立準(zhǔn)則(BIC)[4]。所謂SAC就是要求算法具有良好的雪崩效應(yīng)，輸入當(dāng)中的一個(gè)比特發(fā)生變化都應(yīng)當(dāng)使輸出產(chǎn)生盡可能多的比特變化。嚴(yán)格地說(shuō)，當(dāng)任何單個(gè)輸入比特位i發(fā)生變換時(shí)，一個(gè)S盒的第j比特輸出位發(fā)生變換的概率應(yīng)為1/2，且對(duì)任意的i，j都成立。而比特獨(dú)立準(zhǔn)則的意思是當(dāng)單個(gè)輸入比特位i發(fā)生變化時(shí)，輸出比特位j，k的變化應(yīng)當(dāng)互相獨(dú)立，且任意的i，j，k成立。SAC和BIC可以有效的增強(qiáng)F函數(shù)的“擾亂”功能。

S盒設(shè)計(jì)

S盒的設(shè)計(jì)在對(duì)稱分組密碼研究領(lǐng)域中起著舉足輕重的作用。本質(zhì)上，S盒的作用就是對(duì)輸入向量進(jìn)行處理，使得輸出看起來(lái)更具隨機(jī)性。輸入和輸出之間應(yīng)當(dāng)是非線性的，很難用線性函數(shù)來(lái)逼近。

顯然，S盒的尺寸是一個(gè)很重要的特性。一個(gè)n?×?m的S盒其輸入為n比特，輸出為m比特。DES的S盒大小為6?×?4。S盒越大，就越容易抵制差分和線性密碼分析[1]。一般在實(shí)踐當(dāng)中，通常選擇n在8～10之間。

Mister和Adams[5]提出了很多的S盒設(shè)計(jì)原則，其中包括要求S盒滿足SAC和BIC，以及S盒的所有列的全部線性組合應(yīng)當(dāng)滿足一類稱為bent函數(shù)的高度非線性布爾函數(shù)。Bent函數(shù)具有很多有趣的特性，其中，高度非線性和最高階的嚴(yán)格雪崩準(zhǔn)則對(duì)于S盒的設(shè)計(jì)尤為重要。

Nyberg[12]提出了以下幾種S盒的設(shè)計(jì)和實(shí)踐原則：

(1)隨機(jī)性。采用某些偽隨機(jī)數(shù)發(fā)生器或隨機(jī)數(shù)表格來(lái)產(chǎn)生S盒的各個(gè)項(xiàng)。

(2)隨機(jī)測(cè)試。隨機(jī)選擇S盒各個(gè)項(xiàng)，然后按照不同準(zhǔn)則測(cè)試其結(jié)果。

(3)數(shù)學(xué)構(gòu)造。根據(jù)某些數(shù)學(xué)原理來(lái)產(chǎn)生S盒。其好處就是可以根據(jù)數(shù)學(xué)上的嚴(yán)格證明來(lái)抵御差分和線性密碼分析，并且可以獲得很好的擴(kuò)散(Diffusion)特性。

末置換

末置換是初始置換的逆變換。對(duì)L0和R0進(jìn)行16輪完全相同的運(yùn)算后，將得到的兩部分?jǐn)?shù)據(jù)合在一起經(jīng)過(guò)一個(gè)末置換函數(shù)就可得到64位的密文c，即

c?=?IP-1(R16L16)

表2-8列出了該變換。

DES解密

DES的解密算法與加密算法相同，但子密鑰的次序順序與加密時(shí)相反。

2.3.3DES密碼分析

差分密碼分析是在1990年由埃利比哈姆(EliBiham)和阿迪沙米爾(AdiShamir)兩位密碼學(xué)家首次提出的密碼分析技術(shù)。他們利用該方法找到了針對(duì)DES密碼的選擇明文攻擊，而且這種攻擊比蠻力搜索攻擊有效得多。差分密碼分析依據(jù)所產(chǎn)生的密文對(duì)的差來(lái)檢查明文對(duì)的差，并利用這些差來(lái)計(jì)算出哪些密鑰比其它密鑰的可能性更大，最后求出正確的密鑰。由于DES密碼中，只有F函數(shù)影響輸入對(duì)的模2差，因此差分密碼分析技術(shù)特別適合于對(duì)付DES密碼。由于對(duì)于特定的輸入，輸出差根本不是隨機(jī)的，經(jīng)仔細(xì)選擇輸入，輸出差值便會(huì)暴露密鑰的統(tǒng)計(jì)信息。這種密碼分析技術(shù)需要攻擊者能知道某些明文。

圖2-16是DES的輪函數(shù)。對(duì)于一對(duì)輸入X和X′，對(duì)應(yīng)的輸出為Y和Y′，由此可得各自的差ΔX和ΔY。由于擴(kuò)展置換E和P置換都是已知的，因此由ΔX和ΔY可以計(jì)算出A和C。對(duì)于某個(gè)特定的S盒來(lái)說(shuō)，我們可以事先對(duì)所有可能的ΔB和ΔC進(jìn)行統(tǒng)計(jì)，獲得輸入ΔB和輸出ΔC的統(tǒng)計(jì)關(guān)系。而ΔB?=?ΔA，因此最終我們可以得到ΔA和ΔC之間的聯(lián)系。將ΔA和ΔC聯(lián)合起來(lái)，就可以猜出A異或Ki以及A′異或Ki′的位值，由于A和A′是已知的，故可能推出關(guān)于Ki的信息。

線性密碼分析(LinearCryptanalysis)是MitsuruMatsui提出的一種密碼分析技術(shù)，這種方法通過(guò)尋找分組密碼的線性近似來(lái)進(jìn)行攻擊。

記n位明文組為P[1]，…，P[n]，n位密文組為C[1]，…，C[n]，ｍ位密鑰組為K[1]，…，K[m]。然后定義

線性密碼分析的目的就是要找到一個(gè)下列形式的有效線性等式

其中1≤a,b≤n，1≤c≤m，α，β，γ分別表示某個(gè)特定的位置。一旦確定上述關(guān)系，接下來(lái)就是對(duì)大量的明文和密文對(duì)計(jì)算上述等式的左邊部分。若多數(shù)情況下結(jié)果為0，則假設(shè)，若多屬情況下為1，則假設(shè)。這就得到了密鑰位的線性等式。只要獲得足夠多的上述等式就可以解出密鑰。圖2-16DES輪函數(shù)

圖2-17給出第26位子密鑰的線性等式。b26是S盒5的輸入。b26由a26和子密鑰的Ki,26異或得到，而a26則由輸入的x17通過(guò)擴(kuò)展置換E得到。S盒5對(duì)應(yīng)的4個(gè)輸出位為c17，c18，c19，c20，通過(guò)P盒運(yùn)算成為輪函數(shù)的4位輸出：y3，y8，y14，y25。由此可得等式圖2-17DES的一輪線性逼近

2.3.4DES工作模式

DES有四種工作模式：電子密碼本(ECB)、密碼分組鏈接(CBC)、密文反饋(CFB)和輸出反饋(OFB)。這四種工作模式同樣適用于其它分組密碼。

1．電子密本ECB模式

這是直接應(yīng)用密碼算法的工作模式。對(duì)明文M分成一些64位的分組pi，對(duì)各明文組用給定的密鑰k進(jìn)行加密，得密文組：ci?=?DESk(pi)。將各密文組按順序連接起來(lái)即得到明文的密文，如圖2-18所示。

缺點(diǎn)：在給定密鑰的條件下，同一明文組總是得到同樣的密文組，這會(huì)暴露明文數(shù)據(jù)的格式和統(tǒng)計(jì)特征。圖2-18電子密碼本(ECB)模式

2．密碼分組鏈接CBC模式

在CBC模式下，每個(gè)明文組pi在加密之前先與前一密文組ci-1按位模2求和后，再對(duì)結(jié)果運(yùn)用DES算法。對(duì)于第一個(gè)明文組，由于還沒有反饋密文，需預(yù)置一個(gè)初始向量IV，如圖2-19所示。即

CBC模式通過(guò)反饋使輸出密文與以前的各明文相關(guān)，從而實(shí)現(xiàn)隱蔽明文圖樣的目的。但是這也會(huì)導(dǎo)致錯(cuò)誤傳播的發(fā)生。

3．密文反饋CFB模式

CFB模式將DES作為一個(gè)流密碼產(chǎn)生器，如圖2-20所示。pi和ci為n位分組。移位寄存器的最右邊64位送到DES進(jìn)行加密；將加密結(jié)果的最左邊n位與n位明文組pi作異或運(yùn)算得到密文組ci。然后，將得到的密文組送到移位寄存器的最右端，其他位向左移n位，最左端n位丟棄。然后繼續(xù)下一分組的運(yùn)算。對(duì)第一個(gè)分組同樣需要預(yù)置初始向量IV。算法描述為圖2-20密文反饋(CFB)模式

4．輸出反饋OFB模式

OFB模式也將DES作為密文流產(chǎn)生器。不同的是它將輸出的n位密鑰直接反饋至移位寄存器即DES的輸入端。如圖2-21所示。圖2-21輸出反饋(OFB)模式

2.3.5三重DES

三重DES是DES的一種變行實(shí)現(xiàn)方式，如圖2-22所示。從圖中我們可以得到其加/解密運(yùn)算為

其中，K1、K2、K3為56位DES密鑰。為了獲得更高的安全性，三個(gè)密鑰應(yīng)該選擇為互不相同。但在某些情況下，如與原來(lái)的DES保持兼容，則可以選擇K1?=?K2或K2?=?K3相同。圖2-22三重DES

2.4高級(jí)加密標(biāo)準(zhǔn)(AES)

高級(jí)加密標(biāo)準(zhǔn)(AdvancedEncryptionStandard，AES)是美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院(NIST)旨在取代DES的21世紀(jì)的加密標(biāo)準(zhǔn)。對(duì)AES的基本要求是：采用對(duì)稱分組密碼體制，密鑰長(zhǎng)度的最少支持為128、192、256，分組長(zhǎng)度128位，算法應(yīng)易于各種硬件和軟件實(shí)現(xiàn)。NIST經(jīng)過(guò)五年的甄選流程，最終選擇了由兩名比利時(shí)密碼學(xué)家JoanDaemen和VincentRijmen所設(shè)計(jì)Rijndael算法作為高級(jí)加密標(biāo)準(zhǔn)。該算法結(jié)合兩位作者的名字，以Rijndael命名之(Rijdael的發(fā)音近于“Rhinedoll”。)。

高級(jí)加密標(biāo)準(zhǔn)由美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)于2001年11月26日正式發(fā)布為FIPSPUB197，并在2002年5月26日成為有效的標(biāo)準(zhǔn)。目前，AES已成為對(duì)稱密鑰加密中最流行的算法之一。

2.4.1代數(shù)基礎(chǔ)

鑒于有限域在密碼學(xué)中的重要作用，在介紹AES算法之前，對(duì)群、環(huán)和域等基本概念進(jìn)行簡(jiǎn)單介紹。

1．群

群是一個(gè)集合G，連同一個(gè)運(yùn)算?"·"，它結(jié)合了任何兩個(gè)元素a和b而形成另一個(gè)元素，記為a·b。符號(hào)?"·"，是指某種具體的運(yùn)算。要具備成為群的資格，這個(gè)集合和運(yùn)算(G，·)必須滿足叫做群公理的四個(gè)要求：

(1)封閉性對(duì)于所有G中a、b，運(yùn)算a·b的結(jié)果也在G中。

(2)結(jié)合律對(duì)于所有G中的a、b和c，等式(a·b)·c=a·(b·c)成立。

(3)單位元存在G中的一個(gè)元素e，使得對(duì)于所有G中的元素a，等式e·a=a·e=a成立。

(4)逆元對(duì)于每個(gè)G中的a，存在G中的一個(gè)元素b使得a·b=b·a=e，這里的e是單位元。

進(jìn)行群運(yùn)算的次序可以是重要的。換句話說(shuō)，把元素a與元素b結(jié)合，所得到的結(jié)果不一定與把元素b與元素a結(jié)合相同；等式a·b?=?b·a不一定成立。我們把滿足以下條件的群稱為交換群(又稱阿貝爾群)：

(5)交換律對(duì)于每個(gè)G中的任意元素a、b，都有a·b=b·a成立。

這個(gè)等式在整數(shù)集合的加法運(yùn)算下的群中總是成立，因?yàn)閷?duì)于任何兩個(gè)整數(shù)都有a?+?b?=?b?+?a(加法的交換律)。在乘法運(yùn)算下的非零實(shí)數(shù)集合也是一個(gè)交換群。

2．環(huán)

環(huán)的定義類似于可交換群，只不過(guò)在原有的“+”的基礎(chǔ)上又增添另一種運(yùn)算“·?”(注意我們這里所說(shuō)的?+?與·一般不是通常意義下我們所熟知的加法和乘法)。因此，環(huán)是一個(gè)有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)算分別被稱為加法和乘法。

注：乘法運(yùn)算符·常被省略，所以a·b可簡(jiǎn)寫為ab。此外，乘法是比加法優(yōu)先的運(yùn)算，所以a?+?bc其實(shí)是a?+?(b·c)。

集合R和定義于其上的二元運(yùn)算?+?和·，(R,+,·)構(gòu)成一個(gè)環(huán)，若它們滿足：

(1)?(R,+)形成一個(gè)交換群，其幺元稱為零元素，記作‘0’。即

o(a+b)=(b+a)

o(a+b)+c=a+(b+c)

o0+a=a+0=a

o?a，?(-a)滿足a+?a=-a+a=0

(2)?(R,·)形成一個(gè)半群，即

o(a·b)·c=a·(b·c)

(3)乘法關(guān)于加法滿足分配律

oa·(b+c)=(a·b)+(a·c)

o(a+b)·c=(a·c)+(b·c)

環(huán)就是一個(gè)集合，我們可以在環(huán)中進(jìn)行加法、減法和乘法，而不脫離該集合。

若環(huán)R中，(R，·)還滿足交換律，從而構(gòu)成交換半群，即：?a，b∈R，有ab?=?ba，則R稱為交換環(huán)。

若R中沒有非0的零因子，則稱R為無(wú)零因子環(huán)。

此定義等價(jià)于以下任何一條：

oR\{0}對(duì)乘法形成半群；

oR\{0}對(duì)乘法封閉；

oR中非0元素的乘積非0。

考慮一個(gè)環(huán)R，根據(jù)環(huán)的定義，易知R有以下性質(zhì)：

o?a∈R，a·0=0·a=0；(這也是為什么0作為加法群的幺元，卻被稱為“零元素”)

o?a，b∈R，(-a)·b=a·(-b)=-(a·b)；

若環(huán)R中，(R，·)構(gòu)成幺半群。即：?1∈R，使得?a∈R，有1·a?=?a·1?=?a。則R稱為幺環(huán)。此時(shí)幺半群(R，·)的幺元1，亦稱為環(huán)R的幺元。

無(wú)零因子的交換幺環(huán)稱為整環(huán)。例如普通加法和乘法運(yùn)算下的整數(shù)集合是一個(gè)整環(huán)。

3．域

在抽象代數(shù)中，域(Field)是一種可進(jìn)行加、減、乘和除(除了除以零之外)運(yùn)算的代數(shù)結(jié)構(gòu)。域的概念是數(shù)域以及四則運(yùn)算的推廣。

域是環(huán)的一種。域和環(huán)的區(qū)別在于域要求它的元素(除零元素之外)可以進(jìn)行除法運(yùn)算，這等價(jià)于說(shuō)每個(gè)非零的元素都要有乘法逆元。簡(jiǎn)單來(lái)說(shuō)，域是乘法可交換的除環(huán)。

域是一種交換環(huán)(F，+，·)，當(dāng)中加法單位元(0)不等于乘法單位元(1)，且所有非零元素有乘法逆元。

o乘法逆元：對(duì)所有a≠0，F(xiàn)中存在元素a-1，使得a·a-1=1

常見的數(shù)域都是域。比如說(shuō)，全體復(fù)數(shù)的集合C對(duì)于加法和乘法構(gòu)成一個(gè)域。全體有理數(shù)的集合Q也是一個(gè)域，它是C的子域，并且不包含更小的子域了。所有整數(shù)的集合并不是一個(gè)域，因?yàn)榧现兄挥性?和?-1有乘法逆元。

在密碼學(xué)中，我們更多地對(duì)包含有限個(gè)元素的域感興趣，這就是所謂的有限域或者伽羅瓦域(Galoisfield)。域中的元素個(gè)數(shù)稱為階數(shù)或者基數(shù)。有限域的階數(shù)必須是素?cái)?shù)或者素?cái)?shù)的冪。通常記為GF(pn)，其中p是素?cái)?shù)，n是正整數(shù)。這也意味著有11個(gè)元素的有限域，有256個(gè)元素的有限域，但是不可能有12個(gè)元素的有限域。

n=1時(shí)，GF(p)稱為階數(shù)為p的素域(PrimeField)，它屬于模p的剩余類(ResidueClass)，其中的p個(gè)元素分別是0，1，…，p-1。GF(p)中的a?=?b表示a?≡?b(modp)。GF(p)中的所有非零元素都存在乘法逆元。

例2.7考慮有限域GF(5)={0，1，2，3，4}。下圖給出了兩個(gè)元素之間的加、減、乘和除規(guī)則。

例2.8最小的有限域?yàn)镚F(2)?=?{0，1}，其算術(shù)計(jì)算就是簡(jiǎn)單的模2運(yùn)算，如圖2-23所示。

由圖2-24可知，GF(2)加等效于異或，GF(2)乘等效于邏輯與運(yùn)算。GF(2)在流密碼以及AES中都有重要應(yīng)用。圖2-23GF(5)中的加、減、乘和除法則圖2-24GF(2)中的加和乘運(yùn)算

4．?dāng)U展域GF(2n)

AES密碼所采用的有限域包含256個(gè)元素，可以表示為GF(28)。選擇該域的原因是每一個(gè)域的元素剛好可以表示一個(gè)字節(jié)。字節(jié)是很多AES變換處理的基本單位。但是由于GF(28)有限域的階數(shù)不是素?cái)?shù)，其運(yùn)算無(wú)法再使用素域中的模256來(lái)計(jì)算。對(duì)于n?>?1的擴(kuò)展域，我們需要：

(1)尋求不同的域元素的表示方法；

(2)采用不同的運(yùn)算規(guī)則。

在擴(kuò)展域GF(2n)中，元素不再用整數(shù)來(lái)表示，而是采用多項(xiàng)式表示方法。多項(xiàng)式的系數(shù)屬于GF(2)。多項(xiàng)式的最高階數(shù)等于n-1，因此GF(2n)中的每個(gè)元素都有n個(gè)系數(shù)。對(duì)于AES所使用的GF(28)，其中的每個(gè)元素A可以表示為

顯然這樣的多項(xiàng)式總共有256個(gè)。這256個(gè)多項(xiàng)式的集合就是有限域GF(28)。而且每個(gè)多項(xiàng)式可以簡(jiǎn)單地以8比特向量的形式來(lái)表示

5．?dāng)U展域GF(2n)的運(yùn)算規(guī)則

GF(2n)的加減運(yùn)算相對(duì)簡(jiǎn)單，也就是對(duì)多項(xiàng)式中x各次冪所對(duì)應(yīng)的系數(shù)進(jìn)行GF(2)域下的加減運(yùn)算，即異或運(yùn)算，因此加和減是相同運(yùn)算。

定義：擴(kuò)展域加法和減法

令A(yù)(x)，B(x)∈GF(2m)。兩個(gè)元素的和運(yùn)算如下

兩個(gè)元素的差運(yùn)算如下

例2.9有限域GF(28)中的兩個(gè)元素的加法和減法運(yùn)算：

有限域GF(28)中的乘法是AES算法中MixColumn變化的核心運(yùn)算。采用標(biāo)準(zhǔn)的多項(xiàng)式乘法規(guī)則進(jìn)行運(yùn)算，問(wèn)題是兩個(gè)多項(xiàng)式乘積的最高次冪有可能超過(guò)7，因此，無(wú)法再用一個(gè)字節(jié)來(lái)表示。所以，需要對(duì)乘積結(jié)果用一個(gè)8階不可約多項(xiàng)式進(jìn)行除法運(yùn)算，得到的余數(shù)作為兩個(gè)多項(xiàng)式的乘法運(yùn)算結(jié)果。AES密碼中采用的不可約多項(xiàng)式為

鑒于該多項(xiàng)式最高階為8，無(wú)法用單個(gè)字節(jié)表示，我們通常把它寫為1{00011011}或者1{lb}。

例2.10有限域GF(28)中的兩個(gè)多項(xiàng)式{57}和{83}的乘法運(yùn)算。

首先采用標(biāo)準(zhǔn)多項(xiàng)式乘法進(jìn)行計(jì)算

多項(xiàng)式乘法運(yùn)算還可以利用移位算子來(lái)實(shí)現(xiàn)。我們知道有限域元素{00000010}代表多項(xiàng)式ｘ，如果某個(gè)元素同ｘ相乘，那也就意味著對(duì)該元素的所有項(xiàng)冪次加1。這等價(jià)于左移運(yùn)算，即第i位被移到第i+1位。如果移位前，元素的最高位等于1，那么移位后將產(chǎn)生x8這一項(xiàng)，這時(shí)需要進(jìn)行模運(yùn)算以消除這一項(xiàng)。

例如，對(duì){11001000}乘以ｘ，即{00000010}，得到運(yùn)算結(jié)果1{10010000}，然后同m(ｘ)相加(減)，進(jìn)行異或運(yùn)算，得到最終結(jié)果{10001011}。

重復(fù)上訴步驟，可以得到一個(gè)有限域元素同ｘ的所有冪次相乘的結(jié)果。

最快捷的一種有限域乘法計(jì)算方法是利用查表的方法。

有限域中存在某些元素，稱為生成元(Generator)，記為g。它們的不同冪次gp計(jì)算結(jié)果，可以產(chǎn)生有限域的所有非零元素。在AES算法中，{03}就是GF(28)域的一個(gè)生成元，也就是說(shuō)，{03}ｐ可以構(gòu)成域中的255個(gè)元素：1～255，如表2-9和表2-10所示。還是以例2-10的{57}·{83}為例，{57}?=?{03}62，{83}?=?{03}50(注意：表中的元素都是十六進(jìn)制表示的)。由此，得到{57}·{83}?=?{03}62·{03}50?=?{03}b2，再由表2-10可知{03}b2?=?{c1}，所以{57}·{83}?=?{c1}。

同樣利用表2-9、2-10，還可以用來(lái)計(jì)算有限域元素的乘逆。首先有g(shù)x的逆為gff-x，因此，元素{af}?=?{03}b7的逆為{03}ff-b7?=?{03}48?=?{62}。除了{(lán)00}元素以外，所有的元素都存在逆。

2.4.2AES算法描述

AES的設(shè)計(jì)同樣基于替換-置換網(wǎng)絡(luò)，但并沒有使用DES使用的Feistel網(wǎng)絡(luò)。

AES使用128比特的固定分組大小，密鑰長(zhǎng)度可以是128,192或者256比特。而Rijndael算法設(shè)計(jì)之初，其分組大小和密鑰長(zhǎng)度可以是32比特的整數(shù)倍值，分組最小值取128比特，最大值取256比特，但是密鑰大小在理論上沒有上限。本章的討論都假定秘鑰的長(zhǎng)度為128位。

AES加密有很多輪的重復(fù)和變換，其結(jié)構(gòu)如圖2-25所示。其大致的步驟如下：(1)密鑰擴(kuò)展(KeyExpansion)得到各輪的子密鑰；(2)初始輪(InitialRound)，與輪密鑰相加，(3)重復(fù)輪(Rounds)。每一輪又包括：非線性字節(jié)替換(SubBytes)、置換(ShiftRows)、混合運(yùn)算(MixColumns)、AddRoundKey。(4)最終輪(FinalRound)，最終輪沒有MixColumns。圖2-25AES加密過(guò)程

AES加密算法的輸入分組和解密算法的輸出均為128位。AES的操作對(duì)象是一個(gè)4×4正方形矩陣來(lái)描述的字節(jié)數(shù)組，稱為狀態(tài)矩陣。該矩陣在加密或者解密的各個(gè)階段都會(huì)被改變。密鑰同樣也是以字節(jié)為單位的矩陣來(lái)描述。明文及密鑰的組織排列方式如圖2-26所示。圖2-26AES數(shù)據(jù)結(jié)構(gòu)

2.4.3字節(jié)代替(SubBytes)

字節(jié)代替是對(duì)狀態(tài)矩陣中的每個(gè)字節(jié)單獨(dú)按照S盒進(jìn)行替換。AES定義的S盒如圖2-27所示。圖2-27AESS盒

如果輸入的狀態(tài)矩陣如圖2-28所示，則對(duì)應(yīng)的輸出為：圖2-28S盒替換舉例

在圖2-28中，輸入的第一項(xiàng)ea，被替換成S盒中e行a列中的元素87，其余類推就可以得到整個(gè)輸出結(jié)果。

S盒是AES算法中唯一的一個(gè)非線性組件，也就是說(shuō)，對(duì)于任意兩個(gè)狀態(tài)A和B，都有ByteSub(A)+ByteSub(B)ByteSub(A+B)成立。整個(gè)S盒的替換都是一對(duì)一的映射，而且是可逆的。

AES的S盒可以看成是兩個(gè)數(shù)學(xué)變換的結(jié)果，如圖2-29所示。圖2-29S盒的等效運(yùn)算

第一個(gè)變換就是標(biāo)準(zhǔn)的Galois域的乘法逆元的計(jì)算。圖2-29中的輸入輸出都是域GF(28)中的元素，相應(yīng)的不可約多項(xiàng)式是m(x)?=?x8?+?x4?+?x3?+?x?+?1。圖2-30給出了所有的乘法逆元。需要注意的是0元素其逆元是不存在的，在AES算法中，把0元素的逆元定義為自己。圖中的乘法逆元也可以通過(guò)圖來(lái)組合得到。圖2-30域GF(28)中所有元素{xy}的乘法逆元

替換的第二個(gè)變換就是對(duì)每一個(gè)字節(jié)同一個(gè)常數(shù)矩陣相乘，然后同8比特向量按位異或相加，整個(gè)運(yùn)算如圖2-31所示。圖2-31仿射變換

2.4.4行移位(ShiftRows)

圖2-32描述了正向的行移位變換。狀態(tài)矩陣的第一行保持不變，狀態(tài)矩陣的第二行循環(huán)左移一個(gè)字節(jié)，狀態(tài)矩陣的第三行循環(huán)左移二個(gè)字節(jié)，狀態(tài)矩陣的第四行循環(huán)左移三個(gè)字節(jié)，示例見圖2-33。圖2-32行移位變換圖2-33行移位變換舉例

2.4.5列混淆(MixColumns)

列混淆變換是通過(guò)矩陣乘來(lái)實(shí)現(xiàn)的，如圖2-34所示。列混淆屬于可逆的線性變換，它把狀態(tài)矩陣的每一列的四個(gè)字節(jié)進(jìn)行混合。由于每個(gè)輸入的字節(jié)都會(huì)對(duì)輸出的四個(gè)字節(jié)產(chǎn)生影響，列混淆變換是AES算法中最主要的混淆單元。圖2-34列混淆變換

以矩陣形式來(lái)表示列混淆變換如下式所示，其中所有的值都是有限域中的元素。

其中的乘法運(yùn)算規(guī)則為：乘1意味著不變，乘2就是對(duì)字節(jié)進(jìn)行左移，乘3就是左移后的字節(jié)同原字節(jié)異或相加。注意，如果移位后的值大于0XFF，那么移位后的字節(jié)還必須同0x1B進(jìn)行異或。圖2-35給出了圖2-33的列混淆運(yùn)算結(jié)果。圖2-35列混淆舉例

2.4.6輪密鑰加(AddRoundKey)

在輪密鑰加步驟中，狀態(tài)矩陣中的每個(gè)字節(jié)同輪子密鑰中的對(duì)應(yīng)字節(jié)進(jìn)行異或運(yùn)算。每一輪的子密鑰是通過(guò)密鑰調(diào)度算法計(jì)算得到的。整個(gè)操作如圖2-36所示。圖2-36輪密鑰加

2.4.7密鑰調(diào)度

AES密鑰調(diào)度算法就是把輸入的128位密鑰擴(kuò)展為11組128位子密鑰，其中第0組為輸入密鑰本身。整個(gè)密鑰調(diào)度算法如圖2-37所示。圖2-37AES密鑰調(diào)度算法

圖2-37中的Rot是字循環(huán)，對(duì)一個(gè)字中的四個(gè)字節(jié)循環(huán)左移一個(gè)字節(jié)；然后利用S盒對(duì)輸入字中的每個(gè)字節(jié)進(jìn)行代換。RCON是常量，其值定義為RCON[j]?=?(RC[j],0,0,0)，其中RC[1]?=?1，RC[j]?=?2·RC[j-1]。最終結(jié)果如表2-11所示。

首先輸入的密鑰直接被復(fù)制到擴(kuò)展密鑰數(shù)組的前四個(gè)字w[0]，w[1]，w[2]，w[3]，然后每次由前四個(gè)字計(jì)算得到后續(xù)十組的四個(gè)字。在w數(shù)組中，下標(biāo)為4的倍數(shù)的元素采用更為復(fù)雜的計(jì)算函數(shù)。密鑰調(diào)度算法的偽代碼如下：

2.4.8AES安全性分析

美國(guó)國(guó)家安全局在審核所有參與競(jìng)選AES的最終入圍者時(shí)(包括Rijndael)，就認(rèn)為這些入圍的密碼算法能夠滿足美國(guó)政府傳遞非機(jī)密文件的安全需要。2003年6月，美國(guó)政府還宣布AES可以用于加密機(jī)密文件。AES算法的設(shè)計(jì)和秘鑰長(zhǎng)度足以保護(hù)各種保密信息，對(duì)于絕密信息則要求使用192或者256長(zhǎng)度的密鑰。

通常破解分組密碼系統(tǒng)最常見的方式，是先對(duì)其較弱版本(加密輪數(shù)較少)嘗試各種攻擊。AES算法實(shí)現(xiàn)中，128位密鑰需要10輪加密運(yùn)算，192位密鑰需要12輪加密運(yùn)算，256位密鑰則需要14輪的加密運(yùn)算，而截至2006年，最佳的已知攻擊是128位密鑰的7輪、192位密鑰的8輪、256位密鑰的9輪[7]。

由于已遭破解的弱版的AES，其加密輪數(shù)和原本的加密輪數(shù)相差無(wú)幾，有些密碼學(xué)家開始擔(dān)心AES的安全性：要是有人能將該著名的攻擊加以改進(jìn)，AES分組密碼就會(huì)被破解。要注意的是，在密碼學(xué)的意義上，只要存在一個(gè)方法，比暴力密鑰搜索還要更有效的攻擊都被視為一種“破解”。即便如何，針對(duì)AES128位密鑰的攻擊仍需要2120計(jì)算復(fù)雜度(少于暴力搜索法的2128)，從應(yīng)用的角度來(lái)看，這種破解依然不切實(shí)際。

事實(shí)上，到目前為止，針對(duì)AES算法的最成功攻擊應(yīng)該屬于旁道攻擊(也稱為邊信道攻擊，Side-channelattacks)。

旁道攻擊不攻擊密碼本身，而是攻擊那些密碼算法所運(yùn)行的不安全系統(tǒng)，這些系統(tǒng)有可能會(huì)在不經(jīng)意間泄漏信息。旁道攻擊是一種攻擊方式，它不同于傳統(tǒng)經(jīng)典的、專注于數(shù)學(xué)理論而對(duì)密碼系統(tǒng)進(jìn)行研究的方式，而是一種針對(duì)密碼系統(tǒng)實(shí)現(xiàn)上的物理攻擊方式。它有很多種具體形式，如：能量分析、電磁分析、時(shí)間分析等。

例如，當(dāng)處理密鑰的“1”位時(shí)，要消耗更多的能量。因此通過(guò)監(jiān)控能量的消耗，就可以知道密鑰的每個(gè)位。同樣，我們還可以通過(guò)監(jiān)控算法所耗費(fèi)的時(shí)間來(lái)獲取密鑰的信息。著名的以色列密碼學(xué)家AdiShamir教授給出了旁道攻擊的很多研究成果：監(jiān)聽PC機(jī)運(yùn)行時(shí)的聲音來(lái)獲得GNUPGRSA簽名操作的信息；分析PC機(jī)的USB端口能量變化獲得OPENSSL加解密操作的信息；分析緩存來(lái)獲得AES運(yùn)算信息；對(duì)RFID標(biāo)簽進(jìn)行能量分析等。

2005年4月，D.J.Bernstein[8]公布了一種緩存時(shí)序攻擊法，以此來(lái)破解一臺(tái)安裝有OpenSSL的AES密碼系統(tǒng)的客戶服務(wù)器。攻擊過(guò)程中使用了2億多條篩選過(guò)的明文，以便使該客戶服務(wù)器泄露加密運(yùn)算所導(dǎo)致的定時(shí)信息。

2005年10月，DagArneOsvik[9]展示了數(shù)種針對(duì)AES的緩存時(shí)序攻擊法。其中一種攻擊法只需要800次引發(fā)加密的指令動(dòng)作，費(fèi)時(shí)65ms，就能得到一把完整的AES密鑰。但攻擊者必須在執(zhí)行加密的系統(tǒng)上擁有運(yùn)行程序的權(quán)限，才能破解該密碼系統(tǒng)。

旁道攻擊使我們的密碼系統(tǒng)設(shè)計(jì)陷入了困境，因?yàn)橛靡酝覀儽Ｗo(hù)分組密碼的技術(shù)來(lái)對(duì)付旁道攻擊其效果將適得其反。例如，采用盡量長(zhǎng)的密鑰來(lái)保證分組密碼系統(tǒng)的安全，反而帶來(lái)的是長(zhǎng)時(shí)間的運(yùn)算操作，使得有利于旁道攻擊根據(jù)對(duì)運(yùn)算時(shí)間的分析，來(lái)獲得更多的關(guān)于密碼系統(tǒng)的信息。

因此，也許我們應(yīng)該改變?cè)O(shè)計(jì)密碼系統(tǒng)的方法：只使用大分組的密鑰和數(shù)據(jù)；使用具有內(nèi)在并行機(jī)制的微處理器；或許可以讓Intel在微處理器里加入安全協(xié)處理器來(lái)實(shí)現(xiàn)AES運(yùn)算。

2.5流密碼算法

2.5.1列密碼簡(jiǎn)介序列密碼又稱流密碼。它將明文劃分成字符(如單個(gè)字母)或其編碼的基本單元(如0、1)，然后將其與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的相同密鑰流實(shí)現(xiàn)。序列密碼的原理框圖如圖2-38所示。圖2-38序列密碼原理框圖

序列密碼強(qiáng)度完全依賴于密鑰流產(chǎn)生器所產(chǎn)生的序列的隨機(jī)性和不可預(yù)測(cè)性，其核心問(wèn)題是密鑰流生成器的設(shè)計(jì)。而保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)鍵

技術(shù)。

2.5.2A5算法

A5算法是一種序列密碼，它是歐洲GSM標(biāo)準(zhǔn)中規(guī)定的加密算法，用于數(shù)字蜂窩移動(dòng)電話的加密，加密從用戶設(shè)備到基站之間的鏈路。A5算法包括很多種，主要為A5/1和A5/2。其中，A5/1為強(qiáng)加密算法，適用于歐洲地區(qū)；A5/2為弱加密算法，適用于歐洲以外的地區(qū)。這里將詳細(xì)討論A5/1算法。

A5/1算法的主要組成部分是三個(gè)長(zhǎng)度不同的線性反饋移位寄存器(LFSR)R1、R2和R3，其長(zhǎng)度分別為19、22和23。三個(gè)移位寄存器在時(shí)鐘的控制下進(jìn)行左移，每次左移后寄存器最低位由寄存器中的某些位異或后的位填充。各寄存器的反饋多項(xiàng)式為

各寄存器的詳細(xì)情況如圖2-39所示。圖2-39A5/1序列密碼

當(dāng)時(shí)鐘到來(lái)之時(shí)，三個(gè)移位寄存器并不是都進(jìn)行移位，而是遵循一個(gè)所謂的“多數(shù)為主”的原則。這個(gè)原則為：從每個(gè)寄存器取出一位(R1取第8位、R2取第10位、R3取第10位)，當(dāng)這三個(gè)位中有兩個(gè)或兩個(gè)以上的值等于1時(shí)，則將取出位為1的寄存器進(jìn)行移位，而取出位為0的不移位；當(dāng)三個(gè)取出位中有兩個(gè)或兩個(gè)以上的0時(shí)，將取出位為0的寄存器進(jìn)行移位，為1的不移。最后，將三個(gè)移位寄存器最高位的異或運(yùn)算結(jié)果作為輸出。

A5算法的輸入是64位的會(huì)話密鑰Kc和22位的隨機(jī)數(shù)(幀號(hào))。

對(duì)A5/1的安全性分析及密碼分析可參考文獻(xiàn)[18]。

參考文獻(xiàn)

[1]Diffie,W,HellmanM.NewDirectionsinCryptography.IEEETransactionsonInformationTheory,November1976[2]NationalInstituteofStandardsandTechnology,FIPSPUB46-2.DataEncryptionStandard(DES).U.S.DepartmentofCommerce,Dec1993[3]NationalInstituteofStandardsandTechnology,FIPSPUB81.DESModesofOperation.U.S.DepartmentofCommerce,Dec1980

[4]WebsterA,TavaresS.OntheDesignofS-Boxes.Proceedings,Crypto85,1985;publishedbySpringer-Verlag

[5]MisterS,AdamsC.PracticalS-BoxDesign.Proceedings,WorkshopinSelectedAreasofCryptography,SAC’96,1996

[6]BruceSchneier.AppliedCryptography:Protocols,Algorithms,andSourceCodeinC.2ndedition,JohnWiley&Sons,1996

[7]JohnKelsey,StefanLucks,BruceSchneier,etal.ImprovedCryptanalysisofRijndael,FastSoftwareEncryption,2000pp213–230

[8]DanielJ.Bernstein.Cache-timingattacksonAES.2005.04.14

[9]DagArneOsvik1;AdiShamir2andEranTromer2.CacheAttacksand