橢圓曲線公鑰在網絡安全密碼體系中的應用

高建明

摘 要： 移動設備和無線設備的大量使用需要一種新的公鑰密碼方案，來適應這些設備在計算能力和帶寬方面的限制，同時要滿足安全性級別的要求。橢圓曲線密碼體制作為一種新興的加密及身份認證技術，以其自身的多項特點，已從學術理論研究階段逐步走向實際應用階段，成為目前最有前途的一種公鑰密碼體系，極有可能成為現存公鑰密碼體系RSA的替代者。橢圓曲線密碼算法具有高安全性、低消耗、運算速度快的特點，具有良好的應用前景。文章對橢圓曲線方程、算法的原理、加密算法、安全性進行了分析，實現了橢圓曲線公鑰在網絡Diffie-Hellman密鑰交換中的應用。

關鍵詞： 橢圓曲線； 密碼學； 編碼； 密鑰； 安全性

中圖分類號：TP311 文獻標志碼：A 文章編號：1006-8228（2013）08-25-03

0 引言

目前，大多數使用公鑰密碼學進行加密和數字簽名的產品和標準都使用RSA算法。為了保證RSA在使用中的安全性，最近這些年來密鑰設置的位數一直在增加，這對使用RSA的應用是一個很重的負擔，近年來，出現了一種具有較強競爭力的橢圓曲線密碼學（ECC），它對RSA提出了挑戰[1]。ECC突出的優點是可以使用比RSA短得多的密鑰，但卻能得到相同的安全性，因此在應用上可以大大減少運行負荷。

1 橢圓曲線方程概述

1.1 橢圓曲線方程

一般地說，橢圓曲線是由方程y2+dxy+ey=x3+ax2+bx+c定義的曲線，其中定義a，b，c，d，e為系數，從數學上講，橢圓曲線的形狀并非橢圓，之所以被稱為橢圓曲線，是因為該方程右邊的多項式x3+ax2+bx+c與橢圓曲線的積分有關。

現分析以下橢圓曲線類方程：

令K（b，c）為式⑴的橢圓曲線上所有（x，y）的不同點組成的集合。

這類橢圓曲線的特征是曲線上的點具有加法性質，一般可用于構造交換群，交換群（M，+）滿足以下5個性質的代數結構，其中M為集合，集合上元素的加法運算用符號“+”表示。

⑴ 對任意x，y∈M，x+y∈M，則滿足集合上的封閉性。

⑵ 對任意x，y，z∈M，x+（y+z）=（x+y）+z），則滿足集合上的結合性。

⑶ 單位元：存在0∈M，使得對任意x∈M，則x+0=0+x=0。

⑷ 逆元素：對任x∈M，顯然存在元素x'∈M使x+x'=x'+x。將x'記為-x，并將x+（-y）記為x-y。

⑸ 對任意x，y∈M，x+y=y+x，則滿足集合上交換性。

在交換群中單位元稱為零元。現令X，Y為橢圓曲線上的任意一點，則有以下兩種情形：

⑴ 當X≠Y時，可令L為連接這兩個點的直線。若L不垂直，則可以推出L一定與曲線上第三點相交，并且惟一。

⑵ 當X=Y時，可令L為曲線在點X的切線。若L不垂直，則L一定與曲線上的另一個點相交，且惟一。

在上面兩種情形中，如果當L為垂直線時，則L和曲線不相交。引進一個虛擬點P，假設它在無窮遠處與L線相交。虛擬點P設定為單位元的角色，稱為零點，定義K'（b，c）=K（b，c）∪{0}[2]。對集合K'（b，c）上的點可以定義一個加法運算“+”如下：

⑴ 對任意的K'（b，c），令X+0=X。

⑵ 對任意的X，Y∈K（b，c），如果X≠Y，若它們的X坐標相同，則根據橢圓曲線的性質，則X和Y與X軸互為映像，即X=（x，y），Y=（x，-y）。令X+Y=0，因此，-X=（x，y）。

