Cryptography and Network Security 4e - search …：密码学与网络安全4E -搜索…

1、PART I Symmetric CiphersCHAPTER 5 Advanced Encryption Standard 5.1 Evaluation Criteria For AES 5.2 The AES Cipher 122KEY POINTSAES is a block cipher intended to replace DES for commercial applications. It uses a 128-bit block size and a key size of 128, 192, or 256 bits.AES does not use a Feistel st

2、ructure. Instead, each full round consists of four separate functions: byte substitution, permutation, arithmetic operations over a finite field, and XOR with a key.1235.1 Evaluation Criteria for AESThe Origins of AES A replacement for DES was neededhave theoretical attacks that can break ithave dem

3、onstrated exhaustive key search attacksCan use Triple-DES but slow, has small blocksUS NIST issued call for ciphers in Sep. 12, 1997; (block length:128bits, key length: 128, 192, 256bits, royalty-free basis, stronger & faster than Triple-DES)Submission were due on June 15, 1998, Of 21submitted crypt

4、osystems, 15 met all the necessary criteria. AES candidates“First AES Candidate Conference” on Aug. 20, 98. “Second AES Candidate Conference” on Mar., 99. 124The Origins of AESAug. 99, five of the candidates were chosen by NIST as finalist: MARS, RC6, Rijndael, Serpent, TwofishApr., 2000, Third AES

5、candidates Conference Oct. 2, 2000, Rijndael was selected to be the AES Belgian researcher, Joan Daemen, Vincent RijmenFeb. 28, 2001, (NIST) AES was available for public review and comment. Nov. 26, 2001, Rijndael was adopted as a standard (AES). Dec. 4, 2001, published as FIPS 197. Rijndael was sel

6、ected because its combination of security, performance, efficiency, implementability and flexibility 5.1 Evaluation Criteria for AES125AES Evaluationinitial criteria:security effort for practical cryptanalysiscost in terms of computational efficiencyalgorithm & implementation characteristicsfinal cr

7、iteria (Oct. 2, 2000)general securityease of software & hardware implementationimplementation attacksflexibility (in en/decrypt, keying, other factors)5.1 Evaluation Criteria for AES1265.2 The AES Cipher Designed by Rijmen-Daemen in Belgium Block & Key size : 128/192/256 bit keys Table 5.3 AES Param

8、eters an iterative rather than feistel cipherprocesses data as block of 4 columns of 4 bytesoperates on entire data block in every roundDesigned to be:resistant against known attacksspeed and code compactness on many CPUsdesign simplicity1275.2 The AES Cipher Variable block length : 128, 192, 256 bi

9、ts;State : Intermediate cipher resultNb : the # of 4-bytes(word; 32 bits) of a blockNb = 4, 6, 8 if the block length is 128, 192, 256 bits One dimensional array of a byte within a block; x0, x1, x2, , x15, x23, x31Rectangular(2D) array with four rowsIndex of One dimensional array: n 0n15(Nb = 4); 0n

10、23(Nb = 6); 0n31(Nb = 8) Index of Rectangular(2D): (i, j) i = n mod 4, j = n / 4, n = i + 4 * j 0j3(Nb = 4); 0j5(Nb = 6); 0n7(Nb = 8)1285.2 The AES Cipher State : Intermediate cipher resultVariable key length : 128, 192, 256 bitsNk : the # of 4-bytes(word; 32 bits) of a keyNk = 4, 6, 8 if the key le

11、ngth is 128, 192, 256 bits x0 x4 x8 x12 x1 x5 x9 x13 x2 x6x10 x14 x3 x7x11x15s0,0s0,1s0,2s0,3s1,0s1,1s1,2s1,3s2,0s2,1s2,2s2,3s3,0s3,1s3,2s3,3 State (Nb=4) Nb=6 Nb=8 Plaintext block (Nb=4)1295.2 The AES Cipher Variable key length : 128, 192, 256 bitsNk : the # of 4-bytes(word; 32 bits) of a keyNk = 4

12、, 6, 8 if the key length is 128, 192, 256 bits k0 k4 k8 k12 k1 k5 k9 k13 k2 k6k10k14 k3 k7k11k15 w0w1 w2 w3 w42w43 Key and expanded key Nr = 10Key size (Nk = 4)1305.2 The AES Cipher The AES is an iterated cipher; the # of rounds; NrNr depends on the block length and key length.NrNb = 4Nb = 6Nb = 8Nk

