公開金鑰密碼系統(tǒng)(Public-KeyCryptosystems)?TheMcGraw-HillCompanies,Inc.,20051目錄?TheMcGraw-HillCompanies,Inc.,20057.1公開金鑰基本概念7.2RSA公開金鑰密碼機(jī)制7.3ElGamal的公開金鑰密碼系統(tǒng)7.4橢圓曲線密碼系統(tǒng)7.5混合式的加密機(jī)制7.6密碼系統(tǒng)的評(píng)估27.1公開金鑰基本概念

?TheMcGraw-HillCompanies,Inc.,2005對(duì)稱式密碼系統(tǒng)有金鑰的管理問題，例如要與N個(gè)人做秘密通訊，那麼就必須握有N把秘密金鑰為了改善對(duì)稱式密碼系統(tǒng)問題，於是便有公開金鑰密碼系統(tǒng)(Public-KeyCryptosystems)的產(chǎn)生3Secret-KeyCryptosystem祕(mì)密金鑰密碼系統(tǒng)(Secret-KeyCryptosystems)又稱單金鑰密碼系統(tǒng)(One-KeyCryptosystems)也稱對(duì)稱密碼系統(tǒng)(SymmetricCryptosystems)優(yōu)點(diǎn)：加解密速度快缺點(diǎn)：有金鑰管理的問題每位使用者需儲(chǔ)存n-1把Keys

U1U2U5U3U4?TheMcGraw-HillCompanies,Inc.,200547.1.1公開金鑰密碼系統(tǒng)的基本概念CA明文加密解密明文密文密文明文解密加密明文密文密文張三’s私有金鑰李四’s私有金鑰張三李四李四’s公開金鑰張三’s公開金鑰SendSend金鑰?TheMcGraw-HillCompanies,Inc.,20055Public-KeyCryptosystem公開金鑰密碼系統(tǒng)(Public-KeyCryptosystems)又稱雙金鑰密碼系統(tǒng)(Two-KeyCryptosystems)也稱非對(duì)稱密碼系統(tǒng)(AsymmetricCryptosystems)優(yōu)點(diǎn)：沒有金鑰管理的問題高安全性有數(shù)位簽章功能缺點(diǎn)：加解密速度慢

著名之公開密碼系統(tǒng)：RSA密碼系統(tǒng)ElGamal密碼系統(tǒng)?TheMcGraw-HillCompanies,Inc.,20056非對(duì)稱式密碼系統(tǒng)的一種。1978年美國麻省理工學(xué)院三位教授Rivest、Shamir、Adleman(RSA)所發(fā)展出來的。利用公開金鑰密碼系統(tǒng)作為資料加密的方式，可達(dá)到資料加密及數(shù)位簽署的功能。Encryption:RSA加密演算法，明文加密使用區(qū)塊為每次加密的範(fàn)圍，使用對(duì)方公開金鑰(PublicKey)將明文加密。Decryption:RSA解密演算法，必須使用自己的私有金鑰(PrivateKey)才能將密文解出。?TheMcGraw-HillCompanies,Inc.,20057.2RSA公開金鑰密碼機(jī)制71.張三選2個(gè)大質(zhì)數(shù)

p和q

(至少100位數(shù))，令N=p?q2.再計(jì)算?(N)=(p-1)(q-1)，並選1個(gè)與?(N)互質(zhì)數(shù)e

?(N)為Euler‘sTotient函數(shù)，其意為與N互質(zhì)之個(gè)數(shù)3.(e,N)即為張三的公開金鑰

加密法為C=MemodN4.張三選1個(gè)數(shù)

d，滿足e?dmod?(N)=15.d

即為張三的解密金鑰(亦稱私有金鑰或祕(mì)密金鑰)

解密法為M=CdmodNRSA之安全性取決於質(zhì)因數(shù)分解之困難度要將很大的N因數(shù)分解成P跟Q之相乘，是很困難的7.2.1RSA的加解密機(jī)制?TheMcGraw-HillCompanies,Inc.,20058RSA演算法-例子1.張三選p=3，q=11;此時(shí)N=p?q=3x11=332.張三選出1個(gè)與(p-1)x(q-1)=(3-1)(11-1) =2x10=20 互質(zhì)數(shù)e=33. (e,N)=(3,33)即為張三的公開金鑰4.張三選1個(gè)數(shù)d=7當(dāng)作解密金鑰， 滿足e?d1mod20(7x31mod20)

