信息安全指南課件：Chapter 9 Public Key Cryptography and RSA

ComputerScience&TechnologySchoolofShandongUniversityInstructor:HouMengbo

Email:houmbATOffice:InformationSecurityResearchGroupGuidetoInformationSecurityChapter9–PublicKeyCryptographyandRSAPrivate-KeyCryptographytraditionalprivate/secret/singlekeycryptographyusesonekeysharedbybothsenderandreceiverifthiskeyisdisclosedcommunicationsarecompromisedalsoissymmetric,partiesareequalhencedoesnotprotectsenderfromreceiverforgingamessage&claimingissentbysenderBasedonsubstitutionandpermutationPublic-KeyCryptographyprobablymostsignificantadvanceinthe3000yearhistoryofcryptographyusestwokeys–apublic&aprivatekeyasymmetricsincepartiesarenotequalusescleverapplicationofnumbertheoreticconceptstofunctioncomplementsratherthanreplacesprivatekeycryptoBasedonhardproblemsinmathematicsAretheseopinionsright?Publickeycryptoissaferthanprivatekeycrypto(X)Publickeycryptowillreplaceprivatekeycrypto(X)Keydistributionofprivatekeycryptoismorecomplicatedthanthatofpublickey(X)Public-KeyCryptographypublic-key/two-key/asymmetriccryptographyinvolvestheuseoftwokeys:apublic-key,whichmaybeknownbyanybody,andcanbeusedtoencryptmessages,andverifysignatures

aprivate-key,knownonlytotherecipient,usedtodecryptmessages,andsign(create)signaturesisasymmetricbecausethosewhoencryptmessagesorverifysignaturescannotdecryptmessagesorcreatesignaturesWhyPublic-KeyCryptography?developedtoaddresstwokeyissues:keydistribution–howtohavesecurecommunicationsingeneralwithouthavingtotrustaKDCwithyourkeydigitalsignatures–howtoverifyamessagecomesintactfromtheclaimedsenderpublicinventionduetoWhitfieldDiffie&MartinHellmanatStanfordUniin1976knownearlierinclassifiedcommunityPublic-KeyCharacteristicsPublic-Keyalgorithmsrelyontwokeyswiththecharacteristicsthatitis:computationallyinfeasibletofinddecryptionkeyknowingonlyalgorithm&encryptionkeycomputationallyeasytoen/decryptmessageswhentherelevant(en/decrypt)keyisknowneitherofthetworelatedkeyscanbeusedforencryption,withtheotherusedfordecryption(insomeschemes)Public-KeyCrypto:EncryptionPublic-KeyCrypto:AuthenticationPublickeycrypto

vsprivatekeycryptoPublic-KeyCryptosystem:SecrecyPublic-KeyCryptosys:AuthenticationPublic-KeyCryptosystems:Secrecy&AuthenticationPublic-KeyApplicationscanclassifyusesinto3categories:encryption/decryption(providesecrecy)digitalsignatures(provideauthentication)keyexchange(ofsessionkeys)somealgorithmsaresuitableforalluses,othersarespecifictooneExamplesRequestsforpublickeycryptographyPublicKeypairsgenerationiseasy.Encryptioniscomputationallyeasy(knowplaintextMandKU).Decryptioniscomputationallyeasy(knowciphertextCandKR).computationallyinfeasibletofindKRfromKR.computationallyinfeasibletofindplaintextfromKUandciphertext.SequenceofencryptionanddecryptioniscommutativeTheinbeingofpublickeycryptoOne-wayfunctiony=f(x)easy,whilex=f-1(y)difficult.One-waytrapdoorfunctionknowkandx,y=fk(x)easyknowkandy,x=fk-1(y)easyknowy,butnotk,x=fk-1(y)difficultOne-waytrapdoorfunctionisthekeytodesignpublickeycryptography.SecurityofPublicKeySchemeslikeprivatekeyschemesbruteforceexhaustivesearchattackisalwaystheoreticallypossiblebutkeysusedaretoolarge(>512bits)securityreliesonalargeenoughdifferenceindifficultybetweeneasy(en/decrypt)andhard(cryptanalyse)problemsmoregenerallythehardproblemisknown,itsjustmadetoohardtodoinpractiserequirestheuseofverylargenumbershenceisslowcomparedtoprivatekeyschemes

