信息安全導(dǎo)論 3分組密碼資料

1、 信息安全導(dǎo)論第三講分組密碼 華中科技大學圖象所信息安全研究室8/25/20221分組密碼密碼學與安全性分組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Standard)高級加密標準(Advanced Encryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/20222密碼學密碼學:一個有趣的問題密碼學是數(shù)學的一個分支密碼學涉及的是數(shù)字公式和邏輯密碼學是超凡的技術(shù)均衡器密碼學并不能做比想象多的事情8/25/20223安全性安全性：一個很令人困惑的問題安全性涉及的是人、事物和彼此間的關(guān)系安全性

2、的弱點與數(shù)學毫無關(guān)系安全性是一條鏈，其可靠程度取決于鏈中最薄弱的環(huán)節(jié)安全性是一個過程而不是一個產(chǎn)品安全性本身是相互連接的系統(tǒng)8/25/20224分組密碼密碼學與安全性分組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Standard)高級加密標準(Advanced Encryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/20225分組密碼是什么？直觀的定義：分組密碼是將明文消息編碼表示后的數(shù)字(通常是0與1)序列x1,x2,劃分成長為m的組x=(x1,x2,xm)，各組分別在長度為t的密鑰k

3、=(k1,k2,kt)的控制下變換成等長的輸出序列 y=(y1,y2,ym) 。加密算法解密算法x=(x1,x2,xm)y=(y1,y2,ym)x=(x1,x2,xm)密鑰k密鑰k8/25/20226抽象的定義：分組密碼是一種滿足下列條件的映射 對每個kSk ， 是從 到 的一個置換。8/25/202278/25/20228什么是分組密碼？主要的分組加密算法：DESIDEASquare, Shark, Safer-64Rijndael 現(xiàn)代分組密碼的研究始于20世紀70年代中期，人們在這一研究領(lǐng)域取得了豐碩的研究成果。8/25/20229分組密碼的體系結(jié)構(gòu) 分組密碼算法不應(yīng)是各種計算部件的隨意

4、堆積，而應(yīng)是一種精巧的組合。對于不同的設(shè)計思路，有不同的組合方式。但所有方式的目的只有兩點：一方面要使密鑰與密文間的關(guān)系盡可能復(fù)雜，以便隱藏明文的統(tǒng)計特性；另一方面要將單個明文特征的影響擴散到盡可能多的密文，以便更好的隱藏明文的統(tǒng)計特性。實現(xiàn)這種混亂與擴散的關(guān)鍵在于分組密碼的體系結(jié)構(gòu)設(shè)計。關(guān)于分組密碼體系結(jié)構(gòu)的一種簡單分類如圖所示。 8/25/202210分組密碼體系結(jié)構(gòu)的一種分類方法 分組密碼 SP型結(jié)構(gòu)代替置換結(jié)構(gòu)Feistel結(jié)構(gòu)DES型結(jié)構(gòu)其他結(jié)構(gòu)包含S盒不含S盒與密鑰有關(guān)的S盒固定不變的S盒動態(tài)S盒靜態(tài)S盒8/25/202211代替置換結(jié)構(gòu)(SP網(wǎng)絡(luò)) Feistel等人首先提出的代

5、替置換結(jié)構(gòu)（Substitution Permutation）如下圖所示，它由多個非線性變換（S盒）和簡單的比特置換（位置置換）組成，能有效實現(xiàn)Shannon所描述的混亂與擴散。通過設(shè)計不同的代替與置換部件，就能得到不同的密碼系統(tǒng)。在每一輪中，首先輪輸入被作用于S盒，然后再被作用于一個置換P。S一般被稱為混淆層，主要起混淆的作用。P一般被稱為擴散層，主要起擴散作用。 8/25/202212Feistel結(jié)構(gòu) Feistel密碼是一類特殊的迭代分組密碼，由于DES 中也采用了Feistel結(jié)構(gòu)，F(xiàn)eistel密碼有時也叫DES型密碼。在一個Feistel密碼中，一個明文分組被分割成兩部分。在子密

6、鑰的作用下，輪函數(shù)f 應(yīng)用于其中的一部分，輪函數(shù)的輸出與另一部分做XOR運算，再將這兩部分交換。除第一輪和最后一輪沒有交換外，其余各輪都做相同的運算。Feistel密碼的一個非常好的特征是具有相同的加密和解密結(jié)構(gòu)，只需使用與加密相反順序的子密鑰就可以解密。8/25/202213其他結(jié)構(gòu) 還有很多運用其它結(jié)構(gòu)的分組密碼，其中一些是基于特殊的理論基礎(chǔ)，如IDEA就是在3個不同構(gòu)的代數(shù)群上的混合運算，子密鑰用于模乘法和模加法，輪變換的差分傳播概率主要依賴于這些子密鑰的值。 8/25/202214分組密碼密碼學與安全性分組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Sta

7、ndard)高級加密標準(Advanced Encryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/202215DES算法 DES使用64位密鑰（除去8位奇偶校驗，即8，16，24，32，40，48，56，64這八位是奇偶校驗位，在算法中不起作用，實際密鑰長為56位）對64比特的數(shù)據(jù)分組（二進制數(shù)據(jù)）加密，產(chǎn)生64位密文數(shù)據(jù)。DES是一個對稱密碼體制，加密和解密使用同一密鑰，解密和加密使用同一算法，加密過程分為三個階段。DES的所有保密性均依賴于密鑰。8/25/202216DES算法框圖輸入64比特明文數(shù)據(jù)初始置換IP

8、在密鑰控制下16輪迭代交換左右32比特初始逆置換IP-1輸出64比特密文數(shù)據(jù)8/25/20221758 50 42 34 26 18 10 2 60 52 44 36 28 20 12 462 54 46 38 30 22 14 6 64 56 48 40 32 24 16 857 49 41 33 25 17 9 1 59 51 43 35 27 19 11 361 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7初始置換IP表 初始置換IP（兩步）初始置換IP及其逆置換IP-1沒有密碼意義，因為x與IP(x)(或y與IP-1(y)的一一對應(yīng)關(guān)系是已知的（

9、不含密鑰）。它們的作用在于打亂原來輸入x的ASCII碼字劃分的關(guān)系，并將原來明文的檢驗位變成IP的輸出的一個字節(jié)。初始置換表應(yīng)從左向右、從上向下讀。例如初始置換把明文的第58位換到第1位的位置，把第50位換到第2位的位置，把第42位換到第3位的位置，。對于給定的明文x，通過初始置換IP獲得x0，并將x0分為兩部分，前面32位記為L0，后面32位記為R0。8/25/202218計算16次迭代變換DES算法的核心是算法所規(guī)定的16次迭代變換。從圖中可以看出，DES算法的16次迭代變換具有相同的結(jié)構(gòu)。每一次迭代變換都以前一次迭代變換的結(jié)果（第一次迭代以作x0=L0R0為輸入）和用戶密鑰擴展得到的子密

10、鑰ki作為輸入；每一次迭代變換只變換一半數(shù)據(jù)，它們將輸入數(shù)據(jù)的右半部分經(jīng)過函數(shù) f 后，將其輸出與輸入數(shù)據(jù)的左半部分進行異或運算，并將得到的結(jié)果作為新的右半部分，原來的右半部分變成了新的左半部分。8/25/202219DES的一次迭代過程 8/25/202220DES算法的安全性關(guān)鍵在于非線性函數(shù)f的性質(zhì)。在DES算法中，f 以長度為32位的比特串作為輸入，產(chǎn)生的中間結(jié)果為48位，并在最終產(chǎn)生長度為32位的比特串作為輸出。f函數(shù)的計算過程可以用下圖表示。 8/25/202221擴展置換E（位置置換）：以前一輪迭代的結(jié)果Ri-1作輸入，首先根據(jù)一個固定的擴展函數(shù)E ，將輸入的32比特“擴展”為4

11、8位的比特串。下表給出了哪一輸出位對應(yīng)哪一輸入位。例如：輸入分組中第3位的位置移到了輸出分組中的第4位的位置，輸入分組中第21位的位置移到了輸出分組中的第30和第32位的位置。（每一行首部的兩個元素與上一行尾部的兩個元素重復(fù)）擴展置換（E-盒）表32123454567898910111213121314151617161718192021202122232425242526272829282930313218/25/202222擴展置換的作用它產(chǎn)生了與密鑰同長度的數(shù)據(jù)（與密鑰進行異或運算）它產(chǎn)生了更長的結(jié)果，使得在替代運算時能進行壓縮輸入的一位可能將影響兩個替代，所以輸出對輸入的依賴性將傳播得

12、更快，這叫雪崩效應(yīng)（avalanche effect)。8/25/202223與子密鑰異或：函數(shù)f將擴展得到的48位輸出與子密鑰ki（48位）進行異或運算（按位模2加）8/25/202224S盒替代 ：以6比特長為單位將與子密鑰異或得到的結(jié)果分為8個子分組，并將它們送入替代函數(shù)（即S盒）中進行替代運算。S盒（6輸入/4輸出）是函數(shù) f 的核心所在，同時，也是DES算法的關(guān)鍵步驟。實際上，除了S盒以外，DES的其他運算都是線性的，而S盒是非線性的，它決定了DES算法的安全性。8/25/202225S盒 DES算法中共有8個S盒。每一個子分組將對應(yīng)于一個S盒進行替代運算。將S盒的6位輸入定義為a1

13、a2a3a4a5a6。具體替代方式為：將a1a6組成一個2位二進制數(shù)，對應(yīng)著表中的行號;將a2a3a4a5組成一個4位二進制數(shù)，對應(yīng)表中的列號，交叉點的數(shù)據(jù)（最大為15）就是該S盒的輸出。48位的比特串被分為8個6位分組，經(jīng)過8個S盒進行并行的替代運算后，得到8個4位的分組。它們重新組合在一起形成一個32位的比特串。8/25/202226P盒置換（位置置換）：將S盒輸出的32位比特串根據(jù)固定的置換P（也稱為P盒）置換到相應(yīng)的位置，它也稱為直接置換(straight permutation)。例如第21位移到了第4位處，同時第4位移到了第31位處。 P盒置換表 16720212912281711

14、523265183110142482322739191330622114258/25/20222740 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 逆初始置換IP-1表逆置換IP-1逆置換是初始置換IP的逆。對于第16圈迭代的結(jié)果(R16L16) 再使用逆置換IP-1后，得到的結(jié)果即

15、可作為DES加密的密文Y輸出，即Y=IP-1(R16,L16)。DES解密算法與其加密算法相同，只是子密鑰使用次序相反!8/25/202228子密鑰的生成K=k1k2k64置換選擇1(PC-1)28bits28bitsC0D0h1位h1位C1D1置換選擇2(PC-2)K1h16位h16位C16D1648bits循環(huán)的次數(shù)取決于的輪數(shù)i值，如果i=1,2,9和16，左移循環(huán)的bit數(shù)等于1，否則循環(huán)的bit數(shù)等于 2hi位hi位CiDi置換選擇2(PC-2)Ki置換選擇2(PC-2)K16C1D1CiDiC16D16k4k5k6k7k12k13k14k15k20k21k22k23k28k29k3

16、0k31k37k38k39k45k46k47k53k54k55k61k62k63k1k2k3k9k10k11k17k18k19k25k26k27k33k34k35k36k41k42k43k44k49k50k51k52k57k58k59k60圖中，密鑰排列的左、右部分分別以左、右下腳為起始點，由下至上循環(huán)）8/25/202229PC - 1是對56bit（其他奇偶校驗位）輸入進行重新排序，輸出順序如下（圖中矩陣對應(yīng)的順序為從左到右；從上到下）： 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 左邊ci 19 11 3 60

17、52 44 36 右邊di 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密鑰k應(yīng)是64bit，請注意PC-1表中不出現(xiàn)8，16，24，32，40，48，56，64，所以實際上只有56bit有效。也可以看作是輸入64bit而只選取其中的56bit, 8bit,16bit,64bit被舍去，它本來就是奇偶校驗位。8/25/20223014 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47

18、 55 30 40 51 45 33 4844 49 39 56 34 53 46 42 50 36 29 32置換選擇2(PC-2)丟棄c9c18c22c25c35和d38d43d54 循環(huán)移位的作用 因為有循環(huán)移位運算，在每一個子密鑰中使用了不同的密鑰子集的位。雖然不是所有的位在子密鑰中使用的次數(shù)均相同，但在16個子密鑰中，每一位大約使用了其中14個子密鑰。 8/25/202231關(guān)于DES的幾點注解關(guān)于DES的S盒:S-盒是DES算法的心臟，DES靠它實現(xiàn)非線性變換，關(guān)于S-盒的設(shè)計準則還沒有完全公開。許多密鑰學家懷疑美國國家標準局（NSA）設(shè)計S-盒時隱藏了“陷門”，使得只有他們才可以

19、破譯算法，但沒有證據(jù)能表明這一點。在1976年，NSA披露了S-盒的下面幾條設(shè)計原則：每一個S-盒的每一行是整數(shù)0到15的一個置換；每個S-盒的輸出都不是它的輸入的線性或仿射函數(shù)；改變S-盒的一個輸入比持，其輸出至少有兩個比特產(chǎn)生變化；對任何S-盒和任何輸入x，S(x)和S(x001100)至少有兩比特不同；對任何S-盒和任何輸入x，并且e,f 0,1 ，S(x)S(x11ef00)；對任何S-盒，當它的任一輸入位保持不變，其他5位輸入變化時，輸出數(shù)字中的0和1的總數(shù)接近相等。 8/25/202232關(guān)于DES的密鑰:對DES的安全性批評意見中，較為一致的看法是DES的密鑰太短，其密鑰長度為5

20、6比特，密鑰量為256個，不能抵抗窮盡密鑰搜索攻擊(所謂窮盡密鑰搜索攻擊是指攻擊者在得到一組明文密文對條件下，可對明文用不同的密鑰加密，直到得到的密文與已知的明文密文對中的相符，就可確定所用的密鑰，也許有不只一個這樣的密鑰) 。 1997年3月，美國克羅拉多州的程序員Verser，用了96天的時間，通過Internet在數(shù)萬名志愿者的協(xié)同工作下，成功地找到了DES的密鑰 。1998年7月，電子邊境基金會(EFF)使用一臺25萬美元的電腦在56小時內(nèi)破解了56比特的DES。 1999年1月，電子邊境基金會用22小時15分鐘就宣告完成RSA公司發(fā)起的DES的第三次挑戰(zhàn)。 8/25/202233弱密

21、鑰初始密鑰被分成兩部分，每部分都單獨做移位。如果每一部分的每一位都是0或都是1，則每一圈的子密鑰都相同。這樣的密鑰被稱為弱密鑰。當密鑰是全1、全0或一半是全0、一半是全1時，會發(fā)生這種情況。DES存在4個弱密鑰（16進制編碼）8/25/202234半弱密鑰有些成對的密鑰會將明文加密成相同的密文，即一對密鑰中的一個能用來解密由另一個密鑰加密的消息，這種密鑰稱作半弱密鑰。半弱密鑰: DESK1 = DESK2，至少有12個半弱密鑰。8/25/202235關(guān)于三重DES加密解密兩個密鑰的三重DES目前，沒有針對三重DES的攻擊方法，它是一種較受歡迎的DES替代方案。8/25/202236IDEA簡介

22、瑞士的Xuejia Lai和James Massey于1990年公布了IDEA密碼算法第一版，稱為PES (Proposed Encryption Standard)。為抗擊差分密碼攻擊，他們增強了算法的強度，稱IPES（Improved PES)，并于1992年改名為IDEA（International Data Encryption Algorithm，國際數(shù)據(jù)加密算法）IDEA是一個分組長度為64位的分組密碼算法，密鑰長度為128位（抗強力攻擊能力比DES強），同一算法既可加密也可解密。IDEA的“混淆”和“擴散”設(shè)計原則來自三種運算，它們易于軟、硬件實現(xiàn)，加密速度快。目前軟件實現(xiàn)IDE

