第5章-第2講 雙鑰密碼體制(二)

網(wǎng)絡(luò)安全—技術(shù)與實(shí)踐（第2版）劉建偉王育民編著清華大學(xué)出版社普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材教育部2011年精品教材課件制作人聲明本課件總共有17個(gè)文件，版權(quán)屬于劉建偉所有，僅供選用此教材的教師和學(xué)生參考。本課件嚴(yán)禁其他人員自行出版銷(xiāo)售，或未經(jīng)作者允許用作其他社會(huì)上的培訓(xùn)課程。對(duì)于課件中出現(xiàn)的缺點(diǎn)和錯(cuò)誤，歡迎讀者提出寶貴意見(jiàn)，以便及時(shí)修訂。課件制作人：劉建偉2012年2月8日雙鑰密碼體制（第2講）Rabin公鑰密碼體制二三一橢圓曲線密碼體制Diffie-Hellman密鑰交換一雙鑰密碼體制（第2講）Rabin公鑰密碼體制二三一橢圓曲線密碼體制Diffie-Hellman密鑰交換一一、Diffie-Hellman密鑰交換1976年Diffie和Hellman發(fā)明了DH算法，該算法是一個(gè)公開(kāi)密鑰算法，其安全性源于在有限域上計(jì)算離散對(duì)數(shù)比計(jì)算指數(shù)更為困難。DH算法用于密鑰分配，但不能用于加密或解密。DH算法已經(jīng)申請(qǐng)美國(guó)和加拿大的專利，目前該專利已經(jīng)到期。DH算法容易受到中間人攻擊。Diffie-Hellman密鑰分配方案兩個(gè)通信主體Alice和Bob，希望在公開(kāi)信道上建立共享密鑰選擇一個(gè)大素?cái)?shù)p(～200digits)一個(gè)生成元a

Alice選擇一個(gè)秘密鑰(privatekey)xA<pBob選擇一個(gè)秘密鑰(privatekey)xB<p

AliceandBob計(jì)算他們的公開(kāi)密鑰:yA=axAmodp，yB=axBmodpAlice,Bob分別公開(kāi)yA,yB共享密鑰的生成計(jì)算共享密鑰：KAB

=axA.xBmodp

=(

yAxB

)modp(whichBcancompute)=(yBxA)modp(whichAcancompute)KAB

可以用于對(duì)稱加密密鑰不能用于加密任意消息；可以建立共享密鑰基于有限域上的指數(shù)問(wèn)題安全性是基于計(jì)算離散對(duì)數(shù)的困難性一兩個(gè)主體每次可以選擇新的秘密鑰(私鑰)，并計(jì)算及交換新的公鑰二可以抵抗被動(dòng)攻擊，但不能抵抗主動(dòng)攻擊三為抵抗主動(dòng)攻擊，需要其它新的協(xié)議四每次可以給出新的密鑰，也可以建立長(zhǎng)期公鑰Diffie-Hellman應(yīng)用的問(wèn)題雙鑰密碼體制（第2講）Rabin公鑰密碼體制二三一橢圓曲線密碼體制Diffie-Hellman密鑰交換一二、Rabin公鑰密碼體制1979年，Rabin利用合數(shù)模下求解平方根的困難性構(gòu)造了一種安全的公鑰體制。

Rabin公鑰體制已經(jīng)被證明：對(duì)該體制的破譯的難度等價(jià)于大整數(shù)分解。

Rabin體制是RSA的一種特例，它有以下兩個(gè)特點(diǎn)：RSA中選取的公開(kāi)鑰e滿足1＜e＜φ(n)，且gcd(e,φ(n))=1。而Rabin體制則選擇e=2。

它不是以一一對(duì)應(yīng)的單向陷門(mén)函數(shù)為基礎(chǔ)。即對(duì)于同一密文，可能對(duì)應(yīng)有兩個(gè)以上的明文。破譯該體制等價(jià)于大整數(shù)的分解。2.1密鑰的產(chǎn)生2.隨機(jī)選擇兩大素?cái)?shù)p,q1.Rabin體制則選擇e=2

4.n,e作為公鑰5.p,q為私鑰

3.計(jì)算：n=p×q滿足p≡q≡3mod4即這兩個(gè)素?cái)?shù)的形式為：4k+3（k為整數(shù)）2.2Rabin加密過(guò)程B將明文分組為m1,m2,m3,m4…..。設(shè)其中一個(gè)明文分組為消息m假設(shè)B要將消息加密后發(fā)給A；A公布其公開(kāi)鑰：n,e=2B計(jì)算密文：c≡me≡m2

