第5章-高级加密标准课件

,Click to edit Master title style,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,第,5,章 高级加密标准,第5章 高级加密标准,1,Origins,clear,a replacement for DES,was needed,have theoretical attacks that can break it,have demonstrated exhaustive key search attacks,can use,Triple-DES,but slow,has small blocks,US NIST issued call for ciphers in 1997,15 candidates accepted in June 1998,5 were shortlisted in Aug-99,Rijndael,was selected as the AES in Oct-2000,issued as FIPS PUB 197 standard in Nov-2001,Originsclear a replacement for,2,AES Requirements,private key symmetric block cipher,128-bit data,128/192/256-bit keys,stronger&faster,than Triple-DES,active life of,20-30 years,(+archival use),provide,full specification&design details,both,C&Java implementations,NIST have released all submissions&unclassified analyses,AES Requirementsprivate key sy,3,AES Evaluation Criteria,initial criteria,security effort for practical cryptanalysis,cost in terms of computational efficiency,algorithm&implementation characteristics,final criteria,general security,ease of software&hardware implementation,implementation attacks,flexibility(in en/decrypt,keying,other,factors),AES Evaluation Criteriainitial,4,AES Shortlist,after testing and evaluation,shortlist in Aug-99,:,MARS(IBM),-complex,fast,high security margin,RC6(USA),-v.simple,v.fast,low security margin,Rijndael(Belgium),-clean,fast,good security margin,Serpent(Euro),-slow,clean,v.high security margin,Twofish(USA),-complex,v.fast,high security margin,then subject to further analysis&comment,saw contrast between algorithms with,few complex rounds verses many simple rounds,refined existing ciphers verses new proposals,AES Shortlistafter testing and,5,The AES Cipher-Rijndael,designed by,Rijmen-Daemen,in Belgium,has,128/192/256 bit keys,128 bit data,an,iterative,rather than,feistel,cipher,processes,data as block of 4 columns of 4 bytes,operates on entire data block in every round,designed to be:,resistant against known attacks,speed and code compactness on many CPUs,design simplicity,The AES Cipher-Rijndael desi,6,Rijndael,data block of,4 columns of 4 bytes,is,state,key is,expanded to array of words,has,9/11/13 rounds,in which state undergoes:,byte substitution,(1 S-box used on every byte),shift rows,(permute bytes between groups/columns),mix columns,(subs using matrix multipy of groups),add round key,(XOR state with key material),view as,alternating XOR key&scramble data bytes,initial XOR key material&incomplete last round,with fast XOR&table lookup implementation,Rijndaeldata block of 4 column,7,Rijndael,Rijndael,8,Byte Substitution,a simple substitution of each byte,uses,one table of 16x16 bytes containing a permutation of all 256 8-bit values,each byte of state is replaced by byte indexed by row(left 4-bits)&column(right 4-bits),eg.byte 95 is replaced by byte in row 9 column 5,which has value 2A,S-box constructed using defined transformation of values in GF(2,8,),designed to be resistant to all known attacks,Byte Substitutiona simple subs,9,Byte Substitution,Byte Substitution,10,Shift Rows,a circular byte shift,in each,row,1,st,row is unchanged,2,nd,row does 1 byte circular shift to left,3rd row does 2 byte circular shift to left,4th row does 3 byte circular shift to left,decrypt inverts using shifts to right,since state is processed by columns,this step permutes bytes between the columns,Shift Rowsa circular byte shif,11,Shift Rows,Shift Rows,12,Mix Columns,each column is,processed separately,each byte is replaced by a value dependent on all 4 bytes in the column,effectively a matrix multiplication in GF(2,8,)using prime poly,m(x)=x,8,+x,4,+x,3,+x+1,Mix Columnseach column is proc,13,Mix Columns,Mix Columns,14,Mix Columns,can,express each col as 4 equations,to derive each new byte in col,decryption requires use of,inverse matrix,with larger coefficients,hence a little harder,have an,alternate characterisation,each column a 4-term polynomial,with coefficients in GF(2,8,),and polynomials multiplied modulo(x,4,+1),Mix Columnscan express each co,15,Add Round Key,XOR state with,128-bits of the round key,again processed by,column,(though effectively a series of byte operations),inverse for decryption identical,since XOR own inverse,with reversed keys,designed to be as simple as possible,a form of Vernam cipher on expanded key,requires other stages for complexity/security,Add Round KeyXOR state with 12,16,Add Round Key,Add Round Key,17,AES Round,AES Round,18,AES Key Expansion,takes,128-bit,(16-byte)key and expands into array of,44/52/60 32-bit words,start by copying key into first 4 words,then loop creating words that depend on values in previous&4 places back,in 3 of 4 cases just XOR these together,1,st,word in 4 has rotate+S-box+XOR round constant on previous,before XOR 4,th,back,AES Key Expansiontakes 128-bit,19,AES Key Expansion,复杂函数,AES Key Expansion复杂函数,20,Key Expansion Rationale,designed to,resist known attacks,design,criteria,included,knowing part key insufficient to find many more,invertible transformation,fast on wide range of CPUs,use round constants to break symmetry,diffuse key bits into round keys,enough non-linearity to hinder analysis,simplicity of description,Key Expansion Rationaledesigne,21,AES Decryption,AES decryption is not identical to encryption,since steps done in reverse,but,can define an equivalent inverse cipher,with steps as for encryption,but using inverses of each step,with a different key schedule,works since result is unchanged when,swap byte substitution&shift rows,swap mix columns&add(tweaked)round key,AES DecryptionAES decryption i,22,AES Decryption,AES Decryption,23,Implementation Aspects,can,efficiently implement on 8-bit CPU,byte substitution,works on bytes using a table of 256 entries,shift rows,is simple byte shift,add round key,works on byte XORs,mix columns,requires matrix multiply in,GF(2,8,)which works on byte values,can be simplified to use table lookups&byte XORs,Implementation Aspectscan effi,24,Implementation Aspects,can,efficiently implement on 32-bit CPU,redefine steps to use 32-bit words,can precompute 4 tables of 256-words,then each column in each round can be computed using 4 table lookups+4 XORs,at a cost of 4Kb to store tables,designers believe this very efficient implementation was a key factor in its selection as the AES cipher,Implementation Aspectscan effi,25,Summary,have considered:,the AES selection process,the details of Rijndael the AES cipher,looked at the steps in each round,the key expansion,implementation aspects,Summaryhave considered:,26,