第3章分組密碼—3

1、1第第3 3章章 分組密碼分組密碼本章主要內(nèi)容本章主要內(nèi)容 概述概述 分組密碼的設(shè)計原則與評估分組密碼的設(shè)計原則與評估 分組密碼的設(shè)計方法分組密碼的設(shè)計方法 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES 高級加密標(biāo)準(zhǔn)高級加密標(biāo)準(zhǔn)AES AES 分組密碼的工作模式分組密碼的工作模式 其它分組密碼其它分組密碼 2第第3 3章章 分組密碼分組密碼3.1 3.1 概述概述 分組密碼加解密速度快、易于標(biāo)準(zhǔn)化和便于軟硬件實(shí)分組密碼加解密速度快、易于標(biāo)準(zhǔn)化和便于軟硬件實(shí)現(xiàn)，得到許多芯片的支持。通常是信息與網(wǎng)絡(luò)安全中實(shí)現(xiàn)，得到許多芯片的支持。通常是信息與網(wǎng)絡(luò)安全中實(shí)現(xiàn)數(shù)據(jù)加密和認(rèn)證的核心體制，它在計算機(jī)通信和信息現(xiàn)數(shù)

2、據(jù)加密和認(rèn)證的核心體制，它在計算機(jī)通信和信息系統(tǒng)安全領(lǐng)域有著最廣泛的應(yīng)用。系統(tǒng)安全領(lǐng)域有著最廣泛的應(yīng)用。分組密碼（分組密碼（Block cipher）：是現(xiàn)代密碼學(xué)的重要體制）：是現(xiàn)代密碼學(xué)的重要體制，是應(yīng)用最為廣泛、影響最大的一種密碼體制，其主要，是應(yīng)用最為廣泛、影響最大的一種密碼體制，其主要任務(wù)是提供數(shù)據(jù)保密性。分組密碼一般是指分組對稱密任務(wù)是提供數(shù)據(jù)保密性。分組密碼一般是指分組對稱密碼。碼。3第第3 3章章 分組密碼分組密碼3.1 3.1 概述概述也稱塊密碼，它是將明文消息經(jīng)編碼表示后的二進(jìn)制序也稱塊密碼，它是將明文消息經(jīng)編碼表示后的二進(jìn)制序列列M=x0,x1,xi, 劃分成若干長度為劃

3、分成若干長度為m的組塊。的組塊。Mi=(x0,x1,xm-1)，各組分別在密鑰，各組分別在密鑰k=(k0,k1,kt-1)的控的控制下轉(zhuǎn)換成長度為制下轉(zhuǎn)換成長度為n的密文分組的密文分組Ci =(c0,c1,cn-1)。其本質(zhì)。其本質(zhì)是一個從明文空間（是一個從明文空間（m長的比特串的集合）長的比特串的集合） M到密文空間到密文空間(n長的比特串的集合長的比特串的集合)C的一一映射。的一一映射。 1）一般而言，）一般而言， m=n，即為無數(shù)據(jù)擴(kuò)展和壓縮的分組密碼，即為無數(shù)據(jù)擴(kuò)展和壓縮的分組密碼2）mn，有數(shù)據(jù)壓縮的分組密碼，有數(shù)據(jù)壓縮的分組密碼4第第3 3章章 分組密碼分組密碼3.2 3.2 分組

4、密碼的設(shè)計原則與評估分組密碼的設(shè)計原則與評估3.2.1 3.2.1 分組密碼的設(shè)計原則分組密碼的設(shè)計原則針對安全性的一般設(shè)計原則針對安全性的一般設(shè)計原則1.明文分組長度和密鑰長度望盡可能大明文分組長度和密鑰長度望盡可能大 ：當(dāng)分組長度較小時，攻擊者通過窮舉明文空間，得到密碼變換規(guī)律，當(dāng)分組長度較小時，攻擊者通過窮舉明文空間，得到密碼變換規(guī)律，難于難于抵御選擇明文攻擊抵御選擇明文攻擊如果密鑰量小，攻擊者可以有效地通過窮舉密鑰，對密文進(jìn)行解密，如果密鑰量小，攻擊者可以有效地通過窮舉密鑰，對密文進(jìn)行解密，以得到有意義的明文，難于以得到有意義的明文，難于抵御唯密文攻擊抵御唯密文攻擊2.混亂原則：指在加

