第10章橢圓曲線密碼體制10.1實數(shù)域上的橢圓曲線10.2有限域上的橢圓曲線10.3橢圓曲線加解密算法10.4基于橢圓曲線的Diffie-Hellman密鑰協(xié)商協(xié)議10.5橢圓曲線數(shù)字簽名算法10.6ECC攻擊方法

橢圓曲線密碼學(EllipticCurveCryptography,ECC)是基于橢圓曲線數(shù)學理論和離散對數(shù)問題的一種公鑰密碼算法。相比RSA,ECC可以使用更短的密鑰來實現(xiàn)更安全和更高效的加解密算法。

10.1實數(shù)域上的橢圓曲線

10.1.1實數(shù)域上橢圓曲線的定義

橢圓曲線被描述為一個二元方程解的集合。在實數(shù)域中,一般橢圓曲線可定義為滿足Weierstrass標準型方程的所有點外加一個無窮遠點O的集合E,即其中,約束條件4a3+27b2≠0是為了保證橢圓曲線沒有奇異點,即處處光滑可導。

圖10.1給出y2=x3-x+2的橢圓曲線,可以看出橢圓曲線關于x軸對稱。圖10.1橢圓曲線示例(a=-1,b=2)

橢圓曲線的定義要求曲線是非奇異的,從幾何上來說意味著圖像沒有尖點、自相交點或孤立點。橢圓曲線滿足非奇異要求是因為數(shù)乘運算需要用到切線,而曲線奇點處沒有切線,無法進行計算。

圖10.2給出了無效的橢圓曲線實例,其中左側帶尖角的曲線為y2=x3,右側帶一個自交叉點的曲線為y2=x3-3x+2。

圖10.2無效橢圓曲線

10.1.2實數(shù)域上橢圓曲線的群法則

1.橢圓曲線阿貝爾(Abel)群

基于實數(shù)域上橢圓曲線的點集及其加法運算,可以定義一個群(G,+),該群滿足以下條件。

(1)封閉性:元素是橢圓曲線上的點,且加法運算得到的點也都在橢圓曲線上,即?A、B∈G,A+B∈G。

(2)單位元:選取無窮遠點O為單位元,?P∈G,有P+O=P。

(3)逆元:?P∈G,?-P∈G,使得P+(-P)=O,點P與-P關于x軸對稱。

(4)交換律:繪制一條與橢圓曲線相交于三點的直線,記交點為P、Q、R,則P+Q+R=O,且三點加法滿足交換律,即該群關于加法運算滿足交換律。

(5)結合律:?P、Q、R∈G,有(P+Q)+R=P+(Q+R)。

由此可知,橢圓曲線上的點關于加法運算構成一個阿貝爾群。

2.幾何加法

根據(jù)P+Q+R=O,可以得到計算兩個點P和Q相加的幾何方法:任取橢圓曲線上的兩個點P、Q,過這兩點作直線,交橢圓曲線于另一點R,過R作x軸的垂線,與橢圓曲線交于點-R,則逆元-R=P+Q,如圖10.3所示。

圖10.3幾何加法

當P=Q時,即兩點重合時,過該點作橢圓曲線的切線,交橢圓曲線于點R,則其逆-R=P+Q=P+P=2P=-R,如圖10.4所示。圖10.4P=Q時幾何加法

當P=-Q時,經過這兩點的直線垂直于x軸,與橢圓曲線無第三個交點,但因P是Q的逆元,根據(jù)逆元的定義有P+Q=P+(-P)=O,

為無窮遠點,如圖10.5所圖10.5P=-Q時幾何加法

3.代數(shù)加法

橢圓曲線幾何加法比較直觀,但代數(shù)加法更有利于數(shù)值計算,需要注意的是代數(shù)加法并不是兩個點坐標的簡單相加。

過橢圓曲線上的兩個點P=(x1,y1)、Q=(x2,y2)作直線,求曲線第三個交點R=(x3,y3)的問題用代數(shù)方法很容易解決,具體推導過程如下。

1)求直線PQ的方程

2)將直線PQ方程代入橢圓曲線

將y=kx+c代入y2=x3+ax+b得:

