現(xiàn)代密碼學(xué)第4章1：概述

1、1分組密碼分組密碼現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué)第第4章章(1)2本章主要內(nèi)容本章主要內(nèi)容n1 1、分組密碼概述、分組密碼概述n2 2、數(shù)據(jù)加密標(biāo)準(zhǔn)、數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES算法算法n3 3、分組密碼的運(yùn)行模式、分組密碼的運(yùn)行模式n4 4、差分密碼分析與線性密碼分析、差分密碼分析與線性密碼分析n5 5、IDEAIDEA算法算法n6 6、AESAES算法算法RijndaelRijndael3 在許多密碼系統(tǒng)中，單鑰分組密碼是系統(tǒng)安全的一個(gè)重要組成部分，用分組密碼易于構(gòu)造偽隨機(jī)數(shù)生成器、流密碼、消息認(rèn)證碼（MAC）和雜湊函數(shù)等，還可進(jìn)而成為消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)制、實(shí)體認(rèn)證協(xié)議以及單鑰數(shù)字簽字體制的核心

2、組成部分。第第1 1節(jié)：分組密碼概述節(jié)：分組密碼概述4n 實(shí)際應(yīng)用中對于分組密碼可能提出多方面的要求，除了安全性外，還有運(yùn)行速度、存儲(chǔ)量（程序的長度、數(shù)據(jù)分組長度、高速緩存大小）、實(shí)現(xiàn)平臺（硬件、軟件、芯片）、運(yùn)行模式等限制條件。這些都需要與安全性要求之間進(jìn)行適當(dāng)?shù)恼壑羞x擇。1 分組密碼概述分組密碼概述5n是一種單鑰或?qū)ΨQ算法n通信實(shí)體雙方使用相同的密鑰加密和解密 n現(xiàn)代分組密碼（由乘積密碼構(gòu)成）包括DES, Blowfish, IDEA, LOKI, RC5, Rijndael (AES) 及其它一些算法1 分組密碼概述分組密碼概述6n在分組密碼中，消息被分成許多塊，每塊都要被加密n類似于許

3、多字符被替換-（64-bits or more ）n許多現(xiàn)代分組密碼具有下列形式：1 分組密碼概述分組密碼概述71 分組密碼概述分組密碼概述8分組密碼理論基礎(chǔ)分組密碼理論基礎(chǔ)n理想的方法是使用盡可能大的替換模塊，但不實(shí)際，因?yàn)閷γ總€(gè)64bit的模塊，將需要264 個(gè)實(shí)體的替換表，因此使用一些小的模塊代替。n使用乘積密碼的思想 n這種概念由 Shannon and Feistel 提出9分組密碼的設(shè)計(jì)原理分組密碼的設(shè)計(jì)原理n可變密鑰長度可變密鑰長度n混合操作混合操作n依賴數(shù)據(jù)的循環(huán)移位依賴數(shù)據(jù)的循環(huán)移位n依賴于密鑰的循環(huán)移位依賴于密鑰的循環(huán)移位n依賴密鑰的依賴密鑰的S盒子盒子n冗長的密鑰調(diào)度算法

4、冗長的密鑰調(diào)度算法n可變的可變的F函數(shù)和可變的明文函數(shù)和可變的明文/密文長度密文長度n可變的循環(huán)次數(shù)可變的循環(huán)次數(shù)n在每次循環(huán)中都對兩半數(shù)據(jù)進(jìn)行操作在每次循環(huán)中都對兩半數(shù)據(jù)進(jìn)行操作10Shannons 保密系統(tǒng)理論保密系統(tǒng)理論 nClaude Shannon 對現(xiàn)代密碼的重要工作：nC E Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, Vol 28, Oct 1949, pp 656-715 nC E Shannon, Prediction and Entropy of prin

5、ted English, Bell System Technical Journal, Vol 30, Jan 1951, pp 50-64 n在上述文章中，提出了下列概念: n“熵”的概念n語言冗余度n破譯密碼需要多少信息量n定義了”計(jì)算安全”與”無條件安全”11n即如果通過填加一些英語字母加密英文內(nèi)容，是不安全的。n因?yàn)橛⒄Z有80%的冗余度，英語密文如果有60%的冗余度，就可以破解。Shannons 保密系統(tǒng)理論保密系統(tǒng)理論 12 分組密碼是將明文消息編碼表示后的數(shù)字序列x0,x1,xi,劃分成長為n的組x=(x0,x1,xn-1)，各組（長為n的矢量）分別在密鑰k=(k0,k1,kt-1

6、)控制下變換成等長的輸出數(shù)字序列y=(y0,y1,ym-1)（長為m的矢量），其加密函數(shù)E：VnKVm，Vn和Vm分別是n維和m維矢量空間，K為密鑰空間，如圖1所示。1 1 分組密碼概述分組密碼概述13 明文序列明文序列 x1, x2, xi, 加密函數(shù)加密函數(shù)E: VnKVn 這種密碼實(shí)質(zhì)上是字長為這種密碼實(shí)質(zhì)上是字長為m的數(shù)字序列的代換密碼的數(shù)字序列的代換密碼。 解密算法加密算法密鑰k=(k0, k1, kt-1 )密鑰k=(k0, k1, kt-1 )明文明文x=(x0, x1, xm-1)明文明文x=(x0, x1, xm-1)密文密文x=(y0, y1, ym-1)圖1 分組密碼框圖