23、A比DES快兩倍，在66MHz486機器上加密數(shù)據(jù)速率達2400K位/秒。由ETH Zurich開發(fā)的一種VLSI芯片,在197.8mm2的芯片上包含了251000個晶體管，當時鐘為25MHz時，采用IDEA算法加密數(shù)據(jù)速率時可達177M位/秒。8/25/202237IDEA加密過程的計算框圖8/25/202238異或運算（ ）整數(shù)模216加（田）整數(shù)模216+1乘（ ）（這個運算可看成IDEA的S-盒）所有上述（ IDEA僅有的）運算都在16-位子分組上進行擴散由稱為MA結(jié)構(gòu)的基本構(gòu)件提供。MA結(jié)構(gòu)的作用有些類似于Feistel網(wǎng)絡(luò)中的非線性函數(shù)Z6F2F1Z5G1G2 MA結(jié)構(gòu)8/25/2

24、02239子密鑰的生成 IDEA算法用了52個子密鑰（8輪中的每一輪需要6個） ，其中4個用于輸出變換。首先，將128-位密鑰分成8個16-位子密鑰。這些是算法的第一批8個子密鑰（第一輪六個，第二輪的頭兩個）。然后，密鑰向左循環(huán)移25位后再分成8個子密鑰。開始4個用在第二輪，后面4個用在第三輪。密鑰再次向左環(huán)移25位后產(chǎn)生另外8個子密鑰，如此進行直到算法結(jié)束。 解密過程基本上一樣，只是子密鑰需要求逆且有些微小的差別，解密子密鑰要么是加密子密鑰的加法逆，要么是乘法逆。計算解密子密鑰要花點時間，但對每一個解密密鑰，只需做一次。 參考書應(yīng)用密碼學P228中表13-4給出加密子密鑰和相對應(yīng)的解密子密鑰

