第3講-對稱密鑰密碼體制

第3講

對稱密鑰密碼體制1按加解密采用的密鑰不同按密碼出現(xiàn)的時間不同古典密碼現(xiàn)代密碼密碼學（Cryptology）(Symmetriccipher)(Asymmetriccipher)分組密碼流密碼公鑰密碼按加密的方式對稱密碼非對稱密碼(Classicalcipher)(Moderncipher)(Blockcipher)(Streamcipher)(Public-Keycipher)什么是流密碼一次一密：指在流密碼當中使用與消息長度等長的隨機密鑰,密鑰本身只使用一次流密碼的研究現(xiàn)狀當前對流密碼的研究主要集中在以下兩個方向：（1）什么樣的序列可以作為安全可靠的密鑰序列？即衡量密鑰流序列好壞的標準。（2）如何構(gòu)造線性復雜度高、周期大的密鑰流序列？在保密強度要求高的場合如大量軍事密碼系統(tǒng)，仍多采用流密碼，美軍的核心密碼仍是“一次一密”的流密碼體制。鑒于流密碼的分析和設(shè)計在軍事和外交保密通信中有重要價值，流密碼的設(shè)計基本上都是保密的，國內(nèi)外少有專門論述流密碼學的著作，公開的文獻也不多。盡管如此，由于流密碼長度可靈活變化，且具有運算速度快、密文傳輸中沒有差錯或只有有限的錯誤傳播等優(yōu)點，目前仍是國際密碼應(yīng)用的主流，而基于偽隨機序列的流密碼是當今最通用的密碼系統(tǒng)。流密碼的研究現(xiàn)狀3.1

流密碼在流密碼中，將明文消息按一定長度分組（長度較小，通常按字或字節(jié)），然后對各組用相關(guān)但不同的密鑰進行加密，產(chǎn)生相應(yīng)的密文，相同的明文分組會因在明文序列中的位置不同而對應(yīng)于不同的密文分組。相對分組密碼而言，流密碼主要有以下優(yōu)點：第一，在硬件實施上，流密碼的速度一般要比分組密碼快，而且不需要有很復雜的硬件電路：第二，在某些情況下（例如對某些電信上的應(yīng)用），當緩沖不足或必須對收到的字符進行逐一處理時，流密碼就顯得更加必要和恰當；第三，流密碼能較好地隱藏明文的統(tǒng)計特征等。流密碼的原理在流密碼中，明文按一定長度分組后被表示成一個序列，并稱為明文流，序列中的一項稱為一個明文字。加密時，先由主密鑰產(chǎn)生一個密鑰流序列，該序列的每一項和明文字具有相同的比特長度，稱為一個密鑰字。然后依次把明文流和密鑰流中的對應(yīng)項輸入加密函數(shù)，產(chǎn)生相應(yīng)的密文字，由密文字構(gòu)成密文流輸出。即 設(shè)明文流為：M=m1

m2…mi…

密鑰流為：K=k1

k2…ki…

則加密為：C=c1

c2…ci…=Ek1(m1)Ek2(m2)…Eki(mi)…

解密為：M=m1

m2…mi…=Dk1(c1)Dk2(c2)…Dki(ci)…流密碼通信模式框圖加密算法E密文ci=Ek(mi)解密算法D明文mi=Dk(ci)明文mi密鑰ki密鑰ki流密碼的原理例

設(shè)明文、密鑰、密文都是F2上的二元數(shù)字序列，明文m=m1m2···，密鑰為k=k1k2···，若加密變換與解密變換都是F2中的模2加法，試寫出加密過程與解密過程。

[解]經(jīng)加密變換得密文：

C=Ek(m)=Ek1(m1)Ek2(m2)···=(k1+m1)(k2+m2)···

經(jīng)解密變換得：

Dk(C)=Dk((k1+m1)(k2+m2)···)=(k1+k1+m1)(k2+k2+m2)···

