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

第5章高级加密标准

第5章高级加密标准1OriginsclearareplacementforDESwasneededhavetheoreticalattacksthatcanbreakithavedemonstratedexhaustivekeysearchattackscanuseTriple-DES–butslow,hassmallblocksUSNISTissuedcallforciphersin199715candidatesacceptedinJune19985wereshortlistedinAug-99RijndaelwasselectedastheAESinOct-2000issuedasFIPSPUB197standardinNov-2001Originsclearareplacementfor2AESRequirementsprivatekeysymmetricblockcipher

128-bitdata,128/192/256-bitkeys

stronger&fasterthanTriple-DESactivelifeof20-30years(+archivaluse)providefullspecification&designdetails

bothC&JavaimplementationsNISThavereleasedallsubmissions&unclassifiedanalysesAESRequirementsprivatekeysy3AESEvaluationCriteriainitialcriteriasecurity–effortforpracticalcryptanalysiscost–intermsofcomputationalefficiencyalgorithm&implementationcharacteristicsfinalcriteriageneralsecurityeaseofsoftware&hardwareimplementationimplementationattacksflexibility(inen/decrypt,keying,other

factors)AESEvaluationCriteriainitial4AESShortlistaftertestingandevaluation,shortlistinAug-99:MARS(IBM)-complex,fast,highsecuritymarginRC6(USA)-v.simple,v.fast,lowsecuritymarginRijndael(Belgium)-clean,fast,goodsecuritymarginSerpent(Euro)-slow,clean,v.highsecuritymarginTwofish(USA)-complex,v.fast,highsecuritymarginthensubjecttofurtheranalysis&commentsawcontrastbetweenalgorithmswithfewcomplexroundsversesmanysimpleroundsrefinedexistingciphersversesnewproposalsAESShortlistaftertestingand5TheAESCipher-RijndaeldesignedbyRijmen-DaemeninBelgium,has128/192/256bitkeys,128bitdata

an

iterativeratherthanfeistelcipherprocessesdataasblockof4columnsof4bytesoperatesonentiredatablockineveryrounddesignedtobe:resistantagainstknownattacksspeedandcodecompactnessonmanyCPUsdesignsimplicityTheAESCipher-Rijndaeldesi6Rijndaeldatablockof4columnsof4bytesisstatekeyisexpandedtoarrayofwordshas9/11/13roundsinwhichstateundergoes:bytesubstitution(1S-boxusedoneverybyte)shiftrows(permutebytesbetweengroups/columns)mixcolumns(subsusingmatrixmultipyofgroups)addroundkey(XORstatewithkeymaterial)viewasalternatingXORkey&scrambledatabytesinitialXORkeymaterial&incompletelastroundwithfastXOR&tablelookupimplementationRijndaeldatablockof4column7RijndaelRijndael8ByteSubstitutionasimplesubstitutionofeachbyteusesonetableof16x16bytescontainingapermutationofall2568-bitvalueseachbyteofstateisreplacedbybyteindexedbyrow(left4-bits)&column(right4-bits)eg.byte{95}isreplacedbybyteinrow9column5whichhasvalue{2A}S-boxconstructedusingdefinedtransformationofvaluesinGF(28)designedtoberesistanttoallknownattacksByteSubstitutionasimplesubs9ByteSubstitutionByteSubstitution10ShiftRowsacircularbyteshiftineachrow1strowisunchanged2ndrowdoes1bytecircularshifttoleft3rdrowdoes2bytecircularshifttoleft4throwdoes3bytecircularshifttoleftdecryptinvertsusingshiftstorightsincestateisprocessedbycolumns,thissteppermutesbytesbetweenthecolumnsShiftRowsacircularbyteshif11ShiftRowsShiftRows12MixColumnseachcolumnisprocessedseparatelyeachbyteisreplacedbyavaluedependentonall4bytesinthecolumneffectivelyamatrixmultiplicationinGF(28)usingprimepolym(x)=x8+x4+x3+x+1MixColumnseachcolumnisproc13MixColumnsMixColumns14MixColumnscanexpresseachcolas4equationstoderiveeachnewbyteincoldecryptionrequiresuseofinversematrixwithlargercoefficients,hencealittleharderhaveanalternatecharacterisation

