網(wǎng)絡(luò)安全與保密（第二版）第2章對稱密碼學(xué)-

第2章對稱密碼學(xué)第2章對稱密碼學(xué)密碼系統(tǒng)模型古典密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級加密標(biāo)準(zhǔn)(AES)流密碼算法

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

密碼系統(tǒng)模型在1976年Diffie及Hellman發(fā)表其論文“New

Directions

in

Cryptography”[1]之前，所謂的密碼學(xué)就是指對稱密鑰密碼系統(tǒng)。因為加密/解密用的是同一把密鑰，所以也稱為單

一密鑰密碼系統(tǒng)。這類算法可謂歷史悠久，從最早的凱撒密

碼到目前使用最多的DES密碼算法，以及2000年美國推出的

下一代密碼算法AES[/archive/aes/index.html]都屬于此統(tǒng)。第2章對稱密碼學(xué)通常一個密鑰加密系統(tǒng)包括以下幾個部分：消息空間M(Message)；密文空間C(Ciphertext)；密鑰空間K(Key)；加密算法E(Encryption

algorithm)；解密算法D(Decryption

algorithm)。第2章對稱密碼學(xué)消息空間中的消息M(稱之為明文)通過由加密密鑰K1控制的加密算法加密后得到密文C。密文C通過解密密鑰K2控制的解密算法又可恢復(fù)出原始明文M。即：EK1(M)

=

CDK2(C)

=

MDK2(EK1(M))

=

M第2章對稱密碼學(xué)在圖2-1的加/解密系統(tǒng)模型中，當(dāng)算法的加密密鑰能夠從解密密鑰中推算出來，或反之，解密密鑰可以從加密密鑰中推算出來時，稱此算法為對稱算法，也稱秘密密鑰算法或單密鑰算法。稱加密密鑰和解密密鑰不同并且其中一個密鑰不能通過另一個密鑰推算出來的算法為公開密鑰算法。在現(xiàn)代密碼學(xué)中，所有算法的安全性都要求是基于密鑰的安全性，而不是基于算法細(xì)節(jié)的安全性。也就是說，只要密鑰不公開，即使算法公開并被分析，不知道密鑰的人也無法理解你所加密過的消息。第2章對稱密碼學(xué)圖2-1密鑰加/解密系統(tǒng)模型第2章對稱密碼學(xué)2.2

古典密碼在計算機(jī)出現(xiàn)之前，密碼學(xué)由基于字符的密碼算法構(gòu)成。不同的密碼算法之間互相替代(Substitution)或相互置換

(Transposition)，好的密碼算法是結(jié)合這兩種方法，每次進(jìn)行多次運算?，F(xiàn)在的計算機(jī)密碼算法要復(fù)雜的多，但基本原

理沒有變化。其重要的變化是算法只對位而不是字母進(jìn)行變

換，也就是字母表長度從26個字母變?yōu)?個字母。大多數(shù)好

的密碼算法仍然是以替代和置換作為加密技術(shù)的基本構(gòu)造塊。第2章對稱密碼學(xué)2.2.1替代密碼替代密碼就是明文中的每一個字符被替換為密文中的另外一個字符。接收者對密文進(jìn)行逆替換即可恢復(fù)出明文。在古典密碼學(xué)中有三種類型的替代密碼：單表替代密碼、多表替代密碼和多字母替代密碼。第2章對稱密碼學(xué)1．單表替代密碼所謂的單表替代密碼(Monoalphabetic)就是明文的每一個字符用相應(yīng)的另外一個唯一的密文字符代替。最早的密碼系統(tǒng)“凱撒密碼”就是一種單表替代密碼，也是一種移位替代密碼。凱撒密碼是對英文的26個字母分別向前移3位，于是可以得到其替代表為明文：a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z密文：D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C第2章對稱密碼學(xué)例2.1對明文第2章對稱密碼學(xué)顯然，這種密碼系統(tǒng)是不安全的，它非常容易攻破。首先，簡單的單表替代沒有掩蓋明文不同字母出現(xiàn)的頻率；其次，移位替代的密鑰空間有限，只有25個密鑰，利用暴力攻擊法很容易破解。因此，替代密碼應(yīng)該有更大的密鑰空間，關(guān)鍵詞(Keyword)密碼就是這樣一種加密方法。第2章對稱密碼學(xué)2．關(guān)鍵詞(Keyword)密碼關(guān)鍵詞加密方法包含兩個步驟：選擇一個關(guān)鍵詞，如果關(guān)鍵詞中包含有重復(fù)的字母，則后續(xù)出現(xiàn)的該字母一律刪除。例如，對于關(guān)鍵詞“xidian”則最終使用的詞是“xidan”。將關(guān)鍵詞寫在字母表的下方，剩下的空間用其余的字母按照字母順序進(jìn)行填寫。第2章對稱密碼學(xué)例2.2對于關(guān)鍵詞“KRYPTOS”，其明文和密文對照表如下對消息“cryptography

is

cool”的加密結(jié)果如下明文：C

R

Y

P

T

O

G

R

A

P

H

Y

I

S

C

O

O

L明文：密A文B：CYDLEXFIGNHHISJLKKLIMANXOBPMQYRHSHTEU

V

W

X

YZ密文關(guān)：K鍵R詞Y加P

T密O方S法A

B的C最D大E

F安G全H

缺I

J陷L在M

于N

Q其U很V

容W

X易受到頻率Z分析攻擊。第2章對稱密碼學(xué)在密碼學(xué)中，所謂的頻率分析是指字母或者字母組合在密文中出現(xiàn)的頻率。許多的古典密碼都可以用這種方法進(jìn)行破解。頻率分析是基于這樣一個事實：在任何一種書面語言中，不同的字母或字母組合出現(xiàn)的頻率各不相同。而且，對于以這種語言書寫的任意一段文本，都具有大致相同的字母分布特征。比如，在英語中，字母E出現(xiàn)的頻率很高，而X則出現(xiàn)得較少，如圖2-2所示。類似地，ST、NG、TH，以及QU等雙字母組合出現(xiàn)的頻率非常高，NZ、QJ組合則極少。英語中出現(xiàn)頻率最高的12個字母可以簡記為“ETAOINSHRDLU”。第2章對稱密碼學(xué)圖2-2英文字母出現(xiàn)頻率統(tǒng)計第2章對稱密碼學(xué)有了這些信息，我們再回頭看看關(guān)鍵詞加密方法的破解：首先關(guān)鍵詞加密法仍屬于單表替代密碼，這也就意味著，盡管明文中的某個字母被替換成密文中的某個字母，但是其統(tǒng)計頻率并未改變。因此，通過對密文中的每個字母的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計分析，就可以大致判斷明文和密文的對應(yīng)關(guān)系。例如，密文中出現(xiàn)頻率最高的某個字母很有可能對應(yīng)的就是明文字母“E”。其次可以利用密文的關(guān)鍵詞之后都是按照字母順序排列這一規(guī)律來進(jìn)一步降低破解難度。第2章對稱密碼學(xué)3．仿射加密方法(Affine

Cipher)在仿射加密方法中，每個字母被賦予一個數(shù)字，例如字母a=0，字母b=1，……，字母z=25。加密密鑰為0～25之間的數(shù)字對(a，b)。加解密函數(shù)形式分別為c

=

e(p)

=

(ap

+

b)

(mod

26)

p

=

d(c)

=