7、1 1 分組密碼概述分組密碼概述14n 它與流密碼不同之處在于輸出的每一位數(shù)字不是只與相應(yīng)時(shí)刻輸入的明文數(shù)字有關(guān)，而是與一組長為n的明文數(shù)字有關(guān)。n 在相同密鑰下，分組密碼對長為n的輸入明文組所實(shí)施的變換是等同的，所以只需研究對任一組明文數(shù)字的變換規(guī)則。這種密碼實(shí)質(zhì)上是字長為n的數(shù)字序列的代換密碼。1 1 分組密碼概述分組密碼概述15 通常取m=n。若mn，則為有數(shù)據(jù)擴(kuò)展的分組密碼；若mn，則為有數(shù)據(jù)壓縮的分組密碼。 在二元情況下，x和y均為二元數(shù)字序列，它們的每個(gè)分量xi，yiGF(2)。本節(jié)將主要討論二元情況。設(shè)計(jì)的算法應(yīng)滿足下述要求：1 1 分組密碼概述分組密碼概述16n分組密碼是許多系

8、統(tǒng)安全的一個(gè)重要組分組密碼是許多系統(tǒng)安全的一個(gè)重要組成部分?？捎糜跇?gòu)造成部分?？捎糜跇?gòu)造n擬隨機(jī)數(shù)生成器擬隨機(jī)數(shù)生成器n流密碼流密碼n消息認(rèn)證碼消息認(rèn)證碼(MAC)(MAC)和雜湊函數(shù)和雜湊函數(shù)n消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)構(gòu)、實(shí)體認(rèn)證消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)構(gòu)、實(shí)體認(rèn)證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。分組密碼概述分組密碼概述17分組密碼與序列密碼比較，主要區(qū)別是在加密方式上：序列密碼序列密碼：kKGk=k0k1k2012mmm)()(001122kmkmkm分組密碼概述分組密碼概述18大多數(shù)實(shí)用分組密碼的明文信號取自于F2、且滿足：n=n（即明文

9、沒有被擴(kuò)展）?？疾斓囊粋€(gè)分組密碼體制，設(shè) 為密 鑰空間，n為分組長度，那么加密變換空間為： =Ek|Ek: 是一一映射,k 。若將 中點(diǎn) 與其所對應(yīng)的二進(jìn)制數(shù) 不加區(qū)別，則每個(gè)k(k )可等同一個(gè)2n-置換。nnFF22),(110nxxxXnF22110)(nxxxX分組密碼概述分組密碼概述19線性部分nS2記 為由所有2n-置換構(gòu)成的所謂2n次對稱群，那么一個(gè)好的分組密碼的加密變換空間在 中的位置應(yīng)如下圖所示：nS2nS2分組密碼概述分組密碼概述20應(yīng)用中對于分組碼的要求應(yīng)用中對于分組碼的要求n安全性安全性n運(yùn)行速度運(yùn)行速度n存儲(chǔ)量存儲(chǔ)量( (程序的長度、數(shù)據(jù)分組長度、高速緩存大程序的長度

10、、數(shù)據(jù)分組長度、高速緩存大小小) )n實(shí)現(xiàn)平臺實(shí)現(xiàn)平臺( (硬、軟件、芯片硬、軟件、芯片) )n運(yùn)行模式運(yùn)行模式21分組密碼設(shè)計(jì)問題分組密碼設(shè)計(jì)問題 分組密碼的設(shè)計(jì)問題在于找到一種算分組密碼的設(shè)計(jì)問題在于找到一種算法，能在密鑰控制下從一個(gè)足夠大且足法，能在密鑰控制下從一個(gè)足夠大且足夠好的置換子集中，簡單而迅速地選出夠好的置換子集中，簡單而迅速地選出一個(gè)置換，用來對當(dāng)前輸入的明文的數(shù)一個(gè)置換，用來對當(dāng)前輸入的明文的數(shù)字組進(jìn)行加密變換。字組進(jìn)行加密變換。22 分組長度n要足夠大，使分組代換字母表中的元素個(gè)數(shù)2n足夠大，防止明文窮舉攻擊法奏效。DES、IDEA、FEAL和LOKI等分組密碼都采用n=

11、64，在生日攻擊下用232組密文成功概率為1/2，同時(shí)要求23264b=215MB存貯，故采用窮舉攻擊是不現(xiàn)實(shí)的。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要求23 密鑰量要足夠大（即置換子集中的元素足夠多），盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。但密鑰又不能過長，以便于密鑰的管理。DES采用56比特密鑰，看來太短了，IDEA采用128比特密鑰，據(jù)估計(jì)，在今后3040年內(nèi)采用80 比特密鑰是足夠安全的。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要求24 由密鑰確定置換的算法要足夠復(fù)雜，充分實(shí)現(xiàn)明文與密鑰的擴(kuò)散和混淆，沒有簡單的關(guān)系可循，能抗擊各種已知的攻擊，如差分攻

12、擊和線性攻擊；有高的非線性階數(shù)，實(shí)現(xiàn)復(fù)雜的密碼變換；使對手破譯時(shí)除了用窮舉法外，無其它捷徑可循。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要求25 加密和解密運(yùn)算簡單，易于軟件和硬件高速實(shí)現(xiàn)。如將分組n化分為子段，每段長為8、16或者32。在以軟件實(shí)現(xiàn)時(shí)，應(yīng)選用簡單的運(yùn)算，使作用于子段上的密碼運(yùn)算易于以標(biāo)準(zhǔn)處理器的基本運(yùn)算，如加、乘、移位等實(shí)現(xiàn)，避免用以軟件難于實(shí)現(xiàn)的逐比特置換。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要求26n 為了便于硬件實(shí)現(xiàn)，加密和解密過程之間的差別應(yīng)僅在于由秘密密鑰所生成的密鑰表不同而已。這樣，加密和解密就可用同一器件實(shí)現(xiàn)。設(shè)計(jì)的算法采用規(guī)則的模塊結(jié)構(gòu)，如多輪迭代

13、等，以便于軟件和VLSI快速實(shí)現(xiàn)。此外，差錯(cuò)傳播和數(shù)據(jù)擴(kuò)展要盡可能地小。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要求27 數(shù)據(jù)擴(kuò)展。一般無數(shù)據(jù)擴(kuò)展，在采用同態(tài)置換和隨機(jī)化加密技術(shù)時(shí)可引入數(shù)據(jù)擴(kuò)展。 差錯(cuò)傳播盡可能地小。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要求28l軟件實(shí)現(xiàn)的設(shè)計(jì)原則：使用子塊和簡單的運(yùn)算。密碼運(yùn)算在子塊上進(jìn)行，要求子塊的長度能自然地適應(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)處理器所具有的那些基本指令，比如加法、乘法和移位等。1 1

14、分組密碼軟件設(shè)計(jì)原則分組密碼軟件設(shè)計(jì)原則29加密和解密應(yīng)具有相似性（最好只是在密鑰的使用方式上存在不同，其余皆同）以便可以用同樣的器件來實(shí)現(xiàn)。 盡量使用規(guī)則結(jié)構(gòu)，且應(yīng)符合國際的統(tǒng)一標(biāo)準(zhǔn)，以便適合于用超大規(guī)模集成電路來實(shí)現(xiàn)。：分組密碼常常以乘積密碼的方式來設(shè)計(jì)。由合理選擇的許多子密碼（相繼使用）構(gòu)成的乘積密碼既可實(shí)現(xiàn)良好的混亂、又可實(shí)現(xiàn)良好的擴(kuò)散。1 1 分組密碼硬件設(shè)計(jì)原則分組密碼硬件設(shè)計(jì)原則30 要實(shí)現(xiàn)上述幾點(diǎn)要求并不容易。首先，要在理論上研究有效而可靠的設(shè)計(jì)方法，而后進(jìn)行嚴(yán)格的安全性檢驗(yàn)，并且要易于實(shí)現(xiàn)。 下面介紹設(shè)計(jì)分組密碼時(shí)的一些常用方法。1 1 分組密碼算法設(shè)計(jì)要求分組密碼算法設(shè)計(jì)要

15、求31 如果明文和密文的分組長都為n比特，則明文的每一個(gè)分組都有2n個(gè)可能的取值。為使加密運(yùn)算可逆（使解密運(yùn)算可行），明文的每一個(gè)分組都應(yīng)產(chǎn)生惟一的一個(gè)密文分組，這樣的變換是可逆的，稱明文分組到密文分組的可逆變換為代換。不同可逆變換的個(gè)數(shù)有2n!個(gè)。（1）代換）代換1 1 分組密碼算法設(shè)計(jì)方法分組密碼算法設(shè)計(jì)方法32 圖2表示n=4的代換密碼的一般結(jié)構(gòu)，4比特輸入產(chǎn)生16個(gè)可能輸入狀態(tài)中的一個(gè)，由代換結(jié)構(gòu)將這一狀態(tài)映射為16個(gè)可能輸出狀態(tài)中的一個(gè)，每一輸出狀態(tài)由4個(gè)密文比特表示。 加密映射和解密映射可由代換表來定義，如表3.1所示。這種定義法是分組密碼最常用的形式，能用于定義明文和密文之間的任

16、何可逆映射。（見33頁表3.1）（1）代換）代換33n在Shannon 1949 的文章中，介紹了替換-置換網(wǎng)絡(luò)的思想 (S-P) networks n這種思想形成了現(xiàn)代密碼的基礎(chǔ)nS-P network 替換-置換乘積密碼的現(xiàn)代形式nS-P networks 是基于下列兩種最基本的密碼運(yùn)算（前面介紹過）：n替換（ Substitution ）n置換（ Permutation ）（1）代換）代換34圖2 代換結(jié)構(gòu)（1）代換）代換35 但這種代換結(jié)構(gòu)在實(shí)用中還有一些問題需考慮。如果分組長度太小，如n=4，系統(tǒng)則等價(jià)于古典的代換密碼，容易通過對明文的統(tǒng)計(jì)分析而被攻破。這個(gè)弱點(diǎn)不是代換結(jié)構(gòu)固有的，只

17、是因?yàn)榉纸M長度太小。如果分組長度n足夠大，而且從明文到密文可有任意可逆的代換，那么明文的統(tǒng)計(jì)特性將被隱藏而使以上的攻擊不能奏效。（1）代換）代換36 然而，從實(shí)現(xiàn)的角度來看，分組長度很大的可逆代換結(jié)構(gòu)是不實(shí)際的。仍以表3.1為例，該表定義了n=4時(shí)從明文到密文的一個(gè)可逆映射，其中第2列是每個(gè)明文分組對應(yīng)的密文分組的值，可用來定義這個(gè)可逆映射。 因此從本質(zhì)上來說，第2列是從所有可能映射中決定某一特定映射的密鑰。這個(gè)例子中，密鑰需要64比特。一般地，對n比特的代換結(jié)構(gòu)，密鑰的大小是n2n比特。如對64比特的分組，密鑰大小應(yīng)是64264=2701021比特，因此難以處理。（1）代換）代換37 實(shí)際中