25、。對IDEA而言，對于模216+1乘，全0子分組用216=-1來表示，因此0的乘法逆是0。 8/25/202240實現(xiàn)上的考慮使用子分組：16bits的子分組；使用簡單操作（易于加法、移位等操作實現(xiàn)）；加密解密過程類似；規(guī)則的MA結(jié)構(gòu)（便于VLSI實現(xiàn)）。8/25/202241分組密碼密碼學與安全性分組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Standard)高級加密標準(Advanced Encryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/202242Rijndael不屬于Fei

26、stel結(jié)構(gòu)，是一種SP結(jié)構(gòu)Rijndael加密算法8/25/202243Rijndael是一個迭代型的具有可變分組長度和可變密鑰長度的分組密碼，在AES設(shè)計中要求分組長度為128比特（而Rijndael支持128、192或256比特的分組長度），因此，在AES規(guī)范中，對分組長度限定為128比特，每個輸入分組是用以字節(jié)為單位的44矩陣State描述（8*4*4128），明文的前四個字節(jié)被直接復(fù)制到State的第一列中，接著的四個字節(jié)被復(fù)制到第二列中，每一輪對整個分組都進行變換。S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,

27、2S3,38/25/202244k0k4k8k12k1k5k9k13k2k6k10k14k3k7k11k15w0w1w2w3w42w43AES密鑰擴展算法的輸入是4字（16字節(jié)=128比特）密鑰，輸出是一個44字（176字節(jié)）的一維數(shù)組。密鑰擴展 Key Expansion8/25/202245函數(shù)g的功能：字循環(huán)的功能使一個字中的四個字節(jié)循環(huán)左移一個字節(jié)字節(jié)代換利用S盒對輸入字中的每個字節(jié)進行字節(jié)代換與輪常量進行異或每輪的輪常量均不同，其定義為： Rconj=（RCj,0,0,0）其中：RC11，RCj=2*RCj-1,且乘 法定義在域GF(28)上。8/25/202246AES的一輪加密過

28、程SubBytes 字節(jié)代換變換ShiftRows 行移位變換MixColumns 列混淆變換 AddRoundKey 輪密鑰加8/25/202247輪密鑰加 Add Round Key128位的State按位與128位的密鑰XOR基于State列的操作，把State的一列中的四個字節(jié)與輪密鑰的一個字進行異或逆向輪密鑰加交換與正向輪密鑰加交換相同，因為異或操作是本身的逆。特點：輪密鑰加變換非常簡單，卻能影響State中的每一位。8/25/202248S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3S0,0S0,1S

29、0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3xy字節(jié)代換變換 Byte Substitution簡單的查表操作S盒是由1616個字節(jié)組成的矩陣，包含了8位值所能表達的256種可能的變換State中每個字節(jié)的高4位作為行值，低4位作為列值，取出S盒中對應(yīng)行、列的元素作為輸出，因此S-盒輸入和輸出都是8bit。逆字節(jié)代換變換利用逆S盒。8/25/202249 S-盒的構(gòu)造（由兩個變換復(fù)合而成：S=LF）：逐行按升序排列的字節(jié)值初始化S盒。第一行是00,01,02,.,0F;第二行是10,11,.,1F等。因此，在行x、列y的字節(jié)值是

30、xy。在此，表示16進制數(shù)；把S-盒中的每一字節(jié)映射為它在GF（28）中的逆;00被映射為它自身00（即可將其 看成乘法逆變換F）；把S-盒中的每一字節(jié)記成x7,x6,x0,對S-盒中每一字節(jié)的每一位做如下變換后的更新值記成y7,y6,y0（即可將其 看成仿射變換L） 注：乘積矩陣中每個元素是一個行和列所對應(yīng)元素乘積按位異或的值，進一步而言，最終的加法是按位異或的。8/25/202250例子：考慮輸入值為95的情況。在GF(28)中95的乘法逆為 95-1=8A，用二進制表示就是10001010；仿射變換用方程表示就是： 得到的結(jié)果是24,這是S盒中行號為09，列號為05所對應(yīng)的元素。（這可以

31、從參考書密碼編碼學與網(wǎng)絡(luò)安全原理與實踐p112表5.4（a）即S盒中得到證實。）逆S盒密碼編碼學與網(wǎng)絡(luò)安全原理與實踐 p112表5.4（b）。8/25/202251行移位變換 Shift RowsState數(shù)組的逐字節(jié)循環(huán)移位2nd行循環(huán)左移一字節(jié)3rd行循環(huán)左移兩字節(jié)4th行循環(huán)左移三字節(jié)解密時循環(huán)右移作用：變換確保了某列中的四個字節(jié)被擴展到4個不同的列。逆向行移位變換將state中的后三行執(zhí)行相反方向的移位操作，如第二行向右循環(huán)一個字節(jié)等。行移位變換8/25/202252列混淆變換 Mix Columns對每列獨立地進行操作每列中的每個字節(jié)被映射為一個新值，此值由該列中的四個字節(jié)通過函數(shù)變

32、換得到。這個變換可由以下基于State的矩陣乘法表示的列混淆變換圖確定，矩陣中的乘法使用GF(28)上的本原多項式（它是從30個8次不可約多項式選出，因為它是【LIDL94】中給出的第一個不可約多項式） m(x) =x8+x4+x3+x+1矩陣系數(shù)基于碼字間有最大距離的線性編碼，使得在每列的所有字節(jié)中有良好的混淆性 8/25/202253在列混淆變換圖中，乘積矩陣中的每個元素均是一行和一列中所對應(yīng)元素的乘積之和。其乘法和加法都是定義在GF(28 )上的。State中第j列（0j 3）的列混淆變化可表示為：乘法技巧：一般地，在GF(2n )上，對于n次多項式p(x)，有：xn mod p(x)=

33、p(x)- xn， 特別地，x8 mod m(x)=m(x)- x8=(x4+x2+x+1)。 設(shè)f(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0,則：8/25/202254正向變換方程逆向變換方程不容易看出：下一個方程是上一個方程的逆。詳細證明見密碼編碼學與網(wǎng)絡(luò)安全原理與實踐第116頁。8/25/202255Rijndael加密算法框圖8/25/202256總 結(jié)AES結(jié)構(gòu)的一個顯著特征是它不是Feistel結(jié)構(gòu)。它的結(jié)構(gòu)由四個不同的階段組成，包括一個混淆和三個代換：字節(jié)代換：用一個S盒完成分組中的按字節(jié)的代換。行移位： 一個簡單的置換。列混淆： 一個利用

34、在域GF(28) 上的算術(shù)特性代換。輪密鑰加：利用當前分組和擴展密鑰的一部分（有4個字128位的 密鑰作為該輪的輪密鑰）進行按位XOR。算法結(jié)構(gòu)非常簡單。對加密和解密操作，算法由輪密鑰加開始，接著執(zhí)行九輪迭代運算。每輪都包含所有四個階段的代換，然后執(zhí)行只包含三個階段的最后一輪運算。8/25/202257僅僅在輪密鑰加階段中使用密鑰。由于這個原因，該算法的開始和結(jié)束都有輪密鑰階段。如果將其他不需要密鑰的運算用于算法開始和結(jié)束的階段，在不知道密鑰的情況下就能計算其逆，故不能增加算法的安全性。輪密鑰加就其本身是不難破譯的。而另外三個階段一起提供了混淆、擴散以及非線性功能。因這些階段沒有涉及密鑰，故就

35、他們自身而言，并未提供算法的安全性。我們可以把該算法看成是一個分組的XOR加密(輪密鑰加)，接著是對這個分組的混淆(其他的三個階段)，再接著又是XOR加密等交替執(zhí)行的操作。這種方式非常有效且非常安全。8/25/202258每個階段均可逆。對字節(jié)代換、行移位和列混淆，在解密算法中用與它們相對應(yīng)的逆函數(shù)。輪密鑰加的逆就是用同樣的輪密鑰和分組相異或。與大多數(shù)分組密碼一樣，解密算法按逆序方式利用了擴展密鑰。然而，AES的解密算法和加密算法并不一樣。這是由AES的特定結(jié)構(gòu)所決定的。一旦將所有的四個階段求逆，很容易證明解密函數(shù)的確可以恢復(fù)原來的明文。AES加密和解密流程在縱向上是相反的。在每個水平點上，S

36、tate在加密和解密函數(shù)中是一樣的。8/25/202259加密和解密過程的最后一輪均只包含三個階段。這是由AES的特定結(jié)構(gòu)所決定的，而且也是密碼算法可逆性所要求的。8/25/202260沒有發(fā)現(xiàn)弱密鑰或補密鑰，能有效抵抗目前已知的攻擊算法 線性攻擊、差分攻擊非線性結(jié)構(gòu)的S-boxes，表現(xiàn)出足夠的安全余地在無論有無反饋模式的計算環(huán)境下的硬、軟件中都能顯示出非常好的性能內(nèi)存需求非常低，使它很適合用于受限的環(huán)境操作簡單，并可抵御時間和能量攻擊分組長度和密鑰長度的設(shè)計靈活，算法可根據(jù)分組長度和密鑰長度的不同組合提供不同的迭代次數(shù)關(guān)于Rijndael的注解8/25/202261分組密碼密碼學與安全性分

37、組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Standard)高級加密標準(Advanced Encryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/202262NESSIE（New European Schemes for Signatures,Integrity and Encryption）主要的目的是推出一系列安全的密碼模塊及保持歐洲在密碼研究領(lǐng)域的領(lǐng)先地位，增強密碼在歐洲工業(yè)中的作用。NESSIE涉及的范圍更廣，不僅征集了分組密碼，而且還征集了序列密碼、公鑰密碼、數(shù)字簽名、鑒別

38、碼MAC以及Hash函數(shù)。2003年2月27日，NESSIE確定了24個最終算法，其中包括四個分組密碼算法： MISTYI, Camellia, SHACAL-2, AES2NESSIE8/25/202263日本三菱電子公司Eisaku Takeda 算法參數(shù) 64 比特分組; 128比特密鑰; 8 ( 或4 n ) 圈 獨有特點部件循環(huán)使用;難以分析; 附加FL層; S 盒大小不等; S 盒ANF 簡單,具有優(yōu)化的非線性度;密鑰方案使用了S 盒; 對DC 和LC 可證明安全;加解密結(jié)構(gòu)相同. 聲明安全性 抵抗無FL 層的DC 和LC ; 抵抗5圈以上的高階差分攻擊;抵抗不可能差分攻擊;抵抗相

39、關(guān)密鑰攻擊;抵抗Slide 攻擊. 潛在弱點 S 盒代數(shù)次數(shù)低;密鑰生成方案簡單;不同S 盒增加軟硬件成本;通用線性逼近;參數(shù)未最優(yōu)化; 算法復(fù)雜. 存在的攻擊 4 圈Slicing 攻擊;利用沖突搜尋技術(shù)和不可能差分進行的4 圈攻擊;無FL 層的4 圈高階差分攻擊;46圈整合攻擊. MISTY18/25/202264Camellia 日本電報電信公司ShihoMoriai ; 日本三菱電子公司Mitsuru Matsui 算法參數(shù) 128 比特分組;128/ 192/ 256 比特密鑰; 18/ 24/ 24 圈(每6 圈加一FL層) 獨有特點面向字節(jié)的Feistel結(jié)構(gòu); S 盒使用了取逆

40、函數(shù); FL 函數(shù)及其逆中有一比特的循環(huán)移位 聲明安全性 抵抗DC 和LC ; 抵抗截斷差分析;抵抗線性包攻擊;抵抗不可能差分攻擊、Boomerang 攻擊、高階差分攻擊、相關(guān)密鑰攻擊和Slide 攻擊. 潛在弱點 S 盒中的取逆運算形成代數(shù)弱點,如二次方程式、各輸出之間的仿射關(guān)系;相同圈可能導(dǎo)致Slide 攻擊. 存在的攻擊 5 圈的不可能差分攻擊; 6 圈Square 攻擊;無FL層的7 圈不可能差分攻擊; 無FL層的8 圈截斷差分攻擊; 9 圈Square 加密鑰攻擊;9 圈Boomerang攻擊; Rectangle 攻擊; 無FL 層的11圈差分攻擊;11 圈高階差分攻擊;無FL 層

41、的12 圈線性攻擊. 8/25/202265SHACAL22 法國Gemplus 公司Helena Handschuh ; David Naccache 算法參數(shù) 256 比特分組;512 比特密鑰;4 圈(20步/ 圈) 獨有特點原型算法SHA 已被廣泛深入分析;由哈希函數(shù)轉(zhuǎn)型而來; 使用了模232 加、與、或和循環(huán)移位 聲明安全性 抵抗DC 和LC 潛在弱點 密鑰生成方案中的滑動特性可能形成潛在弱點 存在的攻擊 暫無 8/25/202266分組密碼密碼學與安全性分組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Standard)高級加密標準(Advanced E

42、ncryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/202267完備安全性問題是密碼體制的發(fā)明者做出的承諾，1949年，Claude Elwood Shannon給出了他的信息論框架，明確定義了什么是完備的安全。“Communication Theory of Secrecy Systems”密碼體制的公理化信息論密碼分析8/25/202268密碼分析攻擊根據(jù)密碼分析者破譯時所具備的前提條件，通常人們將攻擊類型分為下述四種：唯密文攻擊：密碼分析者有一個或多個密文；已知明文攻擊：密碼分析者有一些明文以及相對應(yīng)的密文；選

43、擇明文攻擊：密碼分析者有機會使用密碼機，因此可以選擇一些明文，并產(chǎn)生密文；選擇密文攻擊：密碼分析者有機會使用密碼機，因此可以選擇一些密文，并產(chǎn)生明文。上述每種攻擊的目的是決定所使用的密鑰，這四種攻擊類型的強度按序遞增，唯密文攻擊是最弱的一種攻擊，選擇密文攻擊是最強的一種攻擊。如果一個密碼系統(tǒng)能夠抵抗選擇密文攻擊，那么它當然能夠抵抗其余三種攻擊。8/25/202269強力攻擊窮盡密鑰搜索攻擊:設(shè)k是密鑰長度(以比特為單位)，在唯密文攻擊下攻擊者依次試用密鑰空間中所有2k個密鑰解密一個或多個截獲的密文。直至得到一個或多個有意義的明文塊。在已知(選擇)明文攻擊下，攻擊者試用密鑰空間中的所有2k個密鑰

44、對一個已知明文加密。將加密結(jié)果同該明文相對應(yīng)的已知密文比較，直至二者相等，然后再用其他幾個已知明密文對來驗證該密鑰的正確性。8/25/202270字典攻擊:攻擊者搜集明密文對，并把它們編排成一個“字典”。攻擊者看見密文時，檢查這個密文是否在字典里，如果在，他就獲得了該密文相對應(yīng)的明文。如果n是分組長度，那么字典攻擊需要2n個明密文對才能使攻擊者在不知道密鑰的情況下加解密任何消息。時間存儲權(quán)衡（time-memory trade-off）攻擊:一種選擇明文攻擊方法，它由窮盡密鑰搜索攻擊和查表攻擊兩種方法混合而成，它在選擇明文攻擊中以時間換取空間。它比窮盡密鑰搜索攻擊的時間復(fù)雜度小，比查表攻擊的空

45、間復(fù)雜度小。8/25/202271差分密碼分析及差分密碼分析的推廣差分密碼分析:通過分析明文對差值對密文對差值的影響來恢復(fù)某些密鑰比特。差分密碼分析利用的是密碼體制的高概率差分，如果在密碼體制中尋找高概率的差分幾乎是不可能的，那么這種密碼體制就能夠抵抗差分密碼分析。自差分分析引入以后，許多學者著力設(shè)計好的代換盒，以增強基于S盒的分組密碼的安全性 。大量研究表明，S盒抗差分分析的能力本質(zhì)上與差分分布矩陣 有關(guān)。 越大越好， 越小越好。8/25/202272截斷差分密碼分析:L. R. Knudson在差分分析的基礎(chǔ)上提出的一種部分比特的差分分析方法。如果兩個明文塊的部分比特位上的差分為P l1,

46、. . . , lh ，這兩個明文塊經(jīng)過i輪加密后部分比特位的差分為Cm1,. . . ,mn ，則稱(P l1,. . . , lh , Cm1,. . . ,mn ) 為i輪截斷差分。通常，當明文的截斷差分具有某種特殊性質(zhì)時，密文的截斷差分可能將具有某種規(guī)律, 通過這些規(guī)律可以恢復(fù)部分密鑰比特。8/25/202273高階差分密碼分析：利用離散函數(shù)的高階導(dǎo)數(shù)來定義高階差分，這些高階差分具有導(dǎo)數(shù)的某些良好的解析性質(zhì)；也可以利用明文密文的高階相關(guān)性來定義高階差分，使其具有馬爾可夫性。不可能差分密碼分析：排除那些導(dǎo)致概率為0(或非常小)的特征或差分的候選密鑰 8/25/202274線性密碼分析及線

47、性密碼分析的推廣線性密碼分析：是一種已知明文攻擊方法。它的基本思想是通過尋找一個給定密碼算法的有效線性近似表達式來破譯密碼系統(tǒng)。多重線性密碼分析：利用多重線性逼近進行線性密碼分析。多重線性密碼分析的目的是使得線性密碼分析所需的明密文對降低。n重線性密碼分析所需的明密文對，一般不會少于單個線性密碼分析所需明密文對的1/n；而多重線性密碼分析的計算量比單個線性密碼分析大。8/25/202275相關(guān)密鑰攻擊相關(guān)密鑰攻擊反映了密鑰擴展算法對分組密碼安全性的影響。在某些分組密碼中，密鑰擴展算法可以看作是一些子算法的集合，每個子算法是從前幾輪子密鑰導(dǎo)出某個特定子密鑰的過程。如果所有這些子算法是相同的（或有

48、規(guī)律的），則對給定的密鑰K，K1,K2,Kr是K對應(yīng)的子密鑰，把子密鑰K1,K2,Kr向后移一輪（或若干輪）得另一子密鑰集*,K1,Kr-1及對應(yīng)的密鑰K*，則稱K和K*是相關(guān)密鑰?；谙嚓P(guān)密鑰的攻擊和密碼的輪數(shù)無關(guān)，在相關(guān)密鑰攻擊中，需要的數(shù)據(jù)是兩個具有某種關(guān)系的相關(guān)密鑰和幾個明密文對，攻擊者僅知道兩個密鑰之間的關(guān)系，并不知道密鑰本身。8/25/202276積分密碼分析（Square攻擊）積分密碼分析特別適用于面向字節(jié)結(jié)構(gòu)和只采用雙射部件的分組密碼,其主要思想就是攻擊者通過預(yù)測經(jīng)過幾輪加密操作之后的積分值來猜測密鑰字節(jié)。最近Lars Knudsen 根據(jù)高階差分分析的思想提出了高階積分分析。

49、1 階積分分析可以成功攻擊六輪以下的Rijndael ,這種方法已經(jīng)沒有什么前途, 因為它過分依賴輪數(shù), 要想對AES 構(gòu)成很大的威脅可能性不大. 但是高階積分分析是否能夠攻擊更多輪數(shù)的Rijndael ,目前還沒有結(jié)論。8/25/202277代數(shù)攻擊XSL是基于這樣的假設(shè):分組算法的S盒能夠用一個超定代數(shù)方程系統(tǒng)來描述，如果能夠找到有效的方法來解這樣的方程系統(tǒng)就可以破譯密碼系統(tǒng)。XSL 算法可以用來解超定系統(tǒng)方程問題，但該算法對Rijndael 無效。由于用來描述Rijndael 算法的超定代數(shù)方程非常稀疏和一些特定的結(jié)構(gòu),不可用XSL算法進行分析。XSL 攻擊需要一個參數(shù)P ,理論上P 為

50、常數(shù)。研究表明:當P 很大時,XSL攻擊是算法輪數(shù)Nr 的多項式時間，即AES 算法的安全性并不是隨著輪數(shù)的增加成指數(shù)級的增加。8/25/202278其它攻擊方法錯誤攻擊定時攻擊能量攻擊8/25/202279算法的安全性破譯算法可以分為不同的級別：全部破譯（total break）找出密鑰全部推導(dǎo)（global deduction）找出替代算法實例推導(dǎo)（instance deduction）找出明文信息推導(dǎo)（information deduction）獲得一些有關(guān)密鑰或明文的信息。8/25/202280可以用不同的方式來衡量攻擊方法的復(fù)雜性：數(shù)據(jù)復(fù)雜性(data complexity)：用作攻

51、擊輸入所需要的數(shù)據(jù)量處理復(fù)雜性(processing complexity)：完成攻擊所需要的時間存儲需求(storage requirement)：進行攻擊所需要的存儲量。8/25/202281兩個基本設(shè)計方法擴散(Diffusion)：明文的統(tǒng)計結(jié)構(gòu)被擴散消失到密文的長程統(tǒng)計特性,使得明文和密文之間的統(tǒng)計關(guān)系盡量復(fù)雜混亂(confusion)：使得密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡量復(fù)雜實現(xiàn)的設(shè)計原則軟件實現(xiàn)的要求：使用子塊和簡單的運算。密碼運算在子塊上進行，要求子塊的長度能自然地適應(yīng)軟件編程，如8、16、32比特等。應(yīng)盡量避免按比特置換，在子塊上所進行的密碼運算盡量采用易于軟件實現(xiàn)的

52、運算。最好是用處理器的基本運算，如加法、乘法、移位等。硬件實現(xiàn)的要求：加密和解密的相似性，即加密和解密過程的不同應(yīng)僅僅在密鑰使用方式上，以便采用同樣的器件來實現(xiàn)加密和解密，以節(jié)省費用和體積。盡量采用標準的組件結(jié)構(gòu)，以便能適應(yīng)于在超大規(guī)模集成電路中實現(xiàn)。分組密碼的設(shè)計8/25/202282GF( 2)上布爾函數(shù)GF(2)只有兩個：0，1。關(guān)于這兩個量之間的邏輯運算就稱為2元布爾代數(shù)(因為GF(2) 的基數(shù)為2) 。對于GF(2)中的元素，有x yxyx yx+y+xyx=x+1 這里的+,分別表示GF(2)中的加(異或)、乘(與)運算。GF(2n) 到GF(2)的一個映射就稱為一個n元布爾函數(shù)。

53、8/25/202283作為邏輯運算的函數(shù)，布爾函數(shù)是研究數(shù)字邏輯電路的重要數(shù)學工具，也是研究以此為基礎(chǔ)的一切科學技術(shù)的重要工具，從而也是研究密碼學和密碼技術(shù)的重要工具。無論在流密碼還是在分組密碼中，無論在私鑰還是在公鑰密碼中，布爾函數(shù)都有重要的應(yīng)用。8/25/202284布爾函數(shù)的表示為了方便布爾函數(shù)的理論和應(yīng)用，人們在不同的情況下對布爾函數(shù)采用了不同的表示方法，主要有：真值表表示法小項表示法多項式表示法Walsh(沃爾什)譜表示法矩陣表示法等8/25/202285S盒的設(shè)計在對稱分組密碼領(lǐng)域一個最受關(guān)注的研究問題就是S盒的設(shè)計。從本質(zhì)上說，希望S盒輸入向量的任何變動在輸出方都產(chǎn)生看似隨機的變

54、動。S盒的一個明顯特征是其大小。一個nm S盒有n個輸入比特和m個輸出比特。DES具有64的S盒。一般來說較大的S盒對于差分密碼分析和線性密碼分析的抗擊力更強。另一方面，維數(shù)n越大，則查詢表就越大(指數(shù)性的)。因而，由于實現(xiàn)方面的原因，通常n限于8到10。另一個實際的考慮是S盒越大，正確實現(xiàn)它就越困難。Mister和Adams提出了許多S盒的設(shè)計準則，其中包括S盒應(yīng)該滿足SAC和BIC。Mister和Adams也建議S盒的各列的線性組合應(yīng)該是曲折函數(shù)(Bent函數(shù))。曲折函數(shù)是一類特殊的布爾函數(shù)，依據(jù)某些數(shù)學準則，這種函數(shù)是高度非線性。嚴格雪崩準則SAC(strict avalanche cr

55、iterion)：對于任何的i,j，當任何一個輸入比特i變化時，一個S盒的任何輸出比特j變化的概率為1/2。比特獨立準則BIC(bit independence criterion)：對于任意的i,j和k，當任意一個輸入比特i變化時，輸出j和k應(yīng)當獨立地變化。S盒的設(shè)計8/25/202286分組密碼系統(tǒng)中布爾函數(shù)應(yīng)該滿足一定的準則：正交性高代數(shù)次數(shù)高非線性度擴散準則和嚴格雪崩準則擴散性好的函數(shù)非線性度高，擴散性最強，Bent函數(shù)的非線性度達到最大，是完全非線性函數(shù)。均勻差分性與魯棒性布爾函數(shù)應(yīng)該滿足的準則8/25/202287隨機產(chǎn)生帶測試的隨機產(chǎn)生人工產(chǎn)生用數(shù)學方法8/25/202288 僅

56、靠法律保護我們自己還遠遠不夠,我們還需要用數(shù)學保護我們自己。8/25/202289作業(yè)思考題混淆和擴散的差別是什么？差分密碼分析和線性密碼分析的差別是什么？什么是雪崩效應(yīng)？如何構(gòu)造S盒？簡述什么是Rijndael中的列混淆？8/25/202290作業(yè)計算題設(shè):A|B=將串A和B連接起來 Ti(R|L)=DES加密過程第i輪迭代所定義的變換(1i16) TDi(R|L)=DES解密過程第i輪迭代所定義的變換(1i16) T17(R|L)=L|R DES加密過程第16輪迭代之后的變換a.證明下式： TD1(IP(IP-1(T17(T16(L15|R15)=R15|L15b.請判斷下式是否成立： T

57、D1(IP(IP-1(T16(L15|R15)=L15|R158/25/202291作業(yè)計算題若明文是000102030405060708090A0B0C0D0E0F，密鑰是0101010101010101010101010101010101，在Rijndael加密算法中： a.用44的矩陣來描述State的最初內(nèi)容。 b.給出初始化輪密鑰加后State的值。 c.給出字節(jié)代換后State的值。 d.給出行移位后State的值。 e.給出列混淆后State的值。8/25/202292分組密碼密碼學與安全性分組密碼是什么？什么是分組密碼？數(shù)據(jù)加密標準(Data Encryption Standa

58、rd)高級加密標準(Advanced Encryption Standard)歐洲密碼計劃(NESSIE )分組密碼的分析方法與設(shè)計準則混沌理論基礎(chǔ)混沌分組密碼8/25/202293混沌動力學簡介19世紀末、20世紀初發(fā)生的對于牛頓力學的三大變革8/25/202294新力學的理論特點基本方法：定性方法：微分拓撲大范圍分析 代數(shù)與群論數(shù)值方法：計算機模擬大大拓寬了力學的研究領(lǐng)域發(fā)現(xiàn)了許多新的力學現(xiàn)象。如：混沌、分岔、突變、結(jié)構(gòu)穩(wěn)定性轉(zhuǎn)變8/25/202295混沌理論混沌的特征第一個特征：對起始條件的敏感性 蝴蝶效應(yīng)(butterfly effect)迭代(Iterate)分叉(Bifurcati

59、on)孤立波 (Soliton)8/25/202296第二個特征是:不可預(yù)測性第三個特征：遍歷性 亂中有序第四個特征：自我相似性 分形(factal) 8/25/202297蝴蝶效應(yīng) butterfly effect丟了一個釘子，壞了一只蹄鐵；壞了一只蹄鐵，折了一匹戰(zhàn)馬；折了一匹戰(zhàn)馬，傷了一位騎士；傷了一位騎士，輸了一場戰(zhàn)斗；輸了一場戰(zhàn)斗，亡了一個帝國。 8/25/202298迭代 Iteration一種反復(fù)演算，不斷把計算出的答案放回方程式再計算8/25/202299分叉 Bifurcation當系統(tǒng)迭代到一種程度，就會出現(xiàn)一種分叉的路徑，在這個分叉點上，系統(tǒng)可能會通往混沌，也可能會穩(wěn)定下來

60、，一旦穩(wěn)定下來，系統(tǒng)就能抗拒變化達一段時間，直到某種新的擾動又造成新的分叉點。 8/25/2022100自相似性 Self-similarity8/25/2022101邏輯斯蒂映射的形式為其中a是參數(shù)，取值范圍是-2,4，x的取值為0,1。映射的不動點是指滿足關(guān)系=a(1- )的相點,解得1=0,2=1-1/a。設(shè)映射用 f 表示，f 的2次迭代記作f 2，3次迭代記作f 3，等等。f 的不動點也叫f 的周期1點。f 2的不動點實際上是f 的周期2點。同理f n的不動點與f 的周期n點。一維邏輯斯蒂映射8/25/20221028/25/2022103映射f 的周期m (包括不動點，它為周期1點