RSA算法

Securityofe-systemandComputerNetworksRSA算法编码学明文密文方法：密本系统：码本词典密表系统：密码算法密钥（可变）分类：分组密码：DES、RSA序列密码：RC-4内容1.密码算法的设计理论2.公钥密码学3.RSA算法4.RSA算法的攻击5.RSA算法应用一、密码算法的设计理论明文集合：P={p1，p2，…，pn}密文集合：C={c1，c2，…，cm}加密：C=E(p)映射E：PC是一对一的函数即：pipj则f(pi)f(pj)若f(pi)=f(pj)则pi=pjS:PCm(m-1)(m-2)…(m-n+1)映射总个数若m=n则S的秩为m!密钥集合V=(v1,v2,…vr)加密函数集E=(Ev1,Ev2…Evr)加密函数集D=(Dv1,Dv2…Dvr)|V||S|是理想的例DES|P|=|C|=2^64明文、密文64bit|S|=2^64!10^10^20|V|=2^56密钥56bit10^172^64!=256*2^56*(2^64-1)!2^56二、PublicKeyCryptographyEveryEgyptianreceivedtwonames,whichwereknownrespectivelyasthetruenameandthegoodname,orthegreatnameandthelittlename;andwhilethegoodorlittlenamewasmadepublic,thetrueorgreatnameappearstohavebeencarefullyconcealed.—TheGoldenBough,SirJamesGeorgeFrazerPrivate-KeyCryptographytraditionalprivate/secret/singlekeycryptographyusesonekeysharedbybothsenderandreceiverifthiskeyisdisclosedcommunicationsarecompromisedalsoissymmetric,partiesareequalhencedoesnotprotectsenderfromreceiverforgingamessage&claimingissentbysenderPublic-KeyCryptographyprobablymostsignificantadvanceinthe3000yearhistoryofcryptographyusestwokeys–apublic&aprivatekeyasymmetricsincepartiesarenotequalusescleverapplicationofnumbertheoreticconceptstofunctioncomplementsratherthanreplacesprivatekeycryptoPublic-KeyCryptographypublic-key/two-key/asymmetriccryptographyinvolvestheuseoftwokeys:apublic-key,whichmaybeknownbyanybody,andcanbeusedtoencryptmessages,andverifysignaturesaprivate-key,knownonlytotherecipient,usedtodecryptmessages,andsign(create)signaturesisasymmetricbecausethosewhoencryptmessagesorverifysignaturescannotdecryptmessagesorcreatesignaturesPublic-KeyCryptography公钥密码学产生的背景要求单向陷门函数密码分析应用1WhyPublic-KeyCryptography?developedtoaddresstwokeyissues:keydistribution–howtohavesecurecommunicationsingeneralwithouthavingtotrustaKDCwithyourkeydigitalsignatures–howtoverifyamessagecomesintactfromtheclaimedsenderpublicinventionduetoWhitfieldDiffie&MartinHellmanatStanfordUniin1976knownearlierinclassifiedcommunityPublic-KeyCharacteristicsPublic-Keyalgorithmsrelyontwokeyswiththecharacteristicsthatitis:computationallyinfeasibletofinddecryptionkeyknowingonlyalgorithm&encryptionkeycomputationallyeasytoen/decryptmessageswhentherelevant(en/decrypt)keyisknowneitherofthetworelatedkeyscanbeusedforencryption,withtheotherusedfordecryption(insomeschemes)2.要求：Diffie-Hellman提出1）参与方容易产生出一对密钥2）已知PK和明文M，容易计算出密文3）接收方使用SK和C容易恢复出明文4）敌方即使知道PK和C恢复出明文不可能5）敌方即使知道PK要确定SK不可行6）加、解密操作的次序可以互换3.单向陷门函数Y=f(x)4.SecurityofPublicKeychemeslikeprivatekeyschemesbruteforceexhaustivesearchattackisalwaystheoreticallypossiblebutkeysusedaretoolarge(512bits)securityreliesonalargeenoughdifferenceindifficultybetweeneasy(en/decrypt)andhard(cryptanalyse)problemsmoregenerallythehardproblemisknown,itsjustmadetoohardtodoinpractiserequirestheuseofverylargenumbershenceisslowcomparedtoprivatekeyschemes穷举数学分析可能报文攻击（特有）：穷举明文5.Public-KeyCryptosystemsPublic-KeyApplicationscanclassifyusesinto3categories:encryption/decryption(providesecrecy)digitalsignatures(provideauthentication)keyexchange(ofsessionkeys)somealgorithmsaresuitableforalluses,othersarespecifictoone三、RSAbyRivest,Shamir&AdlemanofMITin1977bestknown&widelyusedpublic-keyschemebasedonexponentiationinafinite(Galois)fieldoverintegersmoduloaprimenb.exponentiationtakesO((logn)3)operations(easy)useslargeintegers(eg.1024bits)securityduetocostoffactoringlargenumbersnb.factorizationtakesO(elognloglogn)operations(hard)RSAKeySetupeachusergeneratesapublic/privatekeypairby:selectingtwolargeprimesatrandom-p,qcomputingtheirsystemmodulusN=p.qnoteø(N)=(p-1)(q-1)selectingatrandomtheencryptionkeyewhere1eø(N),gcd(e,ø(N))=1solvefollowingequationtofinddecryptionkeyde.d=1modø(N)and0≤d≤Npublishtheirpublicencryptionkey:KU={e,N}keepsecretprivatedecryptionkey:KR={d,p,q}RSAUsetoencryptamessageMthesender:obtainspublickeyofrecipientKU={e,N}computes:C=MemodN,where0≤MNtodecrypttheciphertextCtheowner:usestheirprivatekeyKR={d,p,q}computes:M=CdmodNnotethatthemessageMmustbesmallerthanthemodulusN(blockifneeded)WhyRSAWorksbecauseofEuler'sTheorem:aø(n)modN=1wheregcd(a,N)=1inRSAhave:N=p.qø(N)=(p-1)(q-1)carefullychosene&dtobeinversesmodø(N)hencee.d=1+k.ø(N)forsomekhence:Cd=(Me)d=M1+k.ø(N)=M1.(Mø(N))q=M1.(1)q=M1=MmodNRSAExample1.Selectprimes:p=17&q=112.Computen=pq=17×11=1873.Computeø(n)=(p–1)(q-1)=16×10=1604.Selecte:gcd(e,160)=1;choosee=75.Determined:de=1mod160andd160Valueisd=23since23×7=161=10×160+16.PublishpublickeyKU={7,187}7.KeepsecretprivatekeyKR={23,17,11}RSAExamplecontsampleRSAencryption/decryptionis:givenmessageM=88(nb.88187)encryption:C=887mod187=11decryption:M=1123mod187=88ExponentiationcanusetheSquareandMultiplyAlgorithmafast,efficientalgorithmforexponentiationconceptisbasedonrepeatedlysquaringbaseandmultiplyingintheonesthatareneededtocomputetheresultlookatbinaryrepresentationofexponentonlytakesO(log2n)multiplesfornumberneg.75=74.71=3.7=10mod11eg.3129=3128.31=5.3=4mod11Exponentiation加密举例：空白=00A＝01，B＝02，…，Z＝26报文R