18、常將n分成較小的段，例如可選n=rn0，其中r和n0都是正整數(shù)，將設(shè)計(jì)n個(gè)變量的代換變?yōu)樵O(shè)計(jì)r個(gè)較小的子代換，而每個(gè)子代換只有n0個(gè)輸入變量。一般n0都不太大，稱每個(gè)子代換為代換盒，簡稱為S盒。例如DES中將輸入為48比特、輸出為32比特的代換用8個(gè)S盒來實(shí)現(xiàn)，每個(gè)S盒的輸入端數(shù)僅為6比特，輸出端數(shù)僅為4比特。（1）代換）代換38代換網(wǎng)絡(luò)代換網(wǎng)絡(luò)n 代換代換是輸入集是輸入集A到輸出到輸出A上的雙射變上的雙射變換換： fk：AA 式中，式中，k是控制輸入變量，在密碼學(xué)是控制輸入變量，在密碼學(xué)中則為密鑰中則為密鑰。n 實(shí)現(xiàn)代換實(shí)現(xiàn)代換fk的網(wǎng)絡(luò)稱作代換網(wǎng)絡(luò)。雙的網(wǎng)絡(luò)稱作代換網(wǎng)絡(luò)。雙射條件保證在給定

19、射條件保證在給定k下可從密文惟一地恢下可從密文惟一地恢復(fù)出原明文復(fù)出原明文。39n代換代換fk的集合：的集合： S=fk k KnK是密鑰空間。如果網(wǎng)絡(luò)可以實(shí)現(xiàn)所有可是密鑰空間。如果網(wǎng)絡(luò)可以實(shí)現(xiàn)所有可能的能的2n!個(gè)代換，則稱其為全代換網(wǎng)絡(luò)。個(gè)代換，則稱其為全代換網(wǎng)絡(luò)。n全代換網(wǎng)絡(luò)密鑰個(gè)數(shù)必須滿足條件：全代換網(wǎng)絡(luò)密鑰個(gè)數(shù)必須滿足條件： k 2n! 代換網(wǎng)絡(luò)代換網(wǎng)絡(luò)40n 密碼設(shè)計(jì)中需要先定義代換集密碼設(shè)計(jì)中需要先定義代換集S，而后還，而后還需定義解密變換集，即逆代換網(wǎng)絡(luò)需定義解密變換集，即逆代換網(wǎng)絡(luò)S-1，它以，它以密文密文y作為輸入矢量，其輸出為恢復(fù)的明文矢作為輸入矢量，其輸出為恢復(fù)的明文矢