5、解密變換過程中明文、密鑰以及密文之間的關(guān)混亂原則：指在加解密變換過程中明文、密鑰以及密文之間的關(guān)系盡可能地復(fù)雜化，以防密碼破譯者采用解析法系盡可能地復(fù)雜化，以防密碼破譯者采用解析法(建立并求解一些方建立并求解一些方程程) 進(jìn)行破譯攻擊?；靵y原則：進(jìn)行破譯攻擊?；靵y原則：具有復(fù)雜的非線性因素具有復(fù)雜的非線性因素3.擴(kuò)散原則：密鑰的每一比特影響密文的許多位，防止對密鑰逐段擴(kuò)散原則：密鑰的每一比特影響密文的許多位，防止對密鑰逐段破譯；明文的每一位也影響密文的許多位，以隱蔽明文的統(tǒng)計特破譯；明文的每一位也影響密文的許多位，以隱蔽明文的統(tǒng)計特性。性。5第第3 3章章 分組密碼分組密碼3.2 3.2 分組

6、密碼的設(shè)計原則與評估分組密碼的設(shè)計原則與評估3.2.1 3.2.1 分組密碼的設(shè)計原則分組密碼的設(shè)計原則針對實(shí)現(xiàn)的設(shè)計原則針對實(shí)現(xiàn)的設(shè)計原則 軟件實(shí)現(xiàn)的設(shè)計原則軟件實(shí)現(xiàn)的設(shè)計原則子塊：子塊長度適合軟件編程，如子塊：子塊長度適合軟件編程，如6464位位，128128位等。位等。簡單運(yùn)算：避免難于實(shí)現(xiàn)的按位置換。簡單運(yùn)算：避免難于實(shí)現(xiàn)的按位置換。硬件實(shí)現(xiàn)的設(shè)計原則硬件實(shí)現(xiàn)的設(shè)計原則 規(guī)則結(jié)構(gòu)，以適用于用超大規(guī)模集成電規(guī)則結(jié)構(gòu)，以適用于用超大規(guī)模集成電路實(shí)現(xiàn)。路實(shí)現(xiàn)。6第第3 3章章 分組密碼分組密碼3.2.2 3.2.2 分組密碼的評估分組密碼的評估 (1)(1)安全性安全性評估中的最重要因素，包

7、括下述要點(diǎn)：算法抗密評估中的最重要因素，包括下述要點(diǎn)：算法抗密碼分析的強(qiáng)度，可靠的數(shù)學(xué)基礎(chǔ)，算法輸出的隨機(jī)性碼分析的強(qiáng)度，可靠的數(shù)學(xué)基礎(chǔ)，算法輸出的隨機(jī)性，與其他候選算法比較的相對安全性，與其他候選算法比較的相對安全性 (2)(2)性能性能在各種平臺上的計算效率和對存儲空間的需求在各種平臺上的計算效率和對存儲空間的需求 (3)(3)算法和實(shí)現(xiàn)特性算法和實(shí)現(xiàn)特性 靈活性、硬件和軟件適應(yīng)性、算法的簡單性等靈活性、硬件和軟件適應(yīng)性、算法的簡單性等 7第第3 3章章 分組密碼分組密碼3.3 3.3 分組密碼常見的設(shè)計方法分組密碼常見的設(shè)計方法乘積密碼乘積密碼: :以某種方式連續(xù)執(zhí)行兩個或多個密碼，所得

8、結(jié)果的密以某種方式連續(xù)執(zhí)行兩個或多個密碼，所得結(jié)果的密碼強(qiáng)度將強(qiáng)于所有單個密碼的強(qiáng)度。碼強(qiáng)度將強(qiáng)于所有單個密碼的強(qiáng)度。乘積密碼常伴隨一系列置換與替代操作，常見的乘積密乘積密碼常伴隨一系列置換與替代操作，常見的乘積密碼是碼是迭代密碼迭代密碼Feistel和和SPN是兩種常用的分組密碼設(shè)計是兩種常用的分組密碼設(shè)計結(jié)構(gòu)：結(jié)構(gòu)：DES等分組密碼采用等分組密碼采用Feistel 結(jié)構(gòu)；結(jié)構(gòu)；AES采用采用SPN結(jié)構(gòu)。結(jié)構(gòu)。8第第3 3章章 分組密碼分組密碼3.3 3.3 分組密碼常見的設(shè)計方法分組密碼常見的設(shè)計方法3.3.1 Feistel3.3.1 Feistel結(jié)構(gòu)結(jié)構(gòu)FeistelFeistel結(jié)

