第三章分組密碼

一、分組密碼的一般模型

二、DES與IDEA

三、AES算法----Rijndael

四、分組密碼分析方法*

五、分組密碼工作模式

2011-7-101

爨

一、分組卷瑪?shù)囊话隳Ｐ?/p>

2011-7-10

2

分組密碼概述

?分組密碼:

將消息編碼表示后的數(shù)字（通常是。和1）序列

…劃分為長(zhǎng)為n的組x=（x0?x19

（長(zhǎng)務(wù)n的矣量）分別在密鑰左=（左o，K，…—的

控制下變換成等長(zhǎng)的輸出數(shù)字序列y=（

（長(zhǎng)為ni的矢量）。Iy（）‘歹1'rrt—i/

"化0，勺，……,卜二國(guó)見…

■分組密碼是一種滿足下列條件的映射氏

F2；xSk”.F2；

?對(duì)每個(gè)k^Sk,E9,k）是從瑁到尸；〃的置換

?萬（?，左）：密鑰為左時(shí)的加密函數(shù)

?:密鑰為左時(shí)的解密函數(shù)

?密鑰規(guī)模：/=log2|5jbit

?密鑰長(zhǎng)度等于密鑰規(guī)模當(dāng)且僅當(dāng)：Sk=F；

Eg:DES真正的密鑰規(guī)模片56bit,且，也就是密鑰長(zhǎng)度

2011-7-104

分組密碼設(shè)計(jì)問題

分組密碼的設(shè)計(jì)問題在于找到一

種算法，能在密鑰控制下從一個(gè)足

夠大且足夠好的置換子集中，簡(jiǎn)單

而迅速地選出一個(gè)置換，用來對(duì)當(dāng)

前輸入的明文的數(shù)字組進(jìn)行加密變

換。

2011-7-105

分組密碼算法應(yīng)滿足的要求*

?分組長(zhǎng)度〃要足夠大：

防止明文窮舉攻擊法奏效。

?密鑰量要足夠大：

盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮

舉攻擊奏效。

?由密鑰確定置換的算法要足夠復(fù)雜：

充分實(shí)現(xiàn)明文與密鑰的擴(kuò)散和混淆，沒有簡(jiǎn)單的關(guān)系可循

,要能抗擊各種已知韻&走

2011-7-106液壽/李

分組密碼算法應(yīng)滿足的要求

?加密和解密運(yùn)算簡(jiǎn)單：

易于軟件和硬件高速實(shí)現(xiàn)。

?數(shù)據(jù)擴(kuò)展：

一般無數(shù)據(jù)擴(kuò)展，在采用同態(tài)置換和隨機(jī)化加密技術(shù)時(shí)

可引入數(shù)據(jù)擴(kuò)展。

?差錯(cuò)傳播盡可能地小

2011-7-107

二、DES與IDEA

2011-7-10

8

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

?DES的歷史

-1971年IBM,由HorstFeistel領(lǐng)導(dǎo)的密碼研究項(xiàng)目

組研究出LUCIFER算法，并應(yīng)用于商業(yè)領(lǐng)域；

-1973年，美國(guó)標(biāo)準(zhǔn)局征求標(biāo)準(zhǔn)，IBM提交結(jié)果;

-1977年，被選為數(shù)據(jù)加密標(biāo)準(zhǔn)；

-雖然DES已有替代的數(shù)據(jù)加密標(biāo)準(zhǔn)算法，但它仍

是迄今為止得到最廣泛應(yīng)用的一種算法，也是一

種最有代表性的分組加密體制。

2011-7-109

廠^密過程

/將64bit明文位置進(jìn)行醫(yī)J

{換，得到一個(gè)亂序的64

bit明文組，而后平分成

?班右兩段，IP中各列元素位號(hào)數(shù)

/相差為8,相當(dāng)于將原明文各字

節(jié)按列寫出，各列比特經(jīng)過,

\奇偶采樣置換后，再對(duì)各「

0V進(jìn)行逆序，將陣中元/

、會(huì)［二、素按行讀出構(gòu)成Am

?該舁法乂置換輸出產(chǎn)

?IP知I廠本義上

作用工X作用

將16輪迭代后給出的64

it組進(jìn)行置換，得到輸出

的密文組。輸出為陣中,

的元素按行讀罩J

—T的結(jié)果

2011-7-1010

?對(duì)F函數(shù)的說明：F(Ry,K)函數(shù)F以長(zhǎng)

度為32的比特串A=R(32bits)作第一個(gè)

輸入，以長(zhǎng)度為48的比特串變?cè)?/p>

J=K(48bits)作為第二個(gè)輸入。產(chǎn)生的輸

出為長(zhǎng)度為32的位串。

-對(duì)第一個(gè)變?cè)狝,由給定的擴(kuò)展函數(shù)E,將其