令明文

M=19

加密

:C=MemodN=193mod33=28

解密

:M=CdmodN=287mod33=19?TheMcGraw-HillCompanies,Inc.,20059Fermat’sLittleTheoremIfpisaprime,andaisnotamultipleofp,thenFermat’slittletheoremsaysap-1modp=1

Ex.26mod7=1

?TheMcGraw-HillCompanies,Inc.,2005費(fèi)瑪(Fermat)定理:若p為質(zhì)數(shù)且(a,p)互質(zhì)，則ap-1modp=110Euler’sTheoremIfgcd(a,n)=1,then

where()calledEulerphifunction.?TheMcGraw-HillCompanies,Inc.,2005Euler通用定理:若a，n互質(zhì)，則a?(n)modn=1定理:?(P)=P-1若P為質(zhì)數(shù)?(N)=?(PQ)=?(P)?(Q)=(P-1)(Q-1)Itisthenumberofpositiveintegerslessthannthatarerelativelyprimeton.

Ifnisaprime,(n)=n-1.Ifn=pq,wherepandqareprime,then(n)=(p-1)(q-1)11ModularInverseProblemTheproblemisfindinganxsuchthat1=(a*x)modn

Thisisalsowrittenasa-1modn=xNote:a-1modn=xhasauniquesolutionifaandnarerelativelyprime.Ifaandnarenotrelativelyprime,thena-1modn=xhasnosolution.Ex.Theinverseof5,modulo14,is3.2hasnoinversemodulo14.

?TheMcGraw-HillCompanies,Inc.,200512HowtoFindMultiplicativeInverseMethod1:UsingEuler’sTheorem

x=a-1modnaxmodn=1

x=a(n)-1modn

Ifgcd(a,n)=1,thena(n)modn=1

Ex.Whatistheinverseof5,modulo7??56-1mod7=55mod7=3Note:(n)isnotalwaysknown

?TheMcGraw-HillCompanies,Inc.,200513HowtoFindMultiplicativeInverseMethod2:UsingExtendedEuclideanAlgorithmEuclideanAlgorithmFindgcd(a,n)Letr0=n,r1=a,wegetr0=r1g1+r2,r1=r2g2+r3,...,rj-2=rj-1gj-1+rj,...,rm-4=rm-3gm-3+rm-2,rm-3=rm-2gm-2+rm-1,rm-2=rm-1gm-1+rm,rm-1=rmgm

?TheMcGraw-HillCompanies,Inc.,200514Wecanfindgcd(a,n)=sa+tn,wheresandtareintegers.

Ifgcd(a,n)=1,wegetsa+tn=1.Wecanfindsandtbyusing

rm=gcd(a,n)=rm-2-rm-1gm-1becauserm-1=rm-3–rm-2gm-2sogcd(a,n)=rm-2-(rm-3–rm-2gm-2)gm-1=(1+gm-1gm-2)rm-2–gm-1rm-3andsoon.sa+tn=1sa+tnmodn=1samodn=1s=a-1modn?TheMcGraw-HillCompanies,Inc.,200515WhyRSAisCorrectC=E(M)=MemodnM=D(C)=CdmodnCd=(Me)d=Medmodnsinceed=1mod(p-1)(q-1)soMed=Ma(p-1)(q-1)+1=MMa(p-1)(q-1)=MMa(n)

modnAccordingtoEuler’sTheorem,wegetM*1=M?TheMcGraw-HillCompanies,Inc.,200516因式分解的問題FactoringProblemFactoringanumbermeansfindingitsprimenumberEx:10=2*5;60=2*2*3*5However,itisdifficulttofactoralargenumber.Trytofactorthelargenumber:3337

RSA的安全性便是植基於解因式分解的難題上?TheMcGraw-HillCompanies,Inc.,200517RSA演算法指數(shù)運(yùn)算：計(jì)算x=ABmodN?a1:=A;b1:=B;x:=1;whileb1

0dobeginwhileb1mod2=0dobegin

b1:=b1div2;a1:=(a1*a1)modN;end

b1:=b1-1;x:=(x*a1)modN

end

計(jì)算x=A17modN

=A10001modN=A?(((A2)2)2)2

計(jì)算x=A13modN

=A1101modN=A?((A2)2)?((A2)2)2

計(jì)算x=A7modN