a-1(c

-

b)(mod

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

mod

m模乘法逆元有唯一解的充要條件是a和26(m)的最大公約數(shù)：gcd(a，26)=1。第2章對稱密碼學(xué)例2.3下面我們對明文“AFFINE

CIPHER”進(jìn)行加密，其中a=5，b=8。整個加密過程如下表所示。第2章對稱密碼學(xué)第2章對稱密碼學(xué)由于仿射密碼仍然是一種單表替換密碼，因此它也存在此類密碼所固有的缺陷。前述的頻率分析方法同樣適用。在考慮加密英文消息時，m=26，此時總共有286種仿射密碼，其中沒有包含26種簡單的凱撒密碼。這主要是因為同26互為素數(shù)的數(shù)有12個，也就是a的取值有12種。每個a對應(yīng)的移位取值是26個，也就是b的值。因此總共有12*26=

312可能的秘鑰。第2章對稱密碼學(xué)該密碼系統(tǒng)的主要弱點在于對手一旦通過頻率分析或者蠻力搜索或者猜測等手段發(fā)現(xiàn)兩個密文字符所對應(yīng)的明文字符，他就可以通過線性解方程得方法來恢復(fù)秘鑰。而且我們知道a和m必須互為素數(shù)，這也有助于判斷解方程得到的結(jié)果是否正確。第2章對稱密碼學(xué)4．多表替代密碼多表替代密碼是以一系列的(兩個以上)替代表依次對明文消息的字母進(jìn)行替代的加密方法。多表替換加密形式是：其中的每個明文字母可以被密文中的不同字母來代替，而每個密文字母也可以表示多個明文字母。這種加密法可以干擾字母出現(xiàn)頻率分析法。著名的Vigenere加密法就是其中的一種，它在長達(dá)三百多年的時間里都被認(rèn)為是不可破解的。第2章對稱密碼學(xué)Vigenere加密過程如下：選擇一個關(guān)鍵詞(例如，“MEC”)。將關(guān)鍵詞重復(fù)地寫在明文的上方，直至兩者長度相等。密文通過查詢Vigenere表得到。其中關(guān)鍵詞字母確定表的行，明文字母確定表的列，如圖2-3所示。行與列的交叉處得到對應(yīng)密文。第2章對稱密碼學(xué)圖2-3

Vigenere替換表第2章對稱密碼學(xué)例2.4用關(guān)鍵詞MEC進(jìn)行消息加密。關(guān)鍵詞

M

E

C

M

E

C

M

E

C

M

E

C

M

E

C

M

E

C

M

E

C

M明文 w

e

n

e

e

d

m

o

r

e

s

u

p

p

l

i

e

s

f

a

s

t密文 I

I

P

Q

I

F

Y

S

T

Q

W

W

B

T

N

U

I

U

R

E

U

F從中，我們可以看到，字母‘e’有時候被加密成‘I’，有時候被加密成‘Q’。而且，密文中的Ｉ表示了兩個不同的明文字母‘w’和‘e’。這種變換特性使得頻率分析方法在此變得無能為力。顯然，出現(xiàn)頻率很高的字母‘e’被替換成了出現(xiàn)頻率不怎么高的‘I’和‘Q’，而且密文中連續(xù)出現(xiàn)的兩個相同字母，如‘II’或‘WW’所對應(yīng)的明文字母并不相同。第2章對稱密碼學(xué)當(dāng)然，這并不意味著沒有辦法來破解Vigenere加密法。幸運的是，F(xiàn)rederickKasiski通過觀察發(fā)現(xiàn)：明文中重復(fù)出現(xiàn)的字符串與關(guān)鍵詞密鑰的重復(fù)部分加密會得到重復(fù)密文字符串，如圖2-4所示。圖2-4Vigenere密碼分析第2章對稱密碼學(xué)在上例中，兩次“kiov”之間的距離為9，“nu”之間的距離為6，由此我們可以猜測這些距離應(yīng)該是密鑰長度的倍數(shù)，密鑰長度可能為3。因此密文中重復(fù)字符串之間的距離反映了密鑰重復(fù)的次數(shù)和密鑰的長度，于是FrederickKasiski提出的破解過程如下：找出密文中重復(fù)的字符串；計算重復(fù)字符串之間的字符數(shù)；找出從步驟(2)中得到的數(shù)的因子(就是最大公約數(shù))；該最大公約數(shù)很可能就是關(guān)鍵詞的長度。第2章對稱密碼學(xué)有了關(guān)鍵詞長度，我們就可以將與關(guān)鍵詞中用同一個字

符替換得到的密文字符集合到一起，這些密文字符的集合就

相當(dāng)于一個單表加密所得到的密文。這樣就可以采用前面提

到的頻率分析方法進(jìn)行密碼破解了。對于上面的例子，把密

鑰run中的r字符所對應(yīng)的密文整合在一起，即kvekvrjvvz…，它們都是由同一個密鑰加密得到的移位加密密文。所以，一

旦得到關(guān)鍵字長度，破解Vigenere加密法就變成了破解n(關(guān)

鍵字長度為n)個不同的單表加密問題。第2章對稱密碼學(xué)對于關(guān)鍵詞長度的計算，美國密碼學(xué)家William

Friedman提出了基于凹凸度量(MR)的方法。我們知道，英語中每個字符出現(xiàn)的概率都是不一樣的，繪成頻率分析圖，圖中就有高峰與低谷，單表加密法是沒有辦法改變字母出現(xiàn)的概率的，但是對于多表加密法，得到的字母頻率圖就變得很平滑。完全平滑的分布就是每個字母等概率(1/26)出現(xiàn)的情況。凹凸度量是指從文本中選取的字母的實際概率與從完全平滑的分布中選取該字母的概率之差。第2章對稱密碼學(xué)Pa是從密文中選取a字母的概率，那么上述的概率偏差

即為(Pa-1/26)2。加平方是為了保證得到的值為正值。Pa為完全偏差，因此a到z所有字母的偏差和為通過拆分和取舍，可以將這個式子簡化成第2章對稱密碼學(xué)對于某個密文，如果估算出，那么MR就能確定。由于P2

為從密文中選取字母a的概率，那么就是從全部密文中選a取字母的概率和從剩余密文中(即去掉第一個a字母的密文)中選取字母a的概率的乘積。如果密文中有n個字母，F(xiàn)a是密文中a字母的個數(shù)，那么計算密文的MR值只依賴于P2

。a第2章對稱密碼學(xué)由此，William

Friedman定義了重合指數(shù)的概念(Indexof

Coincidence，IC)來分析多表加密法。IC定義為第2章對稱密碼學(xué)通過分析和資料，我們得知單表加密法的IC大概為

0.066。完全平滑的文字，其值為0.38，如果IC的值在0.38到0.066之間，就說明該密文很可能就是多表加密法。事實上，通過圖2-5，我們能得知IC值暗示的多表加密法的密鑰長度。第2章對稱密碼學(xué)圖2-5

IC值和秘鑰長度關(guān)系第2章對稱密碼學(xué)多字母(Polygraphic)替代密碼多字母替代密碼是每次對多于1個字母進(jìn)行替代的加密方法，它的優(yōu)點在于將字母的自然頻度隱蔽或均勻化，從而利于抗統(tǒng)計分析。Playfair密碼算法Playfair密碼采用一個包含密鑰的5×5矩陣進(jìn)行加密解密。矩陣首先用去掉重復(fù)字母的密鑰進(jìn)行填充，然后用剩余的字母按照順序進(jìn)行填充。圖2-6給出了密鑰為“playfairexample”的加解密矩陣(注意，I和J被認(rèn)為是同一個字母)。第2章對稱密碼學(xué)圖2-6

Playfair加解密矩陣第2章對稱密碼學(xué)加密消息前，把消息明文按兩個字母一組進(jìn)行分割，如果這個兩個字母相同，則插入一個空字符，比如‘X’。若明文消息的字母個數(shù)為奇數(shù)時，將空字母X加在明文的末端。第2章對稱密碼學(xué)對于每一對明文m1、m2，其加密規(guī)則如下：(1)m1和m2在同一行時，則密文c1和c2分別是緊靠m1、

m2右端的字母。其中第一列看作是最后一列的右方。舉例

如下：第2章對稱密碼學(xué)(2)若m1和m2在同一列時，則密文c1和c2分別是緊靠m1、m2下方的字母。其中第一行看作是最后一行的上方。第2章對稱密碼學(xué)(3)若m1和m2不在同一行，也不在同一列時，則密文c1和c2是由m1和m2確定的矩形的其他兩角的字母，并且c1和m1、c2和m2同行。第2章對稱密碼學(xué)例2.5首先對加密消息“Hide

the

gold

in

the

tree

stump進(jìn)行預(yù)處理后，得到兩個字母一組的明文：HI

DE

TH

EG

OL

DI

NT

HE

TR

EX

ES

TU

MP^通過利用圖所示的加密矩陣加密后得到的密文如下：BM

OD

ZB

XD

NA

BE

KU

DM

UI

XM

MO

UV

IF第2章對稱密碼學(xué)7．Playfair密碼分析破解和分析Playfair密碼的第一步就是要確定你所分析的密碼確實是采用的Playfair加密的。這通?？梢酝ㄟ^以下特征來識別：密文的字母個數(shù)是偶數(shù)；原來在明文中很少出現(xiàn)的一些字母，其在密文中出現(xiàn)的頻率明顯增加；把密文按照兩個字母一組進(jìn)行分割，則每組的字母不會有重復(fù)；雙圖的頻率分布與明文的頻率分布大致相同。第2章對稱密碼學(xué)在具體的密文分析過程中，可以使用以下特征或者規(guī)則進(jìn)行：明文中的字母不會被加密成自己。明文中逆序的兩個雙圖加密后的兩個雙圖同樣也是逆序的。明文中的每個字母只能用某5個字母中的一個來加密。圖2-7給出了Playfair密碼分析的一般過程。第2章對稱密碼學(xué)圖2-7

playfair密碼分析步驟第2章對稱密碼學(xué)2.2.2置換密碼在置換密碼中，明文和密文的字母保持相同，但順序被打亂了。置換密碼使用的密鑰通常是一些幾何圖形，它決定了明文字母被重新排列的順序和方式。第2章對稱密碼學(xué)1．Skytale加密法(天書)Skytale就是一種加密用的、具有一定粗細(xì)的棍棒或權(quán)杖，如圖2-8所示。斯巴達(dá)人把皮革或羊皮紙纏繞在特定直徑的木棍上，寫好文字以后再把皮革或羊皮紙解下來，紙上的字母順序就頓時歪七扭八，就誰也不認(rèn)識了；只有把皮(紙)帶再一點點卷回與原來加密的Skytale同樣粗細(xì)的棍棒上后，文字信息逐圈并列在棍棒的表面，才能還原出本來的意思。第2章對稱密碼學(xué)圖2-8

Skytale天書第2章對稱密碼學(xué)實際上天書就是一種簡單的縱行置換密碼。明文以固定的寬度水平地寫在一張圖表紙上，密文按垂直方向讀出；解密就是將密文按相同的寬度垂直的寫在圖表紙上，然后水平的讀出明文。第2章對稱密碼學(xué)例2.6對下列明文計算天書加密結(jié)果密文：eiffob

nsodml

ctraee

rhmtuf

yeaano

pttirr

trineiaota

onnod

nsosa第2章對稱密碼學(xué)在填寫某個圖表時，可以采用各種形狀的幾何圖形，如rail-fence(柵欄)加密時采用對角線方式寫入，然后按行讀出即可得到密文，如圖2-9所示。圖2-9柵欄密碼第2章對稱密碼學(xué)對應(yīng)的密文如下WECRL

TEERD

SOEEF

EAOCA

IVDEN圖2-10給出了按照三角形方式填充的加密方法，按列讀取就是對應(yīng)的密文。圖2-10三角形置換密碼第2章對稱密碼學(xué)2．列置換密碼在列置換密碼中，消息按照固定長度的行寫入，然后按照某種順序逐列讀出，即可得到密文。行的寬度和列的置換順序由一個關(guān)鍵詞或者密鑰來控制。例如，對于秘鑰“crypto”，總共包含6個字母，因此加密矩陣有6列。然后秘鑰中各個字母在字母表中的順序為：1、4、6、3、5、2，因此相應(yīng)的列置換順序為“1

4

6

3

5

2”。也就是說，密文的第一列仍然是明文矩陣的第一列，而密文的第二列則是明文矩陣的第六列，以此類推。第2章對稱密碼學(xué)對于消息明文“WE

ARE

DISCOVERED.FLEE

ATONCE.”和密鑰“crypto”，其對應(yīng)的明文矩陣和置換規(guī)則如圖2-11所示。圖2-11列置換密碼第2章對稱密碼學(xué)圖2-11中最后5個字母稱為空字符，用于填滿矩陣最后一行，這種列置換密碼稱為規(guī)則列置換矩陣。對于非規(guī)則列置換密碼，矩陣最后一行不進(jìn)行任何填充。最終的加密結(jié)果為WIREE

DEECU

ROFOJ

ESEAQ

EVLNE

ACDTK第2章對稱密碼學(xué)3．置換密碼分析由于置換密碼并不影響單個符號出現(xiàn)的頻率，簡單的置換可以通過頻率計數(shù)進(jìn)行檢測識別。如果密文和明文的頻率分布非常接近，那么很有可能該密文是采用置換密碼加密的。置換密碼最容易用文字拼圖游戲進(jìn)行攻擊，也就是不斷交換字母順序，看能不能發(fā)現(xiàn)單詞或者某些短語。這種短語可能泄露某些列置換模式。隨著發(fā)現(xiàn)更多的短語，從而最終找到整個列置換規(guī)則。第2章對稱密碼學(xué)簡單的置換密碼還容易受到最優(yōu)搜索算法的攻擊，如遺傳算法。因為隨著破解出來的密鑰越來越接近真實的密鑰，每一行中合理的，更加接近語法的明文短語越來越多，越來越長，這就為密鑰的搜索提供有用的信息。第2章對稱密碼學(xué)2.3

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

Standard)。第2章對稱密碼學(xué)2.3.1分組密碼簡介對稱密碼算法有兩種類型：分組密碼(Block

Cipher)和

