第二章對(duì)稱密碼學(xué)

密碼學(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ā)表其論文“New

DirectionsinCryptography"⑴之前，所謂的密碼

學(xué)就是指對(duì)稱密鑰密碼系統(tǒng)。因?yàn)榧用?解密用的是同一把

密鑰，所以也稱為單一密鑰密碼系統(tǒng)。這類算法可謂歷史悠

久，從最早的凱撒密碼到目前使用最多的DES密碼算法，

以及2000年美國(guó)推出的下一代密碼算法AES

[/archive/aes/index.htm

1]都屬于此類密碼系統(tǒng)。

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

1、消息空間M(Message)；

2、密文空間C(Ciphertext)；

3、密鑰空間K(Key)；

4、加密算法E(Encryptionalgorithm)和

5、解密算法D(Decryptionalgorithm)o

加密密鑰Kl解密密鑰K2

明文原始明文

解密

第二章：對(duì)稱密碼學(xué)

圖2-1密鑰加/解密系統(tǒng)模型

消息空間中的消息M(稱之為明文)通過(guò)由加密密鑰

K1控制的加密算法加密后得到密文Co密文C通過(guò)解密密

鑰K2控制的解密算法又可恢復(fù)出原始明文M。即：

EKI(⑷=C

DK2(C)=M

DK2(EKI(M))=M

在圖2-1的加/解密系統(tǒng)模型中，當(dāng)算法的加密密鑰能

夠從解密密鑰中推算出來(lái)，或反之解密密鑰可以從加密密鑰

中推算出來(lái)時(shí)，稱此算法為對(duì)稱算法，也稱秘密密鑰算法或

單密鑰算法。稱加密密鑰和解密密鑰不同并且其中一個(gè)密鑰

不能通過(guò)另一個(gè)密鑰推算出來(lái)的算法為公開(kāi)密鑰算法。

在現(xiàn)代密碼學(xué)中，所有算法的安全性都要求是基于密鑰

的安全性，而不是基于算法細(xì)節(jié)的安全性。也就是說(shuō)，只要

密鑰不公開(kāi)，即使算法公開(kāi)并被分析，不知道密鑰的人也無(wú)

法理解你所加密過(guò)的消息。

2.2古典密碼

在計(jì)算機(jī)出現(xiàn)之前，密碼學(xué)由基于字符的密碼算法構(gòu)

成。不同的密碼算法之間互相替代(Substitution)或相

互置換(Transposition),好的密碼算法是結(jié)合這兩種

方法，每次進(jìn)行多次運(yùn)算?，F(xiàn)在的計(jì)算機(jī)密碼算法要復(fù)雜的

多，但基本原理沒(méi)有變化。其重要的變化是算法只對(duì)位而不

是字母進(jìn)行變換，也就是字母表長(zhǎng)度從26個(gè)字母變?yōu)?個(gè)

字母。大多數(shù)好的密碼算法仍然是以替代和置換作為加密技

術(shù)的基本構(gòu)造塊。

20

2.2.1替代密碼

替代密碼就是明文中的每一個(gè)字符被替換為密文中的另

外一個(gè)字符。接收者對(duì)密文進(jìn)行逆替換即可恢復(fù)出明文。在

古典密碼學(xué)中有三種類型的替代密碼：?jiǎn)伪硖娲艽a、多表

替代密碼和多字母替代密碼。

“單表替代密碼

所謂的單表替代密碼(Monoalphabetic)就是明文的

每一個(gè)字符用相應(yīng)的另外一個(gè)唯一的密文字符代替。最早的

密碼系統(tǒng)“凱撒密碼”就是一種單表替代密碼，也是一種移

位替代密碼。凱撒密碼是對(duì)英文的26個(gè)字母分別向前移3

位，于是可以得到其替代表為：

明文：abcdefghijklmnopcr

stnv~不x-y~z

密文：DEFGH工JKLMNOPQRSTU

VWXYZABC

例2.1:對(duì)明文：

networksecurity

則密文為：