RSAbyRivest,Shamir&AdlemanofMITin1977bestknown&widelyusedpublic-keyschemebasedonexponentiationinafinite(Galois)fieldoverintegersmoduloaprimeuseslargeintegers(eg.1024bits)securityduetocostoffactoringlargenumbersnb.factorizationtakesO(elognloglogn)operations(hard)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:KU={e,N}keepsecretprivatedecryptionkey:KR={d,N}RSAUsetoencryptamessageMthesender:obtainspublickeyofrecipientKU={e,N}

computes:C=MemodN,where0≤M<NtodecrypttheciphertextCtheowner:usestheirprivatekeyKR={d,N}

computes:M=CdmodN

notethatthemessageMmustbesmallerthanthemodulusN(blockifneeded)WhyRSAWorksbecauseofEuler'sTheorem:a?(n)=1modNwheregcd(a,N)=1inRSAhave:N=p.q?(N)=(p-1)(q-1)

carefullychosene&dtobeinversesmod?(N)

hencee.d=1+k.?(N)forsomekhence:

Cd=(Me)d=M1+k.?(N)=M1.(M?(N))k=M1.(1)k=M1=MmodN=MRSAExampleSelectprimes:p=17&q=11Compute

n=pq=17×11=187Compute?(n)=(p–1)(q-1)=16×10=160Selecte:gcd(e,160)=1;choosee=7Determined:de=1mod160andd<160Valueisd=23since23×7=161=10×160+1PublishpublickeyKU={7,187}KeepsecretprivatekeyKR={23,17,11}RSAExamplecontsampleRSAencryption/decryptionis:givenmessageM=88(nb.88<187)encryption:C=887mod187=11

decryption:M=1123mod187=88

ExponentiationcanusetheSquareandMultiplyAlgorithmafast,efficientalgorithmforexponentiationconceptisbasedonrepeatedlysquaringbaseandmultiplyingintheonesthatareneededtocomputetheresultlookatbinaryrepresentationofexponentonlytakesO(log2n)multiplesfornumberneg.75=74.71=3.7=10mod11eg.3129=3128.31=5.3=4mod11ExponentiationAlgorithmRSAKeyGenerationusersofRSAmust:determinetwoprimesatrandom-p,q

selecteithereordandcomputetheotherprimesp,q

mustnotbeeasilyderivedfrommodulusN=p.qmeansmustbesufficientlylargetypicallyguessanduseprobabilistictestexponentse,dareinverses,souseInversealgorithmtocomputetheotherHowtochooseprimenumber1.Chooserandomoddnumberp.2.

Chooserandomintegera,a<p3.

ExecuteMiller-RabinAlgorithmfortest,ifpnopass,thengobackstep1.4.Ifexecutemanytimes(formanya),ppassthetest,thenacceptp,elserejectp,andgobacktostep1.ConsiderationsThereisoneNisprimenumberforevery(ln(N)).Excepttheevennumberandthenumberthatcandevide5,soweshouldtestfor0.4*ln(n)numbersatmost.suchas:forprimenumberasbigas2200,,wetry60times.For(e,(n))=1,tochooseeisnotverydifficut,becausetheprobabilityofrelativelyprimefor2randomnumbersisnearly0.6RSASecuritythreeapproachestoattackingRSA:bruteforcekeysearch(infeasiblegivensizeofnumbers)mathematicalattacks(basedondifficultyofcomputing?(N),byfactoringmodulusN)timingattacks(onrunningofdecryption)FactoringProblemmathematicalapproachtakes3forms:factorN=p.q,hencefind?(N)andthenddetermine?(N)direct