流密碼(Stream

Cipher)。分組密碼一次處理一塊輸入，每個輸入塊生成一個輸出塊，而流密碼對輸入元素進(jìn)行連續(xù)處理，同時產(chǎn)生連續(xù)單個輸出元素。數(shù)據(jù)加密標(biāo)準(zhǔn)DES屬于分組密

碼。分組密碼將明文消息劃分成固定長度的分組，各分組分

別在密鑰的控制下變換成等長度的密文分組。分組密碼的工

作原理如圖2-12所示。第2章對稱密碼學(xué)圖2-12分組密碼工作原理第2章對稱密碼學(xué)DES是一種典型的分組密碼，一種將固定長度的明文通過一系列復(fù)雜的操作變成同樣長度的密文的算法。對DES而言，分組長度為64位。同時，DES使用密鑰來自定義變換過程，因此算法認(rèn)為只有持有加密所用的密鑰的用戶才能解密密文。密鑰表面上是64位的，然而只有其中的56位被實際用于算法，其余8位被用于奇偶校驗，并在算法中被丟棄。因此，DES的有效密鑰長度為56位，通常稱DES的密鑰長度為56位。與其他分組密碼相似，DES自身并不是加密的實用手段，而必須以某種工作模式進(jìn)行實際操作。FIPS—81確定了DES使用的幾種模式[3]。第2章對稱密碼學(xué)2.3.2

DES算法的描述DES加密算法如圖2-13所示。第2章對稱密碼學(xué)圖2-13DES加密算法第2章對稱密碼學(xué)初始置換函數(shù)IPDES對64位明文分組進(jìn)行操作。首先64位明文分組x經(jīng)過一個初始置換函數(shù)IP，產(chǎn)生64位的輸出x0，再將分組x0分成左半部分L0和右半部分R0。即x0

=

IP(x)

=

