密码学与网络安全【英文】

CryptographyandNetworkSecurity

Chapter9FourthEditionbyWilliamStallings LectureslidesbyLawrieBrown密码学与网络安全【英文】全文共27页，当前为第1页。Chapter9–PublicKeyCryptographyandRSA

EveryEgyptianreceivedtwonames,whichwereknownrespectivelyasthetruenameandthegoodname,orthegreatnameandthelittlename;andwhilethegoodorlittlenamewasmadepublic,thetrueorgreatnameappearstohavebeencarefullyconcealed.—TheGoldenBough,SirJamesGeorgeFrazer密码学与网络安全【英文】全文共27页，当前为第2页。Private-KeyCryptographytraditionalprivate/secret/singlekeycryptographyusesonekeysharedbybothsenderandreceiverifthiskeyisdisclosedcommunicationsarecompromisedalsoissymmetric,partiesareequalhencedoesnotprotectsenderfromreceiverforgingamessage&claimingissentbysender密码学与网络安全【英文】全文共27页，当前为第3页。Public-KeyCryptographyprobablymostsignificantadvanceinthe3000yearhistoryofcryptographyusestwokeys–apublic&aprivatekeyasymmetricsincepartiesarenotequalusescleverapplicationofnumbertheoreticconceptstofunctioncomplementsratherthanreplacesprivatekeycrypto密码学与网络安全【英文】全文共27页，当前为第4页。WhyPublic-KeyCryptography?developedtoaddresstwokeyissues:keydistribution–howtohavesecurecommunicationsingeneralwithouthavingtotrustaKDCwithyourkeydigitalsignatures–howtoverifyamessagecomesintactfromtheclaimedsenderpublicinventionduetoWhitfieldDiffie&MartinHellmanatStanfordUniin1976knownearlierinclassifiedcommunity密码学与网络安全【英文】全文共27页，当前为第5页。Public-KeyCryptographypublic-key/two-key/asymmetriccryptographyinvolvestheuseoftwokeys:apublic-key,whichmaybeknownbyanybody,andcanbeusedtoencryptmessages,andverifysignatures

aprivate-key,knownonlytotherecipient,usedtodecryptmessages,andsign(create)signaturesisasymmetricbecausethosewhoencryptmessagesorverifysignaturescannotdecryptmessagesorcreatesignatures密码学与网络安全【英文】全文共27页，当前为第6页。Public-KeyCryptography密码学与网络安全【英文】全文共27页，当前为第7页。Public-KeyCharacteristicsPublic-Keyalgorithmsrelyontwokeyswhere:itiscomputationallyinfeasibletofinddecryptionkeyknowingonlyalgorithm&encryptionkeyitiscomputationallyeasytoen/decryptmessageswhentherelevant(en/decrypt)keyisknowneitherofthetworelatedkeyscanbeusedforencryption,withtheotherusedfordecryption(forsomealgorithms)密码学与网络安全【英文】全文共27页，当前为第8页。Public-KeyCryptosystems密码学与网络安全【英文】全文共27页，当前为第9页。Public-KeyApplicationscanclassifyusesinto3categories:encryption/decryption(providesecrecy)digitalsignatures(provideauthentication)keyexchange(ofsessionkeys)somealgorithmsaresuitableforalluses,othersarespecifictoone密码学与网络安全【英文】全文共27页，当前为第10页。SecurityofPublicKeySchemeslikeprivatekeyschemesbruteforceexhaustivesearchattackisalwaystheoreticallypossiblebutkeysusedaretoolarge(>512bits)securityreliesonalargeenoughdifferenceindifficultybetweeneasy(en/decrypt)andhard(cryptanalyse)problemsmoregenerallythehardproblemisknown,butismadehardenoughtobeimpracticaltobreakrequirestheuseofverylargenumbershenceisslowcomparedtoprivatekeyschemes

密码学与网络安全【英文】全文共27页，当前为第11页。RSAbyRivest,Shamir&AdlemanofMITin1977bestknown&widelyusedpublic-keyschemebasedonexponentiationinafinite(Galois)fieldoverintegersmoduloaprimenb.exponentiationtakesO((logn)3)operations(easy)useslargeintegers(eg.1024bits)securityduetocostoffactoringlargenumbersnb.factorizationtakesO(elognloglogn)operations(hard)密码学与网络安全【英文】全文共27页，当前为第12页。RSAKeySetupeachusergeneratesapublic/privatekeypairby:selectingtwolargeprimesatrandom-p,q

computingtheirsystemmodulusn=p.qnoteø(n)=(p-1)(q-1)

selectingatrandomtheencryptionkeyewhere1<e<ø(n),gcd(e,ø(n))=1solvefollowingequationtofinddecryptionkeyd