擴(kuò)展成48位串E(A);

-計(jì)算E(A)+J,并把結(jié)果寫成連續(xù)的8個(gè)6位串，

B=:b2b3b4b5b6b7b&

2011-7-1012

?a、

-使用8個(gè)S盒，每個(gè)Sj是一個(gè)固定的4x16

矩陣，它的元素取0到15的整數(shù)。給定長(zhǎng)度

為6個(gè)比特串如Bj=b]b2b3b4b5b6,計(jì)算Sj(B,

如下：1)也兩個(gè)比黨確定了Sj的行

r(0<=r<=3);而b2b3b4b5四個(gè)比特確定了Sj

的列數(shù)c(0<=c<=15)o最后Sj(Bj)的值為

S-盒矩陣Sj中r行c列的元素(r,c),得

g=Sj(Bj)。

JJJ

-最后，p為一個(gè)固定置換。

2011-7-1013

子密鑰的生成

?從密鑰K計(jì)算子密鑰：實(shí)際上，K是長(zhǎng)

度為64的位串，其中56位是密鑰，8位是奇偶

校驗(yàn)位(為了檢錯(cuò))，在密鑰編排的計(jì)算中

,這些校驗(yàn)位可略去。

一給定64位的密鑰K,放棄奇偶校驗(yàn)位(8,16,

?…64)并根據(jù)固定置換PO1來排列K中剩下的

位。PC-1(K)=CODO其中Co由PCI(K)的前28

位組成；D。由后28位組成。

一對(duì)1v=iv=16,計(jì)算C^LSjCCj-l)Di=LSi(D「l)

LSj表示循環(huán)左移2或1個(gè)位置，取決于i的的值。

2011-7-1015

子密鑰的生成

i=l,2,9和16時(shí)移1個(gè)位置，否則移2位置。

Ki=PC-2(GDi),PC-2為固定置換。

專之一共16輪，每一輪使用K中48位組成一個(gè)48比特

密鑰。可算出16個(gè)表，第i個(gè)表中的元素可對(duì)應(yīng)上

第i輪密鑰使用K中第幾比特！如：第7輪的表7:K7

取K中的比特情況：

52571112659103444512519

941325035364342336018

2871429474622515636139

4311338536255202337306

2011-7-1016

子密鑰的生成

DES加密的一個(gè)例子

?取16進(jìn)制明文X：0123456789ABCDEF

密鑰K為：133457799BBCDFF1

去掉奇偶校驗(yàn)位以二進(jìn)制形式表示的密鑰是

0001001001101001010110111100100110110111

1011011111111000

應(yīng)用IP,我們得到:

L0=ll001100000000001100110011111111

L1=RO=1111OOOO1O1O10101111000010101010

然后進(jìn)行16輪加密。

最后對(duì)L16,&6使用IP”得到密文：

85ES13540F0AB405

DES解密和加密使用同一算法，但子密鑰

使用的順序相反

201171018々孝/孝

DES的安全性

?互巾卜性：DES算法具有下述性質(zhì)。若明文組x逐位

取補(bǔ)，密鑰。逐位取補(bǔ)，即y=DESk(x),貝4桶=。￡5斤(亍)

?這種互補(bǔ)性會(huì)使DES在選擇明文破譯下所需

的工作量減半。

?絕大多數(shù)消息并無明文補(bǔ)分組。

?弱密鑰和半弱密鑰：DES算法在每次迭代時(shí)都

有一個(gè)子密鑰供加密用。如果給定初始密鑰A,各

輪的子密鑰都相同，即有曷=&=…=叫6,就稱給定

密鑰A為弱密鑰(Weakkey)。

2011-7-10

DES的安全性

若A為弱密鑰，則有：

11

DESk(DESk(x))=xDESk(DESk(x))=x

即以A對(duì)x加密兩次或解密兩次都可恢復(fù)出

明文。其加密運(yùn)算和解密運(yùn)算沒有區(qū)別。

?弱密鑰下使DES在選擇明文攻擊下的搜索量減

半

?如果隨機(jī)地選擇密鑰，弱密鑰所占比例極小，

而且稍加注意就不難避開。因此，弱密鑰的存

在不會(huì)危及DES的安全性。

2011-7-1020

DES的安全性

?DES的密鑰長(zhǎng)度可能太小

?DES的迭代次數(shù)可能太少

?S盒中可能有不安全因素

?DES的關(guān)鍵部分不應(yīng)當(dāng)保密

2011-7-1021

三重DESI

l.兩重DES力口密的強(qiáng)度一定等

￥價(jià)于112bit密鑰的密碼的強(qiáng)

度嗎？考慮對(duì)任意密鑰kl和

k2,能夠找出另一密鑰k3,使