L0R0置換表如表2-1。此表順序為從上到下，從左至右。如初始置換把明文的第58位換至第1位的位置，把第50位換至第二位。以此類推。第2章對稱密碼學(xué)第2章對稱密碼學(xué)獲取子密鑰KiDES加密算法的密鑰長度為56位，但一般表示為64位，其中每個第8位用于奇偶校驗。在DES加密算法中，要利用用戶提供的64位初始密鑰經(jīng)過一系列的處理得到K1，K2，…，K16，分別作為1～16輪運算的16個子密鑰?，F(xiàn)在來看如何獲得這16個子密鑰。首先，將64位密鑰去掉8個校驗位，用密鑰置換PC-1置換剩下的56位密鑰；再將56位分成前28位C0和后28位D0。即：PC-1(K56)=C0D0。密鑰置換PC-1如表2-2所示。第2章對稱密碼學(xué)第2章對稱密碼學(xué)第2章對稱密碼學(xué)綜上所述，整個子密鑰獲得過程如圖2-14。圖2-14子密鑰產(chǎn)生第2章對稱密碼學(xué)密碼函數(shù)F密碼函數(shù)F的輸入是32比特數(shù)據(jù)和48比特的子密鑰，其操作步驟如圖2-15所示。圖2-15F(Ri,Ki)計算第2章對稱密碼學(xué)1．?dāng)U展置換(E)將數(shù)據(jù)的右半部分Ri從32位擴(kuò)展為48位。位選擇函數(shù)(也稱E-盒)如表2-5所示。第2章對稱密碼學(xué)2．異或擴(kuò)展后的48位輸出E(Ri)與壓縮后的48位子密鑰Ki作異或運算。3．S盒替代將第二步異或得到的48位結(jié)果分成8個6位的塊，每一塊通過對應(yīng)一個S盒產(chǎn)生一個4位的輸出。8個S盒如表2-6所示，注意表中各項采用十六進(jìn)制表示。第2章對稱密碼學(xué)第2章對稱密碼學(xué)第2章對稱密碼學(xué)S盒的具體置換過程為：某個Si盒的6位輸入的第一位和第六位形成一個2位的二進(jìn)制數(shù)(從0～3)決定對應(yīng)表中的一行；同時，輸入的中間4位構(gòu)成4位二進(jìn)制數(shù)(從0～15)對應(yīng)表中的一列(注意：行和列均從0開始計數(shù)。)。例如，第8個

S盒的輸入為001011。前后2位形成的二進(jìn)制數(shù)為01，對應(yīng)

第8個S盒的第1行；中間4位為0101，對應(yīng)同一S盒的第5列。從表2-6可得S盒8的第1行第5列的數(shù)為3。于是就用0011代替原輸入001011。第2章對稱密碼學(xué)4．P盒置換將8個S盒的輸出連在一起生成一個32位的輸出，輸出結(jié)果再通過置換P。P產(chǎn)生一個32位的輸出即：F(Ri,Ki)。至此，密碼函數(shù)F的操作就完成了。表2-7為P盒置換。最后，將P盒置換的結(jié)果與最初的64位分組的左半部分異或，然后左、右半部分交換，接著開始下一輪計算。第2章對稱密碼學(xué)第2章對稱密碼學(xué)5．函數(shù)F設(shè)計函數(shù)F是DES加密的核心。而該函數(shù)又依賴于S盒的設(shè)計。這也適用于其它的對稱分組加密算法。下面我們簡單討論一下有關(guān)F函數(shù)的一些通用設(shè)計準(zhǔn)則，以及S盒設(shè)計問題。F的設(shè)計準(zhǔn)則函數(shù)F的基本功能就是“擾亂(Confusion)”輸入，因此，對于F來說其非線性越高越好，也就是說，要恢復(fù)F所做的“擾亂”操作越難越好。第2章對稱密碼學(xué)其他的設(shè)計準(zhǔn)則還包括嚴(yán)格雪崩準(zhǔn)則(SAC)和比特獨立

準(zhǔn)則(BIC)[4]。所謂SAC就是要求算法具有良好的雪崩效應(yīng)，輸入當(dāng)中的一個比特發(fā)生變化都應(yīng)當(dāng)使輸出產(chǎn)生盡可能多的比特變化。嚴(yán)格地說，當(dāng)任何單個輸入比特位i發(fā)生變換時，一個S盒的第j比特輸出位發(fā)生變換的概率應(yīng)為1/2，且對任

意的i，j都成立。而比特獨立準(zhǔn)則的意思是當(dāng)單個輸入比特位i發(fā)生變化時，輸出比特位j，k的變化應(yīng)當(dāng)互相獨立，且

任意的i，j，k成立。SAC和BIC可以有效的增強(qiáng)F函數(shù)的“擾亂”功能。第2章對稱密碼學(xué)S盒設(shè)計S盒的設(shè)計在對稱分組密碼研究領(lǐng)域中起著舉足輕重的作用。本質(zhì)上，S盒的作用就是對輸入向量進(jìn)行處理，使得輸出看起來更具隨機(jī)性。輸入和輸出之間應(yīng)當(dāng)是非線性的，很難用線性函數(shù)來逼近。顯然，S盒的尺寸是一個很重要的特性。一個n×m的S盒其輸入為n比特，輸出為m比特。DES的S盒大小為6×4。S盒越大，就越容易抵制差分和線性密碼分析[1]。一般在實踐當(dāng)中，通常選擇n在8～10之間。第2章對稱密碼學(xué)Mister和Adams[5]提出了很多的S盒設(shè)計原則，其中包括要求S盒滿足SAC和BIC，以及S盒的所有列的全部線性組合應(yīng)當(dāng)滿足一類稱為bent函數(shù)的高度非線性布爾函數(shù)。Bent函數(shù)具有很多有趣的特性，其中，高度非線性和最高階的嚴(yán)格雪崩準(zhǔn)則對于S盒的設(shè)計尤為重要。第2章對稱密碼學(xué)Nyberg[12]提出了以下幾種S盒的設(shè)計和實踐原則：隨機(jī)性。采用某些偽隨機(jī)數(shù)發(fā)生器或隨機(jī)數(shù)表格來產(chǎn)生S盒的各個項。隨機(jī)測試。隨機(jī)選擇S盒各個項，然后按照不同準(zhǔn)則測試其結(jié)果。數(shù)學(xué)構(gòu)造。根據(jù)某些數(shù)學(xué)原理來產(chǎn)生S盒。其好處就是可以根據(jù)數(shù)學(xué)上的嚴(yán)格證明來抵御差分和線性密碼分析，并且可以獲得很好的擴(kuò)散(Diffusion)特性。第2章對稱密碼學(xué)末置換末置換是初始置換的逆變換。對L0和R0進(jìn)行16輪完全相同的運算后，將得到的兩部分?jǐn)?shù)據(jù)合在一起經(jīng)過一個末置換函數(shù)就可得到64位的密文c，即c

=

IP-1(R16L16)表2-8列出了該變換。DES解密DES的解密算法與加密算法相同，但子密鑰的次序順序與加密時相反。第2章對稱密碼學(xué)第2章對稱密碼學(xué)2.3.3

DES密碼分析差分密碼分析是在1990年由埃利比哈姆(Eli

Biham)和阿迪沙米爾(Adi

Shamir)兩位密碼學(xué)家首次提出的密碼分析技術(shù)。他們利用該方法找到了針對DES密碼的選擇明文攻擊，而且這種攻擊比蠻力搜索攻擊有效得多。差分密碼分析依據(jù)所產(chǎn)生的密文對的差來檢查明文對的差，并利用這些差來計算出哪些密鑰比其它密鑰的可能性更大，最后求出正確的密鑰。由于DES密碼中，只有F函數(shù)影響輸入對的模2差，因此差分密碼分析技術(shù)特別適合于對付DES密碼。由于對于特定的輸入，輸出差根本不是隨機(jī)的，經(jīng)仔細(xì)選擇輸入，輸出差值便會暴露密鑰的統(tǒng)計信息。這種密碼分析技術(shù)需要攻擊者能知道某些明文。第2章對稱密碼學(xué)圖2-16是DES的輪函數(shù)。對于一對輸入X和X′，對應(yīng)的輸出為Y和Y′，由此可得各自的差ΔX和ΔY。由于擴(kuò)展置換E和P置換都是已知的，因此由ΔX和ΔY可以計算出A和C。對于某個特定的S盒來說，我們可以事先對所有可能的ΔB和Δ