eachcolumna4-termpolynomialwithcoefficientsinGF(28)andpolynomialsmultipliedmodulo(x4+1)MixColumnscanexpresseachco15AddRoundKeyXORstatewith128-bitsoftheroundkeyagainprocessedbycolumn(thougheffectivelyaseriesofbyteoperations)inversefordecryptionidenticalsinceXORowninverse,withreversedkeysdesignedtobeassimpleaspossibleaformofVernamcipheronexpandedkeyrequiresotherstagesforcomplexity/securityAddRoundKeyXORstatewith1216AddRoundKeyAddRoundKey17AESRoundAESRound18AESKeyExpansiontakes128-bit(16-byte)keyandexpandsintoarrayof44/52/6032-bitwordsstartbycopyingkeyintofirst4wordsthenloopcreatingwordsthatdependonvaluesinprevious&4placesbackin3of4casesjustXORthesetogether1stwordin4hasrotate+S-box+XORroundconstantonprevious,beforeXOR4thbackAESKeyExpansiontakes128-bit19AESKeyExpansion复杂函数AESKeyExpansion复杂函数20KeyExpansionRationaledesignedtoresistknownattacksdesigncriteriaincludedknowingpartkeyinsufficienttofindmanymoreinvertibletransformationfastonwiderangeofCPU’suseroundconstantstobreaksymmetrydiffusekeybitsintoroundkeysenoughnon-linearitytohinderanalysissimplicityofdescriptionKeyExpansionRationaledesigne21AESDecryptionAESdecryptionisnotidenticaltoencryptionsincestepsdoneinreversebutcandefineanequivalentinversecipherwithstepsasforencryptionbutusinginversesofeachstepwithadifferentkeyscheduleworkssinceresultisunchangedwhenswapbytesubstitution&shiftrowsswapmixcolumns&add(tweaked)roundkeyAESDecryptionAESdecryptioni22AESDecryptionAESDecryption23ImplementationAspectscanefficientlyimplementon8-bitCPUbytesubstitutionworksonbytesusingatableof256entriesshiftrowsissimplebyteshiftaddroundkeyworksonbyteXOR’smixcolumnsrequiresmatrixmultiplyinGF(28)whichworksonbytevalues,canbesimplifiedtousetablelookups&byteXOR’sImplementationAspectscaneffi24ImplementationAspectscanefficientlyimplementon32-bitCPUredefinestepstouse32-bitwordscanprecompute4tablesof256-wordstheneachcolumnineachroundcanbecomputedusing4tablelookups+4XORsatacostof4KbtostoretablesdesignersbelievethisveryefficientimplementationwasakeyfactorinitsselectionastheAEScipherImplementationAspectscaneffi25Summaryhaveconsidered:theAESselectionprocessthedetailsofRijndael–theAEScipherlookedatthestepsineachroundthekeyexpansionimplementationaspectsSummaryhaveconsidered:26第5章高级加密标准

第5章高级加密标准27OriginsclearareplacementforDESwasneededhavetheoreticalattacksthatcanbreakithavedemonstratedexhaustivekeysearchattackscanuseTriple-DES–butslow,hassmallblocksUSNISTissuedcallforciphersin199715candidatesacceptedinJune19985wereshortlistedinAug-99RijndaelwasselectedastheAESinOct-2000issuedasFIPSPUB197standardinNov-2001Originsclearareplacementfor28AESRequirementsprivatekeysymmetricblockcipher

128-bitdata,128/192/256-bitkeys

stronger&fasterthanTriple-DESactivelifeof20-30years(+archivaluse)providefullspecification&designdetails

bothC&JavaimplementationsNISThavereleasedallsubmissions&unclassifiedanalysesAESRequirementsprivatekeysy29AESEvaluationCriteriainitialcriteriasecurity–effortforpracticalcryptanalysiscost–intermsofcomputationalefficiencyalgorithm&implementationcharacteristicsfinalcriteriageneralsecurityeaseofsoftware&hardwareimplementationimplementationattacksflexibility(inen/decrypt,keying,other

factors)AESEvaluationCriteriainitial30AESShortlistaftertestingandevaluation,shortlistinAug-99:MARS(IBM)-complex,fast,highsecuritymarginRC6(USA)-v.simple,v.fast,lowsecuritymarginRijndael(Belgium)-clean,fast,goodsecuritymarginSerpent(Euro)-slow,clean,v.highsecuritymarginTwofish(USA)-complex,v.fast,highsecuritymarginthensubjecttofurtheranalysis&commentsawcontrastbetweenalgorithmswithfewcomplexroundsversesmanysimpleroundsrefinedexistingciphersversesnewproposalsAESShortlistaftertestingand31TheAESCipher-RijndaeldesignedbyRijmen-DaemeninBelgium,has128/192/256bitkeys,128bitdata