QHWZRUNVHFXULWB

如將26個(gè)字母分別對(duì)應(yīng)于整數(shù)。?25,可得凱撒密碼變

換為：

力口密：E(m)=(m+3)mod26

解密：D(c)=(c-3)mod26

凱撒密碼的密鑰k=3。更一般化的移位替代密碼變換

為：

加密:E(m)=(m+k)mod26

解密：D(c)=(c-k)mod26

第二章：對(duì)稱密碼學(xué)

顯然，這種密碼系統(tǒng)是不安全的，它非常容易攻破。首

先，簡(jiǎn)單的單表替代沒(méi)有掩蓋明文不同字母出現(xiàn)的頻率；其

次，移位替代的密鑰空間有限，只有25個(gè)密鑰，利用暴力

攻擊法很容易破解。因此，替代密碼應(yīng)該有更大的密鑰空

間，關(guān)鍵詞（Keyword）密碼就是這樣一種加密方法。

、關(guān)鍵詞（Keyword）密碼

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

1.選擇一個(gè)關(guān)鍵詞，如果關(guān)鍵詞中包含有重復(fù)的字

母，則后續(xù)出現(xiàn)的該字母一律刪除。例如，對(duì)于關(guān)

鍵詞"xidian”,則最終使用的詞是

x1da.no

2.將關(guān)鍵詞寫(xiě)在字母表的下方，剩下的空間用其余的

字母按照字母順序進(jìn)行填寫(xiě)。

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

表如下：

明文：ABCDEFGHIJKLMNOPQR

sLpp—v-w—x-Y—z---------------------------------------------

密文：KRYPTOSABCDEFGHIJL

MNQUVWXZ

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

下：

明文：CRYPTOGRAPHY工SCOOL

密文：YLX工NHSLK工AXBMYHHE

關(guān)鍵詞加密方法的最大安全缺陷在于其很容易受到頻率

分析攻擊。

22

在密碼學(xué)中，所謂的頻率分析是指字母或者字母組合在

密文中出現(xiàn)的頻率。許多的古典密碼都可以用這種方法進(jìn)行

破解。

頻率分析是基于這樣一個(gè)事實(shí)：在任何一種書(shū)面語(yǔ)言

中，不同的字母或字母組合出現(xiàn)的頻率各不相同。而且，對(duì)

于以這種語(yǔ)言書(shū)寫(xiě)的任意一段文本，都具有大致相同的字母

分布特征。比如，在英語(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”。

A

u

u

a

n

b

a

±

3

lA

ro

a-

Q:

圖2-2英文字母出現(xiàn)頻率統(tǒng)計(jì)

第二章：對(duì)稱密碼學(xué)

有了這些信息，我們?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)一步降低破解難度。

Z仿射加密方法(AffineCipher)

在仿射加密方法中，每個(gè)字母被賦予一個(gè)數(shù)字，例如字

母a=0,字母b=L......,字母z=25。加密密鑰為0?25之

間的數(shù)字對(duì)(a,b)o

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

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

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

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

1=aoT1modm.

模乘法逆元有唯一解的充要條件是a和26(m)的最大

公約數(shù)：gcd(az26)=lo

例2.3：下面我們對(duì)明文“AFFINECIPHER"進(jìn)行加

密，其中a=5,b=8o整個(gè)加密過(guò)程如下表所示：

明文AFFINECIPHER

對(duì)應(yīng)整數(shù)11

05584287417

值_______35

24

3347214842

5x+8893

3383888338

(5x+8)(mo22121

87725215

d26)21827

密文THHWVCSWFRCP

解密時(shí)首先計(jì)算a-1是21,然后利用解密函數(shù)解密，過(guò)

程如下：

密文：IHHWVCSwFRCP

對(duì)應(yīng)整數(shù)值：877222121822517215

21(y-8):0-21-21294273210294-63189147

126126

：21(y-8)]

055813428157417

mod26:

明文：AFFINECIPIIER

由于仿射密碼仍然是一種單表替換密碼，因此它也存在