C進(jìn)行統(tǒng)計，獲得輸入ΔB和輸出ΔC的統(tǒng)計關(guān)系。而ΔB=Δ

A，因此最終我們可以得到ΔA和ΔC之間的聯(lián)系。將ΔA和ΔC聯(lián)合起來，就可以猜出A異或Ki以及A′異或Ki′的位值，由于A和A′是已知的，故可能推出關(guān)于Ki的信息。第2章對稱密碼學(xué)線性密碼分析(Linear

Cryptanalysis)是Mitsuru

Matsui出的一種密碼分析技術(shù)，這種方法通過尋找分組密碼的線性近似來進(jìn)行攻擊。記n位明文組為P[1]，…，P[n]，n位密文組為C[1]，…，C[n]，ｍ位密鑰組為K[1]，…，K[m]。然后定義第2章對稱密碼學(xué)線性密碼分析的目的就是要找到一個下列形式的有效線性等式其中1≤a,b≤n，1≤c≤m，α，β，γ分別表示某個特定的位置。一旦確定上述關(guān)系，接下來就是對大量的明文和密文對計算上述等式的左邊部分。若多數(shù)情況下結(jié)果為0，則假設(shè)，若多屬情況下為1，則假設(shè)。這就得到了密鑰位的線性等式。只要獲得足夠多的上述等式就可以解出密鑰。第2章對稱密碼學(xué)圖2-16

DES輪函數(shù)第2章對稱密碼學(xué)圖2-17給出第26位子密鑰的線性等式。b26是S盒5的輸

入。b26由a26和子密鑰的Ki,26異或得到，而a26則由輸入的

x17通過擴(kuò)展置換E得到。S盒5對應(yīng)的4個輸出位為c17，c18，

c19，c20，通過P盒運算成為輪函數(shù)的4位輸出：y3，y8，

y14，y25。由此可得等式第2章對稱密碼學(xué)圖2-17DES的一輪線性逼近第2章對稱密碼學(xué)2.3.4

DES工作模式DES有四種工作模式：電子密碼本(ECB)、密碼分組鏈接(CBC)、密文反饋(CFB)和輸出反饋(OFB)。這四種工作模式同樣適用于其它分組密碼。1．電子密本ECB模式這是直接應(yīng)用密碼算法的工作模式。對明文M分成一些64位的分組pi，對各明文組用給定的密鑰k進(jìn)行加密，得密文組：ci=DESk(pi)。將各密文組按順序連接起來即得到明文的密文，如圖2-18所示。缺點：在給定密鑰的條件下，同一明文組總是得到同樣的密文組，這會暴露明文數(shù)據(jù)的格式和統(tǒng)計特征。第2章對稱密碼學(xué)圖2-18電子密碼本(ECB)模式第2章對稱密碼學(xué)2．密碼分組鏈接CBC模式在CBC模式下，每個明文組pi在加密之前先與前一密文組ci-1按位模2求和后，再對結(jié)果運用DES算法。對于第一個明文組，由于還沒有反饋密文，需預(yù)置一個初始向量IV，如圖2-19所示。即CBC模式通過反饋使輸出密文與以前的各明文相關(guān)，從而實現(xiàn)隱蔽明文圖樣的目的。但是這也會導(dǎo)致錯誤傳播的發(fā)生。第2章對稱密碼學(xué)第2章對稱密碼學(xué)3．密文反饋CFB模式CFB模式將DES作為一個流密碼產(chǎn)生器，如圖2-20所示。

pi和ci為n位分組。移位寄存器的最右邊64位送到DES進(jìn)行加密；將加密結(jié)果的最左邊n位與n位明文組pi作異或運算得到密文組ci。然后，將得到的密文組送到移位寄存器的最右端，其他位向左移n位，最左端n位丟棄。然后繼續(xù)下一分組的運

算。對第一個分組同樣需要預(yù)置初始向量IV。算法描述為第2章對稱密碼學(xué)圖2-20密文反饋(CFB)模式第2章對稱密碼學(xué)4．輸出反饋OFB模式OFB模式也將DES作為密文流產(chǎn)生器。不同的是它將輸出的n位密鑰直接反饋至移位寄存器即DES的輸入端。如圖2-21所示。第2章對稱密碼學(xué)圖2-21輸出反饋(OFB)模式第2章對稱密碼學(xué)2.3.5三重DES三重DES是DES的一種變行實現(xiàn)方式，如圖2-22所示。從圖中我們可以得到其加/解密運算為其中，K1、K2、K3為56位DES密鑰。為了獲得更高的安全性，三個密鑰應(yīng)該選擇為互不相同。但在某些情況下，如與原來的DES保持兼容，則可以選擇K1

=K2或K2

=K3相同。第2章對稱密碼學(xué)圖2-22三重DES第2章對稱密碼學(xué)2.4

高級加密標(biāo)準(zhǔn)(AES)高級加密標(biāo)準(zhǔn)(Advanced

Encryption

Standard，AES)是美國國家標(biāo)準(zhǔn)技術(shù)研究院(NIST)旨在取代DES的21世紀(jì)的加密標(biāo)準(zhǔn)。對AES的基本要求是：采用對稱分組密碼體制，密鑰長度的最少支持為128、192、256，分組長度128位，算法應(yīng)易于各種硬件和軟件實現(xiàn)。NIST經(jīng)過五年的甄選流程，

最終選擇了由兩名比利時密碼學(xué)家Joan

Daemen和Vincent

Rijmen所設(shè)計Rijndael算法作為高級加密標(biāo)準(zhǔn)。該算法結(jié)合兩位作者的名字，以Rijndael命名之(Rijdael的發(fā)音近于

“Rhinedoll”。)。第2章對稱密碼學(xué)高級加密標(biāo)準(zhǔn)由美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)于2001年11月26日正式發(fā)布為FIPS

PUB

197，并在2002年5月26日成為有效的標(biāo)準(zhǔn)。目前，AES已成為對稱密鑰加密中最流行的算法之一。2.4.1代數(shù)基礎(chǔ)鑒于有限域在密碼學(xué)中的重要作用，在介紹AES算法之前，對群、環(huán)和域等基本概念進(jìn)行簡單介紹。第2章對稱密碼學(xué)1．群群是一個集合G，連同一個運算"·"，它結(jié)合了任何兩個元素a和b而形成另一個元素，記為a·b。符號"·"，是指某種具體的運算。要具備成為群的資格，這個集合和運算(G，·)必須滿足叫做群公理的四個要求：封閉性對于所有G中a、b，運算a·b的結(jié)果也在G中。結(jié)合律對于所有G中的a、b和c，等式(a·b)·c=

a·(b·c)成立。單位元存在G中的一個元素e，使得對于所有G中的元素a，等式e·a=a·e=a成立。第2章對稱密碼學(xué)(4)逆元對于每個G中的a，存在G中的一個元素b使得a·b=b·a=e，這里的e是單位元。進(jìn)行群運算的次序可以是重要的。換句話說，把元素a與元素b結(jié)合，所得到的結(jié)果不一定與把元素b與元素a結(jié)合相同；等式a·b=b·a不一定成立。我們把滿足以下條件的群稱為交換群(又稱阿貝爾群)：第2章對稱密碼學(xué)(5)交換律對于每個G中的任意元素a、b，都有a·b=