9、構(gòu)是典型的迭代密碼結(jié)構(gòu)是典型的迭代密碼.Feistel.Feistel結(jié)構(gòu)的解結(jié)構(gòu)的解密與加密是完全一樣的，除了所使用的子密鑰的順序密與加密是完全一樣的，除了所使用的子密鑰的順序正好相反。正好相反。 Li-1Ri-1FKiLi = Ri-1Ri = Li-1 F(Ri-1, Ki)9第第3 3章章 分組密碼分組密碼3.3.2 SPN3.3.2 SPN結(jié)構(gòu)結(jié)構(gòu) SPN結(jié)構(gòu)也是一種特殊的迭代密碼結(jié)構(gòu)也是一種特殊的迭代密碼 。SPN結(jié)構(gòu)和結(jié)構(gòu)和Feistel結(jié)構(gòu)相比，可以得到更快速的擴(kuò)散結(jié)構(gòu)相比，可以得到更快速的擴(kuò)散，但是，但是SPN密碼的加解密通常不相似。密碼的加解密通常不相似。 103.4 3.

10、4 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)(DES)DESDES是從是從19751975年被美國聯(lián)邦政府確定為非敏感信息的加密標(biāo)年被美國聯(lián)邦政府確定為非敏感信息的加密標(biāo)準(zhǔn)準(zhǔn). . 第第3 3章章 分組密碼分組密碼DES是一個是一個16輪的輪的Feistel型結(jié)構(gòu)密碼。型結(jié)構(gòu)密碼。明文分組長度為明文分組長度為64比特比特密鑰長度為密鑰長度為64比特。其中，實(shí)用比特。其中，實(shí)用56比特，另比特，另8位用作奇偶校驗(yàn)位用作奇偶校驗(yàn)密文分組長度也為密文分組長度也為64比特。比特。11第第3 3章章 分組密碼分組密碼121. 1. 給定明文，通過一個固定的初始置換給定明文，通過一個固定的初始置換IPIP來重排

11、輸來重排輸入明文塊入明文塊P P中的比特，得到比特串中的比特，得到比特串P P0 0=IP(P)=L=IP(P)=L0 0R R0 0，這里這里L(fēng) L0 0和和R R0 0分別是分別是P P0 0的前的前3232比特和后比特和后3232比特比特IP58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157初始置換初始置換IPIP第第3 3章章 分組密碼分組密碼DES算法算法13DESDES算法算法-Feistel-F

12、eistel結(jié)構(gòu)結(jié)構(gòu)2. 2. 按下述規(guī)則進(jìn)行按下述規(guī)則進(jìn)行1616次迭代，即次迭代，即1 1i i1616 這里這里 是異或，是異或，f f 是是一個函數(shù)（稱為輪函一個函數(shù)（稱為輪函數(shù)）；數(shù)）；1616個長度為個長度為4848比特的子比特的子密鑰密鑰K Ki i(1(1i i16)16)是是由密鑰由密鑰k k經(jīng)密鑰編排經(jīng)密鑰編排函數(shù)計算出來的函數(shù)計算出來的. .-11-1 (,)iiiiiiLRRLf RKL Li-1i-1R Ri-1i-1f f+ +L Li iR Ri ik ki i第第16輪迭代左右兩塊輪迭代左右兩塊不交換不交換第第3 3章章 分組密碼分組密碼1414IP-14084

13、8165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始置換初始置換的逆置換的逆置換IPIP-1-13.3.對比特串對比特串R R1616L L1616使用逆置換使用逆置換IPIP-1-1得到密文得到密文C C，即，即C=IPC=IP-1-1(R(R1616L L1616) )。（注意（注意L L1616和和R R1616的相反順序）的相反順序）第第3 3章章 分組密碼分組密碼DESDES算法算法15第第3 3章章 分

14、組密碼分組密碼密碼函數(shù)密碼函數(shù)f：Ri-1(32位位)Ki-1(32位位)E (E (Ri-1) )（4848位）位）B B1 1B B2 2B B3 3B B4 4B B5 5B B6 6B B7 7B B8 8S S1 1S S2 2S S3 3S S4 4S S5 5S S6 6S S7 7S S8 8C C1 1C C2 2C C3 3C C4 4C C5 5C C6 6C C7 7C C8 8f (f (Ri-1 ,K ,Ki i) )（3232）位）位+ +P PE EE擴(kuò)展擴(kuò)展密鑰加密鑰加S盒代換盒代換P置換置換有兩個參數(shù)，分別為有兩個參數(shù)，分別為長度為長度為3232比特串比特串

15、R Ri-1i-1和和長度為長度為4848比特串比特串K Ki i。產(chǎn)生長度為產(chǎn)生長度為3232比特的比特的輸出。輸出。16第第3 3章章 分組密碼分組密碼密碼函數(shù)密碼函數(shù)f：E E擴(kuò)展擴(kuò)展：3232比特的比特的R Ri-1i-1根據(jù)擴(kuò)展規(guī)則擴(kuò)展為根據(jù)擴(kuò)展規(guī)則擴(kuò)展為4848比特長比特長度的串；度的串；E比特選擇表321234545678989101112131213141516171617181920212021222324252425262728292829303132117第第3 3章章 分組密碼分組密碼密碼函數(shù)密碼函數(shù)f：密鑰加：密鑰加：計算計算 并將結(jié)果寫成并將結(jié)果寫成8 8個比特串個