■■■■42成[耳立M嗎H？=430，這種假設(shè)

2.若有明文密文對(duì)（P,。滿足弘=Ek2Mki【P]l，貝?

可得z=Ekl[P]=Dk2[C]o考慮這種攻擊的情

f況。

3.使用三個(gè)不同的密鑰做三次加密就能抵抗中

途相遇攻擊嗎？

2011-7-1022，步考/李

三重DES

?使用兩個(gè)密鑰做三次加密，實(shí)現(xiàn)方法為加密

—解密一加密，簡(jiǎn)記EDE(encrypt-decrypt-

encrypt)。

加密

KiK2Ki

三重DES

?加密：y=Ekl[Dk2[Ekl[x]]]

?解密：x=Dki[Ek2[Dki[y]]]

?破譯它的窮舉密鑰搜索量為2"2七5X1035量級(jí)，而用

差分分析破譯也要超過1052量級(jí)。此方案仍有足夠的

安全性。

?沒有針對(duì)三重DES的攻擊方法，它是一種較受歡迎的

DES替代方案。

?此方案已在ANSIX9.17和ISO8732標(biāo)準(zhǔn)中采用，并

在保密增強(qiáng)郵遞(PEM)系統(tǒng)中得至4利用。

2011-7-1024

IDEA算法

?IDEA的歷史

-1990年，瑞士的來學(xué)嘉(XuejiaLai)和

JamesMassey于1990年公布了IDEA密碼算

法第一版，稱為PES(ProposedEncryption

Standard);

-1991年，為抗擊差分密碼攻擊，他們?cè)鰪?qiáng)了

算法的強(qiáng)度，稱IPES(ImprovedPES);

一1992年，改名為IDEA(InternationalData

EncryptionAlgorithm)o

2011-7-1025

IDEA加密過程

?IDEA是一個(gè)分組長(zhǎng)度為

64bit的分組密碼算法

F2

,密鑰長(zhǎng)度為128bit（

抗強(qiáng)力攻擊能力比DESz

強(qiáng)），同一算法既可加

密也可解密。

?IDEA的“混淆”和“擴(kuò)Z6

散”設(shè)計(jì)原則來自三種

運(yùn)算，它們易于軟、硬G1G2

件實(shí)現(xiàn)（加密速度快）

2011-7-1026

1.在IDEA的模乘

運(yùn)算中）為什

么將模數(shù)取為

2再1,而不是

1.在其模加運(yùn)算中,為什么模數(shù)取為

216而不是216+1?

2011-7-10

IDEA力口密的總體方案圖

64位明文

128bit密鑰

子密鑰生成器

16/

1T

Z1Z52

28

IDEA的密鑰生成

?56個(gè)16bit的子密鑰從128bit的密鑰中生

成前8個(gè)子密鑰直接從密鑰中取出；

?對(duì)密鑰進(jìn)行25bit的循環(huán)左移，接下來的

密鑰就從中取出；

?重復(fù)進(jìn)行直到52個(gè)子密鑰都產(chǎn)生出來。

2011-7-1030

IDEA的解密

?加密解密實(shí)質(zhì)相同，但使用不同的密鑰；

?解密密鑰以如下方法從加密子密鑰中導(dǎo)出：

-解密循環(huán)I的頭4個(gè)子密鑰從加密循環(huán)10-1的頭

4個(gè)子密鑰中導(dǎo)出；解密密鑰第1、4個(gè)子密鑰

對(duì)應(yīng)于工、4加密子密鑰的乘法逆元；2、3對(duì)應(yīng)

2、3的加法逆元；

-對(duì)前8個(gè)循環(huán)來說，循環(huán)I的最后兩個(gè)子密鑰等

于加密循環(huán)9-I的最后兩個(gè)子密鑰；

201171031海考/呼

IDEA簡(jiǎn)介(Cont.)回

?實(shí)現(xiàn)上的考慮

一使用子分組：16bit的子分組；

-使用簡(jiǎn)單操作（易于加法、移位等操

作實(shí)現(xiàn)）；

-加密解密過程類似；

-規(guī)則的結(jié)構(gòu)（便于VLSI實(shí)現(xiàn)）。

201171032海考/呼

IDEA的安全性

?IDEA能抗差分分析和相關(guān)分析；

?IDEA似乎沒有DES意義下的弱密鑰；

?IDEA是PGP的一部分；

?BruceSchneier認(rèn)為IDEA是DES的最好

替代，但問題是IDEA太新，許多問題沒

解決。

2011-7-1033

s

三、AES算法?Rijindael

2011-7-10

34

AES的歷史

?1997年1月，美國(guó)NIST向全世界密碼學(xué)界發(fā)出征集21

世紀(jì)高級(jí)加密標(biāo)準(zhǔn)(AES------AdvancedEncryption

Standard)算法的公告，并成立了AES標(biāo)準(zhǔn)工祚研究