b·a成立。這個等式在整數(shù)集合的加法運算下的群中總是成立，因為對于任何兩個整數(shù)都有a+b=b+a(加法的交換律)。在乘法運算下的非零實數(shù)集合也是一個交換群。第2章對稱密碼學(xué)2．環(huán)環(huán)的定義類似于可交換群，只不過在原有的“+”的基礎(chǔ)上又增添另一種運算“·”(注意我們這里所說的+與·一般不是通常意義下我們所熟知的加法和乘法)。因此，環(huán)是一個有兩個二元運算的集合，這兩個二元運算分別被稱為加法和乘法。注：乘法運算符·常被省略，所以a·b可簡寫為ab。此外乘法是比加法優(yōu)先的運算，所以a+bc其實是a+(b·c)。第2章對稱密碼學(xué)集合R和定義于其上的二元運算+和·，(R,+,·)構(gòu)成一個環(huán)，若它們滿足：(1)(R,+)形成一個交換群，其幺元稱為零元素，記作‘0’。即o(a

+

b)

=

(b

+

a)o(a

+

b)

+

c

=

a

+

(b

+

c)o0

+

a

=

a

+

0

=

ao?a，?(-a)滿足a+?a=-a+a=0第2章對稱密碼學(xué)(R,·)形成一個半群，即o(a·b)·c=a·(b·c)乘法關(guān)于加法滿足分配律 oa·(b+c)=(a·b)+(a·c) o(a+b)·c=(a·c)+(b·c)環(huán)就是一個集合，我們可以在環(huán)中進(jìn)行加法、減法和乘法，而不脫離該集合。若環(huán)R中，(R，·)還滿足交換律，從而構(gòu)成交換半群，即：?a，b∈R，有ab=ba，則R稱為交換環(huán)。第2章對稱密碼學(xué)若R中沒有非0的零因子，則稱R為無零因子環(huán)。此定義等價于以下任何一條：oR\{0}對乘法形成半群；oR\{0}對乘法封閉；oR中非0元素的乘積非0。第2章對稱密碼學(xué)考慮一個環(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)。此時幺半群(R，·)的幺元1亦稱為環(huán)R的幺元。無零因子的交換幺環(huán)稱為整環(huán)。例如普通加法和乘法運算下的整數(shù)集合是一個整環(huán)。第2章對稱密碼學(xué)3．域在抽象代數(shù)中，域(Field)是一種可進(jìn)行加、減、乘和除(除了除以零之外)運算的代數(shù)結(jié)構(gòu)。域的概念是數(shù)域以及四則運算的推廣。域是環(huán)的一種。域和環(huán)的區(qū)別在于域要求它的元素(除零元素之外)可以進(jìn)行除法運算，這等價于說每個非零的元素都要有乘法逆元。簡單來說，域是乘法可交換的除環(huán)。第2章對稱密碼學(xué)域是一種交換環(huán)(F，+，·)，當(dāng)中加法單位元(0)不等于乘法單位元(1)，且所有非零元素有乘法逆元。o乘法逆元：對所有a≠0，F(xiàn)中存在元素a-1，使得a·a-1

=1常見的數(shù)域都是域。比如說，全體復(fù)數(shù)的集合C對于加法和乘法構(gòu)成一個域。全體有理數(shù)的集合Q也是一個域，它是C的子域，并且不包含更小的子域了。所有整數(shù)的集合并不是一個域，因為集合中只有元素1和-1有乘法逆元。第2章對稱密碼學(xué)在密碼學(xué)中，我們更多地對包含有限個元素的域感興趣，這就是所謂的有限域或者伽羅瓦域(Galois

field)。域中的元素個數(shù)稱為階數(shù)或者基數(shù)。有限域的階數(shù)必須是素數(shù)或者素

數(shù)的冪。通常記為GF(pn)，其中p是素數(shù)，n是正整數(shù)。這也意味著有11個元素的有限域，有256個元素的有限域，但是

不可能有12個元素的有限域。n=1時，GF(p)稱為階數(shù)為p的素域(PrimeField)，它屬于模p的剩余類(Residue

Class)，其中的p個元素分別是0，1，…p-1。GF(p)中的a=b表示a≡b(modp)。GF(p)中的所有非零元素都存在乘法逆元。第2章對稱密碼學(xué)例2.7考慮有限域GF(5)={0，1，2，3，4}。下圖給出了兩個元素之間的加、減、乘和除規(guī)則。例2.8最小的有限域為GF(2)={0，1}，其算術(shù)計算就是簡單的模2運算，如圖2-23所示。由圖2-24可知，GF(2)加等效于異或，GF(2)乘等效于邏輯與運算。GF(2)在流密碼以及AES中都有重要應(yīng)用。第2章對稱密碼學(xué)圖2-23

GF(5)中的加、減、乘和除法則第2章對稱密碼學(xué)圖2-24

GF(2)中的加和乘運算第2章對稱密碼學(xué)4．?dāng)U展域GF(2n)AES密碼所采用的有限域包含256個元素，可以表示為GF(28)。選擇該域的原因是每一個域的元素剛好可以表示一個字節(jié)。字節(jié)是很多AES變換處理的基本單位。但是由于GF(28)有限域的階數(shù)不是素數(shù)，其運算無法再使用素域中的模256來計算。對于n>1的擴(kuò)展域，我們需要：尋求不同的域元素的表示方法；采用不同的運算規(guī)則。第2章對稱密碼學(xué)在擴(kuò)展域GF(2n)中，元素不再用整數(shù)來表示，而是采用多項式表示方法。多項式的系數(shù)屬于GF(2)。多項式的最高階數(shù)等于n-1，因此GF(2n)中的每個元素都有n個系數(shù)。對于AES所使用的GF(28)，其中的每個元素A可以表示為顯然這樣的多項式總共有256個。這256個多項式的集合就是有限域GF(28)。而且每個多項式可以簡單地以8比特向量的形式來表示第2章對稱密碼學(xué)5．?dāng)U展域GF(2n)的運算規(guī)則GF(2n)的加減運算相對簡單，也就是對多項式中x各次冪所對應(yīng)的系數(shù)進(jìn)行GF(2)域下的加減運算，即異或運算，因此加和減是相同運算。定義：擴(kuò)展域加法和減法令A(yù)(x)，B(x)∈GF(2m)。兩個元素的和運算如下兩個元素的差運算如下第2章對稱密碼學(xué)例2.9有限域GF(28)中的兩個元素的加法和減法運算：有限域GF(28)中的乘法是AES算法中MixColumn變化的核心運算。采用標(biāo)準(zhǔn)的多項式乘法規(guī)則進(jìn)行運算，問題是兩個多項式乘積的最高次冪有可能超過7，因此，無法再用一個字節(jié)來表示。所以，需要對乘積結(jié)果用一個8階不可約多項式進(jìn)行除法運算，得到的余數(shù)作為兩個多項式的乘法運算結(jié)果。AES密碼中采用的不可約多項式為鑒于該多項式最高階為8，無法用單個字節(jié)表示，我們通常把它寫為1{00011011}或者1{lb}。第2章對稱密碼學(xué)例2.10有限域GF(28)中的兩個多項式{57}和{83}的乘法運算。首先采用標(biāo)準(zhǔn)多項式乘法進(jìn)行計算第2章對稱密碼學(xué)多項式乘法運算還可以利用移位算子來實現(xiàn)。我們知道有限域元素{00000010}代表多項式ｘ，如果某個元素同ｘ相乘，那也就意味著對該元素的所有項冪次加1。這等價于左移運算，即第i位被移到第i+1位。如果移位前，元素的最高位等于1，那么移位后將產(chǎn)生x8這一項，這時需要進(jìn)行模運算以消除這一項。例如，對{11001000}乘以ｘ，即{00000010}，得到運算結(jié)果1{10010000}，然后同m(ｘ)相加(減)，進(jìn)行異或運算，得到最終結(jié)果{10001011}。重復(fù)上訴步驟，可以得到一個有限域元素同ｘ的所有冪次相乘的結(jié)果。第2章對稱密碼學(xué)最快捷的一種有限域乘法計算方法是利用查表的方法。第2章對稱密碼學(xué)有限域中存在某些元素，稱為生成元(Generator)，記為

g。它們的不同冪次gp計算結(jié)果，可以產(chǎn)生有限域的所有非

零元素。在AES算法中，{03}就是GF(28)域的一個生成元，