由于ki∈F2，則ki+ki=0，i=1,2,···，故Dk(C)=m1m2···=m。密文C可由明文m與密鑰k進行模2加獲得。因此要用該密碼系統(tǒng)通信就要求每發(fā)送一條消息都要產(chǎn)生一個新的密鑰并在一個安全的信道上傳送，習慣上人們稱這種通信系統(tǒng)為“一次一密系統(tǒng)”。流密碼的時變性--隨時間而變化流密碼采用了類似于一次一密的思想，但加密各明文字的密鑰字不是獨立隨機選取的，而是由一個共同的較短的主密鑰按一個算法產(chǎn)生的。因此，它不具有一次一密的無條件安全性，但增加了實用性，只要算法設(shè)計得當，其安全性可以滿足實際應(yīng)用的需要。密鑰流中的元素的產(chǎn)生由i時刻的流密碼內(nèi)部狀態(tài)（記作）和種子密鑰（記作k）決定，即；加密變換與解密變換也和i時刻的流密碼內(nèi)部狀態(tài)有關(guān)。流密碼分類用狀態(tài)轉(zhuǎn)移函數(shù)描述流密碼加密器中存儲器的狀態(tài)隨時間變化的過程。同步流密碼：如果某個流密碼中的狀態(tài)轉(zhuǎn)移函數(shù)不依賴被輸入加密器存儲器的明文，即密鑰流的生成獨立于明文流和密文流的流密碼稱為同步流密碼。使用最廣泛。自同步流密碼也叫異步流密碼：狀態(tài)轉(zhuǎn)移函數(shù)與輸入明文有關(guān)，即其中密鑰流的產(chǎn)生并不是獨立于明文流和密文流的。通常第i個密鑰字的產(chǎn)生不僅與主密鑰有關(guān)，而且與前面已經(jīng)產(chǎn)生的若干個密文字（與明文字）有關(guān)。加密算法E密鑰流發(fā)生器解密算法D密鑰流發(fā)生器安全通道密鑰k密文流ci密鑰流ki密鑰流ki明文流mi明文流mi圖1同步流密碼模型內(nèi)部狀態(tài)輸出函數(shù)內(nèi)部狀態(tài)輸出函數(shù)密鑰發(fā)生器密鑰發(fā)生器明文流mi密文流ci明文流mi種子k種子kkk圖2自同步流密碼模型同步流密碼中，消息的發(fā)送者和接收者必須同步才能做到正確地加密解密，即雙方使用相同的密鑰，并用其對同一位置進行操作。一旦由于密文字符在傳輸過程中被插入或刪除而破壞了這種同步性，那么解密工作將失敗。否則，需要在密碼系統(tǒng)中采用能夠建立密鑰流同步的輔助性方法。分解后的同步流密碼密鑰流生成器密鑰流生成器設(shè)計中，在考慮安全性要求的前提下還應(yīng)考慮以下兩個因素：

密鑰k易于分配、保管、更換簡單；易于實現(xiàn)，快速。目前密鑰流生成器大都是基于移位寄存器的。因為移位寄存器結(jié)構(gòu)簡單，易于實現(xiàn)且運行速度快。這種基于移位寄存器的密鑰流序列稱為移位寄存器序列。密鑰流生成器一個反饋移位寄存器由兩部分組成：移位寄存器和反饋函數(shù),構(gòu)成一個密鑰流生成器。每次輸出一位，移位寄存器中所有位都右移一位，新的最左端的位根據(jù)寄存器中其它位計算得到。移位寄存器輸出的一位常常是最低有效位。移位寄存器的周期是指輸出序列從開始到重復時的長度。這種方法通過一個種子（有限長）產(chǎn)生具有足夠長周期的、隨機性良好的序列。只要生成方法和種子都相同，就會產(chǎn)生完全相同的密鑰流。反饋函數(shù)若，則該LFSR生成的序列為周期序列。又稱為n階線性遞歸關(guān)系密鑰流生成器最簡單的反饋移位寄存器是線性移位寄存器（LFSR），反饋函數(shù)是寄存器中某些位的簡單異或。如教材P64圖4.5。異或(XOR)運算，異或密文和相同的密鑰流就可以完成解密操作。流密碼基于XOR運算具有下列屬性：如果B=A⊕K，那么A=B⊕K。n級移位寄存器（見下圖）開始時，設(shè)第1級內(nèi)容是an-1，第2級內(nèi)容是an-2,···,第n級內(nèi)容是a0，則稱這個寄存器的初始狀態(tài)是(a0,a1,···,an-1)。當加上一個脈沖時，每個寄存器的內(nèi)容移給下一級，第n級內(nèi)容輸出，同時將各級內(nèi)容送給運算器f(x0,x1,···,xn-1)，并將運算器的結(jié)果an=f(a0,a1,…,an-1)反饋到第一級去。這樣這個移位寄存器的狀態(tài)就是(a1,a2,···,an)，而輸出是a0。不斷地加脈沖，上述

n

級移位寄存器的輸出就是一個二元(或q元)序列：a0,a1,a2,···寄存器1寄存器2寄存器3寄存器nf(x0,x1,···,xn-1)···密鑰流生成器移位寄存器產(chǎn)生的序列都是周期序列，周期都不大于2n。例