室，稍后制定了對(duì)AES的評(píng)估標(biāo)準(zhǔn)；

?1998年8月，在首屆AES候選會(huì)議上公布了AES的15個(gè)

候選算法，任由全世界各機(jī)構(gòu)和個(gè)人攻擊和評(píng)論；

?2000年4月，召開了第三屆AES候選會(huì)議，繼續(xù)對(duì)最后

的五個(gè)候選算法進(jìn)行討論；

?2000年10月，NIST宣布Rijndael作為新的AES,至此

,經(jīng)過三年多的討論，Rijndael終于脫穎而出。

2011-7-1035

AES的評(píng)估準(zhǔn)則w

?AES是公開的；

?AES為單鑰體制分組密碼；

?AES的密鑰長(zhǎng)度128/192/256bit;

?AES適于用軟件和硬件實(shí)現(xiàn)；

?AES可以自由地使用，或按符合美國(guó)國(guó)

家標(biāo)準(zhǔn)（ANST）策略的條件使用；

2011-7-1036

AES的評(píng)估準(zhǔn)則g

?滿足以上要求的AES算法，需按下述條

件判斷優(yōu)劣

-安全性

-代價(jià)：各種實(shí)現(xiàn)的計(jì)算效率（速度和存儲(chǔ)

需求），包括軟件實(shí)現(xiàn)、硬件實(shí)現(xiàn)和智能

卡實(shí)現(xiàn)等；

—算法和實(shí)現(xiàn)特性：包括算法的靈活性、簡(jiǎn)

潔性及其它因素。

2011-7-1037

Rijndael算法設(shè)計(jì)原理

?Rijndeal密碼的設(shè)計(jì)力求滿足以下標(biāo)準(zhǔn):

-抵抗所有的已知攻擊

-在多個(gè)平臺(tái)上速度快，編碼緊湊

-設(shè)計(jì)簡(jiǎn)單

-Rijndael沒有采用Feistel結(jié)構(gòu)，輪函數(shù)由3

個(gè)不同的可逆均勻變換構(gòu)成的，稱為3個(gè)

層

-均勻變換是指狀態(tài)的每個(gè)bit都用類似的方

法處理

2011-7-1038

寬軌跡策略

_____j

?“寬軌跡策略”是針對(duì)抗差分分析和線性分析提出

的；

?優(yōu)點(diǎn)：可以給出算法的最佳差分特征的概率即最佳

線性逼近的偏差邊界，由此可以分析算法抵抗差分

密碼及線性密碼分析的能力；

?實(shí)現(xiàn)方法：輪函數(shù)3層中的每層都有它自己的功能：

-線性混合層：確保多輪之上的高度擴(kuò)散；

-非線性層：將具有最優(yōu)的“最壞情況非線性特性”的

S盒并行使用；

-密鑰加層：?jiǎn)屋喿用荑€簡(jiǎn)單的異或到中間狀態(tài)上，實(shí)

現(xiàn)一次性掩蓋。

201171039海壽/李

Rijndael算法描述

?Rijndael是分組和密鑰都可變的迭代分組加密算法,

分組和密鑰長(zhǎng)度可分別為128,192,256位；

?加密之前，首先把數(shù)據(jù)塊寫成字的形式，其次把字

記為列的形式。算法中間的結(jié)果也需要分組，稱之

為狀態(tài)。狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示

,該陣列有4行，列數(shù)％為分組長(zhǎng)度除32;

?種子密鑰類似地以字節(jié)為元素的矩陣陣列表示，陣

列為4行，列數(shù)之為密鑰長(zhǎng)度除32;

?算法輪數(shù)由人和叫共同決定

2011-7-1040

Nb=6和Nk=4的狀態(tài)密鑰陣列

2011-7-10

分組和陣列中元素對(duì)應(yīng)關(guān)系

?分組下標(biāo)n

?陣列位置（i,j）

-i=nmod4,j=[n/4];n=i+4j

?輪數(shù)'與4和時(shí)對(duì)應(yīng)關(guān)系

回=4%=6Nb=8

%=4101214

%=6121214

%=8141414

2011-7-1042

明文MRijndael

加密過程

KNr-^T

▼

車侖|耳i

KN^

2011-7-10

雷2

,字節(jié)代換

非線性代換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)

進(jìn)行，并且代換表(S盒)可逆，記為

ByteSub(State),分兩步：

■將字節(jié)作為GF(28)上的元素映射到自己的

逆元

■將字節(jié)做如下的GF(2)上變換

—

V。10001ill0J

巧11000ill'1

