1、第3章 分組密碼理論3.1 分組密碼概述3.2 DES3.3 分組密碼的設計原理3.4 分組密碼的工作模式3.1 分組密碼概述分組密碼，就是一個明文分組被當作一個整體來產生一個等長（通常）的密文分組的密碼，通常使用的是128位分組大小。分組密碼的實質是，設計一種算法，能在密鑰控制下，把n比特明文簡單而又迅速地置換成唯一n比特密文，并且這種變換是可逆的（解密）。3.1 分組密碼概述(Cont.)分組密碼的設計思想（C.E. Shannon)：擴散(diffusion)將明文及密鑰的影響盡可能迅速地散布到較多個輸出的密文中（將明文冗余度分散到密文中）。產生擴散的最簡單方法是通過“置換(Permut

2、ation)”（比如：重新排列字符）。分組密碼的設計思想(Cont.)混淆(confusion)其目的在于使作用于明文的密鑰和密文之間的關系復雜化，是明文和密文之間、密文和密鑰之間的統計相關特性極小化，從而使統計分析攻擊不能奏效。通常的方法是“代換（Substitution)”（回憶愷撒密碼）。3.2數據加密標準（DES)DES的歷史1971 IBM，由Horst Feistel 領導的密碼研究項目組研究出LUCIFER算法。并應用于商業領域。1973美國標準局征求標準，IBM提交結果，在1977年，被選為數據加密標準。3.2數據加密標準（Cont.)4.2.1 簡化的DES Simplifi

