四、公開密鑰密碼陽(yáng)振坤計(jì)算機(jī)科學(xué)技術(shù)研究所密碼算法與應(yīng)用基礎(chǔ)1信息安全引論對(duì)稱密鑰密碼對(duì)稱密鑰密碼應(yīng)用基礎(chǔ)公開密鑰密碼數(shù)字簽名與Hash函數(shù)公開密鑰密碼應(yīng)用基礎(chǔ)密鑰交換與密鑰管理內(nèi)容提要2信息安全的基本內(nèi)容保密性(Confidentiality)真實(shí)性(Authentication)完整性(Integrity)不可否認(rèn)性(Nonrepudiation)……3公開密鑰密碼基本思想

數(shù)學(xué)基礎(chǔ)

RSA算法基于離散對(duì)數(shù)的算法基于橢圓曲線的算法密鑰分發(fā)總結(jié)4基本思想加密與解密由不同的密鑰完成 加密:XY:Y=EKU(X) 解密:YX:X=DKR(Y)=DKR(EKU(X))從解密密鑰得到加密密鑰在計(jì)算上是不可行的加密與解密的順序沒(méi)有限制(不是必須的)

X=DKR(EKU(X))=EKU(DKR(X))若X=Y且映射E:XY是映上的,則成立

EKU(X)=EKU(DKR(EKU(X)))若X=Y且為有限集合(例如分組密碼),則E:XY是映上的,從而成立5用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(duì)(KU,KR)公鑰KU公開,私鑰KR保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X6用公鑰密碼實(shí)現(xiàn)認(rèn)證條件:加密與解密的順序沒(méi)有限制認(rèn)證: AALL:Y=DKRa(X) ALL:EKUa(Y)=EKUa(DKRa(X))=X認(rèn)證+保密: AB:Z=EKUb(DKRa(X)) B:EKUa(DKRb(Z))=X7公鑰密鑰的應(yīng)用范疇加密/解密數(shù)字簽名(身份認(rèn)證)密鑰交換8公鑰密鑰算法必須滿足的條件密鑰對(duì)的生成在計(jì)算上是可行的用公鑰加密明文在計(jì)算上是可行的用私鑰解密密文在計(jì)算上是可行的從公鑰獲得私鑰在計(jì)算上是不可行的從公鑰和密文來(lái)獲得明文在計(jì)算上是不可行的加密與解密的順序沒(méi)有限制(不是必須的)

X=DKR(EKU(X))=EKU(DKR(X))9One-waytrapdoorfunction對(duì)稱密鑰密碼:Y=FK(X) easyifX&KareknownX=FK-1(Y) easyifY&KareknownX=FK-1(Y) infeasibleifonlyYisknown公開密鑰密碼:Y=FK(X) easyifX&KareknownX=FK-1(Y) easyifY&Kareknown Where,KandKarerelatedkeys.X=FK-1(Y) infeasibleifY&Kareknown butKisunknown.10公鑰密碼分析強(qiáng)制破譯通過(guò)公鑰得到私鑰破譯公鑰加密的對(duì)稱密鑰11數(shù)學(xué)基礎(chǔ)素?cái)?shù),最大公約數(shù)(gcd),互素模運(yùn)算:a=qn+r,0r<n(amodn)=r同余:abmodniff(amodn)=(bmodn)[(amodn)(bmodn)]modn=(ab)modn[(amodn)(bmodn)]modn=(ab)modnIf(ab)(ac)modnandaisrelativelyprimeton,thenbcmodn(ab)(ac)modnn|(ab-ac)

n|(a(b-c))

n|(b-c)

bcmodn12Fermat定理Fermat定理:p素?cái)?shù),a是整數(shù)且不能被p整除,則:ap-1

1modp證明:考慮集合{1,2,…,p-1},對(duì)每個(gè)數(shù)乘以a,得到集合{amodp,2amodp,…,(p-1)amodp},對(duì)于p,后者兩兩不同且都在1與p-1之間,因此兩個(gè)集合相同,于是:

(p-1)!=12…(p-1)[(amodp)(2amodp)…((p-1)amodp)]modp[a2a…(p-1)a]modp[ap-1(p-1)!]modp注意到(p-1)!與p互素,因此定理成立.推論:p素?cái)?shù),a是任意整數(shù),則:ap