16、比特串B=B1B2B3B4B5B6B7B8 ，作為，作為8 8個個S S盒（盒（ S1S8 ）的）的輸入。每個輸入。每個Bi 是長度為是長度為6 6的比特串，記為的比特串，記為Bi =（b1b2b3b4b5b6）1()iiBE RKS S盒代換盒代換：每個每個S S盒盒S Si i是一個固定的是一個固定的4 4* *1616階矩陣，每行是階矩陣，每行是015015之間整數(shù)的一個置換之間整數(shù)的一個置換. . 給給B Bi i計算如下計算如下: : 1) b 1) b1 1b b6 6兩個比特確定了兩個比特確定了S Si i的行的行r r的二進(jìn)制表示（的二進(jìn)制表示（0 0r r3 3），）， 2)

17、 b 2) b2 2b b3 3b b4 4b b5 5四個比特確定了四個比特確定了S Si i的列的列c c的二進(jìn)制表示（的二進(jìn)制表示（0 0c15c15），）， 3) S 3) Si i(B(Bi i) )定義成長度為定義成長度為4 4的比特串的值的比特串的值S Si i(r,c)(r,c)。由此。由此可以算出可以算出C Ci i=S=Si i(B(Bi i),1),1i i8.8.S S盒的輸出為：盒的輸出為： C=C C=C1 1C C2 2C C3 3C C4 4C C5 5C C6 6C C7 7C C8 8 ，共共3232比特比特18第第3 3章章 分組密碼分組密碼S S盒盒 (

18、Substitution Box)(Substitution Box)3.5 3.5 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES48bit塊通過S盒壓縮成32bit塊48bit寄存器寄存器32bit寄存器寄存器 S1S2S3S4S5S6S7S86bit4bit共共8個個S盒盒19第第3 3章章 分組密碼分組密碼 (3)(3)壓縮替代壓縮替代 S S盒盒 (Substitution Box)(Substitution Box)S1盒盒14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13

19、 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13作用作用：將：將6 6個輸入位映射為個輸入位映射為4 4個輸出位；個輸出位；方法方法：若定義：若定義6 6個輸入位為個輸入位為a1a2a3a4a5a6a1a2a3a4a5a6，a1a1代表第代表第1 1位，位，a6a6代表代表第第6 6位，將位，將a1a6a1a6組成組成2 2位二進(jìn)制數(shù)，對應(yīng)位二進(jìn)制數(shù)，對應(yīng)S S盒表中的行號；將盒表中的行號；將a2a3a4a5a2a3a4a5組成一個組成一個4 4位的位的2 2進(jìn)制數(shù)，對應(yīng)進(jìn)制數(shù)，對應(yīng)S S盒表中的列號；映射到盒表中的

20、列號；映射到交叉點(diǎn)的數(shù)據(jù)就是該交叉點(diǎn)的數(shù)據(jù)就是該S S盒的輸出。盒的輸出。輸入為輸入為101011101011的輸出是的輸出是？交叉點(diǎn)數(shù)據(jù)為交叉點(diǎn)數(shù)據(jù)為9 9轉(zhuǎn)化為二進(jìn)制為：轉(zhuǎn)化為二進(jìn)制為：10011001a1a6=11-3-a1a6=11-3-第第3 3行行a2a3a4a5=0101-5-a2a3a4a5=0101-5-第第5 5列列3.5 3.5 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES2020P置換置換：長度為：長度為32比特串比特串C=C1C2C3C4C5C6C7C8, 根據(jù)固定置換根據(jù)固定置換P(*)進(jìn)行置換，得到比特串進(jìn)行置換，得到比特串P(C).達(dá)到雪崩效應(yīng)。達(dá)到雪崩效應(yīng)。第第3 3

21、章章 分組密碼分組密碼密碼函數(shù)密碼函數(shù)f：16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 2521 可以看出，可以看出，DESDES加密需要四個關(guān)鍵點(diǎn)：加密需要四個關(guān)鍵點(diǎn)： (1)IP(1)IP置換表和置換表和IPIP-1-1逆置換表逆置換表; ; (2)(2)函數(shù)函數(shù)f;f; (3)(3)子密鑰子密鑰K Ki i。 (4)S(4)S盒的工作原理。盒的工作原理。 DES DES算法的實(shí)現(xiàn)步驟算法的實(shí)現(xiàn)步驟第第3 3章章 分組密碼分組密碼3.5 3.5 數(shù)據(jù)加密標(biāo)準(zhǔn)