右圖是一個4級線性移位寄存器。給定初狀態(tài)(0001)，求該移位寄存器產(chǎn)生的周期序列。

[解]易見f(x0，x1，x2，x3)=x0+x1，因此對k≥4有ak=ak-3+ak-4

從而該4級移位寄存器產(chǎn)生的序列是周期15的序列：

000100110101111…線性移存器序列的最長周期為2n－1由上例知，移位寄存器(簡記SR，ShiftedRegister)可由短的序列生成具有一定規(guī)律的長序列。這種序列便可以作為密鑰流序列，但抗攻擊能力較差。+密鑰流生成器狀態(tài)轉(zhuǎn)移和相應(yīng)輸出

時刻狀態(tài)輸出32100000011110000201000300100410011511000601100710111801011910100101101111111001211111130111114001111500011

多項式以LFSR的反饋系數(shù)所決定的多項式

又稱反饋多項式、連接多項式。式中，c0=cn=1互反多項式

稱作是LFSR的特征多項式。cn0稱之為非奇異LFSR。

收縮密鑰流生成器（見右圖）通常的密鑰流生成器都是由若干個移位寄存器并聯(lián)，并且與特殊的電子電路組合而成。上圖為由兩個移位寄存器構(gòu)成的收縮密鑰流生成器，通過SR1的輸出選擇SR2的輸出來生成密鑰流，其工作模式如下：輸入?yún)?shù)：兩個移位寄存器的級數(shù)及反饋函數(shù)密鑰：兩個移位寄存器的初始狀態(tài)

(1)移位SR1

并產(chǎn)生yi(1)

；同時移位SR2

并產(chǎn)生yi(2)

；

(2)如果yi(1)=1，則輸出密鑰元素ki=yi(2)

；如果yi(1)=0，則刪去

yi(2)，i=1,2,…，不輸出。由此收縮生成器產(chǎn)生的密鑰流為{ki|i≥1}。SR1SR2yi(1)輸出kiyi(2)密鑰流生成器流密碼對密鑰流的要求沒有絕對不可破的密碼，比如窮搜索總能破譯，只是破譯所需時間是否超過信息的有效期以及破譯所需代價是否值得。若一個加密算法沒有比窮搜索更好的破譯方法，則被認為是不可破的。實際使用的密鑰流序列（簡稱密鑰）都是按一定算法生成的，因而不可能是完全隨機的，所以也就不可能是完善保密系統(tǒng)。為了盡可能提高系統(tǒng)的安全強度，就必須要求所產(chǎn)生的密鑰流序列盡可能具有隨機序列的某些特征。如極大的周期、良好的統(tǒng)計特性。3.2

分組密碼其他分組密碼數(shù)據(jù)加密標準DESFeistel密碼結(jié)構(gòu)分組密碼的設(shè)計原則分組密碼的原理分組密碼的典型攻擊方法1.分組密碼的原理密文中的每位數(shù)字不僅僅與某時刻輸入的明文數(shù)字有關(guān)，而是與該明文中一定組長的明文數(shù)字有關(guān)。分組密碼將明文按一定的位長分組，輸出是固定長度的密文。加密算法解密算法明文x=(x1,x2,···)密文y=(y1,y2,···,yn)明文x=(x1,x2,···)密鑰k=(k1,k2,···)密鑰k=(k1,k2,···)分組密碼的基本模型分組密碼的長度明文為分組長度為m的序列，密文為分組長度為n的序列：n>m，稱其為有數(shù)據(jù)擴展的分組密碼；n<m，稱其為有數(shù)據(jù)壓縮的分組密碼；n=m，稱其為無數(shù)據(jù)擴展與壓縮的分組密碼。我們一般所說的分組密碼為無數(shù)據(jù)擴展與壓縮的分組密碼。典型的分組是64位或128位分組密碼的特點主要優(yōu)點：易于標準化；易于實現(xiàn)同步。主要缺點：不善于隱藏明文的數(shù)據(jù)模式、對于重放、插入、刪除等攻擊方式的抵御能力不強。分組密碼的數(shù)學表示記明文空間和密文空間為（明文與密文分組的長度均為m），密鑰空間為（是的子集，r為密鑰長度）：密鑰k下的加密函數(shù)為，m表示待加密的信息，k為密鑰，則可將該映射記為，這個映射應(yīng)滿足：，是的一個置換；密鑰k下的解密函數(shù)記為，它是的逆。2.分組密碼的設(shè)計原則安全性角度：“混亂原則”：為了避免密碼分析者利用明文與密文之間的依賴關(guān)系進行破譯，密碼的設(shè)計應(yīng)該保證這種依賴關(guān)系足夠復雜?！皵U散原則”：為避免密碼分析者對密鑰逐段破譯，密碼的設(shè)計應(yīng)該保證密鑰的每位數(shù)字能夠影響密文中的多位數(shù)字；同時，為了避免避免密碼分析者利用明文的統(tǒng)計特性，密碼的設(shè)計應(yīng)該保證明文的每位數(shù)字能夠影響密文中的多位數(shù)字，從而隱藏明文的統(tǒng)計特性。2.分組密碼的設(shè)計原則可實現(xiàn)性角度：應(yīng)該具有標準的組件結(jié)構(gòu)（子模塊），以適應(yīng)超大規(guī)模集成電路的實現(xiàn)。分組密碼的運算能在子模塊上通過簡單的運算進行。3.3Feistel密碼結(jié)構(gòu)加密:

Li=Ri-1

Ri=Li-1F(Ri-1,Ki)解密:

Ri-1=Li

Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel結(jié)構(gòu)依賴參數(shù)和特征分組長度：分組長度越長意味著安全性越高（其他條件不變），但是會降低加解密的速度。一般64位的分組長度。密鑰長度：密鑰較長意味著安全性較高，但會降低加解密的速度。一般需要128位密鑰，64位密鑰通常不夠。迭代輪數(shù)：Feistel密碼的本質(zhì)在于單輪不能提供足夠的安全性，多輪可取得很高安全性。迭代輪數(shù)的典型值為16。子密鑰產(chǎn)生算法：子密鑰越復雜，密碼分析攻擊越困難。輪函數(shù)：輪函數(shù)越復雜，抗攻擊的能力就越強。3.4數(shù)據(jù)加密標準DES

（DataEncryptionStandard）DES（DataEncryptionStandard）算法于1977年得到美國政府的正式許可，是一種用56位密鑰來加密64位數(shù)據(jù)的方法，其密文的長度也為64位。國內(nèi)隨著三金工程尤其是金卡工程的啟動，DES算法在ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費站等領(lǐng)域被廣泛應(yīng)用，以此來實現(xiàn)關(guān)鍵數(shù)據(jù)的保密。如信用卡持卡人的PIN的加密傳輸，IC卡與POS間的雙向認證、金融交易數(shù)據(jù)包的MAC校驗等，均用到DES算法。DES(DataEncryptionStandard)是由IBM公司在20世紀70年代研制的，經(jīng)過政府的加密標準篩選后，于1976年11月被美國政府采用，隨后被美國國家標準局和美國國家標準協(xié)會(ANSI)所認可。DES算法具有以下特點：（1）DES算法是分組加密算法：以64位為分組。（2）DES算法是對稱算法：加密和解密用同一密鑰。（3）DES算法的有效密鑰長度為56位。（4）換位和置換。（5）易于實現(xiàn)。1.DES的產(chǎn)生背景DES的生命期NBS最終采納了IBM的LUCIFER方案，于1975年公開發(fā)表。1977年正式頒布為數(shù)據(jù)加密標準（DES-DataEncryptionStandard）。1979年，美國銀行協(xié)會批準使用DES。1980年，DES成為美國標準化協(xié)會(ANSI)標準。1984年，ISO開始在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標準。美國國家安全局NSA每隔年對該算法進行評估，1994年，決定1998年12月之后不再使用DES?，F(xiàn)已經(jīng)確定了選用Rijndael算法作為高級加密算法AES。2.DES算法要點算法設(shè)計中采用的基本變換和操作：置換（P）：重新排列輸入的比特位置。交換（SW）：將輸入的左右兩部分的比特進行互換。循環(huán)移位：將輸入中的比特進行循環(huán)移位，作為輸出。一個復雜變換（fK

）通常是一個多階段的乘積變換；與密鑰Key相關(guān)；必須是非線性變換；實現(xiàn)對密碼分析的擾亂；是密碼設(shè)計安全性的關(guān)鍵。3.DES的加密過程第一步：初始置換IP。對于給定的明文m，通過初始置換IP獲得，并將分為兩部分，前面32位記為，后面32位記為，即第二步：乘積變換（