20、量量x。n 要實(shí)現(xiàn)全代換網(wǎng)絡(luò)并不容易。因此實(shí)用中要實(shí)現(xiàn)全代換網(wǎng)絡(luò)并不容易。因此實(shí)用中常常利用一些簡單的基本代換，通過組合實(shí)現(xiàn)常常利用一些簡單的基本代換，通過組合實(shí)現(xiàn)較復(fù)雜的、元素個(gè)數(shù)較多的代換集。實(shí)用密碼較復(fù)雜的、元素個(gè)數(shù)較多的代換集。實(shí)用密碼體制的集合體制的集合S中的元素個(gè)數(shù)都遠(yuǎn)小于中的元素個(gè)數(shù)都遠(yuǎn)小于2n!。代換網(wǎng)絡(luò)代換網(wǎng)絡(luò)41例例:n=4 代換結(jié)構(gòu)代換結(jié)構(gòu)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1542明文 密文明文 密文0000 11010001 01010010 00010011

21、01100100 10010101 11110110 00100111 00111000 10101001 10001010 10111011 11101100 01111101 01001110 11001111 0000密文 明文密文 明文0000 11110001 00100010 01100011 01110100 11010101 00010110 00110111 11001000 10011001 01001010 10001011 10101100 11101101 00001110 10111111 0101正向代換反向代換43 在二元域上，如果明文和密文在二元域上，如果明文

22、和密文的長度都為的長度都為n則共有多少個(gè)可逆代換？則共有多少個(gè)可逆代換？課堂思考：課堂思考：44 在密碼設(shè)計(jì)中，可選在密碼設(shè)計(jì)中，可選n=r n0，其中，其中r和和n0都為正整都為正整數(shù)，將設(shè)計(jì)數(shù)，將設(shè)計(jì)n個(gè)變量的代換網(wǎng)絡(luò)化為設(shè)計(jì)個(gè)變量的代換網(wǎng)絡(luò)化為設(shè)計(jì)r個(gè)較小的子個(gè)較小的子代換網(wǎng)絡(luò)，而每個(gè)子代換網(wǎng)絡(luò)只有代換網(wǎng)絡(luò)，而每個(gè)子代換網(wǎng)絡(luò)只有n0個(gè)輸入變量。稱個(gè)輸入變量。稱每個(gè)子代換網(wǎng)絡(luò)為代換盒每個(gè)子代換網(wǎng)絡(luò)為代換盒(Substitution Box) S盒 x5 x4 x3 x2 x1 x0 y3 y2 y1 y0DES的S盒代換盒代換盒(S(S盒盒) )45DESDES的的S S1 1- -盒的輸

23、入和輸出關(guān)系盒的輸入和輸出關(guān)系nx5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 列號列號 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行號行號 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y3 , y2, y1 , y0)=(0,0,1,0)46 迄今為止，

