高建明

摘 要： 移動(dòng)設(shè)備和無(wú)線設(shè)備的大量使用需要一種新的公鑰密碼方案，來(lái)適應(yīng)這些設(shè)備在計(jì)算能力和帶寬方面的限制，同時(shí)要滿足安全性級(jí)別的要求。橢圓曲線密碼體制作為一種新興的加密及身份認(rèn)證技術(shù)，以其自身的多項(xiàng)特點(diǎn)，已從學(xué)術(shù)理論研究階段逐步走向?qū)嶋H應(yīng)用階段，成為目前最有前途的一種公鑰密碼體系，極有可能成為現(xiàn)存公鑰密碼體系RSA的替代者。橢圓曲線密碼算法具有高安全性、低消耗、運(yùn)算速度快的特點(diǎn)，具有良好的應(yīng)用前景。文章對(duì)橢圓曲線方程、算法的原理、加密算法、安全性進(jìn)行了分析，實(shí)現(xiàn)了橢圓曲線公鑰在網(wǎng)絡(luò)Diffie-Hellman密鑰交換中的應(yīng)用。

關(guān)鍵詞： 橢圓曲線； 密碼學(xué)； 編碼； 密鑰； 安全性

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）08-25-03

0 引言

目前，大多數(shù)使用公鑰密碼學(xué)進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)都使用RSA算法。為了保證RSA在使用中的安全性，最近這些年來(lái)密鑰設(shè)置的位數(shù)一直在增加，這對(duì)使用RSA的應(yīng)用是一個(gè)很重的負(fù)擔(dān)，近年來(lái)，出現(xiàn)了一種具有較強(qiáng)競(jìng)爭(zhēng)力的橢圓曲線密碼學(xué)（ECC），它對(duì)RSA提出了挑戰(zhàn)[1]。ECC突出的優(yōu)點(diǎn)是可以使用比RSA短得多的密鑰，但卻能得到相同的安全性，因此在應(yīng)用上可以大大減少運(yùn)行負(fù)荷。

1 橢圓曲線方程概述

1.1 橢圓曲線方程

一般地說(shuō)，橢圓曲線是由方程y2+dxy+ey=x3+ax2+bx+c定義的曲線，其中定義a，b，c，d，e為系數(shù)，從數(shù)學(xué)上講，橢圓曲線的形狀并非橢圓，之所以被稱為橢圓曲線，是因?yàn)樵摲匠逃疫叺亩囗?xiàng)式x3+ax2+bx+c與橢圓曲線的積分有關(guān)。

現(xiàn)分析以下橢圓曲線類方程：

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

這類橢圓曲線的特征是曲線上的點(diǎn)具有加法性質(zhì)，一般可用于構(gòu)造交換群，交換群（M，+）滿足以下5個(gè)性質(zhì)的代數(shù)結(jié)構(gòu)，其中M為集合，集合上元素的加法運(yùn)算用符號(hào)“+”表示。

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

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

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

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

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

在交換群中單位元稱為零元?，F(xiàn)令X，Y為橢圓曲線上的任意一點(diǎn)，則有以下兩種情形：

⑴ 當(dāng)X≠Y時(shí)，可令L為連接這兩個(gè)點(diǎn)的直線。若L不垂直，則可以推出L一定與曲線上第三點(diǎn)相交，并且惟一。

⑵ 當(dāng)X=Y時(shí)，可令L為曲線在點(diǎn)X的切線。若L不垂直，則L一定與曲線上的另一個(gè)點(diǎn)相交，且惟一。

在上面兩種情形中，如果當(dāng)L為垂直線時(shí)，則L和曲線不相交。引進(jìn)一個(gè)虛擬點(diǎn)P，假設(shè)它在無(wú)窮遠(yuǎn)處與L線相交。虛擬點(diǎn)P設(shè)定為單位元的角色，稱為零點(diǎn)，定義K'（b，c）=K（b，c）∪{0}[2]。對(duì)集合K'（b，c）上的點(diǎn)可以定義一個(gè)加法運(yùn)算“+”如下：

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

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

⑶ 對(duì)任意X，Y∈K（b，c），如果X坐標(biāo)不相同，定義L為經(jīng)過(guò)這兩個(gè)點(diǎn)的直線，若L不是曲線的切線，則L必定與K（b，c）上的惟一的第三點(diǎn)Z相交，設(shè)X+Y=-Z，則X+Y是Z在X軸上的映像。如果L為點(diǎn)X上的切線，可令X+Y=-X。如果L為在點(diǎn)Y上的切線，則可令X+Y=-Y。

