02-對稱密碼體系

1、第2講 對稱密碼體系王志偉 博士計算機學院 信息安全系2022/8/11南京郵電大學2本講內(nèi)容對稱密碼體系的原理1Fiestel結(jié)構(gòu)2DES3AES42022/8/11南京郵電大學31. 對稱密碼原理對稱密碼技術(shù)也叫做單鑰或傳統(tǒng)密碼技術(shù)特點：加密和解密時所用的密鑰是相同的或者類似的，即由加密密鑰可以很容易推導出解密密鑰分組密碼技術(shù)流密碼技術(shù)在公鑰密碼技術(shù)出現(xiàn)之前，它是唯一的加密類型。4Shannons Guide to Good CiphersAmount of secrecy should determine amount of labor appropriate for encryptio

2、n and decryptionThe set of keys and enciphering algorithm should be free from complexityThe implementation should be as simple as possibleErrors in ciphering should not propagateSize of the enciphered text should be no larger than the original5Commercial Encryption GuidesCryptosystem should be based

3、 on sound mathematicsIt has been analyzed by many expertsIt has stood the “test of time”2022/8/11南京郵電大學6傳統(tǒng)密碼體制 明文密鑰k密鑰k明文密文加密器 Ek解密器 Dk安全信道2022/8/11南京郵電大學7 公開密碼體制 明文私鑰d公鑰e明文密文加密器 Ek解密器 Dk流密碼2022/8/11南京郵電大學8將明文M分割成字符串和比特串,M=m0,m1,mj,并逐字符或逐位進行加密：Ek(M)=Ek0(m0),Ek1(m1),Ekj(mj),其中：密鑰流是K=k0,k1,kj,工作原理 典型的

4、流密碼算法： RC4假設(shè)m=m0m1m2是一個待加密的明文序列(一般是二進制0,1序列),k=k0k1k2是一個與明文序列等長的二元(偽)隨機序列，稱為密鑰序列。收發(fā)兩端都事先知道密鑰序列的內(nèi)容了，于是在序列密碼中，用密鑰序列k對明文序列m進行加密的過程是將k和m對應的分量進行簡單的模2相加，得到加密后的密文序列 c=c0c1c2 即ci=(ki+mi)(mod2)。在接收端，合法的接收者的解密過程就是將密文序列c和密鑰序列的對應分量進行簡單的模2相加。于是原來的明文序列就恢復出來了，因為 mi=(ki+ci)(mod2) 2022/8/11南京郵電大學9分組密碼類似“電碼本密碼”將明文編碼后

5、的數(shù)字序列劃分成長為m的明文組各明文組在長為i的密鑰組的控制下變換成長為n的密文組通常取nmnm 擴展分組密碼nm 壓縮分組密碼典型分組密碼結(jié)構(gòu)-Feistel美國商用數(shù)據(jù)加密標準DES（Data Encryption Standard）2022/8/11南京郵電大學10流密碼和分組密碼 流密碼的優(yōu)缺點： 分組密碼的優(yōu)缺點： 應用場合：優(yōu)點：代碼簡單，加解密速度快；缺點：如果對兩個明文加密使用相同的密碼，則密碼分析極易成功。因此需要經(jīng)常變換密鑰。優(yōu)點：可以重復使用密鑰；缺點：代碼更為復雜，計算速度相對較慢。流密碼適合于對于數(shù)據(jù)流進行加密解密的應用，比如通過一個數(shù)據(jù)通信信道或者網(wǎng)頁瀏覽器連接。分

6、組密碼適合于處理成塊的數(shù)據(jù)，比如文件傳輸、電子郵件和數(shù)據(jù)庫。RC4是應用最為廣泛的流密碼，它被用于SSL/TLS標準，該標準為網(wǎng)絡(luò)瀏覽器和服務器間通信而制定。2022/8/11南京郵電大學11本講內(nèi)容對稱密碼體系的原理1Fiestel結(jié)構(gòu)2DES3AES42022/8/11南京郵電大學12要點概述 分組密碼是一種加解密算法，其將輸入的明文分組當做一個整體處理，輸出一個等長的密文分組。 許多分組密碼都采用Feistel結(jié)構(gòu)，這樣的結(jié)構(gòu)由許多相同的輪函數(shù)組成。每一輪里，對輸入數(shù)據(jù)的一半進行代換，接著用一個置換來交換數(shù)據(jù)的兩個部分。擴展初始的密鑰使得每一輪里使用不同的子密鑰。2022/8/11南京郵

