第04章橢圓曲線密碼體制ECC課件

橢圓曲線密碼（ECC）體制

一般橢圓曲線

有限域上的橢圓曲線

橢圓曲線密碼算法

橢圓曲線密碼體制的安全性

ELGamal密碼體制能夠在任何離散對數(shù)難處理的有限群中實現(xiàn)。我們已經(jīng)使用了乘法群Zp*，但其他群也是合適的候選者，如橢圓曲線群。橢圓曲線在代數(shù)學和幾何學上已廣泛研究了150多年之久，有豐富而深厚的理論積累。橢圓曲線密碼體制（EllipseCurveCryptosystem，ECC）在l985年由Koblitz和Miller提出，不過一直沒有像RSA等密碼系統(tǒng)一樣受到重視?？v觀目前的發(fā)展趨勢，橢圓曲線已經(jīng)逐漸被采用，很可能是一個重要的發(fā)展方向。

橢圓曲線并非橢圓，這么命名是因為它們是由三次方程描述的，而這些三次方程類似于計算橢圓周長的方程。一般的，描述橢圓曲線方程的形式是

y2+axy+by=x3+cx2+dx+e

其中a、b、c、d和e是滿足一些簡單條件的實數(shù)一般來說，橢圓曲線還包含了一個特殊的點，即稱為無窮遠點(PointatInfinity)或零點(ZeroPoint)的O。4.4.1一般橢圓曲線

對于橢圓曲線上的點可以定義一種形式的加法：如果一個橢圓曲線上的三個點處于一條直線上，那么它們的和為O。從這個定義可以導出橢圓曲線上點的加法法則。(1)O是加法的單位元，因而O＝－O；對于橢圓曲線上的任何一點P，有P+O＝P。(2)一條與x軸垂直的線和曲線相交于兩個x坐標相同的點P1=(x，y)和P2＝(x,－y)，同時它也和曲線相交于無窮遠點，因此P1+P2+O＝O。因而一個點的負值是與其有著相同x坐標和相反的y坐標的點，如圖4.1(a)所示。(3)要對具有不同x坐標的兩個點Q與R進行相加，先在它們之間畫一條直線并求出第三個交點P1。容易看出這種交點是惟一的。注意到Q+R+P1＝O，有Q+R＝－P。特別地，當Q=R時，相當于對一個點Q加倍，只需畫出一條切線并求出另一個交點S，那么Q+Q=2Q=－S。顯然，根據(jù)定義，此類加法滿足交換率和結合率.而一個點的倍乘定義為nP＝P+P+P+……+P橢圓曲線E23(1，1)上的點（0，1）（5，4）（9，7）（17，3）（0，22）（5，19）（11，3）（17，20）（1，7）（6，4）（11，20）（18，3）（1，16）（6，19）（12，19）（18，20）（3，10）（7，12）（12，4）（19，5）（3，13）（7，11）（13，7）（19，18）（4，0）（9，16）（13，16）Ep(a，b)上的加法規(guī)則P十O＝P；如果P＝(x,y)，則P+(x,y)=O，點(x，－y)是P的加法逆元，記為－P；如果P＝(x1，y1)，Q＝(x2，y2)，并且P≠Q(mào)，則P+Q=(x3，y3)由下列規(guī)則確定:x3≡λ2–x1–x2(modp)y3≡λ(x1–x3)–y1(modp)其中：(y2-y1)/(x2－x1)如果P≠Q(mào)λ=(3x12－a)/2y1如果P=Q例子：考慮P=(3,10),Q=(9,7)則：λ=(7－10)/(9－3)=－3/6=－1/2=11mod23x3=112－3－9=10917mod23y3=11(3－(－6))－10=89=20mod23因而P+Q=(17,20).計算2P:λ=(3(32)+1)/(2*10)=5/20=1/4=6mod23x3=62－3－3=30=7mod23y3=6(3－7)－10=－34=12mod23因此2P=(7,12)

橢圓曲線群中的離散對數(shù)也屬于難解問題。與通常理解的對數(shù)概念不同，由于橢圓曲線群中的運算是加法，加法的倍數(shù)對應于原來乘法的指數(shù)，因而橢圓曲線群中的離散對數(shù)問題是指已知群中的Q和R，求解方程：

R＝kQ中k值的問題。

對基于F23的橢圓群y2＝x3+9x+17，求R=(4，5)對于Q=(16，5)的離散對數(shù),最直接的方法就是計算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關于Q的離散對數(shù)是9，對于大素數(shù)構成的群Fp，這樣計算離散對數(shù)是不現(xiàn)實的，事實上現(xiàn)在也沒有更好的(非指數(shù)級的)算法來解離散對數(shù)問題。4.4.3橢圓曲線密碼算法

基于上面講的橢圓群上的離散對數(shù)問題，可以用橢圓曲線密碼(ECC)算法加密，具體方法如下：

首先選擇—個點G和一個橢圓群Ep(a,b)作為參數(shù)，用戶A選擇一個私有密鑰nA并產(chǎn)生一個公開密鑰PA=nAG。發(fā)送者要加密并發(fā)送一個報義Pm給A，可選擇一個隨機整數(shù)k，并產(chǎn)生由如下點對組成的密文