此類密碼所固有的缺陷。前述的頻率分析方法同樣適用。

在考慮加密英文消息時(shí)，m=26,此時(shí)總共有286種仿

射密碼，其中沒(méi)有包含26種簡(jiǎn)單的凱撒密碼。這主要是因

為同26互為素?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ù)秘鑰。而且我們

第二章：對(duì)稱密碼學(xué)

知道a和m必須互為素?cái)?shù)，這也有助于判斷解方程得到的

結(jié)果是否正確。

“多表替代密碼

多表替代密碼是以一系列的（兩個(gè)以上）替代表依次對(duì)

明文消息的字母進(jìn)行替代的加密方法。

多表替換加密形式是：其中的每個(gè)明文字母可以被密文

中的不同字母來(lái)代替，而每個(gè)密文字母也可以表示多個(gè)明文

字母。這種加密法可以干擾字母出現(xiàn)頻率分析法。著名的

Vigenere加密法就是其中的一種，它在長(zhǎng)達(dá)三百多年的時(shí)

間里都被認(rèn)為是不可破解的。

Vigenere力口密過(guò)程如下：

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

1,將關(guān)鍵詞重復(fù)地寫(xiě)在明文的上方，直至兩者長(zhǎng)度

相等。

2.密文通過(guò)查詢Vigenere表得到。其中關(guān)鍵詞字

母確定表的行，明文字母確定表的列，如下圖所示。

26

ABCDEFGHIJKLMNOPQRSTUVWXYZ

AABODEFGHIJKLMN0PQRSTUVWXYZ

BBCDEFGN0PQRSTUVWXYZA

CCDEFHIJKLMN0PQRSTUVWXYZAB

DDEFGHIJKLMN0PQRSTUVWXYZABC

EEFGHIJ0PQRSTUVWXYZABCD

FFGHIJ0PQRSTUVWXYZABCDE

GGHIJKLM0PQRSTUVWXYZABcDEF

HIJLMN0PQRSTUVWXYZABCDEFG

IIN0PQRSTUVWXYZABCDEFG

JJ0PQRSTUVWXYZABCDEFGI

NPQRSTUVWXYZABCDEFGHIJ

0PQRSTUWXYZABCDEFGHIJ

M0PQRSTUVXYZABCDEFGH[T]JKL

N0PQRSTUVWYZABCDEFGHIJKLM

00PQRSTUVWXZABCDEFGH

PPQRSTUVWXYZABCDEFGN0

QQRSTUVWXYZABCDEFGIJ0P

RRSTUVWXYZABCDEFG0PQ

SSTUVWXYZABCDEFGHIM0PQR

TTUVWXYZABCDEFGINPQRS

UVWXYZABCDEFGHILM0PQRST

VVWXYZABCDEFGIMN0PQRSTU

wWXYZABCDEFGIKLMN0PQRSTUV

XYZABCDEFGHILMN0PQRSTUVW

圖2-3Vigenere替換表

3.行與列的交叉處得到對(duì)應(yīng)密文。

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

關(guān)鍵MECMECMECMECME

詞CMECMECM

明文;eneedmoresupp

iesfast

密文《IPQIFYSTQWWBT

uIUREUF

從中，我們可以看到，字母'e'有時(shí)候被加密成

'I’,有時(shí)候被加密成'Q'。而且，密文中的I表示了

兩個(gè)不同的明文字母‘w'和'e'。這種變換特性使得頻

第二章：對(duì)稱密碼學(xué)

率分析方法在此變得無(wú)能為力。顯然，出現(xiàn)頻率很高的字母

'e'被替換成了出現(xiàn)頻率不怎么高的‘I'和'Q',而

且密文中的連續(xù)出現(xiàn)的兩個(gè)相同字母，如‘II'或'W

W'所對(duì)應(yīng)的明文字母并不相同。

當(dāng)然，這并不意味著沒(méi)有辦法來(lái)破解Vigenere加密法。