⑷ 對(duì)任意X∈K（b，c），令Lx為曲線在點(diǎn)X上的切線，令Y為L(zhǎng)X與曲線相交的另一點(diǎn)，令X+X=-Y。

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

1.2 離散橢圓曲線

2 橢圓曲線的編碼定義

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

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

令￠>0為一個(gè)非常小的數(shù)，使得（N+1）￡

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

如令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，當(dāng)j=0時(shí)，得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）上的編碼（這里設(shè)￡=15），因?yàn)閇150/15]=10，所以從點(diǎn)（150，9）可推算出N=10[9]。

3 橢圓曲線加密算法的應(yīng)用

3.1 橢圓曲線加密算法

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

令K為任意大于1的整數(shù)。對(duì)任意X∈K'（b，c），令kX=X+（k-1）X，橢圓曲線對(duì)數(shù)問(wèn)題指的就是從給定k×X和X∈K'（b，c）求K的值，通常認(rèn)為橢圓曲線對(duì)數(shù)問(wèn)題沒(méi)有快速算法，這個(gè)問(wèn)題就是研究橢圓曲線公鑰體系的基礎(chǔ)。

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

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

乙方首先選取一個(gè)隨機(jī)正整數(shù)K，將M編碼得PM=（x，y），然后計(jì)算如下Kp（b，c）中的兩個(gè)點(diǎn)作為密文：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確定的困難程度之上的，這個(gè)問(wèn)題稱為橢圓曲線對(duì)數(shù)問(wèn)題，Pollard rho方法是已知的求橢圓曲線對(duì)數(shù)的最快方法之一，表1表示了從密碼分析所需計(jì)算量的角度，通過(guò)給出可比較的密鑰大小，比較了各種算法。由此可知，ECC使用的密鑰比RSA中使用的密鑰要短得多，而且在密鑰長(zhǎng)度相同時(shí)，ECC與RSA所執(zhí)行的計(jì)算量也差別不多。因此，與具有同等安全性的RSA相比，由于ECC使用的密鑰更短，所以ECC所需的計(jì)算量比RSA少。

3.3 橢圓曲線密碼實(shí)現(xiàn)Diffie-Hellman密鑰交換

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

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

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

⑵ B可選擇私鑰nB并計(jì)算公鑰PB。

⑶ A產(chǎn)生秘密鑰k=PB×nA，B產(chǎn)生秘密鑰k=PA×nB。

要破譯這種體制，攻擊者必須由kG和G計(jì)算出k，這通常被認(rèn)為是非常難的[11]。如取p=211，Kp（0，-4），G=（2，2），這里Kp（0，-4）即是曲線y2=x3-4，則計(jì)算可得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）。

這里得出的密鑰是一對(duì)數(shù)字，若將它當(dāng)作傳統(tǒng)密碼中的會(huì)話密鑰，則必須是一個(gè)數(shù)字，可以簡(jiǎn)單地選取x坐標(biāo)或者x坐標(biāo)中的某個(gè)簡(jiǎn)單函數(shù)[12]。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 劉淳，張其善.基于智能卡的ECC算法的實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2009.4：65-68

[2] 蔡慶華，程一飛.一個(gè)基于超橢圓曲線的單向數(shù)字簽名[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006.1：89-90

[3] 王杰.計(jì)算機(jī)網(wǎng)絡(luò)安全的理論與實(shí)踐[M].高等教育出版社，2011.

[4] 唐勇，許金玲.RSA密碼系統(tǒng)有效實(shí)現(xiàn)算法[J].微處理機(jī)，2011.3：128-130

[5] 楊晉.現(xiàn)代電子商務(wù)安全技術(shù)研究[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2009.1：89-92

[6] 楊敏，杜瑞穎.密碼編碼學(xué)與網(wǎng)絡(luò)安全原理與實(shí)踐[M].電子工業(yè)出版社，2012.

[7] 陳頌，何良生，王建華，徐旸.ECC數(shù)字簽名協(xié)議的安全性研究與分析[J].信息網(wǎng)絡(luò)安全，2007.6.

[8] 朱艷琴.基于ECC的密碼系統(tǒng)研究與設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī)，2007.12.

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

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

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

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