也就是說，{03}ｐ可以構(gòu)成域中的255個元素：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，還可以用來計算有限域元素的乘逆。首先有g(shù)x的逆為gff-x，因此，元素{af}={03}b7的逆為{03}ff-b7={03}48={62}。除了{(lán)00}元素以外，所有的元素都存在逆。第2章對稱密碼學(xué)第2章對稱密碼學(xué)第2章對稱密碼學(xué)2.4.2

AES算法描述AES的設(shè)計同樣基于替換-置換網(wǎng)絡(luò)，但并沒有使用DES使用的Feistel網(wǎng)絡(luò)。AES使用128比特的固定分組大小，密鑰長度可以是128,192或者256比特。而Rijndael算法設(shè)計之初，其分組大小和密鑰長度可以是32比特的整數(shù)倍值，分組最小值取128比特，最大值取256比特，但是密鑰大小在理論上沒有上限。本章的討論都假定秘鑰的長度為128位。第2章對稱密碼學(xué)AES加密有很多輪的重復(fù)和變換，其結(jié)構(gòu)如圖2-25所示。其大致的步驟如下：(1)密鑰擴(kuò)展(KeyExpansion)得到各輪的子密鑰；(2)初始輪(Initial

Round)，與輪密鑰相加，(3)重輪(Rounds)。每一輪又包括：非線性字節(jié)替換(SubBytes)、置換(ShiftRows)、混合運算(MixColumns)、AddRoundKey。(4)最終輪(Final

Round)，最終輪沒有MixColumns。第2章對稱密碼學(xué)圖2-25

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

AES數(shù)據(jù)結(jié)構(gòu)第2章對稱密碼學(xué)2.4.3字節(jié)代替(SubBytes)字節(jié)代替是對狀態(tài)矩陣中的每個字節(jié)單獨按照S盒進(jìn)行替換。AES定義的S盒如圖2-27所示。第2章對稱密碼學(xué)圖2-27

AES

S盒第2章對稱密碼學(xué)如果輸入的狀態(tài)矩陣如圖2-28所示，則對應(yīng)的輸出為：圖2-28S盒替換舉例第2章對稱密碼學(xué)在圖2-28中，輸入的第一項ea，被替換成S盒中e行a列中的元素87，其余類推就可以得到整個輸出結(jié)果。S盒是AES算法中唯一的一個非線性組件，也就是說，對于任意兩個狀態(tài)A和B，都有

ByteSub(A)+ByteSub(B)ByteSub(A+B)成立。整個S盒的替換都是一對一的映射，而且是可逆的。AES的S盒可以看成是兩個數(shù)學(xué)變換的結(jié)果，如圖2-29所示。第2章對稱密碼學(xué)圖2-29

S盒的等效運算第2章對稱密碼學(xué)第一個變換就是標(biāo)準(zhǔn)的Galois域的乘法逆元的計算。圖2-29中的輸入輸出都是域GF(28)中的元素，相應(yīng)的不可約多項式是m(x)=x8

+x4

+x3

+x+1。圖2-30給出了所有的乘法逆元。需要注意的是0元素其逆元是不存在的，在AES算法中，把0元素的逆元定義為自己。圖中的乘法逆元也可以通過圖來組合得到。第2章對稱密碼學(xué)圖2-30域GF(28)中所有元素{xy}的乘法逆元第2章對稱密碼學(xué)替換的第二個變換就是對每一個字節(jié)同一個常數(shù)矩陣相乘，然后同8比特向量按位異或相加，整個運算如圖2-31所示。圖2-31仿射變換第2章對稱密碼學(xué)第2章對稱密碼學(xué)2.4.4行移位(ShiftRows)圖2-32描述了正向的行移位變換。狀態(tài)矩陣的第一行保持不變，狀態(tài)矩陣的第二行循環(huán)左移一個字節(jié)，狀態(tài)矩陣的第三行循環(huán)左移二個字節(jié)，狀態(tài)矩陣的第四行循環(huán)左移三個字節(jié)，示例見圖2-33。第2章對稱密碼學(xué)圖2-32行移位變換第2章對稱密碼學(xué)圖2-33行移位變換舉例第2章對稱密碼學(xué)2.4.5列混淆(MixColumns)列混淆變換是通過矩陣乘來實現(xiàn)的，如圖2-34所示。列混淆屬于可逆的線性變換，它把狀態(tài)矩陣的每一列的四個字節(jié)進(jìn)行混合。由于每個輸入的字節(jié)都會對輸出的四個字節(jié)產(chǎn)生影響，列混淆變換是AES算法中最主要的混淆單元。第2章對稱密碼學(xué)圖2-34列混淆變換第2章對稱密碼學(xué)以矩陣形式來表示列混淆變換如下式所示，其中所有的值都是有限域中的元素。第2章對稱密碼學(xué)其中的乘法運算規(guī)則為：乘1意味著不變，乘2就是對字節(jié)進(jìn)行左移，乘3就是左移后的字節(jié)同原字節(jié)異或相加。注意，如果移位后的值大于0XFF，那么移位后的字節(jié)還必須

同0x1B進(jìn)行異或。圖2-35給出了圖2-33的列混淆運算結(jié)果。第2章對稱密碼學(xué)圖2-35列混淆舉例第2章對稱密碼學(xué)2.4.6輪密鑰加(AddRoundKey)在輪密鑰加步驟中，狀態(tài)矩陣中的每個字節(jié)同輪子密鑰中的對應(yīng)字節(jié)進(jìn)行異或運算。每一輪的子密鑰是通過密鑰調(diào)度算法計算得到的。整個操作如圖2-36所示。第2章對稱密碼學(xué)圖2-36輪密鑰加第2章對稱密碼學(xué)2.4.7密鑰調(diào)度AES密鑰調(diào)度算法就是把輸入的128位密鑰擴(kuò)展為11組128位子密鑰，其中第0組為輸入密鑰本身。整個密鑰調(diào)度算法如圖2-37所示。圖2-37

AES密鑰調(diào)度算法第2章對稱密碼學(xué)圖2-37中的Rot是字循環(huán)，對一個字中的四個字節(jié)循環(huán)左移一個字節(jié)；然后利用S盒對輸入字中的每個字節(jié)進(jìn)行代換。RCON是常量，其值定義為RCON[j]=(RC[j],0,0,0)，其中RC[1]=1，RC[j]=2·RC[j-1]。最終結(jié)果如表2-11所示。第2章對稱密碼學(xué)首先輸入的密鑰直接被復(fù)制到擴(kuò)展密鑰數(shù)組的前四個字

w[0]，w[1]，w[2]，w[3]，然后每次由前四個字計算得到后續(xù)十組的四個字。在w數(shù)組中，下標(biāo)為4的倍數(shù)的元素采用

更為復(fù)雜的計算函數(shù)。密鑰調(diào)度算法的偽代碼如下：第2章對稱密碼學(xué)第2章對稱密碼學(xué)第2章對稱密碼學(xué)2.4.8

AES安全性分析美國國家安全局在審核所有參與競選AES的最終入圍者時(包括Rijndael)，就認(rèn)為這些入圍的密碼算法能夠滿足美國政府傳遞非機(jī)密文件的安全需要。2003年6月，美國政府還宣布AES可以用于加密機(jī)密文件。AES算法的設(shè)計和秘鑰長度足以保護(hù)各種保密信息，對于絕密信息則要求使用192或者256長度的密鑰。第2章對稱密碼學(xué)通常破解分組密碼系統(tǒng)最常見的方式，是先對其較弱版本(加密輪數(shù)較少)嘗試各種攻擊。AES算法實現(xiàn)中，128位

密鑰需要10輪加密運算，192位密鑰需要12輪加密運算，256位密鑰則需要14輪的加密運算，而截至2006年，最佳的已知攻擊是128位密鑰的7輪、192位密鑰的8輪、256位密鑰的9輪

[7]。第2章對稱密碼學(xué)由于已遭破解的弱版的AES，其加密輪數(shù)和原本的加密