amodp13Euler數(shù)Euler數(shù)(n)定義為小于n且與n互素的正整數(shù)個(gè)數(shù)p是素?cái)?shù),(p)=p-1若n的因子分解為n=Piai,ai>0,Pi互不相同,則 (n)=Piai(1-1/Pi)若gcd(m,n)=1,則(mn)=(m)(n),特別地,若pq且都是素?cái)?shù),(pq)=(p-1)(q-1)Euler定理:若a與n為互素的正整數(shù),則: a(n)

1modn14Euler定理a(n)

1modn證明:R={x1,x2,…,x(n)}為所有小于n且與n互素的正整數(shù),考慮集合S={(ax1modn),(ax2modn),…,(ax(n)modn)}

(aximodn)與n互素

(aximodn)兩兩不等:

(aximodn)=(axjmodn)ximodn=xjmodnS有(n)個(gè)元素故S也是所有小于n且與n互素的正整數(shù),因此S=R,從而xi=(aximodn)((axi))modn

(a(n)xi)modn注意到xi與n互素,從而得到結(jié)論.15Euler定理推論推論:若n=pq,pq都是素?cái)?shù),k是任意整數(shù),則 mk(p-1)(q-1)+1

mmodn,對(duì)任意0mn證明:若m=0或n,結(jié)論是顯然的;若m與n互素,注意到(n)=(p-1)(q-1),由Euler定理可得到結(jié)論;否則m必定是p或者q的倍數(shù),不妨設(shè)m=sp,則0<s<q為正整數(shù),m與q互素,由Euler定理得到:m(q)

1modq

(m(q))k(p)

1modq

mk(p-1)(q-1)

=tq+1t是整數(shù)等式兩邊乘以m=sp,得到:mk(p-1)(q-1)+1=(tq+1)sp=tspq+spmmodn16中國(guó)剩余定理(1)中國(guó)剩余定理:m1,m2,…,mk是兩兩互素的整數(shù),a1,a2,…,ak是任意整數(shù),M=mi,那么方程組 xaimodmi,1im關(guān)于模M有唯一解:x[aiMi(Mi-1modmi)]modM,Mi=M/mi證明:m1,m2,…,mk兩兩互素因此gcd(Mi,mi)=1Mi-1modmi存在正確性:Mi定義Mi0modmj,任給ij17中國(guó)剩余定理(2)x[aiMi(Mi-1modmi)]modmj

ajMj(Mj-1modmj)modmjajmodmj正確性唯一性:假如x,y都是解xymodmi,對(duì)任意imi|(x-y),對(duì)任意i(mi)

|(x-y),對(duì)任意j(∵m1,m2,…,mk兩兩互素)M|(x-y)xymodM唯一性18(aximodn)與n互素a與n為互素的正整數(shù),{x1,x2,…,x(n)}為所有小于n且與n互素的正整數(shù).S={(ax1modn),(ax2modn),…,(ax(n)modn)}反證法:若某個(gè)(aximodn)與n不互素,則存在素?cái)?shù)p使得 p|n且p|(aximodn)令r=(aximodn),則axi=tn+r,t是整數(shù) p|n,p|rp|(axi)

p|a或者p|xi這說(shuō)明a或者xi與n有共因子p,與假設(shè)a和xi都與n互素相矛盾.19RSA算法簡(jiǎn)介由RonRivest,AdiShamir&LenAdlemen于1977年發(fā)布屬于分組密碼明文和密文在0~n-1之間,n是一個(gè)正整數(shù)應(yīng)用最廣泛的公鑰密碼算法只在美國(guó)申請(qǐng)專利且已于2000年9月到期NSA聲稱在60年代中期發(fā)現(xiàn)了公鑰算法英國(guó)的CliffordCocks在1973年發(fā)表了與RSA幾乎一樣的算法20RSA算法描述分組大小為k,2k<n2k+1加密:C=Memodn解密:M=Cdmodn=Medmodn公鑰:KU={e,n},私鑰:KR={d,n}上述算法需要滿足以下條件:能夠找到e,d,n,使得Medmodn=M,對(duì)所有M<n計(jì)算Me和Cd相對(duì)容易從e和n得到d是在計(jì)算上不可行的21RSA密鑰生成原理令n=pq,pq都是素?cái)?shù),(n)=(p-1)(q-1)是n的Euler數(shù)Euler定理推論:若n=pq,pq都是素?cái)?shù),k是任意整數(shù),則mk(p-1)(q-1)+1