Cm＝(kG，Pm+kPA)。注意這里使用了A的公開密鑰PA。要解密這個報文，A用這個點對的第一個點乘以A的私有密鑰，再從第二個點中減去這個值

Pm+kPA–nA(kG)=Pm+k(nAG)–nA(kG)=Pm

發(fā)送者通過對Pm加上kPA來保護Pm。除了發(fā)送者之外沒有人知道k的值，因此即便PA是公開密鑰也沒有人能去掉kPA，當然只有知道nA的人才可以去掉kPA。攻擊者在不知道nA的情況下要想得到報文只能在知道G和kG的情況下計算出k，這歸結為求解橢圓曲線離散對數(shù)問題，是非常困難的。

1、用戶A選定一條橢圓曲線Ep(a,b)，并取橢圓曲線上一點，作為基點G。2、用戶A選擇一個私有密鑰nA，并生成公開密鑰PA=nAG。3、用戶A將Ep(a,b)和點PA，G傳給用戶B。4、用戶B接到信息后，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點Pm，并產(chǎn)生一個隨機整數(shù)k（k<n,n為基點G的階）。5、用戶B計算點C1=Pm+kPA；C2=kG。6、用戶B將C1、C2傳給用戶A。7、用戶A接到信息后，計算C1-nAC2，結果就是點Pm。因為Pm+kPA–nA(kG)=Pm+k(nAG)–nA(kG)=Pm再對點Pm進行解碼就可以得到明文。利用橢圓曲線進行加密通信的過程：

這個加密通信中，如果有一個偷窺者H，他只能看到Ep(a,b)、PA、G、C1、C2而通過K、G求nA或通過C2、G求k都是相對困難的。因此，H無法得到A、B間傳送的明文信息。

注意到以上的過程并沒有說明怎樣將作為字符串(當然可以看成分段的整數(shù))的消息編碼嵌入到橢圓群的點中(將明文嵌入橢圓曲線)，實際中的轉化方式多種多樣，關鍵的步驟與其正確性證明都涉及到復雜的數(shù)學推導，可以參看相關文獻。4.4.4橢圓曲線密碼體制的安全性

橢圓曲線密碼體制的安全性依賴于求解橢圓曲線離散對數(shù)問題的困難性，即已知橢圓曲線上的點P和kP計算k的困難程度。下圖比較了目前計算橢圓曲線對數(shù)和分解大數(shù)因子的難度?？梢钥闯?，與RSA相比，ECC可以用小得多的密鑰取得與RSA相同的安全性。另外，在密鑰大小相等時，ECC與RSA所需要的計算量相當。因此，在安全性相當?shù)那闆r下，使用ECC比使用RSA具有計算上的優(yōu)勢。兩者都可以用于加解密、密鑰交換和數(shù)字簽名。橢圓曲線和RSA安全性的比較密鑰大小150205234MIPS年3.8*10107.1*10181.6*1028密鑰大小5127681024128015362048MIPS年3*1042*1083*10111*10143*10163*1020MIPS:

T=(p，a，b，G，n，h)。（p、a、b用來確定一條橢圓曲線，G為基點，n為點G的階，h是橢圓曲線上所有點的個數(shù)m與n相除的整數(shù)部分）這幾個參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：

1、p當然越大越安全，但越大，計算速度會變慢，200位左右可以滿足一般安全要求；2、p≠n×h；3、pt≠1(modn)，1≤t<20；4、4a3+27b2≠0(modp)；5、n為素數(shù)；6、h≤4。密碼學描述一條Fp上的橢圓曲線用到六個參量：橢圓曲線在軟件注冊保護的應用

將公開密鑰算法作為軟件注冊算法的好處是Cracker很難通過跟蹤驗證算法得到注冊機。

軟件作者按如下方法制作注冊機（也稱為簽名過程）1、選擇一條橢圓曲線Ep(a,b)，和基點G；2、選擇私有密鑰nA（nA<n，n為G的階），利用基點G計算公開密鑰PA=nAG；3、產(chǎn)生一個隨機整數(shù)k（k<n），計算點R=kG；4、將用戶名和點R的坐標值x,y作為參數(shù)，計算SHA（SecureHashAlgorithm安全散列算法，類似于MD5）值，即Hash=SHA(username,x,y)；5、計算sn≡k－Hash*nA(modn)6、將sn和Hash作為用戶名username的序列號

軟件驗證過程如下：（軟件中存有橢圓曲線Ep(a,b)，和基點G，公開密鑰PA）

1、從用戶輸入的序列號中，提取sn以及Hash；2、計算點R≡sn*G+Hash*PA(modp)，如果sn、Hash正確，其值等于軟件作者簽名過程中點R(x,y)的坐標，因為sn≡k-Hash*nA（modn）所以sn*G+Hash*PA

=(k-Hash*nA)*G+Hash*PA

=kG-Hash*nAG+Hash*PA

=kG-Hash*PA+Hash*PA

=kG=R；3、將用戶名和點R的坐標值x,y作為參數(shù)，計算H=SHA(username,x,y)；4、如