16輪）。在每一輪中依據(jù)下列方法計算（）（16輪中的計算方法相同）：，其中，為第i輪使用的子密鑰，各均為的一個置換選擇，所有構(gòu)成密鑰方案。函數(shù)中的變量為32位字符串，為48位字符串，函數(shù)輸出的結(jié)果為32位字符串。DES的加密過程第三步：初始置換的逆置換。應(yīng)用初始置換的逆置換對進行置換，得到密文c，即。Li-1Ri-1LiRikif+一輪DES加密過程IPL0R0L1=R0R1=L0⊕f(R0,K1)R2=L1⊕f(R1,K2)L2=R1明文L15=R14R16=L15⊕f(R15,K16)R15=L14⊕f(R14,K15)L16=R15IP-1密文fK1fK2fK16DES加密流程圖LRexpandshiftshiftkeykeyS-boxescompressLR28282828282848324832323232OneRoundofDES4832KiPbox（1）IP置換表和IP-1逆置換表輸入的64位數(shù)據(jù)按IP表置換進行重新組合，并把輸出分為L0和R0兩部分，每部分各32位，其IP表置換如表3-1所示表3-1IP置換表5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315741

初始置換IP和IP-1IPIP-1將輸入的64位明文的第58位換到第1位，第50位換到第2位，依此類推，最后一位是原來的第7位。L0和R0則是換位輸出后的兩部分，L0是輸出的左32位，R0是右32位。比如：置換前的輸入值為D1D2D3…D64，則經(jīng)過初始置換后的結(jié)果為：L0=D58D50…D8，R0=D57D49…D7。經(jīng)過16次迭代運算后。得到L16和R16，將此作為輸入進行逆置換，即得到密文輸出。表3-2IP-1逆置換表逆置換正好是初始置的逆運算，例如，第1位經(jīng)過初始置換后，處于第40位，而通過逆置換IP-1，又將第40位換回到第1位，其逆置換IP-1規(guī)則表如3-2所示。40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725(2)函數(shù)f的內(nèi)部流程Ri-1（32bit）ES1S2S8PKi（48bit）48bit32bitf(Ri-1,ki)(32bit)E變換的算法是從Ri-1的32位中選取某些位，構(gòu)成48位，即E將32位擴展為48位。變換規(guī)則根據(jù)E位選擇表，如表3-3所示。表3-3E位選擇表3212345456789891011121312131415161716171819202120212223242524252627282928293031321每個S盒輸出4位，共32位，S盒的工作原理將在第4步介紹。S盒的輸出作為P變換的輸入，P的功能是對輸入進行置換，P換位表如表3-4所示。Ki是由密鑰產(chǎn)生的48位比特串，具體的算法是：將E的選位結(jié)果與Ki作異或操作，得到一個48位輸出。分成8組，每組6位，作為8個S盒的輸入。表3-4P換位表如表1672021291228171152326518311028241432273919133062211425（3）DES的密鑰Ki計算DES在各輪中所用的密鑰均為由初始密鑰（即種子密鑰）導出的48位密鑰。初始密鑰為64位，其中第8、16、24、32、40、48、56、64位均為校驗位。如此設(shè)置校驗位的目的是使每8個字節(jié)所含的字符“1”個數(shù)為奇數(shù)，以便能夠檢測出每個字節(jié)中的錯誤。子密鑰ki產(chǎn)生流程圖PC-1C0D0LS1LS1C1D1LS2LS2C2D2LS16LS16C16D16PC-2PC-2PC-2K(64bit)K1(48bit)K2(48bit)K16(48bit)假設(shè)初始密鑰為K，長度為64位，但是其中第8，16，24，32，40，48，64作奇偶校驗位，實際密鑰長度為56位。K下標i的取值范圍是1到16，用16輪來構(gòu)造。構(gòu)造過程如圖所示。50子密鑰的產(chǎn)生產(chǎn)生子密鑰Ki具體描述為：首先，對于給定的密鑰K，應(yīng)用PC1變換進行選位，選定后的結(jié)果是56位，設(shè)其前28位為C0，后28位為D0。PC1選位如表3-5所示。表3-5PC-1選位表57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124第1輪：對C0作左移LS1得到C1，對D0作左移LS1得到D1，對C1D1應(yīng)用PC2進行選位，得到K1。其中LS1是左移的位數(shù)，如表3-6所示。第2輪：對C1和D1作左移LS2得到C2和D2，進一步對C2D2應(yīng)用PC2進行選位，得到K2。如此繼續(xù)，分別得到K3，K4，…，K16。表3-6LS移位表輪數(shù)循環(huán)左移位數(shù)輪數(shù)循環(huán)左移位數(shù)輪數(shù)循環(huán)左移位數(shù)輪數(shù)循環(huán)左移位數(shù)115291132216210214232721121524282122161表3-7PC-2選位表1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932（4）S盒的工作原理S盒以6位作為輸入，而以4位作為輸出，現(xiàn)在以S1為例說明其過程。假設(shè)輸入為A=a1a2a3a4a5a6，則a2a3a4a5所代表的數(shù)是0到15之間的一個數(shù)，記為：k=a2a3a4a5；由a1a6所代表的數(shù)是0到3間的一個數(shù)，記為h=a1a6。在S1的h行，k列找到一個數(shù)B，B在0到15之間，它可以用4位二進制表示，為B=b1b2b3b4，這就是S1的輸出。S盒由8張數(shù)據(jù)表組成，如教材P84-85所示。S-盒的構(gòu)造