⑶ 對任意X，Y∈K（b，c），如果X坐標不相同，定義L為經過這兩個點的直線，若L不是曲線的切線，則L必定與K（b，c）上的惟一的第三點Z相交，設X+Y=-Z，則X+Y是Z在X軸上的映像。如果L為點X上的切線，可令X+Y=-X。如果L為在點Y上的切線，則可令X+Y=-Y。

⑷ 對任意X∈K（b，c），令Lx為曲線在點X上的切線，令Y為LX與曲線相交的另一點，令X+X=-Y。

可以證明（K'（b，c），+）是一個交換群。為便于將傳送的明文編碼，通常只考慮K（b，c）上的格點（x，y），通常也稱為整數點，即X、Y都是整數。

1.2 離散橢圓曲線

2 橢圓曲線的編碼定義

用橢圓曲線將明文進行加密首先需要將明文M編碼，使它成為橢圓曲線上的一個整數點，從這個點上可惟一推算出明文M[5]。但到目前為止仍不知道這種編碼能否被多項式時間算法所產生。不過，這種編碼可以用概率算法產生，且速度較快，盡管概率算法不一定能保證總能生成一個編碼，但可以證明這種情況發生的幾率是很小的[6]。

假設N是比P小的多的正整數。先令x=N，然后檢查N3+bN+c是否等于模P下的整數平方[7]。如果不是，在N的末尾加入和修改一些數字而得到一個新的整數N'，并且檢查N3+BN+C是否為模P下的整數平方，下面是一個概率編碼的算法。

令￠>0為一個非常小的數，使得（N+1）￡

因為對于每個J，x3+bx+c不是整數平方的概率約為1/2。因此，可以知道算法失敗的概率為ε，給定Pm=（x，y），容易看出N=[x/￡]，并稱Y為橢圓曲線編碼參數。

如令p=179，b=3，c=34，￡=15，則（4b3+27c2）mod p=174≠0。

從（M+1）￡<176得1≤M≤12，令M=10，則x=N￡+j=150+j=150+j，0≤N≤15，當j=0時，得x=150，且（x3+bx+c）mod p=（1503+3.150+34）mod179=81=92。

所以y=9，即P10=（150，9）是N=10在集合K'179（3，34）上的編碼（這里設￡=15），因為[150/15]=10，所以從點（150，9）可推算出N=10[9]。

3 橢圓曲線加密算法的應用

3.1 橢圓曲線加密算法

通常將橢圓曲線加密和解密算法分別簡稱為ECC加密和ECC解密。

令K為任意大于1的整數。對任意X∈K'（b，c），令kX=X+（k-1）X，橢圓曲線對數問題指的就是從給定k×X和X∈K'（b，c）求K的值，通常認為橢圓曲線對數問題沒有快速算法，這個問題就是研究橢圓曲線公鑰體系的基礎。

與Diffie-Hellman密鑰交換體系類似，橢圓曲線公鑰體系要求用戶共享同一參數，首先選取參數B，C，P并構造模P下的離散橢圓曲線Kp（b，c），然后在Kp（b，c）上選取一個G并選取編碼參數￡，共享參數是（Kp（b，c），G，￡）[10]。

假設甲方擬設立橢圓曲線公鑰體系的公鑰和私鑰，則甲方首先隨機選取一個正整數KA作為私鑰，然后計算PA=kAG作為公鑰，假設乙方需要將明文M用ECC加密后送給甲方，這里的M是滿足（M+1）￡

乙方首先選取一個隨機正整數K，將M編碼得PM=（x，y），然后計算如下Kp（b，c）中的兩個點作為密文：C=（kG，PM+kPA），用∏0（C）表示 kG，∏1（C）表示PM+kPA。甲方收到密文C后用ECC解密算法將C解密，算法如下：

PM=∏1（C）—kA∏0（C）

然后從PM=（x，y）算出M=[x/y]。

3.2 橢圓曲線密碼的安全性

ECC的安全性是建立在由P和kP確定的困難程度之上的，這個問題稱為橢圓曲線對數問題，Pollard rho方法是已知的求橢圓曲線對數的最快方法之一，表1表示了從密碼分析所需計算量的角度，通過給出可比較的密鑰大小，比較了各種算法。由此可知，ECC使用的密鑰比RSA中使用的密鑰要短得多，而且在密鑰長度相同時，ECC與RSA所執行的計算量也差別不多。因此，與具有同等安全性的RSA相比，由于ECC使用的密鑰更短，所以ECC所需的計算量比RSA少。