mmodn,對(duì)任意0mn只要選擇e,d,滿足ed=k(n)+1,即 ed1mod(n)de-1mod(n)公鑰:KU={e,n},私鑰:KR={d,n}22RSA密鑰生成與使用選擇兩個(gè)大素?cái)?shù)p,q,pq

計(jì)算n=pq,(n)=(p-1)(q-1)選擇整數(shù)e,使得gcd(e,(n))=1 (兩個(gè)隨機(jī)數(shù)互素概率~0.6)計(jì)算de-1mod(n)公鑰:KU={e,n},私鑰:KR={d,n}加密:C=Memodn

解密:M=Cdmodn23提高RSA解密速度:結(jié)論1解密:M=Cdmodn需作大數(shù)的冪運(yùn)算,速度慢結(jié)論1:若pq都是素?cái)?shù),n=pq,則同余方程 xxpmodp xxqmodq對(duì)模n有唯一解x=(xp-xq)(q-1modp)q+xq證明:pq是素?cái)?shù)gcd(p,q)=1q-1modp存在.唯一性由中國(guó)剩余定理保證.驗(yàn)證解:令r=q-1modp,則r是整數(shù),rq1modpx=(xp-xq)rq+xq對(duì)于q,x=((xp-xq)r)q+xqxqmodq對(duì)于p,x=(xp-xq)(rq)+xq(xp-xq)+xqxpmodp24提高RSA解密速度:結(jié)論2結(jié)論2:p素?cái)?shù),a是任意整數(shù),則 ak

(amodp)kmod(p-1)modp,k是任意整數(shù)證明:若a0modp,結(jié)論是顯然的.否則,令k=t(p-1)+r,t,r是整數(shù),r=kmod(p-1),那么ak=at(p-1)+rat(p-1)armodp

armodp(Fermat定理:ap-1

1modp)(amodp)rmodp(amodp)kmod(p-1)modp25提高RSA解密速度:方法解密:M=Cdmodn,n=pq,pq都是素?cái)?shù)假如得到了 Mp

Mmodp Mq

Mmodq就得到了M=(Mp-Mq)(q-1modp)q+Mqmodn由于M=Cdmodn,因此

Mp=Cdmodp=(Cmodp)dmod(p-1)modp

Mq=Cdmodq=(Cmodq)dmod(q-1)modq由于Cmodp與Cmodq要比C小,dmod(p-1)與dmod(q-1)也比d小,故解密速度會(huì)提高(4~8倍).26提高RSA加密速度?(1)同樣的方法可以用于RSA的加密加密:C=Memodn,n=pq,pq都是素?cái)?shù)假如得到了 Cp

Cmodp Cq

Cmodq就得到了C=(Cp-Cq)(q-1modp)q+Cqmodn由于C=Me,從而Cp=Memodp=(Mmodp)emod(p-1)modpCq=Memodq=(Mmodq)emod(q-1)modq加密速度是否會(huì)提高?27提高RSA加密速度?(2)加密:C=Memodn,n=pq,pq都是素?cái)?shù)M{0,1,2,…,2k-1}{0,1,2,…,n-1},其中2kn<2k+1定義上,加密E:{0,1,2,…,n-1}{0,1,2,…,n-1}實(shí)際上,加密E:{0,1,2,…,2k-1}{0,1,2,…,n-1}解密映射的定義域總是{0,1,2,…,n-1}M在較小的空間上,C在較大的空間上e一般可以選擇比d小加密:Cp=Memodp=(Mmodp)emod(p-1)modp解密:Mp=Cdmodp=(Cmodp)dmod(p-1)modp同樣的方法對(duì)加密速度的提高不如對(duì)解密速度的提高顯著28RSA的安全性強(qiáng)制破解基于數(shù)學(xué)的攻擊

基于運(yùn)算時(shí)間的攻擊29RSA加密解密計(jì)算量加密:C=Memodn解密:M=Cdmodn冪運(yùn)算位數(shù)增長(zhǎng)快冪運(yùn)算速度慢并且e,d都是很大的數(shù)[(amodn)(bmodn)]modn=(ab)modn計(jì)算xm,其中m=2s,只需要計(jì)算s次,即計(jì)算: xmi,mi=2i,i=0,1,…,s30計(jì)算冪計(jì)算d=am,m=bkbk-1…b0(二進(jìn)制表示) d1 forikdownto0 dod(dd)modn ifbi=1 thend(da)modn returnd31Euclid算法gcd(a,b)=gcd(b,a+kb)a,b,k為任意整數(shù)gcd(a,b)=gcd(b,amodb)a0,b>0Eclid(d,f):求最大共約數(shù),假定df