轉成標準式得:

由此可得,只要求出一元三次方程的根即可得到第三個交點。

3)韋達定理及其證明

韋達定理給出了一元n次方程根與系數(shù)的關系。對于一元三次方程ax3+bx2+cx+d=0,假設p、q和r是該方程的三個根,則:

而方程ax3+bx2+cx+d=0兩邊同除以a得

對比式(10.4)和式(10.5)可得到根與系數(shù)的關系:

4)根據(jù)韋達定理求第三個交點

由式(10.3)和式(10.6)得:

所以R的橫坐標:

R的縱坐標:

-R的縱坐標:

5)代數(shù)加法總結

設P=(x1,y1),Q=(x2,y2),則P+Q=(x3,y3)由以下規(guī)則確定:

【例10-1】給定實數(shù)域上橢圓曲線y2=x3-7x+10,P=(1,2),Q=(3,4),計算P+Q和2P。

因為P≠Q,根據(jù)代數(shù)加法規(guī)則有:

所以P+Q=(-3,2)

2P=P+P,根據(jù)代數(shù)加法規(guī)則得:

所以2P=(-1,-4)。

4.標量乘法

設P=(x,y)為橢圓曲線上的一個點,則數(shù)乘運算

利用上述代數(shù)運算計算標量乘法需要進行k-1次加法,可利用倍增加(double-and-add)算法降低計算的復雜度。下面舉例說明該算法的原理。

利用Python實現(xiàn)double-and-add算法,代碼如下:

5.對數(shù)問題

令Q=nP,已知n、P,則可以使用多項式時間復雜度的算法double-and-add來計算Q=nP,但是若已知P、Q,欲快速求解n則是比較困難的,該問題稱作對數(shù)問題。實數(shù)域中曲線連續(xù),找到一些規(guī)律來破解對數(shù)問題相對容易。在實際應用中,常將橢圓曲線限制在有限域內,將曲線變成離散的點,這樣既方便了計算,也加大了破解難度。

10.2有限域上的橢圓曲線

10.2.1有限域設F為非空集合,F內定義兩種二元運算,加法運算“+”和乘法運算“·”,并滿足以下條件,則稱F關于“+”和“·”構成一個域,記作(F,+,·)。(1)F關于加法運算“+”構成阿貝爾群;(2)F關于乘法運算“·”構成阿貝爾群;(3)乘法對加法運算滿足分配律。

【例10-4】(R,+,·)是一個域,稱為實數(shù)域。

如果一個域中元素數(shù)量是有限的,則該域為有限域,又稱伽羅瓦域。有限域中元素的個數(shù)稱為有限域的階。

對素數(shù)p取模運算的整數(shù)域是最常見的有限域之一,通常可表示為Fp、GF(p)等。Fp是定義在整數(shù)集合{0,1,2,…,p-1}上的域,Fp

上的加法和乘法定義為模p加法和模p乘法。

10.2.2有限域上橢圓曲線的定義

為了安全性和便于實現(xiàn),密碼學中需將橢圓曲線限制到一個有限域內,通常用的是模素數(shù)p的整數(shù)域Fp,任意點P=(x,y)滿足x,y∈0,1,…,p-1,其中p為素數(shù)。

有限域上的橢圓曲線定義為如下點集:

其中,a、b為Fp域上的兩個整數(shù),O為無窮遠點。

以下Python代碼實現(xiàn)F97域上橢圓曲線y2=x3-x+2的幾何圖形的繪制(見圖10.6),可以發(fā)現(xiàn)橢圓曲線變成了離散的點集。圖10.6F97域上橢圓曲線y2=x3-x+2

10.2.3有限域上橢圓曲線的群運算

1.求解Fp域上橢圓曲線的點集

設Ep(a,b)表示橢圓曲線上的點集:

其中,a,b為橢圓曲線的參數(shù),求Ep(a,b)點集的步驟如下:

(1)對每一個x(0≤x<p,且x為整數(shù)),計算x3+ax+b(modp)。

(2)確定(1)中求得的值在模p下是否有平方根,計算y2modp。如果沒有,則曲線上沒有與這一x相對應的點;如果有,則求出兩個平方根(y=0時只有一個平方根)。