22、數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES22密鑰編排算法密鑰編排算法根據(jù)密鑰根據(jù)密鑰K K來獲得每輪中所使用的子密鑰來獲得每輪中所使用的子密鑰K Ki i: :第第3 3章章 分組密碼分組密碼密鑰(56bit)PC-1K1C0置換選擇1D0LS1LS1C1D1LS2LS2C2D2PC-2置換選擇228bit28bit56bitK2PC-256bitLS16LS16C16D16K16PC-256bit48bit48bit48bit循環(huán)左移循環(huán)左移1234567811222222091011121314151612222221密鑰表的計算邏輯：密鑰表的計算邏輯：輪數(shù)輪數(shù)2357 49 41 33 25 17 9

23、1 58 50 42 34 26 1810 2 59 51 43 25 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 14 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 8 16 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 48 44 49 39 56 34 5346 42 50 36 29 32置換選擇置換選擇PC-1 置換選擇置換選擇PC-2子密鑰生成

24、器子密鑰生成器- -置換選擇置換選擇第第3章章 分組密碼分組密碼3.5 3.5 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES24第第3 3章章 分組密碼分組密碼 DES DES結(jié)構(gòu)結(jié)構(gòu)3.5 3.5 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES25第第3 3章章 分組密碼分組密碼3.4.2 DES3.4.2 DES的安全性分析的安全性分析 DESDES算法正式公開發(fā)表以后，引起了一場激烈的爭論算法正式公開發(fā)表以后，引起了一場激烈的爭論。19771977年年DiffieDiffie和和HellmanHellman提出了制造一個每秒能測提出了制造一個每秒能測試試106106個密鑰的大規(guī)模芯片，造價昂貴個密鑰的大規(guī)

25、模芯片，造價昂貴 19971997年年1 1月月2828日，美國的日，美國的RSARSA公司在互聯(lián)網(wǎng)上開展了一公司在互聯(lián)網(wǎng)上開展了一項(xiàng)名為項(xiàng)名為“密鑰挑戰(zhàn)密鑰挑戰(zhàn)”的競賽，懸賞一萬美元，破解一的競賽，懸賞一萬美元，破解一段用段用5656比特密鑰加密的比特密鑰加密的DESDES密文。密文。19971997年年6 6月月1717日日RockeRocke和志愿者們成功地找到了密鑰，在計算機(jī)上公和志愿者們成功地找到了密鑰，在計算機(jī)上公布了明文：布了明文：“Strong cryptography makes the Strong cryptography makes the world a safer

26、place”world a safer place”。26第第3 3章章 分組密碼分組密碼3.5.3 3.5.3 三重三重DESDES為了增強(qiáng)為了增強(qiáng)DESDES算法的安全性，人們提出了許多算法的安全性，人們提出了許多DESDES的改進(jìn)方案。其中，稱為三重的改進(jìn)方案。其中，稱為三重DESDES的多重加密算法是的多重加密算法是DESDES的一個重要的改進(jìn)算法。的一個重要的改進(jìn)算法。 DES解密DES加密DES加密DES加密DES解密DES解密明文M密文CK1K2K3加密27第第3 3章章 分組密碼分組密碼3.5 3.5 高級加密標(biāo)準(zhǔn)高級加密標(biāo)準(zhǔn)AESAESAESAES是是DESDES的替代者。的

27、替代者。19971997年年9 9月月1212日，日，NISTNIST發(fā)布了發(fā)布了征集算法的正式公告，要求征集算法的正式公告，要求AESAES具有具有128128比特的分組長比特的分組長度，并支持度，并支持128128、192192和和256256比特的密鑰長度，而且要比特的密鑰長度，而且要求求AESAES要能在全世界范圍內(nèi)免費(fèi)使用。要能在全世界范圍內(nèi)免費(fèi)使用。 20002000年年1010月月2 2日，日，RijndaelRijndael算法被選擇為高級加密算法被選擇為高級加密標(biāo)準(zhǔn)。標(biāo)準(zhǔn)。 AESAES的候選算法根據(jù)以下三條主要原則進(jìn)行評判的候選算法根據(jù)以下三條主要原則進(jìn)行評判 安全性安全性