幸運(yùn)的是，F(xiàn)rederickKasiski通過(guò)觀察發(fā)現(xiàn)：明文中重復(fù)出

現(xiàn)的字符串與關(guān)鍵詞密鑰的重復(fù)部分加密會(huì)得到重復(fù)密文字

符串，如圖2-4所示：

密

鑰：runrunrunrunrunrunrun

runrunrun

明

文:tobeornottobethatisth

equestion

密

文:kiovieeigkiovnurnvjnu

vkhvmgzia

9-------II----6

圖2-4Vigenere密碼分析

在上例中，兩次“kiov”之間的距離為9,“nu”之間的

距離為6,由此我們可以猜測(cè)這些距離應(yīng)該是密鑰長(zhǎng)度的倍

數(shù)，密鑰長(zhǎng)度可能為3。因此密文中重復(fù)字符串之間的距離

反映了密鑰重復(fù)的次數(shù)和密鑰的長(zhǎng)度，于是

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

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

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

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

數(shù)）

28

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

有了關(guān)鍵詞長(zhǎng)度，我們就可以將與關(guān)鍵詞中用同一個(gè)字

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

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

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

run中的r字符所對(duì)應(yīng)的密文整合在一起，即kvekvijvvz...,

它們都是由同一個(gè)密鑰加密得到的移位加密密文。所以，一

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

（關(guān)鍵字長(zhǎng)度為n）個(gè)不同的單表加密問(wèn)題。

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

提出了基于凹凸度量（MR）的方法。我們知道，英語(yǔ)中每

個(gè)字符出現(xiàn)的概率都是不一樣的，繪成頻率分析圖，圖中就

有高峰與低谷，單表加密法是沒(méi)有辦法改變字母出現(xiàn)的概率

的，但是對(duì)于多表加密法，得到的字母頻率圖就變得很平

滑。完全平滑的分布就是每個(gè)字母等概率（1/26）出現(xiàn)的情

況。凹凸度量是指從文本中選取的字母的實(shí)際概率與從完全

平滑的分布中選取該字母的概率之差。

設(shè)才是從密文中選取“字母的概率，那么上述的概率偏差

即為優(yōu)-1/26）2。加平方是為了保證得到的值為正值。設(shè)才為

完全偏差，因此。至人所有字母的偏差和為

MR=6（2-1/26）2

a=a

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

MR=￡p：-1/26

a=a

對(duì)于某個(gè)密文，如果估算出‘2,那么用R就能確定。由于

《，為從密文中選取字母a的概率，那么中就是從全部密文中

選取字母a的概率和從剩余密文中（即去掉第一個(gè)a字母的密

文）中選取字母〃的概率的乘積。如果密文中有〃個(gè)字母，

凡是密文中a字母的個(gè)數(shù)，那么

第二章：對(duì)稱密碼學(xué)

匕=工/〃，乙2=優(yōu)/〃).［優(yōu)—

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

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

(IndexofCoincidence,IC)來(lái)分析多表加密法。IC定義

為：

通過(guò)分析和資料，我們得知單表加密法的IC大概為

0.066o完全平滑的文字，其值為0.38,如果IC的值在0.38

到0.066之間，就說(shuō)明該密文很可能就是多表加密法。事實(shí)

上，通過(guò)下圖，我們能得知IC值暗示的多表加密法的密鑰

長(zhǎng)度：

密鑰長(zhǎng)度IC值

10.0660

20.0520

30.0473

40.0450

50.0436

60.0427

70.0420

80.0415

90.0411

100.0408

110.0405

120.0403

圖2-5IC值和秘鑰長(zhǎng)度關(guān)系

—多字母(Polygraphic)替代密碼

30

多字母替代密碼是每次對(duì)多于1個(gè)字母進(jìn)行替代的加密

方法，它的優(yōu)點(diǎn)在于將字母的自然頻度隱蔽或均勻化，從而

利于抗統(tǒng)計(jì)分析。

^iPlayfair密碼算法

Playfair密碼采用一個(gè)包含密鑰的5x5矩陣進(jìn)行加密