【例10-5】

E11(1,6)表示橢圓曲線y2=x3+x+6,求該曲線上的所有點。

對每一個x(0≤x<11,且x為整數(shù)),計算x3+x+6(mod11),并判斷所求出的值是否為模11的平方剩余,若是則求出對應的y。

歐拉判別法可以判斷一個數(shù)a是否是模p的平方剩余。若p是奇素數(shù),且(a,p)=1,則判定a是模p的平方剩余的充要條件是:

表10.1給出了計算點集的過程。

因此,點集E11(1,6)為表10.1得到的點再加上一個無窮遠點,即E11(1,6)={(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),O}

使用Python求解上述橢圓曲線的點集,代碼如下:

2.Fp域上橢圓曲線的幾何加法

有限域上的橢圓曲線是由一些離散的點組成的,離散點之間的加法和實數(shù)域中類似。實數(shù)域中同一直線上三個點P、Q、R之和為0,有限域中則是滿足ax+by+c≡0(modp)的點的集合。

【例10-6】給定橢圓曲線y2≡x3-x+3(mod127),且P=(16,20)、Q=(41,120),畫出-R=P+Q幾何加法示意圖。

繪制出橢圓曲線的圖像,用“o”表示,直線PQ的方程為y=4x-44,繪制y≡4x-44mod127(0≤x<127,且x為整數(shù))的直線,用“*”表示,觀察直線與橢圓曲線的交點即可得到-R的逆元R,-R與R關于y=63.5對稱。P、Q、R、-R在圖中用“”表示。F127域上橢圓曲線的幾何加法如圖10.7所示。

圖10.7F127域上橢圓曲線的幾何加法

3.Fp域上橢圓曲線的代數(shù)加法

Fp

域上橢圓曲線代數(shù)加法規(guī)則和實數(shù)域上的加法規(guī)則類似,只是加法運算是基于模運算。

4.Fp域上橢圓曲線的標量乘法

設P=(x,y)為Fp域橢圓曲線上的一個點,則標量乘法

仍然可用double-and-add算法將標量乘法運算的時間復雜度控制在O(logk)。

【例10-8】給定橢圓曲線y2≡x3+2x+3(mod97),點P=(3,6),計算nP,n∈(0,1,…,p-1)。計算結果如圖10.8所示,可以發(fā)現(xiàn),nP的取值只有5個,且重復出現(xiàn),所以P的倍數(shù)在加法運算下是封閉的,由此得出一個重要結論:取Fp域橢圓曲線上

的任意一個點P,所有P的倍數(shù)構成的集合是定義在Fp域上橢圓曲線群的一個循環(huán)子群。

圖10.8標量乘

10.2.4Fp域上橢圓曲線群的階及循環(huán)子群的階

Fp域上橢圓曲線的點集Ep(a,b)關于其上的加法運算構成阿貝爾群,因為其上加法運算滿足封閉性、結合律、交換律、存在單位元、所有元素均有逆元。

橢圓曲線群的元素數(shù)量是有限的,元素的個數(shù)就是群的階。

Hasse定理:給定一個橢圓曲線Ep(a,b),N表示橢圓曲線上點的個數(shù),則N的范圍滿足:

循環(huán)子群的階:P為Fp域橢圓曲線上的點,使得NP=O(O為無窮遠點)的最小正整數(shù)N為點P的階。點P生成的循環(huán)子群的階即為橢圓曲線群中點P的階。循環(huán)子群的階為橢圓曲線群階的因子。

【例10-9】給定F37上橢圓曲線y2=x3-x+3,求橢圓曲線群的階和點P=(2,3)的階。

10.2.5基于橢圓曲線的離散對數(shù)問題

建立基于橢圓曲線的加密機制需要找到類似RSA大數(shù)分解這樣的難題,而橢圓曲線上離散對數(shù)是數(shù)學上的一個難題,因此可利用這一點構建橢圓曲線密碼體制。

橢圓曲線離散對數(shù)問題(EllipticCurveDiscreteLogarithmProblem,ECDLP)定義如下:

給定素數(shù)p,有限域Fp,橢圓曲線E,橢圓曲線上的兩個點P、Q,Q=kP,k為整數(shù),則有

(1)給定k、P,根據(jù)標量乘法和加法法則,計算Q很容易;

(2)但給定P、Q,求k非常困難。在ECC實際應用中素數(shù)p非常大,窮舉k非常困難。

【例10-10】給定F73上的橢圓曲線E:y2=x3+8x+7,已知其上有點P=(32,53)和點Q=(39,17),且Q=kP,利用Sage計算k。

10.3橢圓曲線加解密算法

10.3.1ECC加解密過程根據(jù)上述橢圓曲線的運算規(guī)則,基于橢圓曲線的加密和解密算法如下。(1)Alice選定一條橢圓曲線Ep(a,b),并取曲線上的某個點作為基點G;(2)Alice選擇一個私鑰d,并生成公鑰P=dG;(3)Alice將橢圓曲線Ep(a,b)、基點G和公鑰P發(fā)送給Bob;

(4)Bob收到消息后,將待傳輸?shù)拿魑膍編碼到橢圓曲線Ep(a,b)上的一點M,并生成一個隨機整數(shù)k(k<n,n為G的階);

(5)Bob計算點C1=kG,C2=M+kP;

(6)Bob將密文(C1,C2)發(fā)送給Alice;

(7)Alice收到消息后,計算點M'=C2-dC1=M+kP-dkG=M+kP-kP=M,M'解碼后即為明文。

橢圓曲線加解密過程如圖10.9所示。

在橢圓曲線加密解密過程中,攻擊者從信道中能截獲的信息有Ep(a,b))、P、G、C1和C2,而通過P、G求私鑰d,或者通過C1、C2求k都是困難的,因此攻擊者無法恢復明文。

圖10.9橢圓曲線加解密過程

【例10-11】取橢圓曲線E11(1,6),即y2≡x3+x+6mod11,基點G=(2,7),Alice的私鑰dA=7。假設Bob發(fā)送給Alice的消息為m=(10,9),選擇的隨機數(shù)k=3,請給出Bob加密和Alice解密的過程。

解:Alice生成自己的公鑰:PA=7G=(7,2);Bob使用Alice的公鑰加密消息m:C1=kG=(8,3),C2=m+kPA=(10,9)+(3,5)=(10,2),得到加密數(shù)據(jù)C={(8,3),(10,2)};Alice接收到密文C,使用自己的私鑰dA=7解密:m=C2-dAC1=(10,2)-(8,3)=(10,2)+(3,6)=(10,9)。

上述參數(shù)值的選取直接影響密碼的安全性,參數(shù)值一般應滿足以下條件。

(1)p越大越安全,但是越大計算速度會越慢,200位可以滿足一般安全要求;

(2)p≠n×h;

(3)pt≠1modn,1≤20;

(4)4a3+27b2≠0modp;

(5)n為素數(shù);

(6)h≤4

10.3.3ECC與RSA的比較

RSA基于大整數(shù)因子分解難題,ECC基于橢圓曲線上離散對數(shù)計算難題。RSA算法的特點之一是數(shù)學原理簡單,在工程應用中易于實現(xiàn),但它的單位安全強度較低,對它的破解難度是亞指數(shù)級的,而對于ECC的破解難度基本上是指數(shù)級的,因此ECC算法的單位安全強度高于RSA算法,即要達到同樣的安全強度,ECC算法所需要的密鑰長度遠低于RSA算法,這有效解決了提高安全強度必須增加密鑰長度所帶來的工程實現(xiàn)難度的問題。

10.4基于橢圓曲線的Diffie-Hellman密鑰協(xié)商協(xié)議

密鑰協(xié)商機制用于獲取通信雙方的臨時會話密鑰,基于橢圓曲線的Diffie-Hellman(DH)密鑰協(xié)商協(xié)議(ECDH)和DH密鑰協(xié)商協(xié)議思想相同,只是ECDH是基于橢圓曲線離散對數(shù)問題實現(xiàn)的。

ECDH密鑰協(xié)商過程如圖10.10所示。

(1)Alice和Bob隨機生成各自的私鑰dA、dB,并分別計算各自的公鑰PA=dAG,PB=dBG;