13、 = 4101214Nk = 6121214Nk = 8141414Nr =The number of rounds131Fig. 5.1 AES Encryption/ DecryptionNb = 4Nk = 4Nr = 101325.2 The AES Cipher Substitute Bytes Transformation (SubBytes)Forward and Inverse substitute byte transformationS1,1 = 9595S1,1 = 2A S-box constructed using defined transformation of

14、values in GF(28) designed to be resistant to all known attacks1335.2 The AES Cipher Substitute Bytes Transformation (SubBytes)Table 5.4 AES S-box1345.2 The AES Cipher Substitute Bytes Transformation (SubBytes)The S-box is constructed in the following fashion:The value of the byte at row x, column y

15、is xy . Map each byte xy in the S-Box to its multiplicative inverse in the finite field GF(28) =Fx/(x8+x4+x3+x+1)Let xy 1 = b = (b7 b6 b5 b4 b3 b2 b1 b0). Apply the following transformation to each bit of b:bi = bib(i+4) mod 8b(i+5) mod 8b(i+6) mod 8b(i+7) mod 8ciwhere ci such that (c7c6c5c4c3c2c1c0

16、)=(01100011)=6316 b Affine transformation b 1355.2 The AES Cipher Substitute Bytes Transformation (SubBytes)The affine transformation of the S-box in field GF(28). 1365.2 The AES Cipher Substitute Bytes Transformation (SubBytes)Example : xy=95= (10010101): A(x) = x7+ x4+ x2+1 A(x)1 = x7+ x3+ x b= (1

17、0001010)=8A b = (00101010) = 2A1375.2 The AES Cipher Inverse SubBytes Transformation Table 5.4 AES Inverse S-box1385.2 The AES Cipher Inverse SubBytes Transformation The inverse affine transformation: b = 2A 8A 8A1 = 95 : inverse in the field GF(28)1395.2 The AES Cipher Forward ShiftRows Transformat

18、ion A circular byte shift in each row 87F24D 97 EC 6E4C90 4AC346E7 8CD895A6 87F24D 97 6E 4C90EC 46E74AC3 A68CD895no left shift1 left shift2 left shifts3 left shiftsNbRow 1Row 2 Row 3 Row 4 401236012380134 Shift offsets for different block lengths1405.2 The AES Cipher Forward ShiftRows Transformation

19、 Inverse ShiftRows TransformationDecrypt inverts using shifts to right 1415.2 The AES Cipher Forward MixColumn Transformation Each column is processed separately.Each byte is replaced by a value dependent on all 4 bytes in the column 1425.2 The AES Cipher Forward MixColumn Transformation effectively

20、 a matrix multiplication in GF(28) using prime poly. m(x) = x8 + x4 + x3 + x +1 1435.2 The AES Cipher Forward MixColumn Transformation Example : 4740A3 4C 37 D4709F 94E43A42 EDA5A6BC 87F24D 97 6E 4C90EC 46E74AC3 A68CD895Inverse MixColumn Transformation decryption requires use of inverse matrix1445.2

21、 The AES Cipher Forward AddRoundKey Transformation XOR state with 128-bits of the round keyInverse AddRoundKey Transformation inverse for decryption identical; since XOR own inverse, with reversed keys 1455.2 The AES Cipher AES Key Expansion Takes 128-bit (16-byte) key and expands into array of Nk =

22、 44/52/60 32-bit wordsThe function g :1: RotWord : one-byte circular left shift wi = b0 b1 b2 b3 b1 b2 b3 b0 2: SubWord : SubBytes transformaton3: The result of 1 & 2 RconjRconj = 1, Rconj = 2Rconsj1 over GF(28)Rcon2 = 02 Rcon3 = 04 Rcon4 = 08 Rcon5 = 10Rcon6 = 20 Rcon7 = 40Rcon8 = 80 Rcon9 = 1BRcon

23、10 = 361465.2 The AES Cipher AES Key Expansion Rationaledesigned to resist known attacksdesign criteria includedknowing part key insufficient to find many moreinvertible transformationfast on wide range of CPUsuse round constants to break symmetrydiffuse key bits into round keysenough non-linearity

24、to hinder analysissimplicity of description1475.2 The AES Cipher Equivalent Inverse CipherAES decryption is not identical to encryption since steps done in reverse; but can define an equivalent inverse cipher with steps as for encryptionusing inverses of each step with a different key scheduleInterchangeing InvShiftRows and InvSubBytes InvShiftRowsInvSubBytes(Si) = InvSubBytesI