橢圓曲線密碼體制E.ppt

橢圓曲線密碼（ECC）體制,一般橢圓曲線 有限域上的橢圓曲線 橢圓曲線密碼算法 橢圓曲線密碼體制的安全性,ELGamal密碼體制能夠在任何離散對(duì)數(shù)難處理的有限群中實(shí)現(xiàn)。我們已經(jīng)使用了乘法群Zp*，但其他群也是合適的候選者，如橢圓曲線群。 橢圓曲線在代數(shù)學(xué)和幾何學(xué)上已廣泛研究了150多年之久，有豐富而深厚的理論積累。橢圓曲線密碼體制（Ellipse Curve Cryptosystem，ECC）在l 985年由Koblitz和Miller提出，不過(guò)一直沒(méi)有像RSA等密碼系統(tǒng)一樣受到重視?？v觀目前的發(fā)展趨勢(shì)，橢圓曲線已經(jīng)逐漸被采用，很可能是一個(gè)重要的發(fā)展方向。,橢圓曲線并非橢圓，這么命名是因?yàn)樗鼈兪怯扇畏匠堂枋龅?，而這些三次方程類似于計(jì)算橢圓周長(zhǎng)的方程。一般的，描述橢圓曲線方程的形式是 y2 + axy + by = x3 + cx2 + dx + e 其中a、b、c、d和e是滿足一些簡(jiǎn)單條件的實(shí)數(shù) 一般來(lái)說(shuō)，橢圓曲線還包含了一個(gè)特殊的點(diǎn)，即稱為無(wú)窮遠(yuǎn)點(diǎn)(Point at Infinity)或零點(diǎn)(Zero Point)的O。,4.4.1 一般橢圓曲線,對(duì)于橢圓曲線上的點(diǎn)可以定義一種形式的加法：如果一個(gè)橢圓曲線上的三個(gè)點(diǎn)處于一條直線上，那么它們的和為O。從這個(gè)定義可以導(dǎo)出橢圓曲線上點(diǎn)的加法法則。 (1) O是加法的單位元，因而OO；對(duì)于橢圓曲線上的任何一點(diǎn)P，有P+OP。 (2) 一條與x軸垂直的線和曲線相交于兩個(gè)x坐標(biāo)相同的點(diǎn)P1=(x，y)和P2(x,y)，同時(shí)它也和曲線相交于無(wú)窮遠(yuǎn)點(diǎn)，因此P1+P2+OO。因而一個(gè)點(diǎn)的負(fù)值是與其有著相同x坐標(biāo)和相反的y坐標(biāo)的點(diǎn)，如圖4.1(a)所示。,(3)要對(duì)具有不同x坐標(biāo)的兩個(gè)點(diǎn)Q與R進(jìn)行相加，先在它們之間畫(huà)一條直線并求出第三個(gè)交點(diǎn)P1。容易看出這種交點(diǎn)是惟一的。 注意到Q+R+P1O，有Q+RP。 特別地，當(dāng)Q=R時(shí)，相當(dāng)于對(duì)一個(gè)點(diǎn)Q加倍，只需畫(huà)出一條切線并求出另一個(gè)交點(diǎn)S，那么Q+Q=2Q=S。 顯然，根據(jù)定義，此類加法滿足交換率和結(jié)合率.而一個(gè)點(diǎn)的倍乘定義為 nPP+P+P+P,4.4.2 有限域上的橢圓曲線,密碼學(xué)中關(guān)心的是有限域F上的橢園曲線。討論比較多的是素域Fp上的橢圓曲線，這里P是一個(gè)素?cái)?shù)。選擇兩個(gè)小于P的非負(fù)整數(shù)a和b滿足 4a3 + 27b2 (mod p) 0 用Ep(a，b)表示如下模p的橢圓群中的點(diǎn)(或如下有限域Fp上的橢圓曲線的點(diǎn))，再加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O。 設(shè)(x，y)是Ep(a，b)中的點(diǎn)，x和y是小于p的非負(fù)整數(shù)，則有如下橢圓曲線方程： y2 x3 + ax + b (mod p),如取p23，a=b=l，有 4*13 + 27 * 12 (mod 23 ) 8 0， 則y2=x3 + x +1 是橢圓曲線。因此E23(1，1)是一個(gè)模23的橢圓群。產(chǎn)生E23 (1，1)是中點(diǎn)的過(guò)程如下： (1) 對(duì)x=0,1,2,p-1, 計(jì)算x3 + x +1 (mod p)； (2)對(duì)于上一步驟得到的每個(gè)結(jié)果確定它是否有一個(gè)模P的平方根，如果沒(méi)有，則E23 (1，1)中沒(méi)有具有與該結(jié)果相應(yīng)的x坐標(biāo)的點(diǎn)。如果有，就有兩個(gè)平方根y和py，從而點(diǎn)(x，y)和(x，py)是E23 (1，1)中的點(diǎn)(特別情況下，如果結(jié)果是0，只有一個(gè)點(diǎn)(x，0)。,橢圓曲線E23(1，1)上的點(diǎn),Ep(a，b)上的加法規(guī)則,P十OP； 如果P(x , y)，則P + ( x , y) =O，點(diǎn)(x，y)是P的加法逆元，記為 P； 如果P(x1，y1)，Q(x2，y2)，并且PQ，則P + Q = (x3，y3)由下列規(guī)則確定: x32 x1 x2 ( mod p ) y3 ( x1 x3) y1 (mod p ) 其中： (y2-y1)/(x2x1) 如果PQ = (3x12a)/2y1 如果 P=Q,例子：,考慮P=(3,10) , Q=(9,7) 則： =(710)/(93)=3/6=1/2=11 mod 23 x3=11239=109 17 mod 23 y3=11(3(6)10=89 =20 mod 23 因而P+Q=(17,20). 計(jì)算2P: =(3(32)+1)/(2*10)=5/20=1/4=6 mod 23 x3=6233=30=7 mod 23 y3=6(37)10=34= 12 mod 23 因此 2P=(7,12),橢圓曲線群中的離散對(duì)數(shù)也屬于難解問(wèn)題。與通常理解的對(duì)數(shù)概念不同，由于橢圓曲線群中的運(yùn)算是加法，加法的倍數(shù)對(duì)應(yīng)于原來(lái)乘法的指數(shù)，因而橢圓曲線群中的離散對(duì)數(shù)問(wèn)題是指已知群中的Q和R，求解方程： RkQ 中k值的問(wèn)題。,對(duì)基于F23的橢圓群y2x3 + 9x + 17，求R=(4，5)對(duì)于Q=(16，5)的離散對(duì)數(shù),最直接的方法就是計(jì)算Q的倍數(shù)，直到找到R。 Q(16，5)，2Q=(20，20)，3Q(14，14), 4Q=(19，20)，5Q(13，10)， 6Q(7，3)， 7Q(8，7)，8Q(12，17)，9Q(4，5) 因此k關(guān)于Q的離散對(duì)數(shù)是9，對(duì)于大素?cái)?shù)構(gòu)成的群Fp，這樣計(jì)算離散對(duì)數(shù)是不現(xiàn)實(shí)的，事實(shí)上現(xiàn)在也沒(méi)有更好的(非指數(shù)級(jí)的)算法來(lái)解離散對(duì)數(shù)問(wèn)題。,4.4.3 橢圓曲線密碼算法,基于上面講的橢圓群上的離散對(duì)數(shù)問(wèn)題，可以用橢圓曲線密碼(ECC)算法加密，具體方法如下： 首先選擇個(gè)點(diǎn)G和一個(gè)橢圓群Ep(a,b)作為參數(shù)，用戶A選擇一個(gè)私有密鑰nA并產(chǎn)生一個(gè)公開(kāi)密鑰PA=nAG。 發(fā)送者要加密并發(fā)送一個(gè)報(bào)義Pm給A，可選擇一個(gè)隨機(jī)整數(shù)k，并產(chǎn)生由如下點(diǎn)對(duì)組成的密文 Cm(kG，Pm+kPA)。 注意這里使用了A的公開(kāi)密鑰PA。要解密這個(gè)報(bào)文，A用這個(gè)點(diǎn)對(duì)的第一個(gè)點(diǎn)乘以A的私有密鑰，再?gòu)牡诙€(gè)點(diǎn)中減去這個(gè)值 Pm + kPA nA (kG) =Pm + k(nAG) nA (kG) =Pm,發(fā)送者通過(guò)對(duì)Pm加上kPA來(lái)保護(hù)Pm。除了發(fā)送者之外沒(méi)有人知道k的值，因此即便PA是公開(kāi)密鑰也沒(méi)有人能去掉kPA，當(dāng)然只有知道nA的人才可以去掉kPA。攻擊者在不知道nA的情況下要想得到報(bào)文只能在知道G和kG的情況下計(jì)算出k，這歸結(jié)為求解橢圓曲線離散對(duì)數(shù)問(wèn)題，是非常困難的。,1、用戶A選定一條橢圓曲線Ep(a,b)，并取橢圓曲線上一點(diǎn)，作為基點(diǎn)G。 2、用戶A選擇一個(gè)私有密鑰nA，并生成公開(kāi)密鑰PA=nAG。 3、用戶A將Ep(a,b)和點(diǎn)PA，G傳給用戶B。 4、用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點(diǎn)Pm ，并產(chǎn)生一個(gè)隨機(jī)整數(shù)k（kn, n為基點(diǎn)G的階）。 5、用戶B計(jì)算點(diǎn)C1= Pm +kPA；C2=kG。 6、用戶B將C1、C2傳給用戶A。 7、用戶A接到信息后，計(jì)算C1-nAC2，結(jié)果就是點(diǎn)Pm 。因?yàn)?Pm + kPA nA (kG) =Pm + k(nAG) nA (kG) =Pm 再對(duì)點(diǎn)Pm進(jìn)行解碼就可以得到明文。,利用橢圓曲線進(jìn)行加密通信的過(guò)程：,這個(gè)加密通信中，如果有一個(gè)偷窺者H ，他只能看到Ep(a,b)、 PA 、G、C1、C2 而通過(guò)K、G 求nA 或通過(guò)C2、G求k 都是相對(duì)困難的。因此，H無(wú)法得到A、B間傳送的明文信息。,注意到以上的過(guò)程并沒(méi)有說(shuō)明怎樣將作為字符串(當(dāng)然可以看成分段的整數(shù))的消息編碼嵌入到橢圓群的點(diǎn)中(將明文嵌入橢圓曲線)，實(shí)際中的轉(zhuǎn)化方式多種多樣，關(guān)鍵的步驟與其正確性證明都涉及到復(fù)雜的數(shù)學(xué)推導(dǎo)，可以參看相關(guān)文獻(xiàn)。,4.4.4 橢圓曲線密碼體制的安全性,橢圓曲線密碼體制的安全性依賴于求解橢圓曲線離散對(duì)數(shù)問(wèn)題的困難性，即已知橢圓曲線上的點(diǎn)P和kP計(jì)算k的困難程度。 下圖比較了目前計(jì)算橢圓曲線對(duì)數(shù)和分解大數(shù)因子的難度?？梢钥闯?，與RSA相比，ECC可以用小得多的密鑰取得與RSA相同的安全性。另外，在密鑰大小相等時(shí)，ECC與RSA所需要的計(jì)算量相當(dāng)。 因此，在安全性相當(dāng)?shù)那闆r下，使用ECC比使用RSA具有計(jì)算上的優(yōu)勢(shì)。兩者都可以用于加解密、密鑰交換和數(shù)字簽名。,橢圓曲線和RSA安全性的比較,MIPS:,T=(p，a，b，G，n，h)。 （p 、a 、b 用來(lái)確定一條橢圓曲線，G為基點(diǎn)，n為點(diǎn)G的階， h 是橢圓曲線上所有點(diǎn)的個(gè)數(shù)m與n相除的整數(shù)部分） 這幾個(gè)參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個(gè)條件： 1、p 當(dāng)然越大越安全，但越大，計(jì)算速度會(huì)變慢，200位左右可以滿足一般安全要求； 2、pnh； 3、pt1 (mod n)，1t20； 4、4a3+27b20 (mod p)； 5、n 為素?cái)?shù)； 6、h4。,密碼學(xué)描述一條Fp上的橢圓曲線用到六個(gè)參量：,橢圓曲線在軟件注冊(cè)保護(hù)的應(yīng)用,將公開(kāi)密鑰算法作為軟件注冊(cè)算法的好處是Cracker很難通過(guò)跟蹤驗(yàn)證算法得到注冊(cè)機(jī)。 軟件作者按如下方法制作注冊(cè)機(jī)（也稱為簽名過(guò)程） 1、選擇一條橢圓曲線Ep(a,b)，和基點(diǎn)G； 2、選擇私有密鑰nA（nAn，n為G的階），利用基點(diǎn)G計(jì)算公開(kāi)密鑰PA=nAG； 3、產(chǎn)生一個(gè)隨機(jī)整數(shù)k（kn），計(jì)算點(diǎn)R=kG； 4、將用戶名和點(diǎn)R的坐標(biāo)值x,y作為參數(shù)，計(jì)算SHA（Secure Hash Algorithm 安全散列算法，類似于MD5）值，即Hash=SHA(username,x,y)； 5、計(jì)算snk Hash *nA (mod n) 6、將sn和Hash作為用戶名username的序列號(hào),軟件驗(yàn)證過(guò)程如下： （軟件中存有橢圓曲線Ep(a,b)，和基點(diǎn)G，公開(kāi)密鑰PA） 1、從用戶輸入的序列號(hào)中，提取sn以及Hash； 2、計(jì)算點(diǎn)Rsn*G+Hash*PA ( mod p )，如果sn、Hash正確，其值等于軟件作者簽名過(guò)程中點(diǎn)R(x,y)的坐標(biāo)，因?yàn)?snk-Hash*nA （mod n） 所以 sn*G + Hash*PA =(k-Hash*nA)*G+Hash*PA =kG-Hash*nAG+Hash*PA =kG- Hash*PA+ Hash*PA =kG=R ； 3、將用戶名和點(diǎn)R的坐標(biāo)值x,y作為參數(shù)，計(jì)算 H=SHA(username,x,