(2)Alice和Bob通過不安全的信道交換PA和PB;

(3)Alice計算S=dAPB,Bob計算S=dBPA,顯然雙方計算得到的S是一樣的,因此共享密鑰就是S=dAdBG,

即S=dAPB=dA(dBG)=dB(dAG)=dBPA。

在上述密鑰協(xié)商過程中,攻擊者雖然可以竊聽到PA和PB,但由于橢圓曲線離散對數(shù)問題的難解性,攻擊者無法通過PA、PB計算出dA、dB,因此無法獲得協(xié)商出的共享密鑰。

圖10.10ECDH密鑰協(xié)商過程

【例10-12】假設Alice和Bob約定好使用F3851上的橢圓曲線y2=x3+324x+1287,基點G=(920,303),現(xiàn)在Alice選取私鑰dA=1194,Bob選取私鑰dB=1759,編程計算二者的公鑰PA、PB以及密鑰協(xié)商的結果S。

10.4.2ECDH中間人攻擊

雖然攻擊者無法通過公鑰PA、PB反推出雙方的私鑰dA、dB,但是ECDH無法防止中間人攻擊。

ECDH與DH算法一樣,通信實體在不知對方身份的情況下建立共享密鑰,缺乏對實體的認證,因而易受中間人攻擊,因此需要和其他的簽名算法(如數(shù)字簽名算法和橢圓曲線數(shù)字簽名算法)配合,增加對實體身份的認證。

如圖10.11所示,中間人截獲Alice發(fā)往Bob的公鑰PA,替換為自己的公鑰PM,將Bob發(fā)往Alice的公鑰PB,替換為自己的公鑰PM,最后Alice計算的共享密鑰為Alice與中間人協(xié)商出的密鑰,而Bob計算的則為Bob與中間人協(xié)商的密鑰。這樣當Alice和Bob使用各自計算的共享密鑰發(fā)送消息時,中間人都能解密消息,并修改消息重新發(fā)送。

圖10.11ECDH中間人攻擊

10.5橢圓曲線數(shù)字簽名算法

橢圓曲線數(shù)字簽名算法(ECDSA)是ECC與DSA的結合,整個簽名過程與DSA類似,只是ECDSA簽名中采取的算法是ECC,最后得到的簽名值也是分為r和s。

10.5.1簽名和驗證過程

1.簽名過程

(1)Alice希望對消息m進行簽名,首先選擇一條橢圓曲線,參數(shù)為(p,a,b,G,n,h),隨機選擇私鑰d,計算公鑰P=dG,G為基點;

(2)Alice選擇一個隨機數(shù)k(1≤k≤n-1),計算Q=kG;

(3)計算r=xQmodn,n為點G的階,xQ為點Q的橫坐標,若r=0,則返回到第(2)步,重新選擇一個k;

(4)計算消息m的哈希值h(m)(大整數(shù)形式);

(5)計算s=k-1(h(m)+dr)modn,k-1是kmodn的乘法逆元,若s=0,則轉向第(2)步;

(6)(r,s)即為Alice對消息m的簽名;

(7)Alice將消息m、對消息m的簽名(r,s)、所使用的橢圓曲線參數(shù)(p,a,b,G,n,h),以及Alice的公鑰P發(fā)送給Bob。

該算法一開始選擇了一個隨機數(shù)k,經過標量乘法運算將隨機數(shù)隱藏在r中,再通過等式s=k-1(h(m)+dr)modn將r綁定到消息哈希值上。

2.驗證過程

Bob接收到消息m、簽名值(r,s)、所使用的橢圓曲線參數(shù)(p,a,b,G,n,h),以及Alice的公鑰P后,進行以下運算:

(1)計算消息m的哈希值h(m)(大整數(shù)形式);

(2)計算u1=s-1h(m)modn,u2=s-1rmodn;

(3)計算點Q=u1G+u2P;

(4)只有當r≡xQmodn時,簽名才是有效的

3.驗證橢圓曲線簽名算法的正確性

只需證明Q=kG即可,證明過程如下:

由簽名和驗證過程可得

所以

又因為