24、有關(guān)方面未曾完全公開有關(guān)迄今為止，有關(guān)方面未曾完全公開有關(guān)DES的的S盒盒的設(shè)計(jì)準(zhǔn)則。的設(shè)計(jì)準(zhǔn)則。Branstead等曾披露過下述準(zhǔn)則：等曾披露過下述準(zhǔn)則：nP1 S盒的輸出都不是其輸入的線性或仿射函數(shù)。盒的輸出都不是其輸入的線性或仿射函數(shù)。nP2 改變改變S盒的一個(gè)輸入比特，其輸出至少有兩比特盒的一個(gè)輸入比特，其輸出至少有兩比特產(chǎn)生變化，即近一半產(chǎn)生變化。產(chǎn)生變化，即近一半產(chǎn)生變化。nP3 當(dāng)當(dāng)S盒的任一輸入位保持不變，其它盒的任一輸入位保持不變，其它5位輸入變位輸入變化時(shí)化時(shí)(共有共有25 =32種情況種情況)，輸出數(shù)字中的，輸出數(shù)字中的0和和1的總的總數(shù)近于相等。數(shù)近于相等。 這三點(diǎn)使這

25、三點(diǎn)使DES的的S盒能夠?qū)崿F(xiàn)較好的混淆。盒能夠?qū)崿F(xiàn)較好的混淆。S S盒的設(shè)計(jì)準(zhǔn)則盒的設(shè)計(jì)準(zhǔn)則47 問題問題: 如何將幾個(gè)如何將幾個(gè)S盒組合起來構(gòu)成一個(gè)盒組合起來構(gòu)成一個(gè)n值較大的組。值較大的組。 將幾個(gè)將幾個(gè)S S盒的輸入端并行，并通過坐標(biāo)置換盒的輸入端并行，并通過坐標(biāo)置換(P-(P-盒盒) )將各將各S S盒輸出比特次序打亂，再送到下一級盒輸出比特次序打亂，再送到下一級各各S S盒的輸入端，起到了盒的輸入端，起到了ShannonShannon所謂的所謂的“擴(kuò)散擴(kuò)散”作用。作用。S S盒提供非線性變換，將來自上一級不同的盒提供非線性變換，將來自上一級不同的S S盒的輸出進(jìn)行盒的輸出進(jìn)行“混淆混

26、淆”。經(jīng)過。經(jīng)過P P- -盒的擴(kuò)散作用使盒的擴(kuò)散作用使1 1均勻地分散到整個(gè)輸出矢量中，從而保證了輸出均勻地分散到整個(gè)輸出矢量中，從而保證了輸出密文統(tǒng)計(jì)上的均勻性，這就是密文統(tǒng)計(jì)上的均勻性，這就是ShannonShannon的乘積密碼的乘積密碼的作用。的作用。S S盒的組合盒的組合48 擴(kuò)散和混淆是由Shannon提出的設(shè)計(jì)密碼系統(tǒng)的兩個(gè)基本方法，目的是抗擊敵手對密碼系統(tǒng)的統(tǒng)計(jì)分析。如果敵手知道明文的某些統(tǒng)計(jì)特性，如消息中不同字母出現(xiàn)的頻率、可能出現(xiàn)的特定單詞或短語，而且這些統(tǒng)計(jì)特性以某種方式在密文中反映出來，那么敵手就有可能得出加密密鑰或其一部分，或者得出包含加密密鑰的一個(gè)可能的密鑰集合。

27、（2 2）擴(kuò)散和混淆）擴(kuò)散和混淆49n 在Shannon稱之為理想密碼的密碼系統(tǒng)中，密文的所有統(tǒng)計(jì)特性都與所使用的密鑰獨(dú)立。圖2討論的代換密碼就是這樣的一個(gè)密碼系統(tǒng)，然而它是不實(shí)用的。（2）擴(kuò)散和混淆）擴(kuò)散和混淆50 所謂擴(kuò)散，就是將明文的統(tǒng)計(jì)特性散布到密文中去，實(shí)現(xiàn)方式是使得明文的每一位影響密文中多位的值，等價(jià)于說密文中每一位均受明文中多位影響。 例如對英文消息M=m1m2m3的加密操作 其中ord(mi)是求字母mi對應(yīng)的序號，chr(i)是求序號i對應(yīng)的字母。1mod26knn iiychrord m（2）擴(kuò)散和混淆）擴(kuò)散和混淆51n 這時(shí)明文的統(tǒng)計(jì)特性將被散布到密文中，因而每一字母在密

28、文中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于相等，雙字母及多字母出現(xiàn)的頻率也更接近于相等。n 在二元分組密碼中，可對數(shù)據(jù)重復(fù)執(zhí)行某個(gè)置換，再對這一置換作用于一函數(shù)，可獲得擴(kuò)散。（2）擴(kuò)散和混淆）擴(kuò)散和混淆52 分組密碼在將明文分組依靠密鑰變換到密文分組時(shí)： 擴(kuò)散的目的是使明文和密文之間的統(tǒng)計(jì)關(guān)系變得盡可能復(fù)雜，以使敵手無法得到密鑰； 混淆是使密文和密鑰之間的統(tǒng)計(jì)關(guān)系變得盡可能復(fù)雜，以使敵手無法得到密鑰。（2）擴(kuò)散和混淆）擴(kuò)散和混淆53n 因此即使敵手能得到密文的一些統(tǒng)計(jì)關(guān)系，由于密鑰和密文之間的統(tǒng)計(jì)關(guān)系復(fù)雜化，敵手也無法得到密鑰。使用復(fù)雜的代換算法可以得到預(yù)期的混淆效果，而簡單的線性代換函數(shù)得到

