TEA加密算法详述

ACRYPTANALYSISOFTHETINYENCRYPTIONALGORITHMbyVIKRAMREDDYANDEMATHESISSubmittedinpartialfulfillmentoftherequirementsforthedegreeofMasterofScienceintheDepartmentofComputerScienceintheGraduateSchoolofTheUniversityofAlabamaTUSCALOOSA,ALABAMA2003SubmittedbyVikramReddyAndeminpartialfulfillmentoftherequirementsforthedegreeofMasterofSciencespecializinginComputerScience.AcceptedonbehalfoftheFacultyoftheGraduateSchoolbythethesiscommittee:______________________KennethG.Ricks,Ph.D.______________________SibabrataRay,Ph.D.______________________RandyK.Smith,Ph.D.______________________PhillipG.Bradford,Ph.D.Chairperson______________________DavidW.Cordes,Ph.D.DepartmentChairperson__________________Date______________________RonaldW.Rogers,Ph.D.DeanoftheGraduateSchool__________________DateiiACKNOWLEDGMENTSItisdifficulttooverstatemygratitudetomyadvisor,Dr.PhillipBradford.Withhisenthusiasm,hisinspiration,andhisgreateffortstoexplainthingsclearlyandsimply,hehelpedtomakecryptographyfunforme.Throughoutmythesiswritingperiod,heprovidedencouragement,soundadvice,goodteaching,goodcompany,andlotsofgoodideas.Iwouldhavebeenlostwithouthim.IamveryfortunatetohaveDr.RandySmithandDr.SibabrataRayonmythesiscommittee.Theirguidanceandfeedbackwerecrucialtomywork.IwanttothankDr.KennethRicksforservingonmythesiscommittee,andforprovidingvaluablefeedback.Lastandmostimportantly,Iwishtothankmyparents,VenkatReddyAndemandVasanthaReddyAndem.Theyboreme,raisedme,supportedme,taughtme,andlovedme.iiiCONTENTSACKNOWLEDGMENTS……………………………………………………..…………iiiLISTOFFIGURES………………………………………………………………….…...viABSTRACT………………………………………………………………………….....viii1INTRODUCTION…………………………………………………………………..11.1Motivation…………………………………………………………………...….11.2Stateoftheart……………………………………………………..………...….11.3Preliminaries…………………………………………………………………….21.4ResearchStudy……………………………………………………………….….31.5OrganizationoftheThesis……………………………………...........................32MOTIVATIONFORRESEARCH……………………………………………….…42.1Background………………………………………………………………..…….42.2TinyEncryptionAlgorithm………………………………….……………..……42.3TechniqueDevelopedbyInventors…………………………………...……..….52.3.1EncryptionRoutine…………………………………………………….….52.3.2DecryptionRoutine……………………………………………………..…92.4ExtensionsofTinyEncryptionAlgorithm……………………………………..112.5BlockTEA………………………………………………...……………...…....15iv3CRYPTANALYSIS…………………………………………………………….…..173.1Attacks………………………………………………………………………....183.1.1Ciphertextonlyattack………………………………………………..183.1.2Knownplaintextattack…………………………….…………………183.1.3Chosenplaintextattack………………………………….………….…183.2DifferentialCryptanalysis………………………………………………...……193.3RelatedKeyCryptanalysis...……………..………………………………….…193.3.1Attackone……………………………………………………….…….203.3.2Attacktwo……………………………………………………………..203.4ImpossibleDifferentialCryptanalysis………………………………………....203.5EquivalentKeys………………………………………………………………..213.6FirstCorrectionMadebytheDesigners…………………………………..…...233.7ComparisonofTEAandXTEAwiththeEquivalentKeys……………………243.8SecondCorrectionMadebytheDesigners…………………………………….243.9IntermediateCipherTextValuesforSmallKeyPairDifferences………...…..253.10StatisticalAnalysis…………………………………………………………….273.11Observations…………………...……………………………………………...404SUMMARYANDCONCLUSION………………………………………………...…414.1ContributionsoftheThesis………………………………………….……….....414.2FutureWork……………………………………………………………….……41REFERENCES…………………………………………………………………………..42APPENDIXIMPLEMENTATION……………………………………………..……..43vLISTOFFIGURES2.1Encoderoutine…………………………………………………………………….....52.2TheabstractstructureofTEAencryptionroutine……………………..…………….62.3Anabstractionofi-thcycleofTEA………………………………………………….82.4Decoderoutine……………………………………………………………………..…92.5TheabstractstructureofTEAdecryptionroutine………………………………......102.6XTEAroutine……………………………………………………………….……….122.7Anabstractionofi-thcycleofXTEA……………………………………………….132.8Roundkeygenerationalgorithm…………………………………………………….142.9BlockTEAroutine…………………………………………………………………..153.1ComparisonofTEAandXTEAwiththeequivalentkeys………………………….243.2Sampleoutputofdataobtainedbylinearlyincrementingasinglebitinthekeysk[0],k[1],k[2]andk[3]onanInputdata(forv=0000000000000000)..................263.3Decimalequivalentvaluesoftheencodedciphertexts……………………………..273.4Histogramoftheciphertextvaluesincolumnone(C1)……………………………283.5Comparisonofcolumnone(C1)withcolumnthree(C3)…………………………..293.6Comparisonofcolumnsone-threewithcolumnone-five…………………………...303.7Comparisonofciphertextvaluesineachcolumnwiththeciphertextvaluesinothercolumns………………………………………………………….....................313.83DplotofciphertextvaluesincolumnsC1,C3,andC5…………………………..323.93DsurfaceplotofciphertextvaluesincolumnsC1,C3,andC5…………………..33vi3.103DwireframeplotofciphertextvaluesincolumnsC1,C3,andC5……………...343.113DplotofciphertextvaluesincolumnsC2,C4,andC6………………….………353.123DsurfaceplotofciphertextvaluesincolumnsC2,C4,andC6…………………363.133DwireframeplotofciphertextvaluesincolumnsC2,C4,andC6……………..373.14NormalprobabilityplotforcolumnsC1,C3,C5,C7……………………………..383.15NormalprobabilityplotforcolumnsC2,C4,C6,C8……………………………..39viiABSTRACTTheTinyEncryptionAlgorithm(TEA)isacryptographical