28、 代價代價 算法與實(shí)現(xiàn)特性算法與實(shí)現(xiàn)特性283.5.1 AES算法的數(shù)學(xué)基礎(chǔ)算法的數(shù)學(xué)基礎(chǔ) AES中的運(yùn)算是按字節(jié)的，并把一個字節(jié)看成是系數(shù)在有限域GF(2)上的次數(shù)小于8的多項(xiàng)式（即把一個字節(jié)看成是有限域GF(28)中的一個元素) 。 一、有限域GF(28) 可以把出b7b6b5b4b3b2b1b0構(gòu)成的一個字節(jié)看成是系數(shù)在(0, 1)中取值的多項(xiàng)式： b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0 如57（01010111）可寫成： x6 + x4 + x2 + x + 1第第3章章 分組密碼分組密碼291. 多項(xiàng)式加法多

29、項(xiàng)式加法 在多項(xiàng)式表示中，兩個元素的和是一個多項(xiàng)式，其系數(shù)是兩個元素的對應(yīng)系數(shù)的模2加(即異或)。例如：“57”和“83”的和為： 57 83D4，或者采用其多項(xiàng)式記法： 5701010111 x6+x4+x2+x+1 83 10000011 x7+x+1 (x6+x4+x2+x+1)+(x7+x+1)x7+x6+x4+x2 11010100 D4顯然，該加法與簡單的以字節(jié)為單位的比特異或是一致的。 01010111 10000011 110101002. 多項(xiàng)式乘法多項(xiàng)式乘法 有限域GF(28)中兩個元素的乘法為模2元域GF(2)上的一個8次不可約多項(xiàng)式的多項(xiàng)式乘法。對于AES這一8次不可約

30、多項(xiàng)式為例：m(x) = x8+x4+x3+x+1 用十六進(jìn)制表示為11B。第第3章章 分組密碼分組密碼30 【例】 計算：57 83 = ？ (x6+x4+x2+x+1) (x7+x+1) = x13+ x11+ x9+ x8+ x7+ x7+ x5+ x3+ x2+ x+ x6+x4+x2+x+1 =x13+ x11+ x9+ x8+ x6+ x5+ x4+ x3+ 1而: (x13+ x11+ x9+ x8+ x6+ x5+ x4+ x3+ 1)mod m(x) = (x13+ x11+ x9+ x8+ x6+ x5+ x4+ x3+ 1)mod (x8+x4+x3+x+1) ；計算時按

31、降冪排 = x7+x6+1所以： (x6+x4+x2+x+1) (x7+x+1) = x7+x6+1 (多項(xiàng)式表示) 01010111 10000011=11000001 (2進(jìn)制表示) 57 83 = C1 (16進(jìn)制表示)第第3章章 分組密碼分組密碼313. x乘法乘法考慮用 x 乘以多項(xiàng)式B(x): ( b7b6b5b4b3b2b1b0 ) B(x)b7 x7+ b6x6+ b5x5+ b4x4+ b3x3+ b2x2+ b1x + b0 x B(x)b7 x8+ b6x7+ b5x6+ b4x5+ b3x4+ b2x3+ b1x2 + b0 x將上面的結(jié)果模m(x)求余就得到x B(x

32、)。如果 b7 0，則：x B(x)b6x7+ b5x6+ b4x5+ b3x4+ b2x3+ b1x2 + b0 x mod (x8+x4+x3+x+1) 即所得結(jié)果字節(jié)為：即所得結(jié)果字節(jié)為： (b6b5b4b3b2b1b00)如果 b7 1，則：x B(x) x8+ b6x7+ b5x6+ b4x5+ b3x4+ b2x3+ b1x2 + b0 x mod (x8+x4+x3+x+1) = x8+ b6x7+ b5x6+ b4x5+ b3x4+ b2x3+ b1x2 + b0 x + (x8+x4+x3+x+1) 1 = b6x7+ b5x6+ b4x5+ b3x4+ b2x3+ b1x2

33、 + b0 x + (x4+x3+x+1) 即所得結(jié)果字節(jié)為：即所得結(jié)果字節(jié)為： (b6b5b4b3b2b1b00) (00011011)所以 ，x B(x) =(b6b5b4b3b2b1b00) ；b7 0 (b6b5b4b3b2b1b00) (00011011) ；b7 1第第3章章 分組密碼分組密碼32第第3章章 分組密碼分組密碼例例1：f(x)=x6+x4+x2+x+1,g(x)=x7+x+1, m(x)=x8+x4+x3+x+1，求，求f(x)*g(x)modm(x)求求57*83現(xiàn)在我們用二進(jìn)制運(yùn)算的方法來計算，即（現(xiàn)在我們用二進(jìn)制運(yùn)算的方法來計算，即（01010111）*(100

34、00011).首先要求出首先要求出x冪乘冪乘01010111的中間結(jié)果：的中間結(jié)果：（01010111)*(00000010)=(10101110) (01010111) *(00000100) =(10101110)*(00000010)=(01011100)(00011011)=(01000111)(00011011)=(01000111) (01010111) *(00001000)=(10001110) (01010111) *(00010000)=(00011100)(00011011)=(00000111)(00011011)=(00000111) (01010111) *(001

35、00000)=(00001110) (01010111) *(01000000)=(00011100) (01010111) *(10000000)=(00111000)所以：所以：(01010111) *(10000011)=(01010111)*(00000001)+（00000010）+（10000000) =(01010111) (10101110) (00111000)=(11000001) (10101110) (00111000)=(11000001)1100000111000001等價于等價于x x7 7+x+x6 6+1+133第第3 3章章 分組密碼分組密碼二、二、GFGF

