素數域上橢圓曲線密碼體制的軟件實現

金曉剛

（中國電子科技集團第30研究所，四川 成都 610041）

0 引言

橢圓曲線作為代數幾何中的重要問題己有100多年的研究歷史了。1985年，N.Kbolitz和V.Miler獨立將橢圓曲線引入密碼學[1-2]，使其成為構造雙密鑰密碼體制的一個有力工具，并形成了橢圓曲線密碼體制。

橢圓曲線密碼體制[3]的安全性建立在橢圓曲線離散對數問題（ECDLP）上。普遍認為其具有最高的比特安全強度。同RSA密碼體制相比，要達到相同的安全強度，它可以使用較RSA密碼更短的密鑰。由于密鑰短，所以工程實現的加密速度較快，并且可節省能源、帶寬和存儲空間，適于在移動通信、智能卡等系統中應用。

由于橢圓曲線密碼體制具有上述優點，橢圓曲線密碼體制已成為公鑰密碼研究的主流。

1 素數域上橢圓曲線的基本運算

1.1 群和域的概念

定義 1 設R是一個非空集合，若在R上定義一個二元運算“+”滿足下列條件，稱(R，+)是一個群。

①封閉性：對任何a，b∈R，有a+b∈R；

②結合律：對任何a，b，c∈R，有(a+b)+c=a+(b+c)；

③交換律：存在單位元e∈R，使得對任何a∈R，有a+e=e+a=a；

④互逆性：對任何a∈R，存在逆元a-1，使得a+a-1=a-1+a=e，成立。

如R還滿足對任意a，b∈R，有a+b=b+a，則稱R為可交換群，或者稱為阿貝爾伽群。

定義2設R是一個非空集合，在R中定義了加法和乘法兩種二元運算，加法記為“+”，乘法記為“·”，如滿足下列條件，稱(R，+，·)是一個域。

①(R，+)是可交換群，對于加法的單位元稱為零元素；

②R中的全體非零元素對乘法構成可交換群；

③乘法在加法上是可分配的,即對任何a，b，c,R∈有:

域中元素的個數稱為域的階。如果一個域的階是有限的，則該域稱為有限域。

根據有限域的定義得到下面的結論：

①如p為素數，則集合 R=｛0，1，2，…，p-1｝是在模p加法和模p乘法下階為p的域。由于R是由素數p構成的域，所以通常也稱R為素數域，并以 G F(p)表示。如p=2，便得到素數域GF(2)；

②如有一個素數p，則一定可以找到GF(p)上的一個m次既約多項式 f(x)，以它為模構造出一個pm，階的有限域GF(pm)，f(x))稱為域中多項式。并且該域包含了GF(p)上所有m次既約多項式的全部根，可把pm階有限域中的每一個元素，表示成系數在GF(p)上且次數低于m的多項式。

在 G F(p)中的運算定義如下：

模p加法：a，b∈GF(p)，a+b=r，r是a+b被p除得的余數，r ∈[0，p-1]。

模p乘法：a ，b∈GF(p)，a·b∈s，s是a·b被p除得的余數，s ∈[0， p-1]。

求逆：若a是 G F(p)中的非零元，a的逆元 a-1就是GF(p)中的唯一元素c，且滿足a·c=1。

1.2 素數域上的橢圓曲線

素數域上的橢圓曲線方程為：

其中，素數有限域 G F(p)，a、b是模p的整數，且4 a3+27 b2(modp)不等于0。

對于一個給定的橢圓曲線方程，橢圓曲線E由 G F(p)上的點(x,y)組成，其中包括一個無窮遠點（ο表示）。E上點的個數（包括ο）被稱作E的階，表示成#E(G F(p ))。按照Hasse定理，階的范圍由以下公式確定：

1.3 基本運算

橢圓曲線基本運算主要是指對滿足橢圓曲線方程的點(x,y)的運算，由點加運算和點乘運算（即若干次點加運算）組成。

點的加法運算有如下性質：

①加法在E上是封閉的；

②加法是可交換的；

③ο是加法的單位元；

④E上的每個點對有關于加法的逆元；

⑤加法是結合的。

因此，(E，+)是阿貝爾群。

對于一個點 P=( x,y)，在素數有限域GF(p)上，其加法逆元定義為-P=( x,-y)。對于點P、Q，R =P+Q ，則P、Q、-R在一條直線上。

無窮遠點ο相當于普通加法中的0，對于所有點P，有P+ο=P，P+(- P )=ο 。

（1）點加運算

在仿射坐標系下，其運算規則如下述：

如果P1≠P2:

如果P1=P2:

由于求逆的時間耗費遠遠大于乘法，為避免求逆操作，提高算法實現效率，在實際實現中，會將點對從仿射坐標系下的(x,y)轉換為投影坐標系下的(X,Y,Z)，其中X←x，Y←y，Z←1，在投影坐標系下進行運算。

在投影坐標系下，點加操作僅使用乘法，避免了求逆操作。僅在轉換到仿射坐標系時，在點乘的最后需要一次求逆操作。求逆操作的耗費轉換到多個乘法的耗費上。

（2）點乘運算

其基本描述為：Q=kP=P+P+…+P（k次），Q、P是橢圓曲線上的點，k是一個無符號正整數，1≤k≤#E(GF(p))。

點乘運算有多種實現算法，有的適合硬件實現，有的適合軟件實現，算法的選擇決定了實現效率。因此，應對所選擇的算法進行評估，選擇適合軟件實現的算法。