DES加密范例已知明文m=computer，密鑰k=program。

m=0110001101101111011011010111000001110101011101000110010101110010

k=01110000011100100110111101100111011100100110000101101101這里k只有56bit，必須插入第8，16，24，32，40，48，56，64這8個奇偶校驗位成為64比特。k=0111000*0011100*1001101*1110110*0111011*1001001*1000010*1101101*m經(jīng)過IP置換后得

L0=11111111101110000111011001010111

R0=00000000111111110000011010000011

密鑰k經(jīng)PC-1置換得

C0=1110110010011001000110111011

D0=1011010001011000100011100111C0和

D0各循環(huán)左移一位后通過PC-2得到48bit的子密鑰k1。

C1=1101100100110010001101110111

D1=0110100010110001000111001111k1=001111011000111111001101001101110011111101001000DES加密范例R0經(jīng)過E變換后擴展為48bit。100000000001011111111110100000001101010000000110再和k1

作異或運算，得101111011001100000110011101101111110101101001110分成8組

101111011001100000110011101101111110101101001110經(jīng)過S盒后輸出32bit01110110110101000010011010100001再經(jīng)過P置換得01000100001000011001111110011011DES加密范例所以第一輪迭代的結(jié)果為

=10111011100110011110100111001100DES加密范例4.DES的解密過程采用與加密相同的算法。以逆序（即）使用密鑰。實現(xiàn)效果

不同微處理器上的DES軟件實現(xiàn)速度

處理器處理器速度（MHz）每秒處理的DES分組個數(shù)80884.7370680007.69008028661,10068020163,50068030163,90080286255,000680305010,000680402516,000680404023,000804866643,000雪崩效應(yīng)明文或密鑰的微小改變將對密文產(chǎn)生很大的影響是任何算法所期望的一個好性質(zhì)。明文或密鑰的某一位發(fā)生變化會導致密文的很多位發(fā)生變化。如果相應(yīng)的改變很小，可能會給分析者提供縮小搜索密鑰或明文空間的渠道。DES顯示出很強的雪崩效應(yīng)：如下兩條僅有一位不同的明文：00000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000密鑰：00000011001011010010011000100011100001100000111000110010結(jié)果表明僅經(jīng)過3輪迭代后，兩段數(shù)據(jù)有21位不同。全部迭代完成后得到的兩段密文則有34位不同。DES的雪崩效應(yīng)(a)明文的變化(b)密鑰的變化輪數(shù)改變的位數(shù)輪數(shù)改變的位數(shù)0116221335439534632731829...0012214328432530632735834...

5.DES的安全性分析DES的安全性完全依賴于密鑰，與算法本身沒有關(guān)系。主要研究內(nèi)容：密鑰的互補性；弱密鑰與半弱密鑰；密文-明文相關(guān)性；密文-密鑰相關(guān)性；S-盒的設(shè)計；密鑰搜索。密鑰的互補性DES算法具有互補性，即：若、是的補、是的補，則。使用DES算法時不要使用互補的密鑰，否則當密碼攻擊者選擇明文攻擊時，他們僅需試驗一半密鑰。弱密鑰弱密鑰：由密鑰k

確定的加密函數(shù)與解密函數(shù)相同，即。DES的弱密鑰：如果各輪產(chǎn)生的子密鑰一樣，則加密函數(shù)與解密函數(shù)相同。DES至少有4個弱密鑰：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe半弱密鑰半弱密鑰：對于密鑰

k