36、（2 28 8）域上的多項(xiàng)式）域上的多項(xiàng)式一個（4字節(jié)）字可以看作是GF（ 28 ）域上的多項(xiàng)式，每個字對應(yīng)于一個次數(shù)小于4的多項(xiàng)式。1. 1. 多項(xiàng)式加法多項(xiàng)式加法多項(xiàng)式加法通過對應(yīng)的系數(shù)簡單相加可以實(shí)現(xiàn)。2. 2. 多項(xiàng)式乘法多項(xiàng)式乘法 GF(2 28 8)域上的多項(xiàng)式乘法為模 M(x) = x4 + 1的乘法。343.5.2 AES3.5.2 AES算法總體描述算法總體描述 輪數(shù)、密鑰長度的關(guān)系輪數(shù)、密鑰長度的關(guān)系35 AES 算法加密的實(shí)現(xiàn)1. 明文分組和密鑰的組織排列方式明文分組和密鑰的組織排列方式 012345678910111213141504812159132610143711

37、15Fig 2.1. 以明文分組為以明文分組為128bits為例組成的陣列為例組成的陣列3.5.2 AES3.5.2 AES算法總體描述算法總體描述36 AESAES加解密流程圖加解密流程圖1給定一個明文給定一個明文M，將輪密鑰與將輪密鑰與M異或（稱異或（稱為為輪密鑰加輪密鑰加）；）； 2對前對前9輪中的每輪中的每輪輪，用，用s盒進(jìn)行一次盒進(jìn)行一次字節(jié)字節(jié)代換代換操作；對替換的結(jié)操作；對替換的結(jié)果做果做行移位行移位操作；再對操作；再對結(jié)果做結(jié)果做列混淆列混淆變換；然變換；然后進(jìn)行后進(jìn)行(輪密鑰加輪密鑰加操作操作3在最后一輪中依次在最后一輪中依次進(jìn)行進(jìn)行字節(jié)代換字節(jié)代換,行移位行移位,列混淆列混

38、淆操作。操作。4得到密文得到密文C。3.5.2 AES3.5.2 AES算法總體描述算法總體描述37AESAES特點(diǎn)特點(diǎn)3.5.2 AES3.5.2 AES算法總體描述算法總體描述38 每一輪加密的過程每一輪加密的過程中間態(tài)數(shù)據(jù)有的地方也被記為中間態(tài)數(shù)據(jù)有的地方也被記為State3.5.2 AES3.5.2 AES算法總體描述算法總體描述39 AES 算法加密的實(shí)現(xiàn)1. 明文分組和密鑰的組織排列方式明文分組和密鑰的組織排列方式 01234567891011121314150481215913261014371115Fig 2.1. 以明文分組為以明文分組為128bits為例組成的陣列為例組成的

39、陣列3.5.2 AES3.5.2 AES算法總體描述算法總體描述401 字節(jié)代換（字節(jié)代換（SubBytes）S盒的替換操作盒的替換操作3.5.3 算法的基本變換算法的基本變換411 字節(jié)代換（字節(jié)代換（SubBytes）S盒的替換表盒的替換表3.5.3 算法的基本變換算法的基本變換421 字節(jié)代換（字節(jié)代換（SubBytes）設(shè)輸入字節(jié)為 A = ( a0 a1a2 a3 a4 a5 a6 a7 )， (1) 先將該字節(jié)A變換為有限域GF(2)中的乘法逆元素T。 T= A-1 mod m(x) ； m(x) = x8+x4+x3+x+1 即 AT TA 1mod m(x) (2) 對X作GF

40、(2)上的仿射變換： Y = M T B0110001111111000011111000011111000011111100011111100011111100011111100017654321076543210ttttttttyyyyyyyyYMTB3.5.3 算法的基本變換算法的基本變換43S盒字節(jié)代換舉例盒字節(jié)代換舉例3.5.3 算法的基本變換算法的基本變換442、行移位變換、行移位變換 ShiftRows()： 在行移位(ShiftRows)變換中，狀態(tài)矩陣中的每一行將以字節(jié)為單位，循環(huán)右移不同的位移量。33323130232221201312111003020100sssssss

41、sssssssss32313033212023221013121103020100ssssssssssssssss循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)第0行不變453、列混合變換、列混合變換 MixColumns()： 列混合變換MixColumns()對一個狀態(tài)逐列進(jìn)行變換，它將一個狀態(tài)的每一列視為有限域GF(28)上的一個多項(xiàng)式。 在列混合變換中，每一列所表示的多項(xiàng)式將乘以一個固定的多項(xiàng)式C(x)， C(x)=03 x3+01 x2+01x +02 對應(yīng)4字節(jié)向量為( 03 01 01 02)，模多項(xiàng)式為 (x4 + 1)。46列混淆的數(shù)學(xué)基礎(chǔ)列混淆的數(shù)學(xué)基礎(chǔ) b0 c0 c3 c2