3.3 橢圓曲線密碼實現Diffie-Hellman密鑰交換

利用橢圓曲線可實現如下密鑰交換。首先，挑選一個大整數q，及橢圓曲線參數a和b，這里q為素數p或是形式為2m的整數。由此可以定義出點的橢圓群為Kq（a，b）；其次，在Kp（a，b）中挑選一個基點G，G=（x1，y1），G的階為一個非常大的數n。使得nG=0成立的最小正整數是橢圓曲線上的點G的階n。G和Kq（a，b）是該密碼體制中通信各方都已知的參數。

用戶A和用戶B之間完成密鑰交換過程如圖1所示。

⑴ A選擇一個小于n的整數nA作為其私鑰，然后產生其公鑰PA= G×nA；該公鑰是Kq（a，b）中的一個點。

⑵ B可選擇私鑰nB并計算公鑰PB。

⑶ A產生秘密鑰k=PB×nA，B產生秘密鑰k=PA×nB。

要破譯這種體制，攻擊者必須由kG和G計算出k，這通常被認為是非常難的[11]。如取p=211，Kp（0，-4），G=（2，2），這里Kp（0，-4）即是曲線y2=x3-4，則計算可得240G=0。A的私鑰nA=121，所以A的公鑰PA=121（2，2）=（115，48）。B的私鑰nB=203，所以B的公鑰為203（2，3）=（130，203），它們共享的密鑰為121（130，203）=203（115，48）=（161，69）。

這里得出的密鑰是一對數字，若將它當作傳統密碼中的會話密鑰，則必須是一個數字，可以簡單地選取x坐標或者x坐標中的某個簡單函數[12]。

4 結束語

利用橢圓曲線公鑰加密是目前公鑰加密發展的方向，但是，橢圓曲線公鑰密碼的理論復雜，選取不同的橢圓曲線參數和加密算法對加密的安全性和效率影響很大；橢圓曲線公鑰體系的強度依賴于橢圓曲線離散為難題的難解性。橢圓曲線公鑰體系對參數長度的要求雖然沒有RSA公鑰體系的要求高，但是橢圓曲線公鑰體系破譯方法的研究還沒有像RSA公鑰體系破譯方法研究得那么廣泛和深入，這可能與橢圓公鑰體系用到較深的數學有關。利用本文所述方法選取橢圓曲線等參數和相關算法進行加密被證明是安全的、有效的，也真正達到了現階段公鑰加密的要求。

參考文獻：

[1] 劉淳，張其善.基于智能卡的ECC算法的實現[J].計算機工程與應用，2009.4：65-68

[2] 蔡慶華，程一飛.一個基于超橢圓曲線的單向數字簽名[J].計算機技術與發展，2006.1：89-90

[3] 王杰.計算機網絡安全的理論與實踐[M].高等教育出版社，2011.

[4] 唐勇，許金玲.RSA密碼系統有效實現算法[J].微處理機，2011.3：128-130

[5] 楊晉.現代電子商務安全技術研究[J].網絡安全技術與應用，2009.1：89-92

[6] 楊敏，杜瑞穎.密碼編碼學與網絡安全原理與實踐[M].電子工業出版社，2012.

[7] 陳頌，何良生，王建華，徐旸.ECC數字簽名協議的安全性研究與分析[J].信息網絡安全，2007.6.

[8] 朱艷琴.基于ECC的密碼系統研究與設計[J].微電子學與計算機，2007.12.

[9] 高冬妮，陳云峰.一種改進的ECC數字簽名方案[J].信息技術，2009.10：96-99

[10] 徐秋亮，李大興.圓曲線密碼體制[J].計算機研究與發展，2009.5：102-104

[11] 趙澤茂，劉鳳玉：基于橢圓曲線密碼體制的簽名方程的構造方法[J].計算機工程，2007.6：132-135

[12] 張龍軍，沈鈞毅，趙霖：橢圓曲線密碼體制安全性研究[J].西安交通大學學報，2010.10：56-58