Xf,Yd ifY=0thenreturnX XXmodY XY goto上述的循環(huán)最多進(jìn)行多少次? 2log2(max(f,d))32擴(kuò)展Euclid算法ExtEclid(d,f):求最大共約數(shù)或模逆,假定df

(X1,X2,X3)(1,0,f),(Y1,Y2,Y3)(0,1,d) ifY3=0thenreturnX3,noinverse ifY3=1thenreturn1,inverseisY2 Q

(X3/Y3)的整數(shù)部分 (X1,X2,X3)(X1-QY1,X2-QY2,X3-QY3) (X1,X2,X3)(Y1,Y2,Y3)

gotofX1+dX2=X3,fY1+dY2=Y3若Y3=1,則fY1+dY2=1dY2=(-Y1)f+1

dY21modfY2=d-1modf33素?cái)?shù)模的平方剩余解直接判斷一個(gè)整數(shù)是否為素?cái)?shù)是困難的命題:如果p是素?cái)?shù),則方程 x2

1modp只有平凡解x1modp.證明:x2

1modp p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp,k,j是整數(shù) x=kp-1,或者x=jp+1 x1modp,或者x

-1modp34Miller-Rabin素?cái)?shù)測(cè)試算法Miller-Rabin算法用來(lái)測(cè)試一個(gè)整數(shù)是否是素?cái)?shù)WITNESS(a,n)

設(shè)bkbk-1…b0是(n-1)的二進(jìn)制表示 d1 forikdownto0 doxd d(dd)modn//x21modn if(d=1&x1&xn-1)returnTRUE

if(bi=1)thend(da)//d=an-1 if(d1)returnTRUE//Fermat定理 elsereturnFALSEMiller-Rabin是概率測(cè)試(一次概率約0.5)

35素?cái)?shù)生成素?cái)?shù)生成過(guò)程:隨機(jī)選擇一個(gè)奇數(shù)n(如通過(guò)偽隨機(jī)數(shù)發(fā)生器)隨機(jī)選擇a,使a<n進(jìn)行素?cái)?shù)測(cè)試(例如用Miller-Rabin算法),若n沒(méi)有通過(guò)測(cè)試,拋棄n,轉(zhuǎn)到如果通過(guò)了足夠次數(shù)的測(cè)試,認(rèn)為n是素?cái)?shù),否則轉(zhuǎn)到.素?cái)?shù)定理:(N)~N/ln(N),(N)為不超過(guò)N的素?cái)?shù)個(gè)數(shù).隨機(jī)整數(shù)N是素?cái)?shù)的概率是1/ln(N)36基于數(shù)學(xué)的攻擊公鑰:KU={e,n},私鑰:KR={d,n},n=pq分解n=pq(n)=(p-1)(q-1)d=e-1mod(n)不求出p,q,直接求(n)d=e-1mod(n)不求出(n),直接計(jì)算d已知的方法至少跟因子分解一樣難度尚未發(fā)現(xiàn)多項(xiàng)式時(shí)間的因子分解算法因子分解的算法已經(jīng)取得了長(zhǎng)足進(jìn)步如果e<n并且d<n,則d容易被得到.目前已知最好的結(jié)果是=0.292措施:選擇足夠大的n(1024位以上),并且使得e,d之間相差不太大,也不太小37同模攻擊如果A,B使用同樣模n的RSA算法(e1,d1,n),(e2,d2,n),C把信息M用A,B的公鑰分別加密并傳給它們: Y1=Md1:A Y2=Md2:B假如gcd(d1,d2)=1,則竊聽者能獲得明文.做法是:找到整數(shù)a1,a2,使得: a1d1+a2d2=1(∵gcd(d1,d2)=1)不妨假定a1<0,a2>0,那么: M=(Y1–1)-a1Y2a2modn(Y1–1)-a1Y2a2=((Md1)–1)-a1(Md2)a2=Md1a1+a2d2措施:避免在不同用戶之間共享模.38其他攻擊RSA的同態(tài)性質(zhì):EK(m1m2)=EK(m1)EK(m2)措施:加密前對(duì)信息處理,如通過(guò)hash或者單向函數(shù)如果(p-1)或者(q-1)只有小的素?cái)?shù)因子,則n容易被分解,n被分解的計(jì)算量與(p-1)或者(q-1)的最大素因子成某種正比.措施:找到p1q1,使得p1,q1,2p1+1,2q1+1都是素?cái)?shù),然后選擇p=2p1+1,q=2q1+1(安全素?cái)?shù)).39基于運(yùn)算時(shí)間的攻擊基于加密程序運(yùn)行時(shí)間的攻擊計(jì)算d=am,m=bkbk-1…b0(二進(jìn)制表示) d1 forikdownto0 dod(dd)modn ifbi=1 thend(da)modn returnd若bi=1,執(zhí)行d(da)modn,否則不執(zhí)行.有少數(shù)的a,d,上述模乘速度很慢從左到右逐個(gè)確定bi