=A111modN=A?(A2)?(A2)2

?TheMcGraw-HillCompanies,Inc.,200518Public-KeyCryptosystems之特性1.D(d,E(e,M))=M，可還原性2.d和e很容易求得3.若公開(e,n)，別人很難從(e,n)求得d，即只有自己知道如何解密(以e加密)4.E(e,D(d,M))=MPublic-keyCryptosystems一定要能忍受Chosen-PlaintextAttack?TheMcGraw-HillCompanies,Inc.,200519Public-KeyCryptosystems之特性(續(xù))?滿足1~3項(xiàng)稱之為trap-doorone-wayfunction?“one-way”因易加密而不易解密?“trap-door”若知一些特別資訊即可解密?滿足1~4項(xiàng)稱之為trap-doorone-waypermutation?1~3項(xiàng)為public-keycryptosystems之要求?若同時(shí)滿足第4項(xiàng)要求，則該保密法可用來製作數(shù)位簽章。?TheMcGraw-HillCompanies,Inc.,200520DigitalSignature

數(shù)位簽章一般數(shù)位簽章具有下列功能：確認(rèn)性(Authentication)：可確認(rèn)文件來源的合法性，而非經(jīng)他人偽造。完整性(Integrity)：可確保文件內(nèi)容不會(huì)被新增或刪除。不可否認(rèn)性(Non-repudiation)：簽章者事後無法否認(rèn)曾簽署過此文件。?TheMcGraw-HillCompanies,Inc.,200521?TheMcGraw-HillCompanies,Inc.,2005數(shù)位簽章的基本概念227.2.2RSA數(shù)位簽章S=Md張modN張

M=?Se張modN張張三使用自己的祕(mì)密金鑰對(duì)文件M做數(shù)位簽章S張三李四李四使用張三的公開金鑰確認(rèn)數(shù)位簽章及文件傳送M及S一般使用時(shí)會(huì)先將文件M作HASH函數(shù)處理，使得HASH(M)比N小?TheMcGraw-HillCompanies,Inc.,200523數(shù)位簽章法(DigitalSignature:)MHE||MHD比較是否相等SKaPKaESKa[H(M)]為M之簽章DPKa[ESKa[H(M)]]=H(M)512位元?TheMcGraw-HillCompanies,Inc.,200524RSA數(shù)位簽章+加密C=(Md張modN張)e李modN李M=(Cd李modN李)e張modN張

張三對(duì)文件M做數(shù)位簽章後用李四的公用金鑰將簽章加密張三李四李四使用私有金鑰解開密文C再用張三的公開金鑰確認(rèn)數(shù)位簽章傳送密文C?TheMcGraw-HillCompanies,Inc.,200525非對(duì)稱式密碼系統(tǒng)的一種。1985年由ElGamal所發(fā)展出來的。安全性導(dǎo)因於離散對(duì)數(shù)(DiscreteLogarithm)之困難度。相同明文可得到不相同的密文。RSA密碼系統(tǒng)則是相同明文得到相同密文。ElGamal有訊息擴(kuò)充的問題，RSA機(jī)制則沒有此問題7.3ElGamal的公開金鑰密碼系統(tǒng)離散對(duì)數(shù)(DiscreteLogarithm)的問題：若p為很大之質(zhì)數(shù)；g為p之原根(primitiveroot)y=gxmodp雖已知y,g,p，但要導(dǎo)出x值是很困難的?TheMcGraw-HillCompanies,Inc.,200526什麼是原根？？原根generators:ifpisaprime,andgislessthanp,thengisageneratormodpifforeachbfrom1top-1,thereexistssomeawherega

b(modp).

galsocalledprimitiverootofmodp21mod11=222mod11=423mod11=824mod11=525mod11=1026mod11=927mod11=728mod11=329mod11=6210mod11=12isageneratormodulo113isnotageneratormodulo11becausethereisnosolutionon3amod11=2?TheMcGraw-HillCompanies,Inc.,200527解離散對(duì)數(shù)的問題Thisisahardproblem:Findxwhereaxmodn=bEx.If3xmod17=15,thenx=6