7、電大學132. 典型分組密碼結(jié)構(gòu)-Feistel基于“擴散”和“混淆”的思考，F(xiàn)eistel想出了替換和置換交替的方式構(gòu)造密碼。擴散指使明文的統(tǒng)計特性消散在密文中，每個密文數(shù)字被許多明文數(shù)字影響；混淆則盡可能使密文和加密密鑰間的統(tǒng)計關(guān)系更加復雜，以阻止攻擊者發(fā)現(xiàn)密鑰。Feistel是一種設(shè)計原則，并非一個特殊的密碼加密將明文分成左、右兩部分: 明文 = (L0,R0)在每一輪 i=1,2,.,n, 計算Li= Ri1 Ri= Li1 F(Ri1,Ki)其中 F is 輪函數(shù) and Ki is 子密鑰密文 = (Ln,Rn)2022/8/11南京郵電大學14Feistel 解密解密將密文c作為

8、輸入，以逆序（即K16,K15,K1）使用密鑰方案，輸出明文m。15Feistel NetworkStructured to enable use of same S-box and P-box for encryption and decryptionChange only key scheduleMajor feature is key division and swappingL(i) = R(i-1) left half next stage is right half from last stageR(i) = L(i-1) xor F(K(i), R(i-1)Right half

9、next stage is left half last step XORd with function of right half last stage and stage keyMathematical Description16isimple transpositionFeistel Cipher17decryption18Feistel Network StructureEncryptDecryptCIPHERTEXTPLAINTEXT19Avalanche EffectKey desirable property of an encryption algorithmWhere a c

10、hange of one input or key bit results in changing approx half of the output bitsIf the change were small, this might provide a way to reduce the size of the key space to be searchedDES exhibits strong avalanche2022/8/11南京郵電大學20本講內(nèi)容對稱密碼體系的原理1Fiestel結(jié)構(gòu)2DES3AES42022/8/11南京郵電大學213. DESDES是16輪的Feistel結(jié)構(gòu)密

11、碼DES的分組長度是64位DES使用56位的密鑰DES的每一輪使用48位的子密鑰每個子密鑰是56位密鑰的子集構(gòu)成22DES : The Big PictureParity bits dropped(1 per byte)2022/8/11南京郵電大學23DES的總體流程步驟：（1）64位明文經(jīng)過初始置換IP而被重新排列 T0=IP(T)；（2）T0經(jīng)過16輪相同函數(shù)的作用，每輪作用都有置換和代換。（3）最后通過逆置換IP-1得到64位二進制密文輸出。2022/8/11南京郵電大學24DES的3個基本函數(shù) 之 IP初始換位函數(shù)（IP：Initial Permutation）把輸入的64位數(shù)據(jù)的排

12、列順序打亂，每位數(shù)據(jù)按照下面規(guī)則重新組合具體參見課本 P74 表6.1（a）58,50,12,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,72022/8/11南京郵電大學25加密算法的3個基本函數(shù) 之 IP-1 逆初始置換函數(shù)IP-1將L16與R16作為輸入，進行逆初始換位得到密文輸出 是初始置換函

13、數(shù)的逆運算 具體參見課本 P74 表6.1（b）2022/8/11南京郵電大學26加密算法的3個基本函數(shù) 之 F函數(shù)F函數(shù)多個置換函數(shù)和替代函數(shù)的組合函數(shù)1）E函數(shù)（擴展函數(shù) 32b 48b）2）異或運算3）S盒函數(shù) (48b 32b)4) P盒(換位)2022/8/11南京郵電大學27LRexpandshiftshiftkeykeyS-boxescompressLR28282828282848324832323232DES的一輪4832KiP box2022/8/11南京郵電大學28DES 擴展排列（擴充+置換）輸入 32 bits 0 1 2 3 4 5 6 7 8 9 10 11 12

14、13 14 1516 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31輸出 48 bits31 0 1 2 3 4 3 4 5 6 7 8 7 8 9 10 11 12 11 12 13 14 15 1615 16 17 18 19 20 19 20 21 22 23 2423 24 25 26 27 28 27 28 29 30 31 02022/8/11南京郵電大學29DES S盒子（代換+選擇）每個S-box 將6 bits映射為4bits第1個 S-boxinput bits (0,5) input bits (1,2,3,4) | 0000 0

15、001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111-00 | 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 011101 | 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 100010 | 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 100

16、1 0111 0011 1010 0101 000011 | 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101具體例子參見課本P76 2022/8/11南京郵電大學30DES P-盒子 （置換）輸入 32 bits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31輸出 32 bits15 6 19 20 28 11 27 16 0 14 22 25 4 17 30 9