40基于運(yùn)算時(shí)間攻擊的特征與防備特征: 一種全新的攻擊手段

選擇明文的攻擊

適用于攻擊其他公鑰算法防備:計(jì)算d=am,m=bkbk-1…b0(二進(jìn)制表示) forikdownto0 dod(dd)modn ifbi=1 thend(da)modn returndConstantexponentiationtimeRandomdelayBlinding41RSABlindingRSAblinding:選擇一個(gè)隨機(jī)數(shù)r,使得gcd(r,n)=1,0<r<n加密:C=(Mr)emodn C=CD

modn

D=(r-1)e,r-1是r關(guān)于modn的乘法逆解密:M=Cdmodn代價(jià):每個(gè)塊增加兩個(gè)乘法,2~10%的性能損失其他解決措施(初始化向量)42因子分解算法改進(jìn)密鑰位數(shù)實(shí)現(xiàn)時(shí)間MIPS-Yrs算法名稱100(332)1991.47Quadraticsieve110(365)1992.475Quadraticsieve120(398)1993.6830Quadraticsieve129(428)1994.45000Quadraticsieve130(431)1996.4500GeneralizednumberfieldsieveSpecialnumberfieldsieve速度更快43MontreCarlo模型YES-BIASED型MontreCarlo算法:一個(gè)YES的回答總是正確的,一個(gè)NO的回答則可能是正確,也可能是錯(cuò)誤的.稱一個(gè)YES-BIASED算法具有錯(cuò)誤概率,是指它回答NO時(shí)出錯(cuò)的幾率至多是