Note:Notalldiscretelogarithmshavesolution.Ex.3xmod13=7,nosolution!!?TheMcGraw-HillCompanies,Inc.,200528張三將明文M以李四之公開金鑰加密：1.張三選一個(gè)亂數(shù)r2.計(jì)算b=grModPc=M?yrmodP3.張三送(b,c)給李四7.3.1ElGamal的加解密機(jī)制李四之金鑰產(chǎn)生：y=gxmodPy為李四之公開金鑰x為李四之秘密金鑰P為很大之質(zhì)數(shù)g為與P互質(zhì)之原根4.李四收到(b,c)後計(jì)算c?(bx)-1modP=M?TheMcGraw-HillCompanies,Inc.,200529李四將明文M以李四之祕(mì)密金鑰製作簽章：1.李四選一個(gè)亂數(shù)k使得gcd(k,p-1)=12.計(jì)算r=gkmodp3.李四計(jì)算s使得M=(xr+ks)mod(p-1)4.李四送(M,r,s)給驗(yàn)證者(張三)7.3.2ElGamal的數(shù)位簽章機(jī)制李四之金鑰產(chǎn)生：y=gxmodPy為李四之公開金鑰x為李四之秘密金鑰P為很大之質(zhì)數(shù)g為與P互質(zhì)之原根5.張三收到(M,r,s)後驗(yàn)證gM=yrrsmodP上式若相等表示M確定為李四所簽署?TheMcGraw-HillCompanies,Inc.,2005307.4橢圓曲線密碼系統(tǒng)?TheMcGraw-HillCompanies,Inc.,2005RSA或ElGamal密碼系統(tǒng)最為人詬病的問題就是在加解密或是簽章的時(shí)候需要龐大的運(yùn)算量，所以需要較長的運(yùn)算時(shí)間。為了改善其效率（較少之運(yùn)算量），因此提出橢圓曲線的密碼系統(tǒng)(EllipticCurveCryptosystem,ECC)，它的安全性必須相當(dāng)於RSA或ElGamal的密碼系統(tǒng)。31橢圓曲線上的有限加法群?TheMcGraw-HillCompanies,Inc.,2005所使用的橢圓曲線方程式為y2=x3+ax+b此曲線剛好對(duì)稱於y=0這條直線參數(shù)a及b必需滿足4a3+27b2≠0，才能確保沒有重根，具有唯一解加法單位元素O為一無窮遠(yuǎn)的點(diǎn)，並滿足O=-O此加法單位元素亦需滿足：橢圓曲線上某三點(diǎn)共線其合為O32橢圓曲線上不同座標(biāo)點(diǎn)相加?TheMcGraw-HillCompanies,Inc.,200533橢圓曲線上相同座標(biāo)點(diǎn)相加?TheMcGraw-HillCompanies,Inc.,200534橢圓曲線上一座標(biāo)點(diǎn)與一無窮遠(yuǎn)點(diǎn)相加?TheMcGraw-HillCompanies,Inc.,200535橢圓曲線上兩對(duì)稱點(diǎn)相加?TheMcGraw-HillCompanies,Inc.,2005A＋B=A+(-A)=O

B36在有限體內(nèi)的橢圓曲線運(yùn)算?TheMcGraw-HillCompanies,Inc.,2005

在此橢圓曲線上可能出現(xiàn)的點(diǎn)有(0,1)、(0,4)、(2,1)、(2,4)、(3,1)、(3,4)、(4,2)、(4,3)、(∞,∞)任取橢圓曲線上兩點(diǎn)，無論作加法、減法或乘法，其結(jié)果永遠(yuǎn)為上述座標(biāo)點(diǎn)中的一點(diǎn)橢圓曲線中的離散對(duì)數(shù)難題：給訂一參數(shù)K及一點(diǎn)A，要求得另一點(diǎn)B，使得B=KA是很容易的。例如：5A=A+A+A+A+A但若給定A及B要求得K則很困難37?TheMcGraw-HillCompanies,Inc.,2005橢圓曲線的公開金鑰加密機(jī)制38?TheMcGraw-HillCompanies,Inc.,2005橢圓曲線的數(shù)位簽章397.5混合式的加密機(jī)制?TheMcGraw-HillCompanies,Inc.,2005混合式加密機(jī)制顧名思義就是同時(shí)採用對(duì)稱式密碼機(jī)制及公開金鑰密碼機(jī)制的加密系統(tǒng)，截長補(bǔ)短，使得它可以同時(shí)擁有這兩種密碼機(jī)制的優(yōu)點(diǎn)。407.5.1數(shù)位信封(DigitalEnvelope)Sender:AliceReceiver:BobC=ES