3、ed DES方案，簡稱S-DES方案。它是一個供教學而非安全的加密算法，它與DES的特性和結構類似，但參數小。注：1.* 加密算法涉及五個函數：(1)初始置換IP(initial permutation)(2)復合函數fk1，它是由密鑰K確定的，具有置換和代換的運算。 (3)置換函數SW(4)復合函數fk2(5)初始置換IP的逆置換IP-12*. 加密算法的數學表示：IP-1*fk2*SW*fk1*IP也可寫為密文=IP-1（fk2(SW(fk1(IP(明文)其中 K1=P8(移位(P10(密鑰K)K2=P8(移位(移位(P10(密鑰K)解密算法的數學表示：明文=IP-1（fk1(SW(fk2

4、(IP(密文)對S-DES的深入描述（1） S-DES的密鑰生成：設10bit的密鑰為（ k1,k2,k10 )置換P10是這樣定義的P10(k1,k2,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) P8= (k1,k2,k10)=(k6,k3,k7,k4,k8,k5,k10,k9 ) LS-1為循環左移1位， LS-2為循環左移2位按照上述條件,若K選為(1010000010), 產生的兩個子密鑰分別為K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)S-DES的密鑰生成10-bit密鑰P10LS-1LS-1LS-2LS-2P8P

5、8K18K255558(2) S-DES的加密運算: 初始置換用IP函數: IP= 1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7 末端算法的置換為IP的逆置換:IP-1= 1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6 易見IP-1(IP(X)=X S-DES加密圖8-bit 明文IPE/P+S0S1P4+LR4K1844fkF4S-DES加密圖(續)E/P+S0S18K2P4+IP-18-bit 密文4844fkF44228SW8-bit子密鑰：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后與E/P的結果作異或運算得：n4+k

6、11 n1+k12 n2+k13n3+k14n2+k15 n3+k16n4+k17n1+k18把它們重記為8位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3上述第一行輸入進S-盒S0，產生2-位的輸出；第二行的4位輸入進S盒S1，產生2-位的輸出。兩個S盒按如下定義：作業試證明S-DES的加密、解密是互逆的，即：D( E(M,K), K)M。Feistel 密碼結構Feistel 密碼設計原則分組大小 increasing size improves security, but slows cipher 密鑰長度 increasing size improv

7、es security, makes exhaustive key searching harder, but may slow cipher 輪次數 increasing number improves security, but slows cipher 子密鑰生成 greater complexity can make analysis harder, but slows cipher 輪函數 greater complexity can make analysis harder, but slows cipher 快速軟件加密/解密are more recent concerns fo

8、r practical use and testingFeistel 密碼解密3.2 DES的描述DES利用56比特串長度的密鑰K來加密長度為64位的明文，得到長度為64位的密文該算法分三個階段實現：1. 給定明文X，通過一個固定的初始置換IP來排列X中的位，得到X0。X0=IP（X）=L0R0其中L0由X0前32位組成，R0由X0的后32位組成。2.計算函數F的16次迭代, 根據下述規則來計算LiRi(1=i=16） Li=Ri-1, Ri=Li-1 F(Ri-1, Ki)其中Ki是長為48位的子密鑰。子密鑰K1，K2，K16是作為密鑰K（56位）的函數而計算出的。 3.對比特串R16L16

9、使用逆置換IP-1得到密文Y。Y=IP-1（R16L16）DES 算法的一般描述對F函數的說明：（類比于S-DES）F（Ri-1, Ki）函數F以長度為32的比特串A=R（32bits）作第一個輸入，以長度為48的比特串變元J=K(48bits)作為第二個輸入。產生的輸出為長度為32的位串。(1)對第一個變元A，由給定的擴展函數E，將其擴展成48位串，E（A）(2)計算E（A）+J，并把結果寫成連續的8個6位串, B=b1b2b3b4b5b6b7b8(3)使用8個S盒，每個Sj是一個固定的416矩陣，它的元素取015的整數。給定長度為6個比特串，如Bj=b1b2b3b4b5b6計算Sj(Bj)

10、如下：b1b6兩個比特確定了Sj的行數, r(0=r=3); 而b2b3b4b5四個比特確定了Sj的列數c（0=c=15）。最后Sj(Bj)的值為S-盒矩陣Sj中r行c列的元素（r,c）, 得Cj=Sj(Bj)。(4) 最后，P為固定置換。 A=R(32 bits)J=K(48 bits)EE(A)為48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B寫成8個6比特串DES 的F函數(2)對1=i=16，計算Ci=LSi(Ci-1)Di=LSi(Di-1)LSi表示循環左移

11、2或1個位置，取決于i的的值。i=1,2,9和16 時移1個位置，否則移2位置。Ki=PC-2(CiDi), PC-2為固定置。注：一共16輪，每一輪使用K中48位組成一個48比特密鑰。可算出16個表，第i個表中的元素可對應上第i輪密鑰使用K中第幾比特！如：第7輪的表7：K7取K中的比特情況：52 57 11 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 1828 7 14 29 47 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 6圖表（密鑰生成Ki）KPC-1C0 D0L

12、S1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 DES加密的一個例子取16進制明文X：0123456789ABCDEF密鑰K為：133457799BBCDFF1去掉奇偶校驗位以二進制形式表示的密鑰是00010010011010010101101111001001101101111011011111111000應用IP，我們得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后進行16輪加密。最后對L16, R16使用IP-1得到密文：85E813540

13、F0AB4053.2.3 DES的爭論DES的核心是S盒，除此之外的計算是屬線性的。S盒作為該密碼體制的非線性組件對安全性至關重要。S盒的設計準則：1. S盒不是它輸入變量的線性函數2.改變S盒的一個輸入位至少要引起兩位的輸出改變3. 對任何一個S盒，如果固定一個輸入比特，其它輸入變化時，輸出數字中0和1的總數近于相等。公眾仍然不知道S盒的構造中是否還使用了進一步的設計準則（有陷門？）。密鑰長度是否足夠？迭代的長度？（8、16、32？）3.3 分組密碼的設計原理可變密鑰長度混合操作依賴數據的循環移位依賴于密鑰的循環移位依賴密鑰的S盒子冗長的密鑰調度算法可變的F函數和可變的明文/密文長度可變的循

14、環次數在每次循環中都對兩半數據進行操作分組密碼的工作模式分組密碼加密固定長度的數據分組需要使用一些實際的方法來加密任意數量的明文 五種工作模式Electronic Codebook Book (ECB)電碼本模式ECB的優勢與局限相同的明文對于相同的密文 結構化明文 消息有重復部分 主要用于發送少數量的分組數據 Cipher Block Chaining (CBC)密碼分組鏈接模式Advantages and Limitations of CBCeach ciphertext block depends on all message blocks thus a change in the me

15、ssage affects all ciphertext blocks after the change as well as the original block need Initial Value (IV) known to sender & receiver however if IV is sent in the clear, an attacker can change bits of the first block, and change IV to compensate hence either IV must be a fixed value (as in EFTPOS) o

16、r it must be sent encrypted in ECB mode before rest of message at end of message, handle possible last short block by padding either with known non-data value (eg nulls)or pad last block with count of pad size eg. b1 b2 b3 0 0 0 0 5 - 3 data bytes, then 5 bytes pad+count Cipher FeedBack (CFB)密碼反饋模式A

17、dvantages and Limitations of CFBappropriate when data arrives in bits/bytes most common stream mode limitation is need to stall while do block encryption after every n-bits note that the block cipher is used in encryption mode at both ends errors propogate for several blocks after the error Output F

18、eedBack (OFB)輸出反饋模式Advantages and Limitations of OFBused when error feedback a problem or where need to encryptions before message is available superficially similar to CFB but feedback is from the output of cipher and is independent of message a variation of a Vernam cipher hence must never reuse the same sequence (key+IV) sender and receiver must remain in sync,