解密。矩陣首先用去掉重復(fù)字母的密鑰進(jìn)行填充，然后用剩

余的字母按照順序進(jìn)行填充。圖2-6給出了密鑰為

"playfairexample"的加解密矩陣（注意,工和J被認(rèn)

為是同一個(gè)字母）。

PLAYFA

IREXM?LEA

BCD^GH=J

KLMNOPQRS

TUVWxZ

圖2-6Playfair加解密矩陣

加密消息前，把消息明文按兩個(gè)字母一組進(jìn)行分割，如

果這個(gè)兩個(gè)字母相同，則插入一個(gè)空字符，比如'X'。若

明文消息的字母?jìng)€(gè)數(shù)為奇數(shù)時(shí)，將空字母X加在明文的末

端。

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

1.ml和m2在同一行時(shí)，則密文cl和c2分別是緊靠

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

舉例如下：

第二章：對(duì)稱密碼學(xué)

PLAY

EX

IRE>X

形狀:行

BCDGH規(guī)則:以右邊字符替換

KNOQS

XM

TUVWZ

2.若ml和m2在同一列時(shí)，貝ll密文cl和c2分別是緊

靠ml、m2下方的字母。其中第一行看作是最后一行的上

方。

PLFDE

IRXM

形狀：列

BCGH規(guī)則：以下邊字符替換

KNQS

TUWZ0D

3.若ml和m2不在同一行，也不在同一列時(shí)，則密文

cl和c2是由ml和m2確定的矩形的其他兩角的字母，并

且cl和ml、c2和m2同行。

PLAYF

HI

IREX>M形狀：矩形

B<G-D-G-H規(guī)則：以同一行對(duì)角

字符替換

KN0QS

BM

TUVWZ

例2.5：首先對(duì)加密消息“Hidethegoldinthe

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

HIDETHEGOLDINTHETREXESTUMP

A

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

BMODZBXDNABEKUDMUIXMMOUVIF

32

“Playfair密碼分析

破解和分析Playfair密碼的第一步就是要確定你所

分析的密碼確實(shí)是采用的Playfair加密的。這通?？梢?/p>

通過(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ò)程：

---J搜尋匹

配模式

構(gòu)造可

能矩形

圖2-7playfair密碼分析步驟

第二章：對(duì)稱密碼學(xué)

2.2.2置換密碼

在置換密碼中，明文和密文的字母保持相同，但順序被

打亂了。置換密碼使用的密鑰通常是一些幾何圖形，它決定

了明文字母被重新排列得順序和方式。

ZSkytale加密法（天書(shū)）

Skytale就是一種加密用的、具有一定粗細(xì)的棍棒或權(quán)

杖，如圖2-8所示。

圖2-8Skytale天書(shū)

斯巴達(dá)人把皮革或羊皮紙纏繞在特定直徑的木棍上，寫(xiě)好

文字以后再把皮革或羊皮紙解下來(lái)，紙上的字母順序就頓時(shí)

歪七扭八，就誰(shuí)也不認(rèn)識(shí)了；只有把皮（紙）帶再一點(diǎn)點(diǎn)卷

回與原來(lái)加密的Skytale同樣粗細(xì)的棍棒上后，文字信息

逐圈并列在棍棒的表面，才能還原出本來(lái)的意思。

實(shí)際上天書(shū)就是一種簡(jiǎn)單的縱行置換密碼。明文以固定

的寬度水平地寫(xiě)在一張圖表紙上，密文按垂直方向讀出；解

密就是將密文按相同的寬度垂直的寫(xiě)在圖表紙上，然后水平

的讀出明文。

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

34

encryptionisthetransformationofdata

intosomeunreadableform

一ncryPtion

isthetrans

formationo

fdataintos

omeunreada

b1一form

密文：eiffobnsodmlctraeerhmtufyeaano

pttirrtrinemiaotaonnodnsosa

在填寫(xiě)某個(gè)圖表時(shí)，可以采用各種形狀的幾何圖形，如