NO-BIASED型MontreCarlo算法Miller-Rabin屬于YES-BIASED型MontreCarlo算法,其出錯(cuò)概率是0.544密鑰分發(fā)分發(fā)公鑰PublicannouncementPubliclyavailabledirectoryPublic-keyauthorityPublickeycertificates利用公鑰分發(fā)對(duì)稱密鑰SimplesecretkeydistributionSecretkeydistributionwithconfidentialityandauhtenticationHybridscheme45Publicannouncement直接把公鑰散發(fā)出去使用PGP并且把公鑰附上能被假冒46Publiclyavailabledirectory需要可信任的中央授權(quán)機(jī)構(gòu)授權(quán)機(jī)構(gòu)維護(hù)著動(dòng)態(tài){name,publickey}列表用戶在授權(quán)機(jī)構(gòu)注冊(cè)其publickey(安全通道)用戶可以替換其publickey授權(quán)機(jī)構(gòu)定期發(fā)布或更新整個(gè)目錄用戶可在網(wǎng)絡(luò)上直接訪問(wèn)公共目錄(安全通道)47Public-keypublication若成功修改了公共目錄,則攻擊者可假冒用戶48Public-keyauthority需要可信任的中央授權(quán)機(jī)構(gòu)每個(gè)用戶知道授權(quán)機(jī)構(gòu)的公鑰AAuth:(IDA,IDB,T1)AuthA:EKRauth(KUb,T1)AB:EKUb(IDA,N1)BAuth:(IDB,IDA,T2)AuthB:EKRauth(KUa,T2)BA:EKUa(N1,N2)AB:EKUb(N2)49Public-keyDistributionScenario若成功修改了公共目錄,則攻擊者可假冒用戶授權(quán)中心易成為性能及安全瓶頸50Public-keycertificates任何人可以閱讀證書以確定證書擁有者的姓名和公鑰任何人可以驗(yàn)證證書是由授權(quán)機(jī)構(gòu)發(fā)出而非偽造的只有授權(quán)機(jī)構(gòu)才可以發(fā)行和更新證書任何人可以驗(yàn)證證書的時(shí)效性(非失效證書) CA=EKRauth(T,IDA,KUa)51Exchangeofpublic-keycertificates泄漏私鑰等價(jià)于丟失證書證書的時(shí)間作為有效期52SimplesecretkeydistributionMerkle的建議:A生成{KUa,KRa},AB:(IDA,KUa)B生成隨機(jī)密鑰Ks,BA:EKUa(Ks)A解密EKUa(Ks)得到Ks:DKRa(EKUa(Ks))A丟棄{KUa,KRa},B丟棄KUa通訊前不需存在密鑰,通訊后也不存在密鑰能抵抗偷聽,不能抵抗主動(dòng)攻擊(中間人攻擊)53Merkle協(xié)議的中間人攻擊A生成{KUa,KRa},AB:(IDA,KUa)E截獲,生成{KUe,KRe}冒充AB:(IDA,KUe)B生成隨機(jī)密鑰Ks,BA:EKUe(Ks)E截獲,解密后再用EKUa加密KsA:EKUa(Ks)A丟棄{KUa,KRa},B丟棄KUaE獲得了Ks,故以后只需進(jìn)行竊聽.A,B并不知曉它們被攻擊了54Secretkeydistributionwithconfidentialityandauthentication假定A和B已經(jīng)獲得了雙方的公鑰:AB:EKUb(IDA,N1)BA:EKUa(N1,N2)AB:EKUb(N2)AB:Y=EKUb(EKRa(Ks))B解密Y獲得會(huì)話密鑰Ks=DKUa(DKRb(Y))55Secretkeydistributionwithconfidentialityandauthentication:Map56HybridScheme在IBM大型主機(jī)上使用仍然使用KDCKDC與每個(gè)用戶都擁有{公鑰,私鑰}對(duì)KDC與每個(gè)用戶共享主密鑰(對(duì)稱密鑰密碼)會(huì)話密鑰的分發(fā)由主密鑰完成主密鑰更新由公鑰完成PerformanceBackwardcompatibility57原根(primitiveroot)Euler定理表明,對(duì)兩個(gè)互素的整數(shù)a,n, a(n)

1modn因此存在最小正整數(shù)m(n)(m|(n)),使得 am

1modn若對(duì)某個(gè)a,m=(n),則稱a是n的一個(gè)原根(primitiveroot).只有為2,4,p,2p的數(shù)才有原根,其中p是奇素?cái)?shù).對(duì)于素?cái)?shù)p,若a是p的一個(gè)原根,則: a,a1,a2,…,ap-1關(guān)于p兩兩不同余,從而構(gòu)成了p的非0剩余類,即與{1,2,…,(p-1)}關(guān)于模p等價(jià).58離散對(duì)數(shù)若a是素?cái)?shù)p的一個(gè)原根,則對(duì)任意整數(shù)b,b0modp,存在唯一的整數(shù)i,1i(p-1),使得: baimodpi稱為b以a為基模p的指數(shù)(離散對(duì)數(shù)),記作inda,p(b).容易知道: inda,p(xy)=[inda,p(x)+inda,p(y)]mod(p) inda,p(xr)=[rinda,p(x)]mod(p)離散對(duì)數(shù)的計(jì)算: ygxmodp已知g,x,p,計(jì)算y是容易的已知y,g,p,計(jì)算x是困難的59Diffie-Hellman密鑰交換雙方選擇素?cái)?shù)q以及q的一個(gè)原根rA選擇X<q,計(jì)算XA=rXmodp,AB:XAB選擇Y<q,計(jì)算YB=rYmodp,