29、的混淆效果則不夠理想。n 擴(kuò)散和混淆成功地實(shí)現(xiàn)了分組密碼的本質(zhì)屬性，因而成為設(shè)計(jì)現(xiàn)代分組密碼的基礎(chǔ)。（2）擴(kuò)散和混淆）擴(kuò)散和混淆54代換運(yùn)算代換運(yùn)算55n二進(jìn)制字次序被打亂 n重新排序的方法構(gòu)成密鑰 n叫這種變換為 P-boxes 代換運(yùn)算代換運(yùn)算56P-Box57Substitution-Permutation Network nShannon 把這兩種運(yùn)算組合在一起 n一些 S-boxes 由 P-box 連接n這種變換叫做混合變換n（mixing transformations）58替換替換-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò)59實(shí)際使用的替換實(shí)際使用的替換-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò)n實(shí)際中，我們需要加密，也需要

30、解密n因此，有兩種方法：n1.定義每個(gè)替換、置換的逆，這樣增加了復(fù)雜度2. 定義一種結(jié)構(gòu)，容易求逆，這樣可以使用基本的相同編碼或硬件用于加密和解密60nHorst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，設(shè)計(jì)了這樣的結(jié)構(gòu)，我們現(xiàn)在叫做feistel cipher n思想是把輸入塊分成左右兩部分 L(i-1) 和R(i-1), 變換是在密碼的第I輪只使用R(i-1) n函數(shù) g incorporates one stage of the S-P network的每個(gè)階段有g(shù) 工作，由第i 個(gè)密鑰控制（叫子密鑰）。F

31、eistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu)61 很多分組密碼的結(jié)構(gòu)從本質(zhì)上說都是基于一個(gè)稱為Feistel網(wǎng)絡(luò)的結(jié)構(gòu)。 Feistel提出利用乘積密碼可獲得簡單的代換密碼，乘積密碼指順序地執(zhí)行兩個(gè)或多個(gè)基本密碼系統(tǒng)，使得最后結(jié)果的密碼強(qiáng)度高于每個(gè)基本密碼系統(tǒng)產(chǎn)生的結(jié)果，F(xiàn)eistel還提出了實(shí)現(xiàn)代換和置換的方法。其思想實(shí)際上是Shannon提出的利用乘積密碼實(shí)現(xiàn)混淆和擴(kuò)散思想的具體應(yīng)用。Feistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu)62 圖3是Feistel網(wǎng)絡(luò)示意圖，加密算法的輸入是分組長為2w的明文和一個(gè)密鑰K。將每組明文分成左右兩半L0和R0，在進(jìn)行完n輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。其第i輪迭代的

32、輸入為前一輪輸出的函數(shù)： 其中Ki是第i輪用的子密鑰，由加密密鑰K得到。一般地，各輪子密鑰彼此不同而且與K也不同。111,iiiiiiLRRLF RK1.Feistel1.Feistel加密結(jié)構(gòu)加密結(jié)構(gòu)63圖3 Feistel網(wǎng)絡(luò)示意圖64 Feistel網(wǎng)絡(luò)中每輪結(jié)構(gòu)都相同，每輪中右半數(shù)據(jù)被作用于輪函數(shù)F后，再與左半數(shù)據(jù)進(jìn)行異或運(yùn)算，這一過程就是上面介紹的代換。每輪的輪函數(shù)的結(jié)構(gòu)都相同，但以不同的子密鑰Ki作為參數(shù)。 代換過程完成后，再交換左、右兩半數(shù)據(jù)，這一過程稱為置換。這種結(jié)構(gòu)是Shannon提出的代換置換網(wǎng)絡(luò)（substitution-permutation network, SPN）

33、的特有形式。1.Feistel1.Feistel加密結(jié)構(gòu)加密結(jié)構(gòu)65 Feistel網(wǎng)絡(luò)的實(shí)現(xiàn)與以下參數(shù)和特性有關(guān)： 分組大小分組越大則安全性越高，但加密速度就越慢。分組密碼設(shè)計(jì)中最為普遍使用的分組大小是64比特。 密鑰大小密鑰越長則安全性越高，但加密速度就越慢。現(xiàn)在普遍認(rèn)為64比特或更短的密鑰長度是不安全的，通常使用128比特的密鑰長度。1.1.Feistel 網(wǎng)絡(luò)的實(shí)現(xiàn)網(wǎng)絡(luò)的實(shí)現(xiàn)66n 輪數(shù)單輪結(jié)構(gòu)遠(yuǎn)不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為16。n 子密鑰產(chǎn)生算法該算法的復(fù)雜性越大，則密碼分析的困難性就越大。n 輪函數(shù)輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。1.

34、Feistel 網(wǎng)絡(luò)的實(shí)現(xiàn)網(wǎng)絡(luò)的實(shí)現(xiàn)67 在設(shè)計(jì)Feistel網(wǎng)絡(luò)時(shí)，還有以下兩個(gè)方面需要考慮： 快速的軟件實(shí)現(xiàn)在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無法用硬件實(shí)現(xiàn)。此時(shí)算法的執(zhí)行速度是考慮的關(guān)鍵。 算法容易分析如果算法能被無疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設(shè)計(jì)高強(qiáng)度的算法。1.1.Feistel 網(wǎng)絡(luò)的設(shè)計(jì)網(wǎng)絡(luò)的設(shè)計(jì)68 Feistel解密過程本質(zhì)上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，即第1輪使用Kn，第2輪使用Kn-1，最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。2.2.Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)

