分組密碼課件

第8章分組密碼第8章分組密碼8．1分組密碼概述定義8.1一個(gè)分組密碼是一種映射： 記為E(X,K)或 稱為明文空間，稱為密文空間，為密鑰空間。8．1分組密碼概述定義8.1一個(gè)分組密碼是一種映射：8．2分組密碼的設(shè)計(jì)原則有關(guān)實(shí)用密碼的兩個(gè)一般設(shè)計(jì)原則是Shannon提出的混亂原則和擴(kuò)散原則?；靵y：人們所設(shè)計(jì)的密碼應(yīng)使得密鑰和明文以及密文之間的依賴關(guān)系相當(dāng)復(fù)雜以至于這種依賴性對(duì)密碼分析者來(lái)說(shuō)是無(wú)法利用的。擴(kuò)散：人們所設(shè)計(jì)的密碼應(yīng)使得密鑰的每一位數(shù)字影響密文的許多位數(shù)字以防止對(duì)密鑰進(jìn)行逐段破譯，而且明文的每一位數(shù)字也應(yīng)影響密文的許多位數(shù)字以便隱蔽明文數(shù)字統(tǒng)計(jì)特性。8．2分組密碼的設(shè)計(jì)原則有關(guān)實(shí)用密碼的兩個(gè)一般設(shè)計(jì)原則是軟件實(shí)現(xiàn)的設(shè)計(jì)原則：使用子塊和簡(jiǎn)單的運(yùn)算。密碼運(yùn)算在子塊上進(jìn)行，要求子塊的長(zhǎng)度能自然地適應(yīng)軟件編程，比如8、16、32比特等。在軟件實(shí)現(xiàn)中，按比特置換是難于實(shí)現(xiàn)的，因此我們應(yīng)盡量避免使用它。子塊上所進(jìn)行的一些密碼運(yùn)算應(yīng)該是一些易于軟件實(shí)現(xiàn)的運(yùn)算，最好是用一些標(biāo)準(zhǔn)處理器所具有的一些基本指令，比如加法、乘法和移位等。軟件實(shí)現(xiàn)的設(shè)計(jì)原則：使用子塊和簡(jiǎn)單的運(yùn)算。密碼運(yùn)算在子塊上進(jìn)硬件實(shí)現(xiàn)的設(shè)計(jì)原則：加密和解密可用同樣的器件來(lái)實(shí)現(xiàn)。盡量使用規(guī)則結(jié)構(gòu)，因?yàn)槊艽a應(yīng)有一個(gè)標(biāo)準(zhǔn)的組件結(jié)構(gòu)以便其能適應(yīng)于用超大規(guī)模集成電路實(shí)現(xiàn)。硬件實(shí)現(xiàn)的設(shè)計(jì)原則：加密和解密可用同樣的器件來(lái)實(shí)現(xiàn)。盡量使用其他原則：簡(jiǎn)單性原則：包括規(guī)范的簡(jiǎn)單性和分析的簡(jiǎn)單性。必須能抗擊所有已知的攻擊，特別是差分攻擊和線性攻擊?？蓴U(kuò)展性。要求能提供128、192、256比特的可變分組或密鑰長(zhǎng)。其他原則：8．3分組密碼的結(jié)構(gòu)8．3分組密碼的結(jié)構(gòu)Feistel網(wǎng)絡(luò)與SP網(wǎng)絡(luò)，它們的主要區(qū)別在于：SP結(jié)構(gòu)每輪改變整個(gè)數(shù)據(jù)分組，而Feistel密碼每輪只改變輸入分組的一半。AES和DES分別是這兩種結(jié)構(gòu)的代表。Feistel網(wǎng)絡(luò)（又稱Feistel結(jié)構(gòu)）可把任何輪函數(shù)轉(zhuǎn)化為一個(gè)置換，它是由HorstFeistel在設(shè)計(jì)Lucifer分組密碼時(shí)發(fā)明的，并因DES的使用而流行。“加解密相似”是Feistel型密碼的實(shí)現(xiàn)優(yōu)點(diǎn)。SP網(wǎng)絡(luò)（又稱SP結(jié)構(gòu)）是Feistel網(wǎng)絡(luò)的一種推廣，其結(jié)構(gòu)清晰，S一般稱為混淆層，主要起混淆作用。P一般稱為擴(kuò)散層，主要起擴(kuò)散作用。SP網(wǎng)絡(luò)與Feistel網(wǎng)絡(luò)相比，可以得到更快速的擴(kuò)散，不過(guò)SP網(wǎng)絡(luò)的加解密通常不相似。有關(guān)這兩種結(jié)構(gòu)的特點(diǎn)，讀者在了解了DES和AES算法之后再細(xì)細(xì)體會(huì)。Feistel網(wǎng)絡(luò)與SP網(wǎng)絡(luò)，它們的主要區(qū)別在于：SP結(jié)構(gòu)每8.4分組密碼的安全性