輪數(shù)相差無幾，有些密碼學(xué)家開始擔(dān)心AES的安全性：要是

有人能將該著名的攻擊加以改進(jìn)，AES分組密碼就會被破解。要注意的是，在密碼學(xué)的意義上，只要存在一個方法，比暴力密鑰搜索還要更有效的攻擊都被視為一種“破解”。即便如何，針對AES

128位密鑰的攻擊仍需要2120計算復(fù)雜度(少于暴力搜索法的2128)，從應(yīng)用的角度來看，這種破解依然不切實際。事實上，到目前為止，針對AES算法的最成功攻擊應(yīng)該屬于旁道攻擊(也稱為邊信道攻擊，Side-channel

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

因此通過監(jiān)控能量的消耗，就可以知道密鑰的每個位。同樣，我們還可以通過監(jiān)控算法所耗費的時間來獲取密鑰的信息。

著名的以色列密碼學(xué)家Adi

Shamir教授給出了旁道攻擊的很

多研究成果：監(jiān)聽PC機(jī)運行時的聲音來獲得GNUPG

RSA簽名操作的信息；分析PC機(jī)的USB端口能量變化獲得OPENSSL加解密操作的信息；分析緩存來獲得AES運算信息；對RFID標(biāo)簽進(jìn)行能量分析等。第2章對稱密碼學(xué)2005年4月，D.J.Bernstein[8]公布了一種緩存時序攻擊法，以此來破解一臺安裝有OpenSSL的AES密碼系統(tǒng)的客戶服務(wù)器。攻擊過程中使用了2億多條篩選過的明文，以便使該客戶服務(wù)器泄露加密運算所導(dǎo)致的定時信息。2005年10月，DagArneOsvik[9]展示了數(shù)種針對AES的緩存時序攻擊法。其中一種攻擊法只需要800次引發(fā)加密的指令動作，費時65

ms，就能得到一把完整的AES密鑰。但攻擊者必須在執(zhí)行加密的系統(tǒng)上擁有運行程序的權(quán)限，才能破解該密碼系統(tǒng)。第2章對稱密碼學(xué)旁道攻擊使我們的密碼系統(tǒng)設(shè)計陷入了困境，因為用以往我們保護(hù)分組密碼的技術(shù)來對付旁道攻擊其效果將適得其反。例如，采用盡量長的密鑰來保證分組密碼系統(tǒng)的安全，反而帶來的是長時間的運算操作，使得有利于旁道攻擊根據(jù)對運算時間的分析，來獲得更多的關(guān)于密碼系統(tǒng)的信息。因此，也許我們應(yīng)該改變設(shè)計密碼系統(tǒng)的方法：只使用大分組的密鑰和數(shù)據(jù)；使用具有內(nèi)在并行機(jī)制的微處理器；或許可以讓Intel在微處理器里加入安全協(xié)處理器來實現(xiàn)AES運算。第2章對稱密碼學(xué)2.5

流密碼算法2.5.1列密碼簡介序列密碼又稱流密碼。它將明文劃分成字符(如單個字母)或其編碼的基本單元(如0、1)，然后將其與密鑰流作用進(jìn)行加密，解密時以同步產(chǎn)生的相同密鑰流實現(xiàn)。序列密碼的原理框圖如圖2-38所示。第2章對稱密碼學(xué)圖2-38序列密碼原理框圖第2章對稱密碼學(xué)序列密碼強(qiáng)度完全依賴于密鑰流產(chǎn)生器所產(chǎn)生的序列的隨機(jī)性和不可預(yù)測性，其核心問題是密鑰流生成器的設(shè)計。而保持收發(fā)兩端密鑰流的精確同步是實現(xiàn)可靠解密的關(guān)鍵技術(shù)。第2章對稱密碼學(xué)2.5.2

A5算法A5算法是一種序列密碼，它是歐洲GSM標(biāo)準(zhǔn)中規(guī)定的

加密算法，用于數(shù)字蜂窩移動電話的加密，加密從用戶設(shè)備到基站之間的鏈路。A5算法包括很多種，主要為A5/1和A5/2。其中，A5/1為強(qiáng)加密算法，適用于歐洲地區(qū)；A5/2為弱加密算法，適用于歐洲以外的地區(qū)。這里將詳細(xì)討論A5/1算法。第2章對稱密碼學(xué)A5/1算法的主要組成部分是三個長度不同的線性反饋移位寄存器(LFSR)R1、R2和R3，其長度分別為19、22和23。三個移位寄存器在時鐘的控制下進(jìn)行左移，每次左移后寄存器最低位由寄存器中的某些位異或后的位填充。各寄存器的反饋多項式為第2章對稱密碼學(xué)各寄存器的詳細(xì)情況如圖2-39所示。圖2-39

A5/1序列密碼第2章對稱密碼學(xué)當(dāng)時鐘到來之時，三個移位寄存器并不是都進(jìn)行移位，而是遵循一個所謂的“多數(shù)為主”的原則。這個原則為：從每個寄存器取出一位(R1取第8位、R2取第10位、R3取第10位)，當(dāng)這三個位中有兩個或兩個以上的值等于1時，則將取出位為1的寄存器進(jìn)行移位，而取出位為0的不移位；當(dāng)三個取出位中有兩個或兩個以上的0時，將取出位為0的寄存器進(jìn)行移位，為1的不移。最后，將三個移位寄存器最高位的異或運算結(jié)果作為輸出。A5算法的輸入是64位的會話密鑰Kc和22位的隨機(jī)數(shù)(幀號)。對A5/1的安全性分析及密碼分析可參考文獻(xiàn)[18]。第2章對稱密碼學(xué)參考文獻(xiàn)Diffie,W,

Hellman

M.

New

Directions

inCryptography

.

IEEE

Transactions

on

Information

Theory,November

1976National

Institute

of

Standards

and

Technology,

PUB

46-2.

Data

Encryption

Standard(DES)

.

U.S.

Departmen

of

Commerce,

Dec

1993National

Institute

of

Standards

and

Technology,PUB

81.

DES

Modes

of

Operation

.

U.S.

Department

ofCommerce,

Dec

1980第2章對稱密碼學(xué)Webster

A,

Tavares

S.

On

the

Design

of

S-Boxes.Proceedings,

Crypto

85

,

1985;

published

by

Springer-VerlMister

S,

Adams

C.

Practical

S-Box

Design.Proceedings

,

Workshop

in

Selected

Areas

of

Cryptography,SAC

’96,

1996Bruce

Schneier.

Applied

Cryptography:

Protocols,Algorithms,

and

Source

Code

in

C

.

2nd

edition,

John

WileySons,

1996John

Kelsey,

Stefan

Lucks,

Bruce

Schneier,

et

al.Improved

Cryptanalysis

of

Rijndael,

Fast

Software

Encryp2000

pp213–230第2章對稱密碼學(xué)Daniel

J.

Bernstein.

Cache-timing

attacks

on

AES.2005.04.14Dag

Arne

Osvik1;

Adi

Shamir2

and

Eran

Tromer2.Cache

Attacks

and

Countermeasures:

the

Case

of

AES.2005.11.20Bruce

Schneier.

New

Attack

on

AES.

Schneier

onSecurity,

A

blog

covering

security

and

securitytechnology.2009.07.01Biryukov,

Alex,

Khovratovich,

et

al.

Related-keCryptanalysis

of

the

Full

AES-192

and

AES-256.

2009.12.04第2章對稱密碼學(xué)Alex

Biryukov,

Orr

Dunkelman,

Nathan

Keller,

etKey

Recovery

Attacks

of

Practical

Complexity

on

AES

VarianWith

Up

To

10

Rounds.

2009.08.19Henri

Gilbert,

Thomas

Peyrin.

Super-SboxCryptanalysis:

Improved

Attacks

for

AES-like

permutation2009.11.09Vincent

Rijmen.

Practical-Titled

Attack

on

AES-Using

Chosen-Text

Relations./

2010/337.

pdf.

2