所以

10.5.2ECDSA安全性

在生成ECDSA簽名的過程中,必須確保k的隨機性,如果對所有的簽名操作都使用相同的k,或者隨機數(shù)生成器存在可預測性,攻擊者可能恢復出私鑰d。

假設兩個ECDSA簽名信息(r1,s1)和(r2,s2),明文哈希值分別為h1、h2,使用的橢圓曲線各參數(shù)相同,選擇的隨機數(shù)均為k,則:

10.6ECC攻擊方法

橢圓曲線密碼體制的安全性是基于橢圓曲線上離散對數(shù)的難解性,雖然ECC的安全性很高,但是依然有一些解決橢圓曲線上離散對數(shù)難題的有效方法。一般橢圓曲線的離散對數(shù)求解方法有窮舉搜索法、小步大步法、Pollardsrho算法、Pollardslambda算法、Pohlig-Hellman算法、MultipleLogarithms算法等。不過,其中最有效的算法Pollardsrho也是指數(shù)級時間復雜度,并沒有亞指數(shù)級時間復雜度的算法。

10.6.1窮舉搜索法

橢圓曲線離散對數(shù)問題指已知P和Q是橢圓曲線E上的兩個點,點P的階ord(P)=N,求k,使得k滿足:Q=kP,0≤k≤N-1。

窮舉搜索是一種常用的解決問題的方法,通過計算

P、2P、3P、…,直到kP=Q為止,但是這種方法花費的時間代價較高。顯而易見,最壞情況下需要進行N次比較,存儲N個點,所以空間復雜度為O(N)。當N足夠大時,該算法在計算時間上變得不可行。

10.6.2橢圓曲線小步大步法

橢圓曲線離散對數(shù)問題是已知P和Q是橢圓曲線E上的兩個點,點P的階ord(P)=N,求k,使得k滿足:Q=kP,0≤k≤N-1。

任意整數(shù)x都可以寫成x=am+b的形式,其中a、m、b為任意的三個整數(shù),例如10=2×4+2。以此為基礎,可以將橢圓曲線離散對數(shù)難題的方程改寫為如下形式:

1971年,Shank提出小步大步法(BabyStepGiantStep),用來求解大整數(shù)分解問題和離散對數(shù)問題。小步大步是一種“中間相遇”算法,相較于窮舉攻擊,只需要計算少量的bP和Q-amP即可找到答案,算法步驟如下:

1.小步大步法原理

對于方程Q=amP+bP:

(1)當a=0時,將驗證Q=bP,其中b為[0,m]中的整數(shù),相當于將Q與0P~mP之間的所有點進行了比較;

(2)當a=1時,將驗證Q=mP+bP,相當于將Q與mP~2mP之間的所有點進行比較;

(3)當a=2時,將驗證Q=2mP+bP,相當于將Q與2mP~3mP之間的所有點進行比較;

(4)當a=m-1時,將驗證Q=(m-1)mP+bP,相當于將Q與(m-1)mP~m2P(=NP)之間的所有點進行比較。

因此,通過最多2m次點加法運算,實現(xiàn)對0P~nP之間的所有點進行檢查,其中m次小步指的是計算0P~mP,m次大步指的是計算0mP~m2P(=NP)。

10.6.3橢圓曲線Pollard＇srho算法

1978年,Pollard提出一種稱之為Pollard＇srho的算法,該算法是目前求解橢圓曲線離散對數(shù)難題速度最快的算法,因此可以說Pollard＇srho算法決定了ECC的安全性,如果橢圓曲線離散對數(shù)難題在較短的時間內能被Pollard＇srho算法破解,那么橢圓曲線密碼體制的安全性就會大打折扣。

橢圓曲線離散對數(shù)問題:已知P和Q是橢圓曲線E上的兩個點,點P的階ord(P)=N,求k,使得k滿足:Q=kP,0≤k≤N-1。

Pollard＇srho算法的基本思想是創(chuàng)建一個函數(shù)f:G→G,f為橢圓曲線群G到自身的一個映射,群的階為N,對于i≥0,計算xi+1=f(xi),因為G是有限的,最終會得到xi=xj,xi+1=f(x