8.4.1安全需求如果不知道密鑰的知識(shí)，攻擊者從密文恢復(fù)出明文是實(shí)際不可能的。用固定的k比特的秘密鑰，加密T個(gè)明文，其中 ，最大化T后仍能達(dá)到一個(gè)可接受的安全性是現(xiàn)代分組密碼追求的目標(biāo)。幾乎所有當(dāng)代分組密碼用更小的查表（代替盒或S盒）合并其他變換（線性變換）模仿這樣一個(gè)大的隨機(jī)查表。這種做法實(shí)際上是安全性和可接受的復(fù)雜性的一個(gè)折中。8.4分組密碼的安全性8.4.1安全需求8.4.2安全模型1）無(wú)條件安全性。2）多項(xiàng)式安全性。3）“可證明的安全性”。4）實(shí)際的安全性。5）歷史的安全性。8.4.2安全模型1）無(wú)條件安全性。8.4.3分組密碼作為一個(gè)偽隨機(jī)置換

偽隨機(jī)意味：在多項(xiàng)式時(shí)間內(nèi)，加密詢問(wèn)使得沒(méi)有攻擊者可以區(qū)分分組密碼和一真實(shí)的隨機(jī)置換；相應(yīng)于選擇明文攻擊。超偽隨機(jī)意味：在多項(xiàng)式時(shí)間內(nèi)，加、解密詢問(wèn)使得沒(méi)有攻擊者可以區(qū)分分組密碼和一真實(shí)的隨機(jī)置換。相應(yīng)于選擇明、密文攻擊。分組密碼也可以與單向函數(shù)聯(lián)系。8.4.3分組密碼作為一個(gè)偽隨機(jī)置換偽隨機(jī)意味：在多項(xiàng)式8.4.4攻擊的分類數(shù)據(jù)復(fù)雜度：實(shí)施一個(gè)攻擊所需輸入的數(shù)據(jù)量，用長(zhǎng)為N的分組作單位。處理復(fù)雜度：執(zhí)行一個(gè)攻擊所花的時(shí)間，時(shí)間單位可取攻擊者不得不親自做的加密次數(shù)。存儲(chǔ)復(fù)雜度：需要記憶的字，單位可取長(zhǎng)為N的分組。8.4.4攻擊的分類數(shù)據(jù)復(fù)雜度：實(shí)施一個(gè)攻擊所需輸入的數(shù)組密碼的攻擊方法目前有：窮舉密鑰搜索法、差分分析、截?cái)嗖罘址治?、不可能差分分析、高階差分分析、線性分析、差分線性分析，Boomerang攻擊、相關(guān)密鑰攻擊、插值攻擊、非雙射攻擊、Slide攻擊、攻擊。組密碼的攻擊方法目前有：窮舉密鑰搜索法、差分分析、截?cái)嗖罘址?.5典型的分組密碼算法——DES

DES的歷史1971IBM，由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)。8.5典型的分組密碼算法——DESDES的歷史8.5.1

DES的描述

DES利用56比特串長(zhǎng)度的密鑰K來(lái)加密長(zhǎng)度為64位的明文，得到長(zhǎng)度為64位的密文該算法分三個(gè)階段實(shí)現(xiàn)：

1.給定明文X，通過(guò)一個(gè)固定的初始置換IP來(lái)排列X中的位，得到X0。

X0=IP（X）=L0R0

其中L0由X0前32位組成，R0由X0的后32位組成。