BA:YBA計(jì)算:(YB)X(rY)XrXYmodpB計(jì)算:(XA)Y(rX)YrXYmodp雙方獲得一個(gè)共享密鑰(rXYmodp)素?cái)?shù)q以及q的原根r可由一方選擇后發(fā)給對(duì)方不能抵抗replay攻擊對(duì)中間人攻擊的抵抗力遠(yuǎn)好于“Simplesecretkeydistribution(Merkle的建議)”60Diffie-Hellman密鑰交換的攻擊雙方選擇素?cái)?shù)q以及q的一個(gè)原根r(假定E知道)A選擇X<q,計(jì)算XA=rXmodp,AB:XAE截獲XA,選Z,計(jì)算ZE=rZmodp,冒充AB:ZEB選擇Y<q,計(jì)算YB=rYmodp,BA:YBE截獲YB,冒充BA:ZEA計(jì)算:(ZE)X(rZ)XrZXmodpB計(jì)算:(ZE)Y(rZ)YrYZmodpE計(jì)算:(XA)ZrXZmodp,(YB)ZrYZmodpE無(wú)法計(jì)算出rXYmodpE永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn).61ElGamal加密算法選擇:一個(gè)素?cái)?shù)p,p的一個(gè)原根r,一個(gè)整數(shù)a,令s=ra,公開{p,r,s},保密a.對(duì)于明文信息x,加密:秘密選擇隨機(jī)數(shù)k,計(jì)算(rkmodp,xskmodp)作為密文解密:(xsk)((rk)a)-1xrakr-akxmodp信息有擴(kuò)張62橢圓曲線密碼介紹1985年Miller,Koblitz獨(dú)立提出 y2+axy+by=x3+cx2+dx+e曲線上的點(diǎn)連同無(wú)窮遠(yuǎn)點(diǎn)O的集合加法:若曲線三點(diǎn)在一條直線上,則其和為零倍數(shù):一個(gè)點(diǎn)的兩倍是它的切線與曲線的另一個(gè)交點(diǎn)63橢圓曲線密碼示意圖64有限域上橢圓曲線有限域上橢圓曲線

y2x3+ax+bmodp p是奇素?cái)?shù),且4a3+27b20modp

y2+xyx3+ax2+bmod2m加法公式:P=(x1,y1),Q=(x2,y2)若x1=x2且y1=-y2,則P+Q=O,否則P+Q=(x3,y3) x3=2-x1-x2 y3=(x1-x3)-y1 其中,=(y2-y1)/(x2-x1),如果PQ

=(3x12+a)/2y1,如果P=Q65Ep(a,b)橢圓曲線上的整數(shù)點(diǎn)在上述運(yùn)算下成為一個(gè)交換群(Abelian群),記作Ep(a,b).關(guān)于|Ep(a,b)|,有如下不等式: p+1-2p1/2

|Ep(a,b)|p+1+2p1/2該不等式表明:|Ep(a,b)|~pG是Ep(a,b)的一個(gè)元素,使得nG=O的最小正整數(shù)n稱為元素G的階.66橢圓曲線密鑰交換雙方選擇Ep(a,b)以及Ep(a,b)的一個(gè)元素G,使得G的階n是一個(gè)大素?cái)?shù)A選擇X<n,計(jì)算PA=XG,AB:PAB選擇Y<n,計(jì)算PB=YG,

BA:PBA計(jì)算:X(PB)=XYGB計(jì)算:Y(PA)=YXG=XYG雙方獲得了一個(gè)共享會(huì)話密鑰(XYG)不能抵抗replay攻擊對(duì)中間人攻擊的抵抗力遠(yuǎn)好于“Simplesecretkeydistribution(Merkle的建議)”67橢圓曲線密鑰交換的攻擊雙方選擇Ep(a,b)以及Ep(a,b)的一個(gè)元素G,使得G的階n是一個(gè)大素?cái)?shù)A選擇X<n,計(jì)算PA=XG,AB:PAE截獲PA,選Z,計(jì)算PE=ZG,冒充AB:PEB選擇Y<n,計(jì)算PB=YG,

BA:PBE截獲PB,冒充BA:PEA計(jì)算:XZE=

XZGB計(jì)算:YZE=YZGE計(jì)算:ZPA=ZXG,ZPB=ZYGE無(wú)法計(jì)算出XYGE永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn).68橢圓曲線加密解密選擇Ep(a,b)的元素G,使得G的階n是一個(gè)大素?cái)?shù),秘密選擇整數(shù)r.計(jì)算P=rG,公開(p,a,b,G,P),保密r.加密M:選擇隨機(jī)數(shù)k,C={kG,M+kP) 如果k使得kG或者kP為O,則要重新選擇k.解密C:(M+kP)-r(kG)=M+krG-rkG=M加密信息有擴(kuò)張69橢圓曲線密碼的安全性難點(diǎn):從P和kP獲得k對(duì)橢圓曲線研究的時(shí)間短橢圓曲線要求密鑰長(zhǎng)度短,速度快對(duì)比:ECCRSAKeysizeMIPS-Yrs1503.810102057.110182341.61028