2 素數域上橢圓曲線密碼體制的軟件實現

2.1 橢圓曲線密碼體制

國際上，在橢圓曲線密碼體制的標準化方面，IEEE、ANSI、ISO、IETF、ATM等都作了大量的工作，它們所開發的橢圓曲線標準的文檔有：IEEE P1363 P1363a、ANSI X9.62、X9.63、ISO/IEC 14888等，其中包括了橢圓曲線數字簽名算法ECDSA[4-6]和橢圓曲線的密鑰交換協議ECDH。

為加快橢圓曲線密碼體制在國內的推廣，提高密碼產品的安全性能，中國相關管理部門也制定了橢圓曲線密碼體制的國家標準，并已頒布實施。

橢圓曲線密碼體制具有相似的模塊結構，如圖1所示。

圖1 橢圓曲線密碼體制具有相似的模塊結構

（1）大數運算模塊

大數運算模塊中主要包括了大數的基本操作，如大數的加、減、乘、除、平方等。

（2）有限域上基本操作模塊

有限域上的操作是建立在大數操作之上的，在具體的實現過程中，需要將大數運算的結果進行取模操作，將其限制在某個大數的范圍之內。

（3）橢圓曲線上點的操作模塊

在實際的使用中，為了增加密碼系統的安全性，用到的密碼數據都是上百位的整數或二進制數。橢圓曲線密碼系統當然也不例外，所以整個橢圓曲線上點的操作都是架構在已經定義與實現了的大數的操作的基礎之上得。

（4）隨機數生成函數模塊

生成橢圓曲線密碼體制需要的隨機數。

（5）安全雜湊函數模塊

橢圓曲線密碼體制所需的安全雜湊函數。

（6）橢圓曲線密碼應用模塊

如密鑰對生成(KG)，ECDSA簽名算法，ECDH算法。

2.2 軟件實現

作者采用標準C語言和匯編語言相結合的方式，開發出軟件包，在DSP 6205上實現了ECDSA算法，DSP主頻200 MHz，帶寬32比特。

ECDSA算法的密鑰長度選定為192比特，采用域Fp上的橢圓曲線，其參數為 { p, a, b, G, n }，以十六進制形式表示如下：

經過實際測試，ECDSA簽名速率70次/秒，驗證速率60次/秒。

2.3 提高軟件實現效率的方法

可從以下幾個方面提高橢圓曲線密碼算法的實現效率：

①對點乘運算模塊、大數運算模塊，選擇最適合軟件實現的算法；

②模乘運算是橢圓曲線密碼算法最基本的算法模塊，進行一次簽名運算，調用次數上千次。可從兩方面加快模乘運算：匯編實現 Montgomery乘法，盡量提高編程效率；用硬件協處理器完成模乘運算；

③采用運算能力較強的處理器，如DSP6205，其帶寬32比特，內核時鐘 200 M，編譯器效率高，能夠很好的實現橢圓曲線密碼算法；

④橢圓曲線密碼算法在簽名和加密時，需要輸入隨機數。因此，隨機數的生成時間盡可能短。

3 結語

目前，國際上公認的比較安全實用的公鑰密碼體制是橢圓曲線密碼體制。經過長期的理論研究和科學實踐，橢圓曲線密碼體制得到了迅猛的發展。橢圓曲線密碼體制的安全性，是基于計算有限域上橢圓曲線可交換群群上定義的離散對數的困難性。橢圓曲線密碼體制具有安全性能高、存儲空間占用小和帶寬要求低等特點，在如 PDA、手機、智能卡等領域具有很大的發展優勢。現在橢圓曲線密碼體制不僅是一個重要的理論研究領域，而且已經從理論研究轉化為實際可用的密碼算法，促使民用信息安全技術走向產業化。當前，國內外很多生產密碼產品的公司都在致力于橢圓曲線密碼體制產品的開發。

現所做的主要工作有:

①對橢圓曲線密碼體制的基礎理論知識進行了簡單介紹；

②介紹了橢圓曲線密碼算法層次結構；

③討論了素數域上橢圓曲線密碼體制的軟件實現，給出了提高算法實現效率的一些方法。

由于橢圓曲線密碼體制自身優越條件，它將會成為 21世紀最主要的公鑰密碼體制。按當前的電子信息化程度，橢圓曲線密碼體制將會迅速擴展到人們生活的各個層面，具有廣闊的應用前景。

[1] 盧開澄.計算機密碼學[M].北京:清華大學出版社,2001.

[2] BRUCE S.應用密碼學[M].北京:機械工業出版社,2002.

[3] KOBLITZ N. Elliptic Curve Cryptosystems[J].Mathematics of Computation,1987(48):203-209.

[4] FIPS PUB 186. Digital Signature Standard[EB/OL] (2009-06-01)[2010-07-30].http://www.itl.nist.gov/ fipspubs/.

[5] DON J,ALFRED M，SCOTT V.The Elliptic Curve Digital Signature Algorithm[J].International Journal of Information Security,2007,1(01):36-63..

[6] IEEE P1363/D9(Draft Version 9).Standard Specification for Public Key Cryptography[EB/OL](2008-10-10)[2010-07-30].http://grouper.ieee.Org/ groups/1363.

[7] DARREL H, ALFRED M,SCOTT V.橢圓曲線密碼學導論[M].北京:電子工業出版社,2005.

[8] MICHAEL W.密碼編碼學-加密方法的C與C++實現[M].第2版.北京:電子工業出版社,2003.