2.計(jì)算函數(shù)F的16次迭代,根據(jù)下述規(guī)則來(lái)計(jì)算LiRi(1<=i<=16）

Li=Ri-1,Ri=Li-1

F(Ri-1,Ki)

其中Ki是長(zhǎng)為48位的子密鑰。子密鑰K1，K2，…，K16是作為密鑰K（56位）的函數(shù)而計(jì)算出的。

3.對(duì)比特串R16L16使用逆置換IP-1得到密文Y。

Y=IP-1（R16L16）8.5.1DES的描述

DES利用56比特串長(zhǎng)度的密鑰K第8章分組密碼課件IP-初始置換58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7IP-初始置換58,50,42,34,26,18,PC157,49,41,33,25,17,9,CHalf1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,63,55,47,39,31,23,15,DHalf7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4PC157,49,41,33,25,17,9,S-box-10123456789abcdefCOL

S[1]

14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13

S-box-1012345DES一輪加密的簡(jiǎn)圖

Li-1Ri-1F+LiRiKiDES一輪加密的簡(jiǎn)圖Li-1Ri-1F+Li對(duì)F函數(shù)的說(shuō)明：（類比于S-DES）F（Ri-1,Ki）

函數(shù)F以長(zhǎng)度為32的比特串A=R（32bits）作第一個(gè)輸入，以長(zhǎng)度為48的比特串變?cè)狫=K(48bits)作為第二個(gè)輸入。產(chǎn)生的輸出為長(zhǎng)度為32的位串。

(1)對(duì)第一個(gè)變?cè)狝，由給定的擴(kuò)展函數(shù)E，將其擴(kuò)展成48位串，E（A）

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

B=b1b2b3b4b5b6b7b8

(3)使用8個(gè)S盒，每個(gè)Sj是一個(gè)固定的416矩陣，它的元素取0~15的整數(shù)。給定長(zhǎng)度為6個(gè)比特串，如

Bj=b1b2b3b4b5b6

計(jì)算Sj(Bj)如下：b1b6兩個(gè)比特確定了Sj的行數(shù),r(0<=r<=3);而b2b3b4b5四個(gè)比特確定了Sj的列數(shù)c（0<=c<=15）。最后Sj(Bj)的值為S-盒矩陣Sj中r行c列的元素（r,c）,得Cj=Sj(Bj)。

(4)最后，P為固定置換。

對(duì)F函數(shù)的說(shuō)明：（類比于S-DES）F（Ri-1,Ki）

DES輪函數(shù)F（）DES輪函數(shù)F（）DES中使用的其它特定函數(shù)：

初始置換IP：見(jiàn)140頁(yè)圖4-4-3,從圖中看出X的第58個(gè)比特是IP（X）的第一個(gè)比特；X的第50個(gè)比特是IP（X）的第二個(gè)比特…

逆置換IP-1；擴(kuò)展函數(shù)E；置換函數(shù)P。從密鑰K計(jì)算子密鑰：

實(shí)際上，K是長(zhǎng)度為64的位串，其中56位是密鑰，8位是奇偶校驗(yàn)位（為了檢錯(cuò)），在密鑰編排的計(jì)算中，這些校驗(yàn)位可略去。

(1).給定64位的密鑰K，放棄奇偶校驗(yàn)位（8，16，…，64）并根據(jù)固定置換PC-1（見(jiàn)144頁(yè)圖4-4-9）來(lái)排列K中剩下的位。我們寫(xiě)

PC-1(K)=C0D0

其中C0由PC-1（K）的前28位組成；D0由后28位組成。DES中使用的其它特定函數(shù)：

初始置換IP：見(jiàn)140頁(yè)圖4-(2)對(duì)1<=i<=16，計(jì)算

Ci=LSi(Ci-1)

Di=LSi(Di-1)

LSi表示循環(huán)左移2或1個(gè)位置，取決于i的的值。i=1,2,9和16時(shí)移1個(gè)位置，否則移2位置（143頁(yè)表4-4-2）。

Ki=PC-2(CiDi),PC-2為固定置（見(jiàn)145頁(yè)圖4-4-10)。注：一共16輪，每一輪使用K中48位組成一個(gè)48比特密鑰?？伤愠?6個(gè)表，第i個(gè)表中的元素可對(duì)應(yīng)上第i輪密鑰使用K中第幾比特！如：