modnB將密文c發(fā)給A。2.3Rabin解密過(guò)程A解密就是求c的模n平方根，即解x2≡cmodn；由中國(guó)剩余定理可知，解以上方程等價(jià)于解方程組：由于p≡q≡3mod4，可以很容易求出方程組的解：經(jīng)過(guò)組合可以得到4個(gè)同余方程組：2.3

Rabin解密過(guò)程（續(xù)）可見(jiàn)：由中國(guó)剩余定理解出的每一方程組的解有4個(gè)，即每一密文對(duì)應(yīng)的明文不是唯一的。解決辦法：為了有效地確定唯一的明文，發(fā)送者可以在明文消息m中加入某些信息，如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間等。雙鑰密碼體制（第2講）Rabin公鑰密碼體制二三一橢圓曲線密碼體制Diffie-Hellman密鑰交換一三、橢圓曲線密碼體制ECC1985年，Koblitz和Miller獨(dú)立將橢圓曲線（EllipticCurve）引入密碼學(xué)中，成為構(gòu)造雙鑰體制的有力工具。目前，對(duì)這種橢圓曲線離散對(duì)數(shù)密碼體制研究已經(jīng)有16年的歷史，尚未發(fā)現(xiàn)明顯的弱點(diǎn)。目前，大多數(shù)的產(chǎn)品和標(biāo)準(zhǔn)均使用RSA。為了保證RSA的安全性，近年來(lái)所采用的密鑰長(zhǎng)度不斷增加，這直接導(dǎo)致了RSA計(jì)算量的增加。

ECC對(duì)RSA提出了巨大的挑戰(zhàn)。在公鑰密碼的標(biāo)準(zhǔn)化過(guò)程中，IEEEP1363標(biāo)準(zhǔn)已經(jīng)采用了ECC。與RSA相比，ECC的主要優(yōu)點(diǎn)是可以使用比RSA更短的密鑰獲得相同水平的安全性。3.1實(shí)數(shù)域上橢圓曲線的概念實(shí)數(shù)域上的橢圓曲線可以定義為滿足方程

y2=x3+ax+b

的點(diǎn)(x,y)的集合可以證明：如果x3+ax+b

沒(méi)有重復(fù)因子，或者滿足4a3+27b2≠0

，那么橢圓曲線上的點(diǎn)集可構(gòu)成一個(gè)群（group）。

橢圓曲線群包括所有曲線上的點(diǎn)以及一個(gè)特殊的點(diǎn)，我們稱其為無(wú)限遠(yuǎn)點(diǎn)

O群定義：若在集合上定義的加法運(yùn)算是封閉的，且滿足交換律和結(jié)合律，我們就稱這個(gè)集合為群。實(shí)數(shù)域橢圓曲線上加法:P+Q加法定律：P+Q=R實(shí)數(shù)域橢圓曲線上加法:P+(-P)加法定律P+(-P)=O實(shí)數(shù)域橢圓曲線上加法：2P加法定律：2P=P+P=R3.2有限域Fq上的橢圓曲線有限域Fq

上的橢圓曲線y2=x3+ax+b，其點(diǎn)集(x,y)構(gòu)成有限域上的Abel群。條件為：4a3+27b2≠0

modq設(shè)P=(x1,y1),Q=(x2,y2),P+Q=(x3,y3)，那么：

舉例說(shuō)明—F23的橢圓曲線

取p=23,a=b=1,則橢圓曲線方程為：y2=x3+x+1

把滿足上式的所有點(diǎn)(x,y)和元素O所組成的點(diǎn)集記為E23(1,1)

對(duì)于E23(1,1)，只關(guān)心滿足模p方程的、從(0,0)到(p-1,p-1)的象限中的非負(fù)整數(shù)。下表列出E23(1,1)若干點(diǎn)(O

點(diǎn)除外)。(0,1)(6,4)(12,19)(0,22)(6,19)(13,7)(1,7)(7,11)(13,16)(1,16)(7,12)(17,3)(3,10)(9,7)(17,20)(3,13)(9,16)(18,3)(4,0)(11,2)(18,20)(5,4)(11,20)(19,5)(5,19)(12,4)(19,18)(9,7)舉例說(shuō)明—F23的橢圓曲線例如：當(dāng)a=1,b=1,p=23時(shí)可滿足(2)式：4×13+27×12=31mod23≠0且x=9,y=7時(shí)，(1)式的兩邊分別為：說(shuō)明：對(duì)于有限域Fp上的橢圓曲線，使用變?cè)拖禂?shù)均在0到p-1的整數(shù)集上取值的三次方程，其中p是大素?cái)?shù)，所執(zhí)行的運(yùn)算均為模p運(yùn)算。舉例說(shuō)明—F23的橢圓曲線舉例說(shuō)明—F23的橢圓曲線例如：E23(1,1)為一橢圓曲線，設(shè)P=(3,10),Q=(9,7)，則：可以求出： x3=112-3-9=109=17mod23 y3=11(3-17)-10=-164=20mod23所以： P+Q=(17,20)可以看出：P+Q仍然為橢圓曲線E23(1,1)上的點(diǎn)。舉例說(shuō)明—F23的橢圓曲線設(shè)P=(3,10)，則2P的計(jì)算為：可以求出： x3=62-3-3=30=7mod23 y3=6(3-7)-10=-34=12mod23所以： 2P=(7,12)可以看出：2P仍然為橢圓曲線E23(1,1)上的點(diǎn)。類似地：我們可以求出：4P=P+P+P+P結(jié)論