(

111000112

11110001(

3+

(

111110004

01111100-5]

001111106]

(

」7000111117

2011-7-1044第

行移變換

?將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，記為

ShiftRow(State)o不同行的移位量不

同：

ClC2C3

-0行：不動(dòng)

-工行：循環(huán)左移C1字節(jié)4123

-2行：循環(huán)左移C2字節(jié)6123

-3行：循環(huán)左移C3字節(jié)

8134

移位量與分組長(zhǎng)度的關(guān)系

2011-7-1045海擇/冬

列混合變換

?列混合變換表示為MixColumn（State）

?將每列視為GF（29上多項(xiàng)式，與固定的

多項(xiàng)式C（X）進(jìn)行模X4+1乘法,要求c（X）

模X4+1可逆。

c(x)=,03!x3+!0rx2+,0rx+f02!

2011-7-1046

/密鑰加&?

?密鑰加表示為AddRoundKey(State)

?輪密鑰與狀態(tài)進(jìn)行逐比特異或。

?輪密鑰由種子密鑰通過密鑰編排算法得

到

?輪密鑰長(zhǎng)度與分組密鑰長(zhǎng)度相同

2011-7-1047

輪密鑰生成

?從種子密鑰到輪密鑰由密鑰擴(kuò)展和輪密鑰選取兩部

分組成。基本原則如下：

-輪密鑰的比特?cái)?shù)等于分組長(zhǎng)度乘以輪數(shù)加1;

一種子密鑰被擴(kuò)展成為擴(kuò)展密鑰。其中根據(jù)Nk>6

和Nk<=6兩種不同的情況，采取不同的主密鑰

擴(kuò)展方式；

-從擴(kuò)展密鑰中選取輪密鑰。第i個(gè)輪密鑰由輪密

鑰緩沖字W[Nb*i]到W[N*(i+1)]給出。如圖

G芹-^_________________________________

WoWiW2W3W4W5W6W7W8W9W10WilW12W13W14???

輪密鑰0輪密鑰1

Nb二6且Nk二4時(shí)的密鑰擴(kuò)展和輪密鑰選取

2011-7-1048

Rijndael的解密

VRijndael解密算法的結(jié)構(gòu)和加密算法

的結(jié)構(gòu)相同，其中的變換為加密算法變換

的逆變換，使用了一個(gè)稍有改變的密鑰編

制

2011-7-10

Rijndael算法的安全性

?對(duì)密鑰的選取沒有任何限制

-每輪常數(shù)的不同消除了密鑰的對(duì)稱性;

-密鑰擴(kuò)展的非線性消除了相同密鑰的可能性；

-加解密使用不同的變換，消除了在DES里出現(xiàn)的

弱密鑰和半弱密鑰存在的可能性。

?能有效地抵抗密鑰已知的攻擊方法的攻擊,

目前最有效的攻擊還是窮盡密鑰搜索攻擊

2011-7-1050

四，分組密巧分析方法

2011-7-10

51

分組密碼分析方法

?對(duì)分組密碼的分析方法主要有以下幾種

類型：

-窮盡密鑰搜索（強(qiáng)力攻擊）；

-差分密碼分析；

-線性密碼分析；

-相關(guān)密鑰密碼分析；

-中間相遇攻擊。

2011-7-1052

差分密碼分析

?1991年Biham和Shamir公開發(fā)表了差分密碼分析法

才使對(duì)DES一類分組密碼的分析工作向前推進(jìn)了一

大步。

?差分分析是迄今已知的攻擊迭代密碼最有效的方法

之一，基本思想是通過分析明文隊(duì)的差值對(duì)密文隊(duì)

的差值的影響來恢復(fù)某些密鑰比特。

?它對(duì)多種分組密碼和Hash函數(shù)都相當(dāng)有效，相繼

攻破了FEAL、LOKI、LUCIFER等密碼。

2011-7-1053

差分密碼分析

?它不是直接分析密文或密鑰的統(tǒng)計(jì)相關(guān)性，而是分

析明文差分和密文差分之間的統(tǒng)計(jì)相關(guān)性；

?給定分組長(zhǎng)度為〃的r輪迭代密碼，兩個(gè)〃比特串y和

Y*,定義其差分為A>y（8）（產(chǎn)尸。其中，九表示小

bits串集上的定義的特定群運(yùn)算，（產(chǎn)尸為產(chǎn)在群中

的逆元。