35、69 圖4的左邊表示16輪Feistel網(wǎng)絡(luò)的加密過程，右邊表示解密過程，加密過程由上而下，解密過程由下而上。為清楚起見，加密算法每輪的左右兩半用LEi和REi表示，解密算法每輪的左右兩半用LDi和RDi表示。 圖中右邊標(biāo)出了解密過程中每一輪的中間值與左邊加密過程中間值的對應(yīng)關(guān)系，即加密過程第i輪的輸出是LEiREi（表示鏈接），解密過程第16-i輪相應(yīng)的輸入是RDiLDi。2.2.Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)70明文(2w比特) F1L1R0L0RW比特W比特第1輪 FnLnR1nL1nR第n輪1KnK密文(2w比特)1nL1nR712 Feistel網(wǎng)絡(luò)解密結(jié)構(gòu)網(wǎng)絡(luò)解密結(jié)構(gòu)輸入（明文）

36、 F1K F1K0LE0RE1RE1LE2RE2LE F15K14RE14LE F16K15LE15RE16RE16LE輸出（密文）輸入（密文） F16K160RELD 160LERD F15K F2K F1K輸出（明文）151LERD 151RELD142RELD 142LERD 214RELD 214LERD 115LERD115RELD 016RELD 016LERD72圖4 Feistel加解密過程73 加密過程的最后一輪執(zhí)行完后，兩半輸出再經(jīng)交換，因此密文是RE16LE16。解密過程取以上密文作為同一算法的輸入，即第1輪輸入是RE16LE16，等于加密過程第16輪兩半輸出交換后的結(jié)果

37、。下面證明解密過程第1輪的輸出等于加密過程第16輪輸入左右兩半的交換值。2.2.Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)74在加密過程中：在解密過程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLE2.2.Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)75 所以解密過程第1輪的輸出為LE15RE15，等于加密過程第16輪輸入左右兩半交換后的結(jié)果。容易證明這種對應(yīng)關(guān)系在16輪中每輪都成立。一般地，加密過程的第i輪有因此111,iiiiiiLERERELEF REK111,iiii

38、iiiiiRELELEREF REKREF LEK2.2.Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)76 以上兩式描述了加密過程中第i輪的輸入與第i輪輸出的函數(shù)關(guān)系，由此關(guān)系可得圖4右邊顯示的LDi和RDi的取值關(guān)系。 最后可以看到，解密過程第16輪的輸出是RE0LE0，左右兩半再經(jīng)一次交換后即得最初的明文。2.2.Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)77nShannons 混合變換形成一種特殊的乘積密碼，組成部分一起工作: nS-Boxes （S-盒)：提供輸入bits混合作用 (confusion) 其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，使明文和密文之間、密文和密鑰之間的統(tǒng)計(jì)相關(guān)特性極小化

39、，從而使統(tǒng)計(jì)分析攻擊不能奏效。通常的方法是“替換（Substitution)”（回憶愷撒密碼）。2.2.Feistel 結(jié)構(gòu)設(shè)計(jì)原理結(jié)構(gòu)設(shè)計(jì)原理78P-BoxesnP-Boxes：提供擴(kuò)散作用(diffusion) 將明文及密鑰的影響盡可能迅速地散布到較多個(gè)輸出的密文中（將明文冗余度分散到密文中）。產(chǎn)生擴(kuò)散的最簡單方法是通過“換位(Permutation)”（比如：重新排列字符）n這種效果進(jìn)一步解釋為”雪崩”與”完全性” (Avalanche and Completeness )by Webster & Tavares nOn the Design of S-boxes, in Adv

40、ances in Cryptology - Crypto 85, Lecture Notes in Computer Science, No 218, Springer-Verlag, 1985, pp 523-53479雪崩效應(yīng)雪崩效應(yīng)(Avalanche effect )n輸入改變1bit, 導(dǎo)致近一般的比特發(fā)生變化n一個(gè)函數(shù)F具有好的雪崩特性是指: 對2m個(gè)明文 向量, 分為2m-1個(gè)向量對xi和xi,每對向量只有一個(gè)bit不同, 定義Vi = f(X) XOR f(Xi) ,則近一半的Vi為1.80完備性效應(yīng)完備性效應(yīng)(Completeness effect )n每個(gè)輸出比特是所有輸入

41、比特的復(fù)雜函數(shù)的輸出，n www.cs.adfa.oz.au/teaching/studinfo/csc/lectures/ss-less07.html具有好的完備性是指: 對密文輸出向量的每一比特j, 0jm, 至少存在一個(gè)明文對(xi,xi), 此明文對只在第i比特不同,且F(xi)與F(xi)的第j比特不同.81分組密碼設(shè)計(jì)分組密碼設(shè)計(jì)(Block Cipher Design) n這些設(shè)計(jì)原理是設(shè)計(jì)好的分組密碼的準(zhǔn)這些設(shè)計(jì)原理是設(shè)計(jì)好的分組密碼的準(zhǔn)則。則。 n“雪崩雪崩”保證小的輸入變化導(dǎo)致大的輸保證小的輸入變化導(dǎo)致大的輸出變化；出變化；n完全性保證每個(gè)輸出比特依賴于所有的完全性保證每個(gè)