17、 1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 242022/8/11南京郵電大學31DES算法可能有如下安全問題1）DES的56位密鑰可能太小。1998年7月，DES算法被宣布攻破，攻擊者使用的是不到25萬美元的特殊的“DES破譯機”，這種攻擊只需要不到3天的時間。2）DES的迭代次數(shù)可能太少。（16次恰巧能抵抗差分分析）。3）S盒（即替代函數(shù)S）中可能有不安全因素。4）DES的一些關(guān)鍵部分不應當保密。多重加密是將一個加密算法多次使用的技術(shù)。在第一次使用中，明文通過加密算法轉(zhuǎn)化為密文；然后將該密文作為輸入重新執(zhí)行加密算法，該過程可以重復執(zhí)行。2022/8/11

18、南京郵電大學32三重DES三重DES是人們在發(fā)現(xiàn)DES密鑰過短，易于受到蠻力攻擊而提出的一種替代加密算法。三重DES使用3個密鑰，執(zhí)行3次DES算法。加密過程為加密-解密-加密（EDE），可表示為如下的公式： C=EK3(DK2(EK1(M)2022/8/11南京郵電大學33為了避免三重DES使用3個密鑰進行三階段加密帶來的密鑰過長的缺點（168bit），Tuchman提出使用兩個密鑰的三重加密方法，這個方法只要求112bit密鑰，即令其K1=K3： C=EK1(DK2(EK1(M)三重DES的特點2022/8/11南京郵電大學34本講內(nèi)容對稱密碼體系的原理1Fiestel結(jié)構(gòu)2DES3AES

19、42022/8/11南京郵電大學35高級加密標準AESNIST （美國國家標準技術(shù)研究所）征集的AES的基本要求是：AES應該像DES和三重DES那樣是一個分組加密方法，并且至少像三重DES一樣安全，但是其軟件實現(xiàn)應該比三重DES更加有效。NIST在1997年9月發(fā)布征集候選AES的塊加密方法時明確提出要求的指標：（1）不是機密的，可以向公眾公開的加密方法。（2）可以提供128、192和256比特的密鑰長度。（3）具有128比特塊長度(具有更強的安全性)。（4）在世界任何地方都可用，不受任何限制。 2022/8/11南京郵電大學36高級加密標準AES(續(xù))對AES候選方案的評審標準有3條：（1

20、）全面的安全性，這是最為重要的指標。（2）性能，特別是軟件實現(xiàn)的處理性能。（3）算法的知識產(chǎn)權(quán)等特征。 比利時學者Joan Daemen和Vincent Rijmen提出的Rijndael加密算法最終被選為AES算法。NIST在2001年12月正式頒布了基于Rijndael算法AES標準。AES是一種分組密碼，用以取代DES的商業(yè)應用。其分組長度為128位，密鑰長度為128/192/256位2022/8/11南京郵電大學37AES介紹1997年NIST宣布征集AES算法要求: 與三重DES比，要快且至少一樣安全,分組128位,密鑰128/192/256位1998年確定第一輪15個候選者1999

21、年確定第二輪五個候選者: MARSRC6Rijndael (萊恩戴爾)SerpentTwofish2000年底Rijndael勝出2022/8/11南京郵電大學38Rijndael簡介不屬于Feistel結(jié)構(gòu)加密、解密相似但不對稱支持128/192/256(/32=Nb)數(shù)據(jù)塊大小支持128/192/256(/32=Nk)密鑰長度有較好的數(shù)學理論作為基礎(chǔ)結(jié)構(gòu)簡單、速度快2022/8/11南京郵電大學39Rijndael特點Rijndael算法是一種分組長度和密鑰長度均可變的分組密碼算法，其分組長度和密碼長度都分別可為128/192/256bit。一般說來， Rijndael匯聚了安全、效率、易

22、用、靈活等優(yōu)點，使它能成為AES最合適的選擇。2022/8/11南京郵電大學40Rijndael特點安全性： Rijndael算法抗線性攻擊和抗差分攻擊的能力大大增強。算法的速度：RC6需要用到乘法運算，并且需要大量內(nèi)存；Twofish不便于在硬件中實現(xiàn)；Mars和Serpent的速度都不如Rijndael。靈活性： Rijndael的密鑰長度可根據(jù)不同的加密級別進行選擇。 Rijndael的分組長度也是可變的，彌補了DES的弊端。 Rijndael的循環(huán)次數(shù)允許在一定范圍內(nèi)根據(jù)安全要求進行修正。41Implementation IssuesCan be efficiently impleme

23、nted on 8-bit CPUByte substitution works on bytes using a table of 256 entriesShift rows is simple byte shiftingAdd round key works on byte XORsMix columns requires matrix multiply in GF(28) on byte values, can be simplified to use a table lookup2022/8/11南京郵電大學42算法密鑰長度分組長度循環(huán)次數(shù)DES566416三重DES112/1686448IDEA128648AES128/192/256128/192/25610/12/14分組加密算法對比43ECB ProblemProblem: identical plaintext blocks produce identical ciphertext bl