密钥分散管理系统——密钥确认算法实现外文资料翻译--原文

大学毕业设计论文外文资料翻译学院系计算机学院专业信息安全学生姓名班级学号外文出处WILLIAMSTALLINGSCRYPTOGRAPHYANDNETWORKSECURITY,FOURTHEDITIONPRENTICEHALLNOVEMBER16,2005附件1外文资料翻译译文；2外文原文A1A0A2A3A4A5A7A1A0A2A3A6A8A7A11A12A13外文资料翻译原文101KEYMANAGEMENTINCHAPTER7,WEEXAMINEDTHEPROBLEMOFTHEDISTRIBUTIONOFSECRETKEYSONEOFTHEMAJORROLESOFPUBLICKEYENCRYPTIONHASBEENTOADDRESSTHEPROBLEMOFKEYDISTRIBUTIONTHEREAREACTUALLYTWODISTINCTASPECTSTOTHEUSEOFPUBLICKEYCRYPTOGRAPHYINTHISREGARDTHEDISTRIBUTIONOFPUBLICKEYSTHEUSEOFPUBLICKEYENCRYPTIONTODISTRIBUTESECRETKEYSWEEXAMINEEACHOFTHESEAREASINTURNDISTRIBUTIONOFPUBLICKEYSSEVERALTECHNIQUESHAVEBEENPROPOSEDFORTHEDISTRIBUTIONOFPUBLICKEYSVIRTUALLYALLTHESEPROPOSALSCANBEGROUPEDINTOTHEFOLLOWINGGENERALSCHEMESPUBLICANNOUNCEMENTPUBLICLYAVAILABLEDIRECTORYPUBLICKEYAUTHORITYPUBLICKEYCERTIFICATESPUBLICANNOUNCEMENTOFPUBLICKEYSONTHEFACEOFIT,THEPOINTOFPUBLICKEYENCRYPTIONISTHATTHEPUBLICKEYISPUBLICTHUS,IFTHEREISSOMEBROADLYACCEPTEDPUBLICKEYALGORITHM,SUCHASRSA,ANYPARTICIPANTCANSENDHISORHERPUBLICKEYTOANYOTHERPARTICIPANTORBROADCASTTHEKEYTOTHECOMMUNITYATLARGEFIGURE101FOREXAMPLE,BECAUSEOFTHEGROWINGPOPULARITYOFPGPPRETTYGOODPRIVACY,DISCUSSEDINCHAPTER15,WHICHMAKESUSEOFRSA,MANYPGPUSERSHAVEADOPTEDTHEPRACTICEOFAPPENDINGTHEIRPUBLICKEYTOMESSAGESTHATTHEYSENDTOPUBLICFORUMS,SUCHASUSENETNEWSGROUPSANDINTERNETMAILINGLISTSALTHOUGHTHISAPPROACHISCONVENIENT,ITHASAMAJORWEAKNESSANYONECANFORGESUCHAPUBLICANNOUNCEMENTTHATIS,SOMEUSERCOULDPRETENDTOBEUSERAANDSENDAPUBLICKEYTOANOTHERPARTICIPANTORBROADCASTSUCHAPUBLICKEYUNTILSUCHTIMEASUSERADISCOVERSTHEFORGERYANDALERTSOTHERPARTICIPANTS,THEFORGERISABLETOREADALLENCRYPTEDMESSAGESINTENDEDFORAANDCANUSETHEFORGEDKEYSFORAUTHENTICATIONSEEFIGURE93PUBLICLYAVAILABLEDIRECTORYAGREATERDEGREEOFSECURITYCANBEACHIEVEDBYMAINTAININGAPUBLICLYAVAILABLEDYNAMICDIRECTORYOFPUBLICKEYSMAINTENANCEANDDISTRIBUTIONOFTHEPUBLICDIRECTORYWOULDHAVETOBETHERESPONSIBILITYOFSOMETRUSTEDENTITYORORGANIZATIONFIGURE102SUCHASCHEMEWOULDINCLUDETHEFOLLOWINGELEMENTS1THEAUTHORITYMAINTAINSADIRECTORYWITHANAME,PUBLICKEYENTRYFOREACHPARTICIPANT2EACHPARTICIPANTREGISTERSAPUBLICKEYWITHTHEDIRECTORYAUTHORITYREGISTRATIONWOULDHAVETOBEINPERSONORBYSOMEFORMOFSECUREAUTHENTICATEDCOMMUNICATION3APARTICIPANTMAYREPLACETHEEXISTINGKEYWITHANEWONEATANYTIME,EITHERBECAUSEOFTHEDESIRETOREPLACEAPUBLICKEYTHATHASALREADYBEENUSEDFORALARGEAMOUNTOFDATA,ORBECAUSETHECORRESPONDINGPRIVATEKEYHASBEENCOMPROMISEDINSOMEWAY4PARTICIPANTSCOULDALSOACCESSTHEDIRECTORYELECTRONICALLYFORTHISPURPOSE,SECURE,AUTHENTICATEDCOMMUNICATIONFROMTHEAUTHORITYTOTHEPARTICIPANTISMANDATORYTHISSCHEMEISCLEARLYMORESECURETHANINDIVIDUALPUBLICANNOUNCEMENTSBUTSTILLHASVULNERABILITIESIFANADVERSARYSUCCEEDSINOBTAININGORCOMPUTINGTHEPRIVATEKEYOFTHEDIRECTORYAUTHORITY,THEADVERSARYCOULDAUTHORITATIVELYPASSOUTCOUNTERFEITPUBLICKEYSANDSUBSEQUENTLYIMPERSONATEANYPARTICIPANTANDEAVESDROPONMESSAGESSENTTOANYPARTICIPANTANOTHERWAYTOACHIEVETHESAMEENDISFORTHEADVERSARYTOTAMPERWITHTHERECORDSKEPTBYTHEAUTHORITYPUBLICKEYAUTHORITYSTRONGERSECURITYFORPUBLICKEYDISTRIBUTIONCANBEACHIEVEDBYPROVIDINGTIGHTERCONTROLOVERTHEDISTRIBUTIONOFPUBLICKEYSFROMTHEDIRECTORYATYPICALSCENARIOISILLUSTRATEDINFIGURE103,WHICHISBASEDONAFIGUREINPOPE79ASBEFORE,THESCENARIOASSUMESTHATACENTRALAUTHORITYMAINTAINSADYNAMICDIRECTORYOFPUBLICKEYSOFALLPARTICIPANTSINADDITION,EACHPARTICIPANTRELIABLYKNOWSAPUBLICKEYFORTHEAUTHORITY,WITHONLYTHEAUTHORITYKNOWINGTHECORRESPONDINGPRIVATEKEYTHEFOLLOWINGSTEPSMATCHEDBYNUMBERTOFIGURE103OCCUR1ASENDSATIMESTAMPEDMESSAGETOTHEPUBLICKEYAUTHORITYCONTAININGAREQUESTFORTHECURRENTPUBLICKEYOFB2THEAUTHORITYRESPONDSWITHAMESSAGETHATISENCRYPTEDUSINGTHEAUTHORITYSPRIVATEKEY,PRAUTHTHUS,AISABLETODECRYPTTHEMESSAGEUSINGTHEAUTHORITYSPUBLICKEYTHEREFORE,AISASSUREDTHATTHEMESSAGEORIGINATEDWITHTHEAUTHORITYTHEMESSAGEINCLUDESTHEFOLLOWINGBSPUBLICKEY,PUBWHICHACANUSETOENCRYPTMESSAGESDESTINEDFORBTHEORIGINALREQUEST,TOENABLEATOMATCHTHISRESPONSEWITHTHECORRESPONDINGEARLIERREQUESTANDTOVERIFYTHATTHEORIGINALREQUESTWASNOTALTEREDBEFORERECEPTIONBYTHEAUTHORITYTHEORIGINALTIMESTAMP,SOACANDETERMINETHATTHISISNOTANOLDMESSAGEFROMTHEAUTHORITYCONTAININGAKEYOTHERTHANBSCURRENTPUBLICKEY3ASTORESBSPUBLICKEYANDALSOUSESITTOENCRYPTAMESSAGETOBCONTAININGANIDENTIFIEROFAIDAANDANONCEN1,WHICHISUSEDTOIDENTIFYTHISTRANSACTIONUNIQUELY4BRETRIEVESASPUBLICKEYFROMTHEAUTHORITYINTHESAMEMANNERASARETRIEVEDBSPUBLICKEYATTHISPOINT,PUBLICKEYSHAVEBEENSECURELYDELIVEREDTOAANDB,ANDTHEYMAYBEGINTHEIRPROTECTEDEXCHANGEHOWEVER,TWOADDITIONALSTEPSAREDESIRABLE5BSENDSAMESSAGETOAENCRYPTEDWITHPUAANDCONTAININGASNONCEN1ASWELLASANEWNONCEGENERATEDBYBN2BECAUSEONLYBCOULDHAVEDECRYPTEDMESSAGE3,THEPRESENCEOFN1INMESSAGE6ASSURESATHATTHECORRESPONDENTISB6ARETURNSN2,ENCRYPTEDUSINGBSPUBLICKEY,TOASSUREBTHATITSCORRESPONDENTISATHUS,ATOTALOFSEVENMESSAGESAREREQUIREDHOWEVER,THEINITIALFOURMESSAGESNEEDBEUSEDONLYINFREQUENTLYBECAUSEBOTHAANDBCANSAVETHEOTHERSPUBLICKEYFORFUTUREUSE,ATECHNIQUEKNOWNASCACHINGPERIODICALLY,AUSERSHOULDREQUESTFRESHCOPIESOFTHEPUBLICKEYSOFITSCORRESPONDENTSTOENSURECURRENCYPUBLICKEYCERTIFICATESTHESCENARIOOFFIGURE103ISATTRACTIVE,YETITHASSOMEDRAWBACKSTHEPUBLICKEYAUTHORITYCOULDBESOMEWHATOFABOTTLENECKINTHESYSTEM,FORAUSERMUSTAPPEALTOTHEAUTHORITYFORAPUBLICKEYFOREVERYOTHERUSERTHATITWISHESTOCONTACTASBEFORE,THEDIRECTORYOFNAMESANDPUBLICKEYSMAINTAINEDBYTHEAUTHORITYISVULNERABLETOTAMPERINGANALTERNATIVEAPPROACH,FIRSTSUGGESTEDBYKOHNFELDERKOHN78,ISTOUSECERTIFICATESTHATCANBEUSEDBYPARTICIPANTSTOEXCHANGEKEYSWITHOUTCONTACTINGAPUBLICKEYAUTHORITY,INAWAYTHATISASRELIABLEASIFTHEKEYSWEREOBTAINEDDIRECTLYFROMAPUBLICKEYAUTHORITYINESSENCE,ACERTIFICATECONSISTSOFAPUBLICKEYPLUSANIDENTIFIEROFTHEKEYOWNER,WITHTHEWHOLEBLOCKSIGNEDBYATRUSTEDTHIRDPARTYTYPICALLY,THETHIRDPARTYISACERTIFICATEAUTHORITY,SUCHASAGOVERNMENTAGENCYORAFINANCIALINSTITUTION,THATISTRUSTEDBYTHEUSERCOMMUNITYAUSERCANPRESENTHISORHERPUBLICKEYTOTHEAUTHORITYINASECUREMANNER,ANDOBTAINACERTIFICATETHEUSERCANTHENPUBLISHTHECERTIFICATEANYONENEEDEDTHISUSERSPUBLICKEYCANOBTAINTHECERTIFICATEANDVERIFYTHATITISVALIDBYWAYOFTHEATTACHEDTRUSTEDSIGNATUREAPARTICIPANTCANALSOCONVEYITSKEYINFORMATIONTOANOTHERBYTRANSMITTINGITSCERTIFICATEOTHERPARTICIPANTSCANVERIFYTHATTHECERTIFICATEWASCREATEDBYTHEAUTHORITYWECANPLACETHEFOLLOWINGREQUIREMENTSONTHISSCHEME1ANYPARTICIPANTCANREADACERTIFICATETODETERMINETHENAMEANDPUBLICKEYOFTHECERTIFICATESOWNER2ANYPARTICIPANTCANVERIFYTHATTHECERTIFICATEORIGINATEDFROMTHECERTIFICATEAUTHORITYANDISNOTCOUNTERFEIT3ONLYTHECERTIFICATEAUTHORITYCANCREATEANDUPDATECERTIFICATESTHESEREQUIREMENTSARESATISFIEDBYTHEORIGINALPROPOSALINKOHN78DENNINGDENN83ADDEDTHEFOLLOWINGADDITIONALREQUIREMENT4ANYPARTICIPANTCANVERIFYTHECURRENCYOFTHECERTIFICATEACERTIFICATESCHEMEISILLUSTRATEDINFIGURE104EACHPARTICIPANTAPPLIESTOTHECERTIFICATEAUTHORITY,SUPPLYINGAPUBLICKEYANDREQUESTINGACERTIFICATEFIGURE104EXCHANGEOFPUBLICKEYCERTIFICATESAPPLICATIONMUSTBEINPERSONORBYSOMEFORMOFSECUREAUTHENTICATEDCOMMUNICATIONFORPARTICIPANTA,THEAUTHORITYPROVIDESACERTIFICATEOFTHEFORMCAEPRAUTH,T|IDA|PUAWHEREPRAUTHISTHEPRIVATEKEYUSEDBYTHEAUTHORITYANDTISATIMESTAMPAMAYTHENPASSTHISCERTIFICATEONTOANYOTHERPARTICIPANT,WHOREADSANDVERIFIESTHECERTIFICATEASFOLLOWSDPUAUTH,CADPUAUTH,EPRAUTH,T|IDA|PUAT|IDA|PUATHERECIPIENTUSESTHEAUTHORITYSPUBLICKEY,PUAUTHTODECRYPTTHECERTIFICATEBECAUSETHECERTIFICATEISREADABLEONLYUSINGTHEAUTHORITYSPUBLICKEY,THISVERIFIESTHATTHECERTIFICATECAMEFROMTHECERTIFICATEAUTHORITYTHEELEMENTSIDAANDPUAPROVIDETHERECIPIENTWITHTHENAMEANDPUBLICKEYOFTHECERTIFICATESHOLDERTHETIMESTAMPTVALIDATESTHECURRENCYOFTHECERTIFICATETHETIMESTAMPCOUNTERSTHEFOLLOWINGSCENARIOASPRIVATEKEYISLEARNEDBYANADVERSARYAGENERATESANEWPRIVATE/PUBLICKEYPAIRANDAPPLIESTOTHECERTIFICATEAUTHORITYFORANEWCERTIFICATEMEANWHILE,THEADVERSARYREPLAYSTHEOLDCERTIFICATETOBIFBTHENENCRYPTSMESSAGESUSINGTHECOMPROMISEDOLDPUBLICKEY,THEADVERSARYCANREADTHOSEMESSAGESINTHISCONTEXT,THECOMPROMISEOFAPRIVATEKEYISCOMPARABLETOTHELOSSOFACREDITCARDTHEOWNERCANCELSTHECREDITCARDNUMBERBUTISATRISKUNTILALLPOSSIBLECOMMUNICANTSAREAWARETHATTHEOLDCREDITCARDISOBSOLETETHUS,THETIMESTAMPSERVESASSOMETHINGLIKEANEXPIRATIONDATEIFACERTIFICATEISSUFFICIENTLYOLD,ITISASSUMEDTOBEEXPIREDONESCHEMEHASBECOMEUNIVERSALLYACCEPTEDFORFORMATTINGPUBLICKEYCERTIFICATESTHEX509STANDARDX509CERTIFICATESAREUSEDINMOSTNETWORKSECURITYAPPLICATIONS,INCLUDINGIPSECURITY,SECURESOCKETSLAYERSSL,SECUREELECTRONICTRANSACTIONSSET,ANDS/MIME,ALLOFWHICHAREDISCUSSEDINPARTTWOX509ISEXAMINEDINDETAILINCHAPTER14DISTRIBUTIONOFSECRETKEYSUSINGPUBLICKEYCRYPTOGRAPHYONCEPUBLICKEYSHAVEBEENDISTRIBUTEDORHAVEBECOMEACCESSIBLE,SECURECOMMUNICATIONTHATTHWARTSEAVESDROPPINGFIGURE92,TAMPERINGFIGURE93,ORBOTHFIGURE94ISPOSSIBLEHOWEVER,FEWUSERSWILLWISHTOMAKEEXCLUSIVEUSEOFPUBLICKEYENCRYPTIONFORCOMMUNICATIONBECAUSEOFTHERELATIVELYSLOWDATARATESTHATCANBEACHIEVEDACCORDINGLY,PUBLICKEYENCRYPTIONPROVIDESFORTHEDISTRIBUTIONOFSECRETKEYSTOBEUSEDFORCONVENTIONALENCRYPTIONSIMPLESECRETKEYDISTRIBUTIONANEXTREMELYSIMPLESCHEMEWASPUTFORWARDBYMERKLEMERK79,ASILLUSTRATEDINFIGURE105IFAWISHESTOCOMMUNICATEWITHB,THEFOLLOWINGPROCEDUREISEMPLOYED1AGENERATESAPUBLIC/PRIVATEKEYPAIRPUA,PRAANDTRANSMITSAMESSAGETOBCONSISTINGOFPUAANDANIDENTIFIEROFA,IDA2BGENERATESASECRETKEY,KS,ANDTRANSMITSITTOA,ENCRYPTEDWITHASPUBLICKEY3ACOMPUTESDPRA,EPUA,KSTORECOVERTHESECRETKEYBECAUSEONLYACANDECRYPTTHEMESSAGE,ONLYAANDBWILLKNOWTHEIDENTITYOFKS4ADISCARDSPUAANDPRAANDBDISCARDSPUAFIGURE105SIMPLEUSEOFPUBLICKEYENCRYPTIONTOESTABLISHASESSIONKEYAANDBCANNOWSECURELYCOMMUNICATEUSINGCONVENTIONALENCRYPTIONANDTHESESSIONKEYKSATTHECOMPLETIONOFTHEEXCHANGE,BOTHAANDBDISCARDKSDESPITEITSSIMPLICITY,THISISANATTRACTIVEPROTOCOLNOKEYSEXISTBEFORETHESTARTOFTHECOMMUNICATIONANDNONEEXISTAFTERTHECOMPLETIONOFCOMMUNICATIONTHUS,THERISKOFCOMPROMISEOFTHEKEYSISMINIMALATTHESAMETIME,THECOMMUNICATIONISSECUREFROMEAVESDROPPINGTHEPROTOCOLDEPICTEDINFIGURE105ISINSECUREAGAINSTANADVERSARYWHOCANINTERCEPTMESSAGESANDTHENEITHERRELAYTHEINTERCEPTEDMESSAGEORSUBSTITUTEANOTHERMESSAGESEEFIGURE14CSUCHANATTACKISKNOWNASAMANINTHEMIDDLEATTACKRIVE84INTHISCASE,IFANADVERSARY,E,HASCONTROLOFTHEINTERVENINGCOMMUNICATIONCHANNEL,THENECANCOMPROMISETHECOMMUNICATIONINTHEFOLLOWINGFASHIONWITHOUTBEINGDETECTED1AGENERATESAPUBLIC/PRIVATEKEYPAIRPUA,PRAANDTRANSMITSAMESSAGEINTENDEDFORBCONSISTINGOFPUAANDANIDENTIFIEROFA,IDA2EINTERCEPTSTHEMESSAGE,CREATESITSOWNPUBLIC/PRIVATEKEYPAIRPUE,PREANDTRANSMITSPUE|IDATOB3BGENERATESASECRETKEY,KS,ANDTRANSMITSEPUE,KS4EINTERCEPTSTHEMESSAGE,ANDLEARNSKSBYCOMPUTINGDPRE,EPUE,KS5ETRANSMITSEPUA,KSTOATHERESULTISTHATBOTHAANDBKNOWKSANDAREUNAWARETHATKSHASALSOBEENREVEALEDTOEAANDBCANNOWEXCHANGEMESSAGESUSINGKSENOLONGERACTIVELYINTERFERESWITHTHECOMMUNICATIONSCHANNELBUTSIMPLYEAVESDROPSKNOWINGKSECANDECRYPTALLMESSAGES,ANDBOTHAANDBAREUNAWAREOFTHEPROBLEMTHUS,THISSIMPLEPROTOCOLISONLYUSEFULINANENVIRONMENTWHERETHEONLYTHREATISEAVESDROPPINGSECRETKEYDISTRIBUTIONWITHCONFIDENTIALITYANDAUTHENTICATIONFIGURE106,BASEDONANAPPROACHSUGGESTEDINNEED78,PROVIDESPROTECTIONAGAINSTBOTHACTIVEANDPASSIVEATTACKSWEBEGINATAPOINTWHENITISASSUMEDTHATAANDBHAVEEXCHANGEDPUBLICKEYSBYONEOFTHESCHEMESDESCRIBEDEARLIERINTHISSECTIONTHENTHEFOLLOWINGSTEPSOCCUR1AUSESBSPUBLICKEYTOENCRYPTAMESSAGETOBCONTAININGANIDENTIFIEROFAIDAANDANONCEN1,WHICHISUSEDTOIDENTIFYTHISTRANSACTIONUNIQUELY2BSENDSAMESSAGETOAENCRYPTEDWITHPUAANDCONTAININGASNONCEN1ASWELLASANEWNONCEGENERATEDBYBN2BECAUSEONLYBCOULDHAVEDECRYPTEDMESSAGE1,THEPRESENCEOFN1INMESSAGE2ASSURESATHATTHECORRESPONDENTISB3ARETURNSN2ENCRYPTEDUSINGBSPUBLICKEY,TOASSUREBTHATITSCORRESPONDENTISA4ASELECTSASECRETKEYKSANDSENDSMEPUB,EPRA,KSTOBENCRYPTIONOFTHISMESSAGEWITHBSPUBLICKEYENSURESTHATONLYBCANREADITENCRYPTIONWITHASPRIVATEKEYENSURESTHATONLYACOULDHAVESENTIT5BCOMPUTESDPUA,DPRB,MTORECOVERTHESECRETKEYFIGURE106PUBLICKEYDISTRIBUTIONOFSECRETKEYSNOTICETHATTHEFIRSTTHREESTEPSOFTHISSCHEMEARETHESAMEASTHELASTTHREESTEPSOFFIGURE103THERESULTISTHATTHISSCHEMEENSURESBOTHCONFIDENTIALITYANDAUTHENTICATIONINTHEEXCHANGEOFASECRETKEYAHYBRIDSCHEMEYETANOTHERWAYTOUSEPUBLICKEYENCRYPTIONTODISTRIBUTESECRETKEYSISAHYBRIDAPPROACHINUSEONIBMMAINFRAMESLE93THISSCHEMERETAINSTHEUSEOFAKEYDISTRIBUTIONCENTERKDCTHATSHARESASECRETMASTERKEYWITHEACHUSERANDDISTRIBUTESSECRETSESSIONKEYSENCRYPTEDWITHTHEMASTERKEYAPUBLICKEYSCHEMEISUSEDTODISTRIBUTETHEMASTERKEYSTHEFOLLOWINGRATIONALEISPROVIDEDFORUSINGTHISTHREELEVELAPPROACHPERFORMANCETHEREAREMANYAPPLICATIONS,ESPECIALLYTRANSACTIONORIENTEDAPPLICATIONS,INWHICHTHESESSIONKEYSCHANGEFREQUENTLYDISTRIBUTIONOFSESSIONKEYSBYPUBLICKEYENCRYPTIONCOULDDEGRADEOVERALLSYSTEMPERFORMANCEBECAUSEOFTHERELATIVELYHIGHCOMPUTATIONALLOADOFPUBLICKEYENCRYPTIONANDDECRYPTIONWITHATHREELEVELHIERARCHY,PUBLICKEYENCRYPTIONISUSEDONLYOCCASIONALLYTOUPDATETHEMASTERKEYBETWEENAUSERANDTHEKDCBACKWARDCOMPATIBILITYTHEHYBRIDSCHEMEISEASILYOVERLAIDONANEXISTINGKDCSCHEME,WITHMINIMALDISRUPTIONORSOFTWARECHANGESTHEADDITIONOFAPUBLICKEYLAYERPROVIDESASECURE,EFFICIENTMEANSOFDISTRIBUTINGMASTERKEYSTHISISANADVANTAGEINACONFIGURATIONINWHICHASINGLEKDCSERVESAWIDELYDISTRIBUTEDSETOFUSERS102DIFFIEHELLMANKEYEXCHANGETHEFIRSTPUBLISHEDPUBLICKEYALGORITHMAPPEAREDINTHESEMINALPAPERBYDIFFIEANDHELLMANTHATDEFINEDPUBLICKEYCRYPTOGRAPHYDIFF76BANDISGENERALLYREFERREDTOASDIFFIEHELLMANKEYEXCHANGE1ANUMBEROFCOMMERCIALPRODUCTSEMPLOYTHISKEYEXCHANGETECHNIQUE1WILLIAMSONOFBRITAINSCESGPUBLISHEDTHEIDENTICALSCHEMEAFEWMONTHSEARLIERINACLASSIFIEDDOCUMENTWILL76ANDCLAIMSTOHAVEDISCOVEREDITSEVERALYEARSPRIORTOTHATSEEELLI99FORADISCUSSIONTHEPURPOSEOFTHEALGORITHMISTOENABLETWOUSERSTOSECURELYEXCHANGEAKEYTHATCANTHENBEUSEDFORSUBSEQUENTENCRYPTIONOFMESSAGESTHEALGORITHMITSELFISLIMITEDTOTHEEXCHANGEOFSECRETVALUESTHEDIFFIEHELLMANALGORITHMDEPENDSFORITSEFFECTIVENESSONTHEDIFFICULTYOFCOMPUTINGDISCRETELOGARITHMSBRIEFLY,WECANDEFINETHEDISCRETELOGARITHMINTHEFOLLOWINGWAYFIRST,WEDEFINEAPRIMITIVEROOTOFAPRIMENUMBERPASONEWHOSEPOWERSMODULOPGENERATEALLTHEINTEGERSFROM1TOP1THATIS,IFAISAPRIMITIVEROOTOFTHEPRIMENUMBERP,THENTHENUMBERSAMODP,A2MODP,AP1MODPAREDISTINCTANDCONSISTOFTHEINTEGERSFROM1THROUGHP1INSOMEPERMUTATIONFORANYINTEGERBANDAPRIMITIVEROOTAOFPRIMENUMBERP,WECANFINDAUNIQUEEXPONENTISUCHTHATBAIMODPWHERE0IP1THEEXPONENTIISREFERREDTOASTHEDISCRETELOGARITHMOFBFORTHEBASEA,MODPWEEXPRESSTHISVALUEASDLOGA,PBSEECHAPTER8FORANEXTENDEDDISCUSSIONOFDISCRETELOGARITHMSTHEALGORITHMFIGURE107SUMMARIZESTHEDIFFIEHELLMANKEYEXCHANGEALGORITHMFORTHISSCHEME,THEREARETWOPUBLICLYKNOWNNUMBERSAPRIMENUMBERQANDANINTEGERTHATISAPRIMITIVEROOTOFQSUPPOSETHEUSERSAANDBWISHTOEXCHANGEAKEYUSERASELECTSARANDOMINTEGERXAQANDCOMPUTESYAAXAMODQSIMILARLY,USERBINDEPENDENTLYSELECTSARANDOMINTEGERXAQANDCOMPUTESYBAXBMODQEACHSIDEKEEPSTHEXVALUEPRIVATEANDMAKESTHEYVALUEAVAILABLEPUBLICLYTOTHEOTHERSIDEUSERACOMPUTESTHEKEYASKYBXAMODQANDUSERBCOMPUTESTHEKEYASKYAXBMODQTHESETWOCALCULATIONSPRODUCEIDENTICALRESULTSKYBXAMODQAXBMODQXAMODQAXBXAMODQBYTHERULESOFMODULARARITHMETICAXBXAMODQAXAXBMODQAXAMODQAXAMODQXBMODQYAXBMODQFIGURE107THEDIFFIEHELLMANKEYEXCHANGEALGORITHMTHERESULTISTHATTHETWOSIDESHAVEEXCHANGEDASECRETVALUEFURTHERMORE,BECAUSEXAANDXBAREPRIVATE,ANADVERSARYONLYHASTHEFOLLOWINGINGREDIENTSTOWORKWITHQ,A,YA,ANDYBTHUS,THEADVERSARYISFORCEDTOTAKEADISCRETELOGARITHMTODETERMINETHEKEYFOREXAMPLE,TODETERMINETHEPRIVATEKEYOFUSERB,ANADVERSARYMUSTCOMPUTEXBDLOGA,QYBTHEADVERSARYCANTHENCALCULATETHEKEYKINTHESAMEMANNERASUSERBCALCULATESITTHESECURITYOFTHEDIFFIEHELLMANKEYEXCHANGELIESINTHEFACTTHAT,WHILEITISRELATIVELYEASYTOCALCULATEEXPONENTIALSMODULOAPRIME,ITISVERYDIFFICULTTOCALCULATEDISCRETELOGARITHMSFORLARGEPRIMES,THELATTERTASKISCONSIDEREDINFEASIBLEHEREISANEXAMPLEKEYEXCHANGEISBASEDONTHEUSEOFTHEPRIMENUMBERQ353ANDAPRIMITIVEROOTOF353,INTHISCASEA3AANDBSELECTSECRETKEYSXA97ANDXB233,RESPECTIVELYEACHCOMPUTESITSPUBLICKEYACOMPUTESYA397MOD35340BCOMPUTESYB3233MOD353248AFTERTHEYEXCHANGEPUBLICKEYS,EACHCANCOMPUTETHECOMMONSECRETKEYACOMPUTESKYBXAMOD35324897MOD353160BCOMPUTESKYAXEMOD35340233MOD353160WEASSUMEANATTACKERWOULDHAVEAVAILABLETHEFOLLOWINGINFORMATIONQ353A3YA40YB248INTHISSIMPLEEXAMPLE,ITWOULDBEPOSSIBLEBYBRUTEFORCETODETERMINETHESECRETKEY160INPARTICULAR,ANATTACKERECANDETERMINETHECOMMONKEYBYDISCOVERINGASOLUTIONTOTHEEQUATION3AMOD35340ORTHEEQUATION3BMOD353248THEBRUTEFORCEAPPROACHISTOCALCULATEPOWERSOF3MODULO353,STOPPINGWHENTHERESULTEQUALSEITHER40OR248THEDESIREDANSWERISREACHEDWITHTHEEXPONENTVALUEOF97,WHICHPROVIDES397MOD35340WITHLARGERNUMBERS,THEPROBLEMBECOMESIMPRACTICALKEYEXCHANGEPROTOCOLSFIGURE108SHOWSASIMPLEPROTOCOLTHATMAKESUSEOFTHEDIFFIEHELLMANCALCULATIONSUPPOSETHATUSERAWISHESTOSETUPACONNECTIONWITHUSERBANDUSEASECRETKEYTOENCRYPTMESSAGESONTHATCONNECTIONUSERACANGENERATEAONETIMEPRIVATEKEYXA,CALCULATEYA,ANDSENDTHATTOUSERBUSERBRESPONDSBYGENERATINGAPRIVATEVALUEXBCALCULATINGYB,ANDSENDINGYBTOUSERABOTHUSERSCANNOWCALCULATETHEKEYTHENECESSARYPUBLICVALUESQANDAWOULDNEEDTOBEKNOWNAHEADOFTIMEALTERNATIVELY,USERACOULDPICKVALUESFORQANDAANDINCLUDETHOSEINTHEFIRSTMESSAGEFIGURE108DIFFIEHELLMANKEYEXCHANGEASANEXAMPLEOFANOTHERUSEOFTHEDIFFIEHELLMANALGORITHM,SUPPOSETHATAGROUPOFUSERSEG,ALLUSERSONALANEACHGENERATEALONGLASTINGPRIVATEVALUEXIFORUSERIANDCALCULATEAPUBLICVALUEYITHESEPUBLICVALUES,TOGETHERWITHGLOBALPUBLICVALUESFORQANDA,ARESTOREDINSOMECENTRALDIRECTORYATANYTIME,USERJCANACCESSUSERISPUBLICVALUE,CALCULATEASECRETKEY,ANDUSETHATTOSENDANENCRYPTEDMESSAGETOUSERAIFTHECENTRALDIRECTORYISTRUSTED,THENTHISFORMOFCOMMUNICATIONPROVIDESBOTHCONFIDENTIALITYANDADEGREEOFAUTHENTICATIONBECAUSEONLYIANDJCANDETERMINETHEKEY,NOOTHERUSERCANREADTHEMESSAGECONFIDENTIALITYRECIPIENTIKNOWSTHATONLYUSERJCOULDHAVECREATEDAMESSAGEUSINGTHISKEYAUTHENTICATIONHOWEVER,THETECHNIQUEDOESNOTPROTECTAGAINSTREPLAYATTACKS103ELLIPTICCURVEARITHMETICMOSTOFTHEPRODUCTSANDSTANDARDSTHATUSEPUBLICKEYCRYPTOGRAPHYFORENCRYPTIONANDDIGITALSIGNATURESUSERSAASWEHAVESEEN,THEKEYLENGTHFORSECURERSAUSEHASINCREASEDOVERRECENTYEARS,ANDTHISHASPUTAHEAVIERPROCESSINGLOADONAPPLICATIONSUSINGRSATHISBURDENHASRAMIFICATIONS,ESPECIALLYFORELECTRONICCOMMERCESITESTHATCONDUCTLARGENUMBERSOFSECURETRANSACTIONSRECENTLY,ACOMPETINGSYSTEMHASBEGUNTOCHALLENGERSAELLIPTICCURVECRYPTOGRAPHYECCALREADY,ECCISSHOWINGUPINSTANDARDIZATIONEFFORTS,INCLUDINGTHEIEEEP1363STANDARDFORPUBLICKEYCRYPTOGRAPHYTHEPRINCIPALATTRACTIONOFECC,COMPAREDTORSA,ISTHATITAPPEARSTOOFFEREQUALSECURITYFORAFARSMALLERKEYSIZE,THEREB