rail-fence（柵欄）加密時(shí)采用對(duì)角線方式寫(xiě)入，然后按

行讀出即可得到密文，如圖2-9所示：

T...E

.E.R.D.S.O.E.E.F.E.A.

O.C.

N..

圖2-9柵欄密碼

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

WECRLTEERDSOEEFEAOCAIVDEN

圖2-10給出了按照三角形方式填充的加密方法，按列

讀取就是對(duì)應(yīng)的密文。

EAR

EDISC

OVEREDF

LEEATONCE

第二章：對(duì)稱密碼學(xué)

圖2-10三角形置換密碼

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

LOEEVEEDEAWAIRTRSEOEDNFCE

'列置換密碼

在列置換密碼中，消息按照固定長(zhǎng)度的行寫(xiě)入，然后按

照某種順序逐列讀出，即可得到密文。行的寬度和列的置換

順序由一個(gè)關(guān)鍵詞或者密鑰來(lái)控制。例如，對(duì)于秘鑰

“crypt。”，總共包含6個(gè)字母，因此加密矩陣有6歹U。

然后秘鑰中各個(gè)字母在字母表中的順序?yàn)椋?、4、6、3、

5、2,因此相應(yīng)的列置換順序?yàn)椤?46352”。也就

是說(shuō)，密文的第一列仍然是明文矩陣的第一列，而密文的第

二列則是明文矩陣的第六列，以此類推。

對(duì)于消息明文“WEAREDISCOVERED.FLEEAT

ONCE.”和密鑰“crypto”，其對(duì)應(yīng)的明文矩陣和置換規(guī)

則如下圖所示：

146352

WEARED

ISCOVE

REDFLE

EAT0NC

EQKJEU

圖2-n列置換密碼

圖中最后5個(gè)字母稱為空字符，用于填滿矩陣最后一

行，這種列置換密碼稱為規(guī)則列置換矩陣。對(duì)于非規(guī)則列置

換密碼，矩陣最后一行不進(jìn)行任何填充。

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

WIREEDEECUROFOJESEAQEVLNEACDTK

36

?置換密碼分析

由于置換密碼并不影響單個(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é)開(kāi)始將介紹兒種對(duì)稱密碼系統(tǒng)。首先介紹一種

最通用的計(jì)算機(jī)加密算法一數(shù)據(jù)加密標(biāo)準(zhǔn)DES(Data

EncryptionStandard)。

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

對(duì)稱密碼算法有兩種類型：分組密碼(Block

Cipher)和流密碼(StreamCipher)。分組密碼一■次

處理一塊輸入，每個(gè)輸入塊生成一個(gè)輸出塊，而流密碼對(duì)輸

入元素進(jìn)行連續(xù)處理，同時(shí)產(chǎn)生連續(xù)單個(gè)輸出元素。數(shù)據(jù)加

密標(biāo)準(zhǔn)DES屬于分組密碼。分組密碼將明文消息劃分成固

定長(zhǎng)度的分組，各分組分別在密鑰的控制下變換成等長(zhǎng)度的

密文分組。分組密碼的工作原理如下圖：

第二章：對(duì)稱密碼學(xué)

X比特密鑰X比特密鑰

Tt

圖2-12分組密碼工作原理

2.3.2DES的歷史

數(shù)據(jù)加密標(biāo)準(zhǔn)成為世界范圍內(nèi)的標(biāo)準(zhǔn)已經(jīng)20多年了。

1973年，美國(guó)國(guó)家標(biāo)準(zhǔn)局(NBS)在認(rèn)識(shí)到建立數(shù)據(jù)保護(hù)

標(biāo)準(zhǔn)既明顯又急迫需要的情況下，開(kāi)始征集聯(lián)邦數(shù)據(jù)加密標(biāo)

準(zhǔn)的方案。1975年3月17日，NBS公布了工BM公司提供

的密碼算法，以標(biāo)準(zhǔn)建議的形式在全國(guó)范圍內(nèi)征求意見(jiàn)。經(jīng)