e.d=1modø(n)and0≤d≤n

publishtheirpublicencryptionkey:PU={e,n}keepsecretprivatedecryptionkey:PR={d,n}密码学与网络安全【英文】全文共27页，当前为第13页。RSAUsetoencryptamessageMthesender:obtainspublickeyofrecipientPU={e,n}

computes:C=Memodn,where0≤M<ntodecrypttheciphertextCtheowner:usestheirprivatekeyPR={d,n}

computes:M=Cdmodn

notethatthemessageMmustbesmallerthanthemodulusn(blockifneeded)密码学与网络安全【英文】全文共27页，当前为第14页。WhyRSAWorksbecauseofEuler'sTheorem:aø(n)modn=1wheregcd(a,n)=1inRSAhave:n=p.qø(n)=(p-1)(q-1)

carefullychosee&dtobeinversesmodø(n)

hencee.d=1+k.ø(n)forsomekhence:

Cd=Me.d=M1+k.ø(n)=M1.(Mø(n))k

=M1.(1)k=M1=Mmodn

密码学与网络安全【英文】全文共27页，当前为第15页。RSAExample-KeySetupSelectprimes:p=17&q=11Compute

n=pq=17x11=187Computeø(n)=(p–1)(q-1)=16x10=160Selecte:

gcd(e,160)=1;choosee=7Determined:

de=1mod160andd<160Valueisd=23since23x7=161=10x160+1PublishpublickeyPU={7,187}KeepsecretprivatekeyPR={23,187}密码学与网络安全【英文】全文共27页，当前为第16页。RSAExample-En/DecryptionsampleRSAencryption/decryptionis:givenmessageM=88(nb.88<187)encryption:C=887mod187=11

decryption:M=1123mod187=88

密码学与网络安全【英文】全文共27页，当前为第17页。ExponentiationcanusetheSquareandMultiplyAlgorithmafast,efficientalgorithmforexponentiationconceptisbasedonrepeatedlysquaringbaseandmultiplyingintheonesthatareneededtocomputetheresultlookatbinaryrepresentationofexponentonlytakesO(log2n)multiplesfornumberneg.75=74.71=3.7=10mod11eg.3129=3128.31=5.3=4mod11密码学与网络安全【英文】全文共27页，当前为第18页。Exponentiationc=0;f=1fori=kdownto0doc=2xcf=(fxf)modnifbi==1

thenc=c+1

f=(fxa)modn

returnf

密码学与网络安全【英文】全文共27页，当前为第19页。EfficientEncryptionencryptionusesexponentiationtopowerehenceifesmall,thiswillbefasteroftenchoosee=65537(216-1)alsoseechoicesofe=3ore=17butifetoosmall(ege=3)canattackusingChineseremaindertheorem&3messageswithdifferentmoduliiifefixedmustensuregcd(e,ø(n))=1ierejectanyporqnotrelativelyprimetoe密码学与网络安全【英文】全文共27页，当前为第20页。EfficientDecryptiondecryptionusesexponentiationtopowerdthisislikelylarge,insecureifnotcanusetheChineseRemainderTheorem(CRT)tocomputemodp&qseparately.thencombinetogetdesiredanswerapprox4timesfasterthandoingdirectlyonlyownerofprivatekeywhoknowsvaluesofp&qcanusethistechnique密码学与网络安全【英文】全文共27页，当前为第21页。RSAKeyGenerationusersofRSAmust:determinetwoprimesatrandom-p,q

selecteithereordandcomputetheotherprimesp,q

mustnotbeeasilyderivedfrommodulusn=p.qmeansmustbesufficientlylargetypicallyguessanduseprobabilistictestexponentse,dareinverses,souseInversealgorithmtocomputetheother密码学与网络安全【英文】全文共27页，当前为第22页。RSASecuritypossibleapproachestoattackingRSAare:bruteforcekeysearch(infeasiblegivensizeofnumbers)mathematicalattacks(basedondifficultyofcomputingø(n),byfactoringmodulusn)timingattacks(onrunningofdecryption)chosenciphertextattacks(givenpropertiesofRSA)密码学与网络安全【英文】全文共27页，当前为第23页。FactoringProblemmathematicalapproachtakes3forms:factorn=p.q,hencecomputeø(n)andthenddetermineø(n)directlyandcomputedfindddirectlycurrentlybelieveallequivalenttofactoringhaveseenslowimprovementsovertheyearsasofMay-05bestis200decimaldigits(663)bitwithLSbiggestimprovementcomesfromimprovedalgorithmcfQStoGHFStoLScurrentlyassume1024-2048bitRSAissecureensurep,qofsimilarsizeandmatchingotherconstraints密码学与网络安全【英文】全文共