?由加密對(duì)可得差分序列△，△兒???,，，冢中/*和

是明文對(duì)Z甜是第i輪的輸出，他們同

時(shí)也是第i+1輪的輸入。第i輪的子密鑰記的，且有

?Yi=F（Y-,K）

2011-7-1054液壽/李

差分密碼分析

定義一'：L輪特征Q是一個(gè)差分序列：

其中，是明文對(duì)％和”的差分，a.(i<f<r)是第i輪輸出

y.和-*的差分。

II

?定義二：L輪特征的概率。=痣?，…一是在明文4和

子密鑰,獨(dú)立、均勻隨機(jī)時(shí)，明文對(duì)乙和%*

的差分為九的條件下，第，(1Wr)輪輸出匕和匕*的差

分為名的概率；

?定義三：在L輪特征。=痣?，…-中定義：

P1二尸@□

I'、/I|4一1，

即夕：表示在輸入差分為的條件下，輪函數(shù)內(nèi)的輸出

差分為名的概率

2011-7-1055液壽/李

差分密碼分析

?L輪迭代密碼的差分分析過程可以綜述為如下步

驟：

1.找出一個(gè)（）輪特征。（尸-1）=。0,2,…使得他

的概率達(dá)到最大或幾乎最大；

2,均勻隨機(jī)地選擇明為%并計(jì)算〃使得乙和%*的差分

為當(dāng)找出和在實(shí)際密鑰加密下所彳差的密文科.

,若最后一輪的子密鑰或獎(jiǎng)部分比特看2m個(gè)可能

值（1（＞歿）置相應(yīng)的2m個(gè)計(jì)數(shù)器，用,每

個(gè)，密文和心彳導(dǎo)到就」1，婀果花匕T

的墓分是，物與合相應(yīng)的計(jì)數(shù)器茄1A/

3.重復(fù)步驟2,直到1個(gè)或幾個(gè)計(jì)數(shù)器的值’明顯高于

其他計(jì)數(shù)器的值，輸出彳也們所對(duì)應(yīng)的字密鑰（或部

分比婷）

2011-7-1056

差分密碼分析的復(fù)雜度

?一種攻擊的復(fù)雜度可以分為兩部分：數(shù)據(jù)復(fù)

雜度和處理復(fù)雜度。

-數(shù)據(jù)復(fù)雜度是實(shí)施該攻擊所需輸入的數(shù)據(jù)量；

-處理復(fù)雜度是處理這些數(shù)據(jù)所需的計(jì)算量；

?差分密碼分析的數(shù)據(jù)復(fù)雜度是成對(duì)加密所需

的選擇明文對(duì)個(gè)數(shù)的兩倍，處理復(fù)雜度是從

莪出子密鑰展其部分比特的計(jì)算量，實(shí)際上

和r無關(guān)。而且由于輪函數(shù)是弱的，所以此計(jì)

算量在大多數(shù)情況下相對(duì)較小。因此，差分

密碼分析的復(fù)雜度取決于它的數(shù)據(jù)復(fù)雜度。

2011-7-1057

線性密碼分析

?線性密碼分析是對(duì)迭代密碼的一種已知明文攻擊。是

通過尋找一個(gè)給定密碼算法的有效的線性近似表達(dá)式

來破譯密碼家統(tǒng)；

?線形密碼分析的目標(biāo)是找出以下形式的有效的線性方

程：

pp"，…/U--

1<a,b<n1<c<m

其中，。

-尸…，一-是明文分組；

-C[1],C[2],-,…是密文分組；

-一是密鑰分組；

-定義/必，

2011-7-1058面壽/孝

線性密碼分析

1

?如果方程成立的概率尸H5，則稱該方程是有

效的線性逼近；

1

?如果尸—3是最大的，則稱該方程是最有效的

線性遢近。

?設(shè)N表示明文數(shù)，T是使方程左邊為。的明文數(shù):

0,(夕>%)

則鏟內(nèi)，左2，，勺］二

-如果T>N/2,1,("%)

。,(0<%)

則^^出［,k2,,kA=v

一如果TVN/2,

2011-7-1059

線性密碼分析

?從而可得關(guān)于密鑰比特的一個(gè)線性方程，對(duì)不同的

明密文對(duì)重復(fù)以上過程可得關(guān)于密鑰的一組線性方

程，從而確定出密鑰比特

?研究表明，當(dāng)p—上無分小時(shí)，攻擊成功的概率是:

2

2

1%

1嚴(yán)一"歹

聲L詞公

這一概率只依賴于,并隨著N或。-《的增

加而增加

2011-7-1060

當(dāng)前研究熱點(diǎn)

如何對(duì)差分密碼分析和線性密碼

分析進(jìn)行改進(jìn)，降低它們的復(fù)雜度

仍是現(xiàn)在理論研究的熱點(diǎn)。

2011-7-1061

五、分組巧的工作模式

2011-7-10

62

主要工作模式

?分組密碼可以按不同的模式工作，實(shí)際

應(yīng)用的環(huán)境不同應(yīng)采用不同的工作模式

-電碼本(ECB)模式

-密碼分組鏈接(CBC)模式

-密碼反饋(CFB)模式

-輸出反饋(OFB)模式

-計(jì)數(shù)器(CTR)模式

2011-7-1063

電碼本(ECB)模式

?最簡(jiǎn)單的運(yùn)行模式，一次對(duì)一個(gè)64bit長(zhǎng)的

明文分組加密，且每次加密密鑰都相同。

kk

2011-7-1064

電碼本(ECB)模式

?在用于短數(shù)據(jù)(如加密密鑰)時(shí)非常理想，

是安全傳遞DES密鑰的最合適的模式

?在給定的密鑰下同一明文組總產(chǎn)生同樣的密

文組。這會(huì)暴露明文數(shù)據(jù)的格式和統(tǒng)計(jì)特征

O

?明文數(shù)據(jù)都有固定的格式，需要以協(xié)議的形

式定義，重要的數(shù)據(jù)常常在同一位置上出現(xiàn)

,使密碼分析者可以對(duì)其進(jìn)行統(tǒng)計(jì)分析、重

傳和代換攻擊

2011-7-1065

密碼分組鏈接(CBC)模式

?一1次對(duì)'一1個(gè)明文分組加密，每次加密使用同'一密鑰

,加密算法的輸入是當(dāng)前明文分組和前一次密文分

組的異或(在產(chǎn)生第1個(gè)密文分組時(shí)，需要有一個(gè)初

始向量IV與第一個(gè)明文分組異或)；

第1次Pl第2次P2

DES

I

2011-7-10

富瑪分組鏈接CCBCJ模式

?解密時(shí)，每一個(gè)密文分組被解密后，再與前一個(gè)密

文分組異或（第一個(gè)密文分組薜密后和初始向量IV

異或恢復(fù)出第一個(gè)明文分組）。

2011-7-1067

富號(hào)分組筵接CCBCJ模式舞）

?為使安全性最高，IV應(yīng)像密鑰一樣被保護(hù)。可使用ECB

加密模式來發(fā)送IV;

?保護(hù)IV原因是：如果敵手能欺騙接受方使用不同的IV,

敵手就能夠在明文的第一個(gè)分組中插入自己選擇的比特

履；

?IV的完整性要比其保密性更為重要。在CBC模式下，最

好是每發(fā)一個(gè)消息，都改變IV,比如將其值加一；

?由于CBC模式的鏈接機(jī)制，該模式對(duì)于加密長(zhǎng)于64bit的

消息非常合適；

?CBC模式除能獲得保密性外，還能用于認(rèn)證。

2011-7-1068液壽/李

密碼反饋（CFB）模式

?加密算法的輸入是64bit移位寄存器，其初始值為某個(gè)初

始向量IV,加密算法輸出的最左（最高有效位）jbit與

明文的第一個(gè)單元進(jìn)行異或，產(chǎn)生第一個(gè)密文單元G并

傳送該單元。然后將移位寄存器的內(nèi)容左移j位并將送

入移位寄存器最右邊（最低有效位）j位。這一過程持續(xù)

到明文的所有單元都被加密為止

密碼反饋（CFB）模式

?解密時(shí)，

將收到的

密文單元

與加密函

數(shù)的輸出

進(jìn)行異或

兩輪CFB模式解密示意圖

?為什么此時(shí)仍然使用加密算法而不

是解密算法？

2011-7-1070

密碼反饋（CFB）模式

?利用CFB模式或者OFB模式可將DES轉(zhuǎn)換為

流密碼；

?流密碼不需要對(duì)消息進(jìn)行填充，而且運(yùn)

行是實(shí)時(shí)的，因此如果傳送字母流，可

使用流密碼對(duì)每個(gè)字母直接加密進(jìn)行傳

送；

?CFB模式除了獲得保密性外，還能用于認(rèn)

證。

2011-7-1071

輸出反饋(OFB)模式

?OFB模式的結(jié)構(gòu)類似于CFB,不同之處在于：OFB

模式將加密算法的輸出反饋到移位寄存器，而CFB

模式中是將密文單元反饋到移位寄存器

▼5a5

?-------------??-------------'

P2

兩輪OFB模式加密示意圖

201171072海考/呼

cT1尹

Pip2

兩輪OFB模式解密示意圖/

2011-7-1073液壽/李

輸出反饋（OFB）模式

?克服了CFB的錯(cuò)誤傳播所帶來的問題。

?比CFB模式更易受到對(duì)消息流的篡改攻擊，

使得敵手有可能通過對(duì)消息校驗(yàn)部分的篡改

和對(duì)數(shù)據(jù)部分的篡改，而以糾錯(cuò)碼不能檢測(cè)

的方式篡改密文。

2011-7-1074

計(jì)數(shù)器(CRT)模式

?CTR可以把分組密碼轉(zhuǎn)換為流密碼

?和OFB類似，但是加密計(jì)數(shù)器值，而不是密

文反饋值

?必須對(duì)每一個(gè)明文使用一個(gè)不同的密鑰和計(jì)

數(shù)值

G=Pxor

0尸DESKW)

2011-7-1075

CTR模式加密示意圖

2011-7-1076

計(jì)數(shù)器(CRT)模式

■該模式優(yōu)點(diǎn)是安全、高效、可并行、適合

任意長(zhǎng)度的數(shù)據(jù)，。，的計(jì)算可以預(yù)處理，

適用于高速網(wǎng)絡(luò)。加解密過程僅涉及加密

運(yùn)算，不涉及解密算法，因此不用實(shí)現(xiàn)解

密算法。

?缺點(diǎn)是沒有錯(cuò)誤傳播，因此不易確保數(shù)據(jù)

完整性。信息快可被替換，重放，對(duì)明文

的主動(dòng)攻擊時(shí)可能的。

2011-7-1077

比較和選用

?ECB模式，簡(jiǎn)單、高速，但最弱、易受重發(fā)攻擊

,一般不推薦。

?CBC適用于文件加密，但較ECBI曼。安全性加強(qiáng)

o當(dāng)有少量錯(cuò)誤時(shí)，也不會(huì)造成同步錯(cuò)誤。

?OFB和CFB較CBC慢許多。每次迭代只有少數(shù)bit

完成加密。若可以容忍少量錯(cuò)誤擴(kuò)展，則可換來

恢復(fù)同步能力，此時(shí)用CFB。在字符為單元的流

密碼中多選CFB模式。

?OFB用于高速同步系統(tǒng)，不容忍差錯(cuò)傳播。

2011-7-1078海考/李

習(xí)題

1.證明可以通過顛倒密鑰方案用DES加密算法加密密

文實(shí)現(xiàn)DES解密。

2.在DES數(shù)據(jù)加密標(biāo)準(zhǔn)中，

明文m=0011100011010101101110000100

00101101010100111001100101011110

0111

密鑰K=1010101100110100100001101001

01001101100101110011101000101101

0011

試求L和I。

3.假設(shè)我們有128bit的AES密鑰，用16進(jìn)制表示為：

201171079海壽/李

2B7E151628AED2A6ABF7158809CF4F3C

由該種子密鑰構(gòu)造一個(gè)完整的密鑰編排方案。

4.使用上題中的128bit密鑰,在10輪AES下計(jì)算下列

明文（以16進(jìn)制表示）的加密結(jié)果：

3243F6A8885A308D313198A2E0370734。

5.在IDEA的模乘運(yùn)算中，為什么將模數(shù)取為216+1而

不是216?在其模加運(yùn)算中，為什么模數(shù)取為216而

不是216+1?

6.已知IDEA密碼算法中，

明文m=010m00100011011010100111011110

10101101001101010001001110010011;

2011-7-1080

1一上

MW

密鑰K=0010100110100011110110001110011110100101

0101001110100010010110010010010001011001

1100101011100111101000100010101011010101

00110101,求第一輪的輸出和第二輪的輸出。

7.在DES的ECB模式中，如果在密文分組中有一個(gè)錯(cuò)誤，解密后

僅相應(yīng)的明文分組受到影響，然而在CBC模式中，將有錯(cuò)誤

傳播(見PPT相應(yīng)的圖中的的一個(gè)錯(cuò)誤明顯地影響Pi和P2的結(jié)

果)。

(1)P2后的結(jié)果是否受到影響？

(2)設(shè)加密前的明文分組P］中有l(wèi)bit的錯(cuò)誤，問這一錯(cuò)誤將

在多少個(gè)密文分組中傳播？對(duì)接收者有什么影響？

2011-7-10

謝謝大家!

歡迎指正!

2011-7-1082

SuccesswithMoneyandJoy

附落人生心語

?成功是一種觀念

?致富是一種義務(wù)

?快樂是一種權(quán)利

?每個(gè)人都有能力、有義

務(wù)、有權(quán)利辦到成功

致富快樂

附贈(zèng)人生心語

成成功不是打敗別人

功成功不是超越別人

成功不是名、利、權(quán)的獲得

致?lián)碛薪】档纳眢w

豐足的物質(zhì)生活

富平衡的心理狀態(tài)

又才能擁有成功

快SuccesswithMoneyandJoy

戰(zhàn)勝自己

樂貢獻(xiàn)自己

扮演好自己的歷史角色

才能超越自己

融入成功里

附贈(zèng)人生心語

知人者智，自知者明，勝人者力，自

勝者強(qiáng)。

——老子

附贈(zèng)人生心語

?成功必須靠百分之九十八的辛勤血

汗，加上百分之二的天才靈感。

?世界上注定只有百分之二十的人會(huì)成

功。

附贈(zèng)人生心語

成猶太諺語中有一句名言，

功會(huì)傷人的東西有三個(gè)：苦惱、爭(zhēng)吵、空的錢包。

其中最傷人的是——空的錢包。

致金錢本身并沒有善惡，

但沒有錢，

富卻的確是一件不幸的事情。

又所以，我們