過(guò)兩年多的公開(kāi)討論之后，1977年7月15日，NBS宣布

逑受這個(gè)建議，作為聯(lián)邦信息處理標(biāo)準(zhǔn)46號(hào)⑵，數(shù)據(jù)加密

標(biāo)準(zhǔn)(DataEncryptionStandard),即DES正式頒

布，供商業(yè)界和非國(guó)防性政府部門使用。

DES是一種典型的分組密碼，一種將固定長(zhǎng)度的明文通

過(guò)一系列復(fù)雜的操作變成同樣長(zhǎng)度的密文的算法。對(duì)DES

而言，分組長(zhǎng)度為64位。同時(shí)，DES使用密鑰來(lái)自定義變

38

換過(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使用的幾種模式⑶。

2.3.3DES算法的描述

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

64比特明文輸入

第二章：對(duì)稱密碼學(xué)

32-bitLo32-bitRo

40

64比特密文輸出

圖2-13DES加密算法

?初始置換函數(shù)IP

DES對(duì)64位明文分組進(jìn)行操作。首先64位明文分組x

經(jīng)過(guò)一個(gè)初始置換函數(shù)HP,產(chǎn)生64位的輸出xo，再將分

組X。分成左半部分L。和右半部分R。。即：

x()=IP(x)=LQRQO

置換表如表2.1。此表順序?yàn)閺纳系较拢瑥淖笾劣?。?/p>

初始置換把明文的第58位換至第1位的位置，把第50位

換至第二位。以此類推。

表2.1初始置換IP

55432112

8024680

65432214

0246802

65433216

2468024

65443218

4680246

54432191

791357

55432113

9135791

65432215

1357913

65433217

3579135

第二章：對(duì)稱密碼學(xué)

"獲取子密鑰Ki

DES加密算法的密鑰長(zhǎng)度為56位，但一般表示為64

位，其中每個(gè)第8位用于奇偶校驗(yàn)。在DES加密算法中，

要利用用戶提供的64位初始密鑰經(jīng)過(guò)一系列的處理得到

Ki，K2,.…，K16,分別作為1916輪運(yùn)算的16個(gè)子密

鑰。現(xiàn)在來(lái)看如何獲得這16個(gè)子密鑰。

首先，將64位密鑰去掉8個(gè)校驗(yàn)位，用密鑰置換PC-1

置換剩下的56位密鑰；再將56位分成前28位Co和后28

位Do。即：PC-1(K56)=CODOO密鑰置換PC-1如表2.2所

示：

表2.2密鑰置換PCT

5443219

791367

1554321

802468

1255432

091357

1136543

910246

6543321

3579135

7654332

246802

1665432

413579

2152214

13802

接下來(lái)，根據(jù)輪數(shù)這兩部分分別循環(huán)左移1位或2位。

具體每輪移位的位數(shù)見(jiàn)表2.3：

42

表2.3每輪移動(dòng)的位數(shù)

輪

1234567891111111

次

0123456

位1122222212222221

數(shù)

移動(dòng)后，將兩部分合并成56位后通過(guò)壓縮置換PC-2后

得到48位子密鑰。即：

Ki=PC-2(CiDi)o壓縮置換如表2.4：

表2.4壓縮置換PC-2

11121532

47148

16212114

510392

28172212

66703

45334534

12177500

54344435

15384996

35445323

43620692

綜上所述，整個(gè)子密鑰獲得過(guò)程如圖2-14：

第二章：對(duì)稱密碼學(xué)

64位密鑰

1f0

圖2-14子密鑰產(chǎn)生

?密碼函數(shù)f

密碼函數(shù)f的輸入是32比特?cái)?shù)據(jù)和48比特的子密鑰,

其操作步驟如圖2-15：

44

32比特48比特子密鑰

圖2-157(Ri,R)計(jì)算

1、擴(kuò)展置換(E)

將數(shù)據(jù)的右半部分J從32位擴(kuò)展為48位。位選擇函