第7輪的表7：K7取K中的比特情況：

52571112659103444512519

941325035364342336018

2871429474622515636139

4311338536255202337306(2)對(duì)1<=i<=16，計(jì)算

Ci=LSi(Ci-1)

D輪密鑰編排KPC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16

…輪密鑰編排KPC-1C0D0LS1LS114,17,11,24,1,5,Chalf3,28,15,6,21,10,(bits1-28)23,19,12,4,26,8,16,7,27,20,13,2,41,52,31,37,47,55,Dhalf30,40,51,45,33,48,(bits29-56)44,49,39,56,34,53,46,42,50,36,29,32ChalfprovidesbitstoS1-S4,DhalftoS5-S8

PC214,17,11,24,1,5,DES加密的一個(gè)例子

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

密鑰K為：133457799BBCDFF1

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

應(yīng)用IP，我們得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010

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

最后對(duì)L16,R16使用IP-1得到密文：85E813540F0AB405DES加密的一個(gè)例子

取16進(jìn)制明文X：0123456788.5.2DES的設(shè)計(jì)思想和特點(diǎn)

DES的核心是S盒，除此之外的計(jì)算是屬線性的。S盒作為該密碼體制的非線性組件對(duì)安全性至關(guān)重要。S盒的設(shè)計(jì)準(zhǔn)則：

1.S盒不是它輸入變量的線性函數(shù)

2.改變S盒的一個(gè)輸入位至少要引起兩位的輸出改變

3.對(duì)任何一個(gè)S盒，如果固定一個(gè)輸入比特，其它輸入變化時(shí)，輸出數(shù)字中0和1的總數(shù)近于相等。8.5.2DES的設(shè)計(jì)思想和特點(diǎn)DES的核心是S盒，除此DES的弱點(diǎn)：1）存在一些弱密鑰和半弱密鑰。

2）在DES的明文m，密文C與密鑰k之間存在著互補(bǔ)的特性。

DES的弱點(diǎn)：8.5.3DES的工作方式（對(duì)其他分組密碼也適用）

1.電子密文方式（ECB）8.5.3DES的工作方式（對(duì)其他分組密碼也適用）1.2.密文分組鏈接方式(CBC)2.密文分組鏈接方式(CBC)3.密文反饋方式（CFB）3.密文反饋方式（CFB）4.輸出反饋模式（OFB）4.輸出反饋模式（OFB）8.5.5DES的安全性對(duì)DES的批評(píng)主要集中在以下幾點(diǎn)：DES的密鑰長(zhǎng)度（56位）可能太小。DES的迭代次數(shù)可能太少。S盒中可能有不安全因素。DES的一些關(guān)鍵部分不應(yīng)當(dāng)保密。8.5.5DES的安全性對(duì)DES的批評(píng)主要集中在以下幾8.6典型的分組密碼的分析方法

1.窮盡密鑰搜索（強(qiáng)力攻擊）2.線性分析方法3.差分分析方法4.相關(guān)密鑰密碼分析5.中間相遇攻擊8.6典型的分組密碼的分析方法1.窮盡密鑰搜索（強(qiáng)力攻8.6.1差分分析法差分分析方法是一種選擇明文攻擊.基本思想是通過(guò)分析特定明文差分對(duì)相應(yīng)密文差分影響來(lái)獲得可能性最大的密鑰。8.6.1差分分析法差分分析方法是一種選擇明文攻擊.8.6.1.1差分分析的理論依據(jù)