，存在一個不同的密鑰，滿足。DES的半弱密鑰：子密鑰生成過程中只能產(chǎn)生兩個不同的子密鑰或四個不同的子密鑰，互為對合。DES至少有12個半弱密鑰。S-盒的設(shè)計原則S-盒的設(shè)計原理沒有公開，一些原則如下：所有S-盒的每一行是0,1,…,15的一個置換；所有S-盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)；S-盒的輸入改變?nèi)我庖晃欢紩疠敵鲋兄辽賰晌话l(fā)生變化；對于任何輸入x（6位），S(x)與S(x⊕001100)至少有兩位不同；對于任何輸入x（6位），S(x)與S(x⊕00ef00)不相等，e,f取0或1；對于任意一個輸入位保持不變而其他五位變化時，輸出中0和1的數(shù)目幾乎相等。針對DES的攻擊方法攻擊DES的方法主要有：密鑰窮搜索攻擊，DES算法總的密鑰量為，1998年使用高級計算機的情況下，破譯DES只需56小時；差分攻擊；線性攻擊，較有效的方法；相關(guān)密鑰攻擊等。DES遭受攻擊的原因只是因為其密鑰過短，而不是因為存在比窮舉密鑰更有效的個攻擊方法。所有DES的攻擊都要嘗試幾乎所有的密鑰70DESCrackerDESCracker:ADESkeysearchmachinecontains1536chipsCost:$250,000.couldsearch88billionkeyspersecondwonRSALaboratory’s“DESChallengeII-2”bysuccessfullyfindingaDESkeyin56hours.DESisfeelingitsage.Amoresecurecipherisneeded.DES加密練習1、假設(shè)明文和密鑰有相同的位模式，即：用十六進制表示：0123456789ABCDEF用二進制表示：0000000100100011010001010110011110001001101010111100110111101111a、推導第一輪的子密鑰K1b、推導L0，R0c、擴展R0，求E[R0]d、計算A=E[R0]K1e、把（d）的48位結(jié)果分成6位（數(shù)據(jù)）的集合并求對應(yīng)S盒代換的值DES加密練習f、利用（e）的結(jié)論來求32位的結(jié)果，Bg、應(yīng)用置換求P(B)h、計算R1=P[B]L0i、寫出密文2、為什么說研究Feistel密碼很重要？3、分組密碼和流密碼的區(qū)別是什么？由于DES的密鑰長度相對于窮舉攻擊過短，所以一般使用多重DES進行加密，一般的是三重DES，定義為：C=E(D(E(P,K1),K2),K1)，即EDE（112bitkey）。P=D(E(D(C,K1),K2),K1)DESDES-1DESDES-1DESDES-1mck1k2k1DES的變形——3-DES3DESWhyEncrypt-Decrypt-Encryptwith2keys?Backwardcompatible:E(D(E(P,K),K),K)=E(P,K)And112bitsisenoughWhynotC=E(E(P,K),K)?Trickquestion---it’sstilljust56bitkeyWhynotC=E(E(P,K1),K2)?A(semi-practical)knownplaintextattack3DESWhynotC=E(E(P,K1),K2)?A(semi-practical)knownplaintextattackPre-computetableofE(P,K1)foreverypossiblekeyK1(resultingtablehas256entries)ThenforeachpossibleK2computeD(C,K2)untilamatchintableisfoundWhenmatchisfound,haveE(P,K1)=D(C,K2)Resultgivesuskeys:C=E(E(P,K1),K2)3.4其他分組密碼IDEA算法RC5算法Rijndael算法1.IDEA

算法IDEA國際數(shù)據(jù)加密算法（InternationalDataEncryptionAlgorithm）瑞士聯(lián)邦理工學院：XuejiaLai&JamesMassey,1990；1991改進，加強了對差分密碼分析的抗擊能力；明文分組與密文分組的長度均為64位，密鑰長度為128位。IDEA

算法算法的設(shè)計思想混合使用來自不同代數(shù)群中的運算；通過對于兩個16位的子模塊連續(xù)使用三個“不相容”的群運算（分別是異或、模加、模乘），可以獲得所需的“混亂”；選擇使用的密碼結(jié)構(gòu)可以提供必要的“擴散”。IDEA

算法描述IDEA

算法描述加密過程：長度為64位的分組被分為4個長度為16位的子分組。這些子分組作為算法第1輪的輸入（注：該算法共8輪）。在每一輪中，子分組相互間進行異或、模加、模乘運算，并且與6個長度為16位的子密鑰進行異或、模加、模乘運算。在各輪之間，第2個子分組和第3個子分組進行交換。最后，在輸出變換中，子分組與子密鑰進行運算，將運算所得的4個子分組重新連接便得到密文。IDEA

算法描述子密鑰的產(chǎn)生過程：將長度為128位的密鑰分為8個長度為16位的子密鑰，作為算法第1輪需要的6個子密鑰和第2輪中的前兩個子密鑰；將原來長度為128位的密鑰向左環(huán)移25位，再次分為8個長度為16位的子密鑰，作為算法第2輪需要的另外4個子密鑰和第3輪所需的6個子密鑰；依次類推，便得到全部所需的52個密鑰。解密過程與加密過程基本相同。但是需要對子密鑰進行求逆運算。