數(shù)(也稱E-盒)如表2.5:

表2.5擴(kuò)展置換E

312345

2

456789

891111

0123

111111

234567

222222

012345

223331

89012

2、異或

擴(kuò)展后的48位輸出E(^)與壓縮后的48位子密鑰匕

作異或運(yùn)算。

第二章：對(duì)稱密碼學(xué)

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)制表示：

表2.6DESS盒

S0123456789ABCDEF

1

0E4D12FB83A6C5907

10F74E2D1A6CB9538

241E8D62BFC973A50

3FC8249175B3EA06D

S0123456789ABCDEF

2

0F18E6B34972DC05A

13D47F28EC01A69B5

20E7BA4D158C6932F

3D8A13F42B67C05E9

S0123456789ABCDEF

3

0A09E63F51DC7B428

1D709346A285ECBF1

2D6498F30B12C5AE7

31AD069874FE3B52C

S0123456789ABCDEF

4

46

07DE3069A1285Bc4F

1D8B56F03472C1AE9

2A690CB7DF13E5284

33F06A1D8945BC72E

S0123456789ABCDEF

5

02C417AB6853FD0E9

1EB2C47D150FA3986

2421BAD78F9C5630E

3B8C71E2E6F09A453

S0123456789ABCDEF

6

0C1AF92680D34E75B

1AF427C9561DE0B38

29EF528C3704A1DB6

3432C95FABE17608D

S0123456789ABCDEF

7

04B2EF08D3C975A61

1D0B7491AE35C2F86

214BDC37EAF680592

36BD814A7950FE23C

S0123456789ABCDEF

8

第二章：對(duì)稱密碼學(xué)

0D28E6FB1A93E50C7

11FD8A374C56B0E92

27B419CE206ADF358

321E74A8DFC90356B

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開(kāi)

始計(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歹I］。從表中可得S盒8的

第1行第5列的數(shù)為30于是就用0011代替原輸入

OOlOllo

4、P盒置換

將8個(gè)S盒的輸出連在一起生成一個(gè)32位的輸出，輸

出結(jié)果再通過(guò)置換PoP產(chǎn)生一個(gè)32位的輸出即：

f（RizKi）o至此，密碼函數(shù)f的操作就完成了。表2.7為

P盒置換。

48

最后，將P盒置換的結(jié)果與最初的64位分組的左半部分

異或，然后左、右半部分交換，接著開(kāi)始下一輪計(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)⑷。所謂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ú)立，對(duì)任意的

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è)〃X機(jī)的S盒

其輸入為n比特，輸出為m比特。DES的S盒大小為6x4。

第二章：對(duì)稱密碼學(xué)

S盒越大，就越容易抵制差分和線性密碼分析⑷。一般在實(shí)

踐當(dāng)中，通常選擇n在8到10之間。

Mister和Adams⑸提出了很多的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^］提出了以下幾種s盒的設(shè)計(jì)和實(shí)踐原則：

□隨機(jī)性：采用某些偽隨機(jī)數(shù)發(fā)生器或隨機(jī)數(shù)表格來(lái)產(chǎn)

生S盒的各個(gè)項(xiàng)。

□隨機(jī)測(cè)試：隨機(jī)選擇S盒各個(gè)項(xiàng)，然后按照不同準(zhǔn)則

測(cè)試其結(jié)果。

□數(shù)學(xué)構(gòu)造：根據(jù)某些數(shù)學(xué)原理來(lái)產(chǎn)生S盒。其好處就

是可以根據(jù)數(shù)學(xué)上的嚴(yán)格證明來(lái)抵御差分和線性密碼

分析，并且可以獲得很好的擴(kuò)散(Diffusion)特

性。

?末置換

末置換是初始置換的逆變換。對(duì)L0和Ro進(jìn)行16輪完全

相同的運(yùn)算后，將得到的兩部分?jǐn)?shù)據(jù)合在一起經(jīng)過(guò)一個(gè)末置

換函數(shù)就可得到64位的密文