從上例可以看出：加法運(yùn)算在E23(1,1)上是封閉的，且還能驗(yàn)證滿足交換律；對(duì)于一般形式的Ep(a,b)，可證明其上的加法運(yùn)算是封閉的，且滿足交換律。同樣，我們還可以證明Ep(a,b)上的加法逆元運(yùn)算也是封閉的。所以，Ep(a,b)是一個(gè)Abel群。3.3建立在橢圓曲線上的密碼為了使用橢圓曲線構(gòu)造公鑰密碼體制，需要找出橢圓曲線上的數(shù)學(xué)難題。在橢圓曲線構(gòu)成的Abel群Ep(a,b)上，考慮方程Q=kP，其中P,Q∈Ep(a,b),k＜p由k和P求Q非常容易；由P,Q求k則非常困難。這就是橢圓曲線上的離散對(duì)數(shù)問(wèn)題—ECDLPDiffie-Hellman以及ElGamal是基于有限域上的離散對(duì)數(shù)問(wèn)題構(gòu)造的公鑰體制，它們也可以采用橢圓曲線來(lái)構(gòu)造。首先取一素?cái)?shù)p≈2180，以及參數(shù)a,b，則橢圓曲線上的點(diǎn)構(gòu)成Abel群Ep(a,b)。取Ep(a,b)上的一個(gè)生成元G(x1,y1)，要求G的階是一個(gè)非常大的數(shù)，G的階是滿足nG=O的最小正整數(shù)。Ep(a,b)和G作為公鑰體制的公開(kāi)密鑰參數(shù)，對(duì)外公布。橢圓曲線上的Diffie-Hellman密鑰交換EC上的Diffie-Hellman密鑰交換算法A選擇一小于n的整數(shù)nA作為私鑰，由PA=nAG產(chǎn)生Ep(a,b)上的一點(diǎn)作為公鑰。B類似地選取自己的私鑰nB，并計(jì)算自己的公鑰PB=nBG。A可以獲得B的公鑰PBB可以獲得A的公鑰PAA計(jì)算：K=nA×

PB=nAnBGB計(jì)算：K=nB×

PA=nAnBG至此，A和B共同擁有密鑰K=nAnBG。攻擊者如果想獲得密鑰K，他就必須由PA和G求出nA，或者由PB和G求出nB，而這等價(jià)于求橢圓曲線上的離散對(duì)數(shù)問(wèn)題ECDLP，因此是不可行的舉例說(shuō)明—EC上的DH密鑰交換算法選擇p=211，E211(0,-4)，即橢圓曲線為y2≡x3-4mod211G=(2,2)是E211(0,-4)上的一個(gè)生成元，階n=241，241G=OA取私鑰為nA=121，可計(jì)算公鑰PA=121×(2,2)=(115,48)B取私鑰為nB=203，可計(jì)算公鑰PB=203×(2,2)=(130,203)A計(jì)算共享密鑰：121×PB=121×(130,203)=(161,169)B計(jì)算共享密鑰：203×PA=203×(115,48)=(161,169)可見(jiàn)，此時(shí)A和B共享密鑰是一對(duì)數(shù)據(jù)。如果在后續(xù)采用單鑰體制加密時(shí)，可以簡(jiǎn)單地取其中的一個(gè)坐標(biāo)，比如x坐標(biāo)，或x坐標(biāo)的一個(gè)簡(jiǎn)單函數(shù)作為共共享的密鑰進(jìn)行加密/解密運(yùn)算。RSA算法與ECC算法比較ECC標(biāo)準(zhǔn)(Drafts&Proposals)ANSIX9:62,63,92