密碼學(xué)與網(wǎng)絡(luò)安全【英文】

CryptographyandNetworkSecurity

Chapter9FourthEditionbyWilliamStallings LectureslidesbyLawrieBrown密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第1頁。Chapter9–PublicKeyCryptographyandRSA

EveryEgyptianreceivedtwonames,whichwereknownrespectivelyasthetruenameandthegoodname,orthegreatnameandthelittlename;andwhilethegoodorlittlenamewasmadepublic,thetrueorgreatnameappearstohavebeencarefullyconcealed.—TheGoldenBough,SirJamesGeorgeFrazer密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第2頁。Private-KeyCryptographytraditionalprivate/secret/singlekeycryptographyusesonekeysharedbybothsenderandreceiverifthiskeyisdisclosedcommunicationsarecompromisedalsoissymmetric,partiesareequalhencedoesnotprotectsenderfromreceiverforgingamessage&claimingissentbysender密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第3頁。Public-KeyCryptographyprobablymostsignificantadvanceinthe3000yearhistoryofcryptographyusestwokeys–apublic&aprivatekeyasymmetricsincepartiesarenotequalusescleverapplicationofnumbertheoreticconceptstofunctioncomplementsratherthanreplacesprivatekeycrypto密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第4頁。WhyPublic-KeyCryptography?developedtoaddresstwokeyissues:keydistribution–howtohavesecurecommunicationsingeneralwithouthavingtotrustaKDCwithyourkeydigitalsignatures–howtoverifyamessagecomesintactfromtheclaimedsenderpublicinventionduetoWhitfieldDiffie&MartinHellmanatStanfordUniin1976knownearlierinclassifiedcommunity密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第5頁。Public-KeyCryptographypublic-key/two-key/asymmetriccryptographyinvolvestheuseoftwokeys:apublic-key,whichmaybeknownbyanybody,andcanbeusedtoencryptmessages,andverifysignatures

aprivate-key,knownonlytotherecipient,usedtodecryptmessages,andsign(create)signaturesisasymmetricbecausethosewhoencryptmessagesorverifysignaturescannotdecryptmessagesorcreatesignatures密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第6頁。Public-KeyCryptography密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第7頁。Public-KeyCharacteristicsPublic-Keyalgorithmsrelyontwokeyswhere:itiscomputationallyinfeasibletofinddecryptionkeyknowingonlyalgorithm&encryptionkeyitiscomputationallyeasytoen/decryptmessageswhentherelevant(en/decrypt)keyisknowneitherofthetworelatedkeyscanbeusedforencryption,withtheotherusedfordecryption(forsomealgorithms)密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第8頁。Public-KeyCryptosystems密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第9頁。Public-KeyApplicationscanclassifyusesinto3categories:encryption/decryption(providesecrecy)digitalsignatures(provideauthentication)keyexchange(ofsessionkeys)somealgorithmsaresuitableforalluses,othersarespecifictoone密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第10頁。SecurityofPublicKeySchemeslikeprivatekeyschemesbruteforceexhaustivesearchattackisalwaystheoreticallypossiblebutkeysusedaretoolarge(>512bits)securityreliesonalargeenoughdifferenceindifficultybetweeneasy(en/decrypt)andhard(cryptanalyse)problemsmoregenerallythehardproblemisknown,butismadehardenoughtobeimpracticaltobreakrequirestheuseofverylargenumbershenceisslowcomparedtoprivatekeyschemes

密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第11頁。RSAbyRivest,Shamir&AdlemanofMITin1977bestknown&widelyusedpublic-keyschemebasedonexponentiationinafinite(Galois)fieldoverintegersmoduloaprimenb.exponentiationtakesO((logn)3)operations(easy)useslargeintegers(eg.1024bits)securityduetocostoffactoringlargenumbersnb.factorizationtakesO(elognloglogn)operations(hard)密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第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}密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第13頁。RSAUsetoencryptamessageMthesender:obtainspublickeyofrecipientPU={e,n}

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

computes:M=Cdmodn

notethatthemessageMmustbesmallerthanthemodulusn(blockifneeded)密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第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

密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第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}密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第16頁。RSAExample-En/DecryptionsampleRSAencryption/decryptionis:givenmessageM=88(nb.88<187)encryption:C=887mod187=11

decryption:M=1123mod187=88

密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第17頁。ExponentiationcanusetheSquareandMultiplyAlgorithmafast,efficientalgorithmforexponentiationconceptisbasedonrepeatedlysquaringbaseandmultiplyingintheonesthatareneededtocomputetheresultlookatbinaryrepresentationofexponentonlytakesO(log2n)multiplesfornumberneg.75=74.71=3.7=10mod11eg.3129=3128.31=5.3=4mod11密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第18頁。Exponentiationc=0;f=1fori=kdownto0doc=2xcf=(fxf)modnifbi==1

thenc=c+1

f=(fxa)modn

returnf

密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第19頁。EfficientEncryptionencryptionusesexponentiationtopowerehenceifesmall,thiswillbefasteroftenchoosee=65537(216-1)alsoseechoicesofe=3ore=17butifetoosmall(ege=3)canattackusingChineseremaindertheorem&3messageswithdifferentmoduliiifefixedmustensuregcd(e,?(n))=1ierejectanyporqnotrelativelyprimetoe密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第20頁。EfficientDecryptiondecryptionusesexponentiationtopowerdthisislikelylarge,insecureifnotcanusetheChineseRemainderTheorem(CRT)tocomputemodp&qseparately.thencombinetogetdesiredanswerapprox4timesfasterthandoingdirectlyonlyownerofprivatekeywhoknowsvaluesofp&qcanusethistechnique密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第21頁。RSAKeyGenerationusersofRSAmust:determinetwoprimesatrandom-p,q

selecteithereordandcomputetheotherprimesp,q

mustnotbeeasilyderivedfrommodulusn=p.qmeansmustbesufficientlylargetypicallyguessanduseprobabilistictestexponentse,dareinverses,souseInversealgorithmtocomputetheother密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第22頁。RSASecuritypossibleapproachestoattackingRSAare:bruteforcekeysearch(infeasiblegivensizeofnumbers)mathematicalattacks(basedondifficultyofcomputing?(n),byfactoringmodulusn)timingattacks(onrunningofdecryption)chosenciphertextattacks(givenpropertiesofRSA)密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共27頁，當(dāng)前為第23頁。FactoringProblemmathematicalapproachtakes3forms:factorn=p.q,hencecompute?(n)andthenddetermine?(n)directlyandcomputedfindddirectlycurrentlybelieveallequivalenttofactoringhaveseenslowimprovementsovertheyearsasofMay-05bestis200decimaldigits(663)bitwithLSbiggestimprovementcomesfromimprovedalgorithmcfQStoGHFStoLScurrentlyassume1024-2048bitRSAissecureensurep,qofsimilarsizeandmatchingotherconstraints密碼學(xué)與網(wǎng)絡(luò)安全【英文】全文共