42、輸出比特依賴于所有的輸入比特；輸入比特；n我們可以看到我們可以看到,古典密碼沒有這些性質(zhì)。古典密碼沒有這些性質(zhì)。82Feistel Cipher 設(shè)計(jì)設(shè)計(jì)n設(shè)計(jì)密碼時(shí),下列參數(shù)需要考慮: n分組大小分組大小(block size) 增加分組長度會(huì)提高安全性, 但降低了密碼運(yùn)算速度n密鑰大小密鑰大小(key size) 增加密鑰長度,可以提高安全性(使得窮搜索困難),同樣,降低了密碼速度. 83n輪數(shù)輪數(shù) 增加輪數(shù)可以提高安全性,但降低速度n子密鑰生成子密鑰生成 子密鑰生成越復(fù)雜,就越安全,但降低速度n輪函數(shù)輪函數(shù) 復(fù)雜的輪函數(shù)能夠使的密碼分析困難,但降低速度 n(所有問題就是平衡問題)n設(shè)計(jì)”

43、安全”的密碼算法并不難,只要使用足夠多的輪數(shù)就可以,但降低速度n 得到一個(gè)快速安全的算法是困難的Feistel Cipher 設(shè)計(jì)設(shè)計(jì)84密碼設(shè)計(jì)密碼設(shè)計(jì) 評價(jià)評價(jià) “好的”密碼設(shè)計(jì)具有: 雪崩特性,完備性,不可預(yù)料性(avalanche, completeness, unpredictability )n差的密碼設(shè)計(jì)缺乏隨機(jī)性,具有太大的可預(yù)料性n許多密碼都被攻破 (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers) n即使密碼學(xué)專家也會(huì)犯這樣的錯(cuò)誤n最好的辦法是測試, 通過

44、實(shí)際檢驗(yàn)證明它的安全性85n若以一個(gè)簡單函數(shù)若以一個(gè)簡單函數(shù)f，進(jìn)行多次迭代，就稱其為迭代密碼。，進(jìn)行多次迭代，就稱其為迭代密碼。n每次迭代稱作一輪每次迭代稱作一輪(Round)。相應(yīng)函數(shù)。相應(yīng)函數(shù)f 稱作輪函數(shù)。稱作輪函數(shù)。n每一輪輸出都是前一輪輸出的函數(shù)，即每一輪輸出都是前一輪輸出的函數(shù)，即y(i)=fy(i-1), k(i)，其，其中中k(i)是第是第i輪迭代用的子密鑰，由秘密密鑰輪迭代用的子密鑰，由秘密密鑰k通過密鑰生成通過密鑰生成算法產(chǎn)生。算法產(chǎn)生。 子 密 鑰 產(chǎn) 生 器kk(1)k(2)k(r)y(0) = xy(1)y(2)y(r-1)y(r)=y迭代分組密碼迭代分組密碼86

45、加密函數(shù)加密函數(shù)f(x, k)，實(shí)現(xiàn)，實(shí)現(xiàn)F F2n F F2t F F2n的映射。的映射。其中，其中，n是分組長，是分組長，t是密鑰長。若對每個(gè)密鑰取值是密鑰長。若對每個(gè)密鑰取值都有都有 ff(x, k)，k=x，即，即f(x, k)2 =I (恒等置換恒等置換) 則稱其為對合密碼，以則稱其為對合密碼，以fI表示。表示。對合密碼對合密碼( (Involution Cipher) )87I I型迭代分組密碼型迭代分組密碼n以對合密碼函數(shù)構(gòu)造的多輪迭代分組密碼以對合密碼函數(shù)構(gòu)造的多輪迭代分組密碼。Ex, k=fIfI fI fIx, k(1)，k(2) ，k(r-1)，k(r)Dy, k =fI

46、 fI fIfIy, k(r)，k(r-1) ，k(2) ，k(1) n 缺點(diǎn)：對任意偶數(shù)輪變換，若對所有缺點(diǎn)：對任意偶數(shù)輪變換，若對所有i選擇選擇k(2i-1) =k(2i)，則，則加密的變換等價(jià)于恒等變換，在實(shí)用中需要避免這類密鑰加密的變換等價(jià)于恒等變換，在實(shí)用中需要避免這類密鑰選擇。選擇。88n對合置換對合置換 令令P是對是對x的置換，即的置換，即P： F F2n F F2n ，若對所有，若對所有x GF(2n)，有，有PPx=x，即，即PP=I(恒等置換恒等置換)，以，以PI表示。表示。nII型迭代分組密碼型迭代分組密碼 每輪采用對合密碼函數(shù)和對合置換級連，即每輪采用對合密碼函數(shù)和對合置換級連，即 Fx, kPI fI x, k 并選解密子密鑰與加密子密鑰逆序，則加密解并選解密子密鑰與加密子密鑰逆序，則加密解密可用同一器件完成。密可用同一器件完成。 DES、FEAL和和LOKI等都屬此類。等都屬此類。對合置換和對合置換和IIII型迭代分組密碼型迭代分組密碼89 群密碼群密碼：若密鑰與明文、密文取自同一空間：若密鑰與明文、密文取自同一空間GF(2 n)，且，且 y=x k，式中，式中， 是是群運(yùn)算群運(yùn)算，則稱其為，則稱其為群密碼。群密碼。 顯然顯然x可通過可通過k的逆元求得的逆元求得 x=y k-1