定義8.6.1設(shè)Sj是一個(gè)給定的S－盒 是一對(duì)長(zhǎng)度為6比特的串。稱Sj的輸入異或是 的輸出異或是 。定理8.6.1設(shè)Ej和Ej×是S－盒Sj的兩輸入，Sj的輸出異或是Cjt，記 ，則密鑰比特Jj出現(xiàn)在集合 之中，即 。8.6.1.1差分分析的理論依據(jù)定義8.6.1設(shè)S8.6.1.2差分分析的應(yīng)用實(shí)例例3假定有下列的三對(duì)明文和密文，這里明文具有確定的異或，并且使用同一個(gè)密鑰加密。為簡(jiǎn)單起見(jiàn)，使用16進(jìn)制表示。8.6.1.2差分分析的應(yīng)用實(shí)例例3假定有下列的三對(duì)8.6.2線性密碼分析是一種已知明文攻擊攻擊者的目的是希望找到有效的線性表達(dá)式 使其成功的概率p≠1/2，且|p-1/2|最大。8.6.2線性密碼分析是一種已知明文攻擊在已知Ｎ個(gè)明密文對(duì)時(shí)，線性攻擊可實(shí)施如下：（1）對(duì)所有明文P和密文C，T表示（8.5.2.2）左邊為0的次數(shù)。（2）若T>N/2，那么當(dāng)p>1/2時(shí)，猜測(cè)K[k1…kl]=0；當(dāng)p<1/2時(shí)，猜測(cè)K[k1…kl]=1；否則，當(dāng)p>1/2時(shí)，猜測(cè)K[k1…kl]=1；當(dāng)p<1/2，猜測(cè)K[k1…kl]=0；當(dāng)|p-1/2|充分小時(shí)，成功的概率為在已知Ｎ個(gè)明密文對(duì)時(shí)，線性攻擊可實(shí)施如下：8.7美國(guó)高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)——AES背景從各方面來(lái)看，DES已走到了它生命的盡頭。其56比特密鑰實(shí)在太小，雖然三重DES可以解決密鑰長(zhǎng)度的問(wèn)題，但是DES的設(shè)計(jì)主要針對(duì)硬件實(shí)現(xiàn)，而今在許多領(lǐng)域，需要用軟件方法來(lái)實(shí)現(xiàn)它，在這種情況下，它的效率相對(duì)較低。鑒于此，1997年4月15日美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所（NIST）發(fā)起征集AES（AES—AdvancedEncryptionStandard）算法的活動(dòng)，并成立了AES工作組。目的是為了確定一個(gè)非保密的、公開(kāi)披露的、全球免費(fèi)使用的加密算法，用于保護(hù)下一世紀(jì)政府的敏感信息。也希望能夠成為保密和非保密部門(mén)公用的數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）。8.7美國(guó)高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)——AES背景要求該算法應(yīng)比三重DES快而且至少還要一樣的安全，它應(yīng)當(dāng)具有128比特分組長(zhǎng)度和256比特分組密鑰長(zhǎng)度（不過(guò)必須支持128和192比特的密鑰），此外，還應(yīng)該具有較大的靈活性。要求8．7．1AES的評(píng)估準(zhǔn)則

1）安全性；2）代價(jià)，主要包括：許可要求，在各種平臺(tái)上的計(jì)算效率（速度）和內(nèi)存空間的需求；3）算法和實(shí)現(xiàn)特性，主要包括：靈活性、硬件和軟件適應(yīng)性、算法的簡(jiǎn)單性等。8．7．1AES的評(píng)估準(zhǔn)則1998年8月20日，NIST在第一階段討論（AES1）中宣布了由12個(gè)國(guó)家提出的15個(gè)候選算法，1999年3月開(kāi)始的第二階段討論（AES2），1999年8月NIST選出5個(gè)算法候選:MARS、RC6、Rijndael、Serpent和Twofish。1998年8月20日，NIST在第一階段討論8．7．2高級(jí)加密標(biāo)準(zhǔn)算法AES——Rijndael最大優(yōu)點(diǎn)是可以給出算法的最佳差分特征的概率及最佳線性逼近的偏差的界，由此，可以分析算法抵抗差分密碼分析及線性密碼分析的能力。8．7．2高級(jí)加密標(biāo)準(zhǔn)算法AES——Rijndael最第8章分組密碼課件Rijndael算法的安全性 能有效地抵抗目前已知的攻擊方法的攻擊。如：部分差分攻擊、相關(guān)密鑰攻擊、插值攻擊（Interpolationattack）等。對(duì)于Rijndael，最有效的攻擊還是窮盡密鑰搜索攻擊。

Rijndael算法的安全性先進(jìn)分組密碼的特點(diǎn)可變密鑰長(zhǎng)度混合操作依賴數(shù)據(jù)的循環(huán)移位依賴于密鑰的循環(huán)移位依賴