an

iterativeratherthanfeistelcipherprocessesdataasblockof4columnsof4bytesoperatesonentiredatablockineveryrounddesignedtobe:resistantagainstknownattacksspeedandcodecompactnessonmanyCPUsdesignsimplicityTheAESCipher-Rijndaeldesi32Rijndaeldatablockof4columnsof4bytesisstatekeyisexpandedtoarrayofwordshas9/11/13roundsinwhichstateundergoes:bytesubstitution(1S-boxusedoneverybyte)shiftrows(permutebytesbetweengroups/columns)mixcolumns(subsusingmatrixmultipyofgroups)addroundkey(XORstatewithkeymaterial)viewasalternatingXORkey&scrambledatabytesinitialXORkeymaterial&incompletelastroundwithfastXOR&tablelookupimplementationRijndaeldatablockof4column33RijndaelRijndael34ByteSubstitutionasimplesubstitutionofeachbyteusesonetableof16x16bytescontainingapermutationofall2568-bitvalueseachbyteofstateisreplacedbybyteindexedbyrow(left4-bits)&column(right4-bits)eg.byte{95}isreplacedbybyteinrow9column5whichhasvalue{2A}S-boxconstructedusingdefinedtransformationofvaluesinGF(28)designedtoberesistanttoallknownattacksByteSubstitutionasimplesubs35ByteSubstitutionByteSubstitution36ShiftRowsacircularbyteshiftineachrow1strowisunchanged2ndrowdoes1bytecircularshifttoleft3rdrowdoes2bytecircularshifttoleft4throwdoes3bytecircularshifttoleftdecryptinvertsusingshiftstorightsincestateisprocessedbycolumns,thissteppermutesbytesbetweenthecolumnsShiftRowsacircularbyteshif37ShiftRowsShiftRows38MixColumnseachcolumnisprocessedseparatelyeachbyteisreplacedbyavaluedependentonall4bytesinthecolumneffectivelyamatrixmultiplicationinGF(28)usingprimepolym(x)=x8+x4+x3+x+1MixColumnseachcolumnisproc39MixColumnsMixColumns40MixColumnscanexpresseachcolas4equationstoderiveeachnewbyteincoldecryptionrequiresuseofinversematrixwithlargercoefficients,hencealittleharderhaveanalternatecharacterisation

eachcolumna4-termpolynomialwithcoefficientsinGF(28)andpolynomialsmultipliedmodulo(x4+1)MixColumnscanexpresseachco41AddRoundKeyXORstatewith128-bitsoftheroundkeyagainprocessedbycolumn(thougheffectivelyaseriesofbyteoperations)inversefordecryptionidenticalsinceXORowninverse,withreversedkeysdesignedtobeassimpleaspossibleaformofVernamcipheronexpandedkeyrequiresotherstagesforcomplexity/securityAddRoundKeyXORstatewith1242AddRoundKeyAddRoundKey43AESRoundAESRound44AESKeyExpansiontakes128-bit(16-byte)keyandexpandsintoarrayof44/52/6032-bitwordsstartbycopyingkeyintofirst4wordsthenloopcreatingwordsthatdependonvaluesinprevious&4placesbackin3of4casesjustXORthesetogether1stwordin4hasrotate+S-box+XORroundconstantonprevious,beforeXOR4thbackAESKeyExpansiontakes128-bit45AESKeyExpansion复杂函数AESKeyExpansion复杂函数46KeyExpansionRationaledesignedtoresistknownattacksdesigncriteriaincludedknowingpartkeyinsufficienttofindmanymoreinvertibletransformationfastonwiderangeofCPU’suseroundconstantstobreaksymmetrydiffusekeybitsintoroundkeysenoughnon-linearitytohinderanalysissimplicityofdescriptionKeyExpansionRationaledesigne47AESDecryptionA