2.RC5算法RSA公司的Rivest所設(shè)計的一種參數(shù)（分組大小、密鑰長度、加密輪數(shù)）可變的分組密碼算法。一個RC5算法通常被記為：RC5-w/r/b。其中，“w”為分組大?。╳=16,32,64），“r”為加密輪數(shù)（），“b”為密鑰長度（）。該算法實際上包含三部分：密鑰擴展算法、加密算法、解密算法。3.Rijndael算法不屬于Feistel結(jié)構(gòu)，Adi

Shamir相信“永遠安全的”。已被美國國家標準技術(shù)研究所選定作為高級加密算法AES。迭代分組密碼算法。密鑰128/192/256，分組128/192/256，循環(huán)次數(shù)10/12/14。速度快、對內(nèi)存要求小，操作簡單。算法的抗攻擊能力強。3.5

分組密碼的工作模式為了將DES應(yīng)用于實際，已經(jīng)提出的分組密碼工作模式有：密碼分組鏈接（CBC）模式；密碼反饋（CFB）模式；輸出反饋（OFB）模式；級連（CM）模式（又稱多重加密模式）；計數(shù)器模式；擴散密碼分組鏈連（PCBC）模式。模式描述典型應(yīng)用電碼本（ECB）用相同的密鑰分別對明文組加密單個數(shù)據(jù)的安全傳輸（如下一個加密密鑰）密碼分組鏈接（CBC）加密算法的輸入是上一個密文組和下一個明文組的異或普通目的面向分組的傳輸認證密碼反饋（CFB）一次處理J位。上一個分組密文作為產(chǎn)生一個偽隨機數(shù)輸出的加密算法的輸入，該輸出與明文異或，作為下一個分組的輸入普通目的的向分組的傳輸認證輸出反饋（OFB）與CFB基本相同，只是加密算法的輸入是上一次DES的輸出噪聲通道上的數(shù)據(jù)流的傳輸（如衛(wèi)星通信）計數(shù)器（CTR）每個明文組是加密的計數(shù)器的異或。對每個后續(xù)的組，計算器是累加的普通目的面向分組的傳輸用于高速需求3.5

分組密碼的工作模式

86電碼本（ECB）Ci=EK(Pi)

Pi=DK(Ci)ECB特點簡單和有效可以并行實現(xiàn)不能隱藏明文的模式信息相同明文相同密文同樣信息多次出現(xiàn)造成泄漏對明文的主動攻擊是可能的信息塊可被替換、重排、刪除、重放誤差傳遞：密文塊損壞僅對應(yīng)明文塊損壞適合于傳輸短信息AliceHatesECBModeAlice’suncompressedimage,andECBencrypted(TEA)Whydoesthishappen?Sameplaintextyieldssameciphertext!密碼分組鏈接（CBC）模式密文分組被反饋到輸入端，明文分組與的異或結(jié)果被作為DES加密算法的輸入，從而得到下一個密文分組，即。解密過程為。密文分組為無須保密的事先設(shè)定的初值，不同的明文x（而非明文分組）對應(yīng)不同的。各密文分組不僅與與之對應(yīng)的明文分組有關(guān)，也和此前的所有明文分組（即）有關(guān)。Ci=EK(Ci-1Pi)

Pi=EK(Ci

)Ci-1密碼分組鏈接（CBC）模式密碼分組鏈接（CBC）模式優(yōu)點:能夠隱蔽明文的數(shù)據(jù)模式，相同的明文不一定產(chǎn)生相同的密文；能夠在一定程度上防止分組的重放、插入和刪除等攻擊。缺點：易導致錯誤傳播。由于任何一個明文或密文分組出錯都會導致其后的密文分組出錯AliceLikesCBCModeAlice’suncompressedimage,AliceCBCencrypted(TEA)Whydoesthishappen?Sameplaintextyieldsdifferentciphertext!密碼反饋（CFB）模式實質(zhì)上是一種自同步流密碼。適用于必須按比特或者字符對明文進行加密的情況。采用該模式實現(xiàn)DES算法時，反饋的密文分組的長度與此前的密文分組長度不同，而是通常為事先設(shè)定的n值（），與明文相加的只是密文分組的最左邊n位，反饋的密文分組同時反饋到密鑰產(chǎn)生器。密碼反饋（CFB）模式基本原理如圖：輸出反饋（OFB）模式優(yōu)點：能夠克服錯誤傳播。缺點：很難發(fā)現(xiàn)密文被篡改；不具備自同步能力。

輸出反饋（OFB）模式基本原理如圖

:級連（CM）模式基本原理如圖：主要是為了增加密鑰