42、 c1 a0 b1 = c1 c0 c3 c2 a1 b2 c2 c1 c0 c3 a2 b3 c3 c2 c1 c0 a347列混淆的數(shù)學(xué)基礎(chǔ)列混淆的數(shù)學(xué)基礎(chǔ) b0 02 03 01 01 a0 b1 = 01 02 03 01 a1 b2 01 01 02 03 a2 b3 03 01 01 02 a3AES中，中，48AddRoundKey(AddRoundKey(輪密鑰加輪密鑰加) )將輪密鑰與中間態(tài)數(shù)據(jù)（將輪密鑰與中間態(tài)數(shù)據(jù)（State）按比特異或。）按比特異或。輪密鑰是通過輪密鑰是通過Key Schedule過程從密碼密鑰中得到的，過程從密碼密鑰中得到的，輪密鑰長度等于分組長度。輪

43、密鑰長度等于分組長度。K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3K3,3 K3,3 B3,3 (mod 2)AES每輪密鑰加操作，需要每輪密鑰加操作，需要128bit（16字節(jié)，字節(jié)，4個字）的輪密鑰。算法中有個字）的輪密鑰。算法中有11次次輪密鑰操作。故輪

44、密鑰操作。故AES算法共需要算法共需要44個字個字長度的密鑰。長度的密鑰。49密鑰擴(kuò)展密鑰擴(kuò)展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+K4的生成：下頁的生成：下頁K5、K6、K7的生成：如右的生成：如右50K0K1K2K3K4K5K6K7ByteSubstitutionByteRotKte+RconK4的生成的生成51Wi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotKte+Rcons+Key expKnsion Key exp

45、Knsion 4 = i 4 ( Rnd + 1 )i mod 4 = 0i mod 4 != 052輪密鑰選取輪密鑰選取K0K1K2K3K4K5K6K7K8K9K10K11K12輪密鑰輪密鑰0輪密鑰輪密鑰1輪密鑰輪密鑰253第第3 3章章 分組密碼分組密碼3.6 3.6 分組密碼的工作模式分組密碼的工作模式 DESAESDESAES算法只解決了如何對一個算法只解決了如何對一個6464128128比特的明比特的明文分組進(jìn)行加密保護(hù)的問題文分組進(jìn)行加密保護(hù)的問題, ,對于比特數(shù)不等于對于比特數(shù)不等于6464 128的明文如何加密的明文如何加密, ,并不關(guān)心。這個問題并不關(guān)心。這個問題, ,就由分

46、就由分組密碼的工作模式解決。組密碼的工作模式解決。54第第3 3章章 分組密碼分組密碼3.6 3.6 分組密碼的工作模式分組密碼的工作模式分組密碼的分組密碼的“工作模式工作模式”是指以某個分是指以某個分組密碼算法為基礎(chǔ)組密碼算法為基礎(chǔ),解決對任意長度的明文的解決對任意長度的明文的加密問題的方法。加密問題的方法。 1電碼本(ECB)模式 2密碼分組鏈接(CBC)模式 3密碼反饋(CFB)模式 4輸出反饋(OFB)模式 5. 計數(shù)器模式這五種工作模式適用于不同的應(yīng)用需求這五種工作模式適用于不同的應(yīng)用需求. .55(),1,2, .ikiCEMin3.6 3.6 分組密碼的工作模式分組密碼的工作模式3.6.13.6.1電子密碼本模式（電子密碼本模式（ECBECB）56第第3 3章章 分組密碼分組密碼3.6 3.6 分組密碼的工作模式分組密碼的工作模式3.6.13.6.1電子密碼