有限域上素數階的安全橢圓曲線的選取及實現
2006-12-31 00:00:00殷新春汪彩梅陳決偉
計算機應用研究 2006年8期
(揚州大學 計算機科學與工程系， 江蘇 揚州 225009)
摘 要：在有限域上討論了素數階的安全橢圓曲線的選取算法，并通過對多項式使用預處理技術和偽隨機方法實現了選取算法，實驗結果表明在不影響安全性的基礎上，該算法比常用的隨機算法的速度要快，且實驗的結果可用于公鑰密碼體制中，具有一定的實用價值。
關鍵詞：素數階； 安全橢圓曲線； 多項式； 預處理； 偽隨機
中圖法分類號：TP393．08文獻標識碼：A
文章編號：1001-3695(2006)08-0095-02
Selection and Implementation of Secure Elliptic Curves of Prime Order over Finite Field
YIN Xin chun， WANG Cai mei， CHEN Jue wei
(Dept. of Computer Science Engineering， Yangzhou University， Yangzhou Jiangsu 225009， China)
Abstract:In this paper， an algorithm which generates the secure elliptic curves of prime order defined over the finite field is described. The algorithm is implemented by both the polynomials pre process and bogus random method. Implementation results show that the algorithm is faster than other common algorithms with the same security. The results are useful and can be put into the elliptic curve cryptography.
Key words:Prime Order; Secure Elliptic Curves; Polynomial; Pre process; Bogus Random
1引言
1977年R.Rivest，A.Shamir和L.Adleman首次提出公鑰密碼體制后，開辟了密碼學界的新天地。隨后不斷地有人提出各種公鑰密碼的加密算法，所有這些算法的安全性都是基于復雜的數學難題。根據基于的不同難題，目前公鑰密碼體系主要分為三大類：基于整數因式分解的公鑰密碼體制，如RSA；基于離散對數的公鑰密碼體制，如DSA，DH，MQV；基于橢圓曲線的公鑰密碼體制，如ECDA，ECDH，ECMQV，ECAES。
橢圓曲線密碼體制(ECC)[1，2]是在1985年由Koblitz 和Miller分別獨立提出的，它的安全性主要是基于橢圓曲線離散對數問題的難解性。橢圓曲線上的離散對數問題比有限域上的離散對數問題更難處理，這使得在橢圓曲線公鑰密碼中采用較小的密鑰就可以達到使用更大的有限域所達到的同樣的安全性。除了依賴于橢圓曲線上離散對數的分解難度，橢圓曲線密碼體制(ECC)還依賴于曲線的選擇。一個好的橢圓曲線可以抵抗住現有的所有攻擊，而一條差的或特殊的橢圓曲線則可能會被不同的攻擊方法所攻破。因此建立安全的橢圓曲線密碼體制的第一步就是要選擇出好的橢圓曲線。
本文在有限域上討論了素數階的安全橢圓曲線的選取，并在Pentium 2．8GHz的機器上對不同的特征值進行了測試，所獲得的速度指標較好，實驗選出的橢圓曲線可用于公鑰密碼體制中，具有一定的實用價值。
2有限域上素數階的安全橢圓曲線的選取
選取橢圓曲線是建立橢圓曲線密碼體制的第一步，目前選取橢圓曲線的方法主要有兩種，即隨機選取法和復乘(CM)法。由CM法產生的橢圓曲線與虛二次域的某個階有著內在的聯系，因而在此基礎上所建立的橢圓曲線密碼體制可能帶有一定的潛在安全威脅。
本文從安全、長遠的角度出發，通過一些預處理技術，在實現隨機選取法的基礎上經過一些改進后實現了一種偽隨機的選取算法。文中所涉及的橢圓曲線(EC)均是定義在有限域Fp上，形如y2=x3+Ax+B，4A3+27B2≠0，A，B∈Fp的方程。
2．1求階的算法回顧
隨機選取的橢圓曲線的安全性完全依賴于橢圓曲線階的計算，因此求階是橢圓曲線選取中的一個重點。1985年，Schoof[3，4]在《Mathematics of Computation》雜志上發表的一篇題為“Elliptic Curves over Finite Fields and the Computation of Square Roots modp ”的文章解決了計算橢圓曲線上有理點個數的問題，這就是著名的Schoof算法。該算法的時間復雜度為多項式時間，它不依賴于任何假設或猜想，是一種基于計算多項式最大公因式方法之下的完全確定的算法。
Schoof算法的基本思想是：為求t(Frobenius映射的跡)，先對一些小的素數ι計算 tmodl ，也就是在不同的子群上構造t的同余方程組，然后由中國剩余定理求出t，從而最終確定橢圓曲線的階 #E(Fp)=p+1-t。
在Schoof算法中當多項式的次數達到一定的值時，該算法在計算上是不可行的；在其后幾年里經Elkies和Atkin等人[5～7]的改進，該算法才具有了實用價值，并最終被稱作SEA算法。
SEA算法主要分為兩個改進，即Elkies改進和Atkin改進。Elkies改進是將Schoof算法中的ι次除多項式fι(x)（次數為(ι2-1)/2）換成了該多項式的一個次數為(l-1)/2的因子，得到的是tmodl 的精確值，從而提高了Schoof算法的速度。Atkin改進則是將ι次除多項式fι(x)換成了次數為ι+1的ι次模多項式，得到的是tmodl 的一個可能值的集合。最后將兩個改進結合起來，利用中國剩余定理和大步小步法原理即可求出 t 的確切值。
2．2多項式的預處理
在SEA算法中模多項式是一個非常重要的概念，不僅如此，它還是一個完全獨立于該算法的概念，也就是對于不同的素數，只要求出模多項式后可以被重復使用。因此本文在選取素數階的橢圓曲線之前對多項式使用了預處理的方法。
本文預處理的過程如下：
(1)求出所有的指定的300以內的素數模多項式，并保存為P300.raw。
(2)輸入有限域 Fp。
(3)對于已知的p，確定素數ln，使
(4)將Ｌ中的所有的素數模多項式從文件P300.raw中抽取出并保存為P*txt(*依p的位數而定)。
本文中主要預計算了160bits，224bits的情況，保存了兩個文件P160．txt和P224．txt。
2．3素數階安全橢圓曲線的選取
本文利用一種偽隨機的方法產生了10條素數階的安全橢圓曲線，下面給出算法過程。
輸入：可執行文件名。
輸出：10條素數階橢圓曲線的參數 a，b， #E(a，b) 。
(1)讀入預計算的模多項式；
(2)while ECSnum≠10 do
①隨機選取曲線參數 a，b∈Fp，ab≠0， 判別式Δ≠0；
②檢驗 E (Fp)是否為特殊的橢圓曲線(t≠1且t≠0)，其中t 為Frobenius映射的跡；
③while ∏ιi＜4pdo。
根據E的ιi次模多項式在Fp中的分解形式判斷ιi是Elkies素數還是Atkin素數：
若ιi是Elkies素數，do
Elkies改進算法：確定Frobenius映射的特征多項式在 Fιi中的特征值λ；t←λ+p/λ( modιi)，保存(t，ιi);
若ιi 是Atkin素數，do
Atkin改進算法：計算 tmodιi的可能值的集合T，保存(T，ιi)；
④結合②中獲得的 tmodιi 的精確值以及可能值，利用CRT與BSGS算法計算出 t ;
⑤素性檢測# E(a，b)：
if # E(a，b) 是大素數then輸出 E(a，b) 參數到文件中
else保留 a不變，b加一個常量(α)do
步驟②～步驟⑤，直到# E(a，b) 為素數為止，返回到①。
本實驗中對常用的隨機選取曲線參數部分進行了點變化，即對于隨機選取的橢圓曲線判斷其階后，若階不符合橢圓曲線的安全性，則保留 a不變，而對b 加個常量，直到取到素數階為止。本文在做實驗過程中取常量 α =1。實驗表明這種經過變化后的偽隨機方法比完全隨機法產生的橢圓曲線速度要快，而且不改變橢圓曲線的安全性。
2．4安全性分析
一個安全的橢圓曲線密碼體制需要有好的橢圓曲線的支撐，而一個好的橢圓曲線就能夠抵抗現有的所有攻擊。
目前對橢圓曲線密碼體制的主要攻擊有：Pohlig Hellman攻擊、Pollard ρ攻擊。其中Pohlig Hellman攻擊主要是將階為 N的有限群上的離散對數問題化為N 的一個素因子的循環子群上的離散對數問題，它的復雜度為 O(N′)，其中N′為N 的大素因子。對于橢圓曲線來說，Pohlig Hellman攻擊主要是基于對橢圓曲線的階# E(Fp)的因式分解，并根據中國剩余定理構造同余方程組來求解橢圓曲線離散對數問題。Pollard ρ攻擊是目前解決橢圓曲線離散對數問題的最好算法，它的時間復雜度為O(N)。
根據第2．3節中的算法得出的橢圓曲線的階# E(Fp)（p 是個足夠的大素數）是一個大的素數，且數量級為 O(p )。對于Pohlig Hellman攻擊在構造同余方程中要對 O(p )數量級的數進行窮舉幾乎是不可能的，所以Pohlig Hellman攻擊無效。同樣，對于階為 O(p )數量級的有限群，Pollard ρ攻擊也是不可能的，因此Pollard ρ攻擊對本文所得的橢圓曲線也是無效的。
3實驗結果
本文經過多次測試，每次產生出10條素數階橢圓曲線的數據。表1是普通隨機法與本文偽隨機法所獲得的數據的一個比較表。
從以上實驗數據結果可以得出，本文將對多項式的預處理技術與偽隨機選取橢圓曲線的方法相結合是一種有效的選取安全橢圓曲線的方法。
在對p為160bits(p是160位，值是FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD1)的實驗中，有如下兩條素數階橢圓曲線：
a ：234499431D6744C1B524EAD02FE7479AEA23940A
b ：6349F88A1295B7ABF58F29C851A1797A2911DA6D
# E(a，b) ：FFFFFFFFFFFFFFFFFFFE97294D61FF45E46EA3E3
a ：3BF9FE10515F83C9BE3DF12782AF5ADE244687E
b ：9100F9E0A357C5DEDA90C8EDFF228BFD8CA8C0A7
# E(a，b) ：100000000000000000001078326B504A294DB28F5
4結束語
本文在使用對模多項式進行預處理的技術下，討論了有限域上素數階的安全橢圓曲線的選取，并成功地實現了選取的算法。其中實驗所得的結果可以用于公鑰密碼體制中，且經過安全性分析在此橢圓曲線上實現的密碼體制可以抵抗現有的所有攻擊。
參考文獻：
[1]I Blake， G Seroussi， N Smart. Elliptic Curves in Cryptography[M]. Cambridge Kingdom: Cambridge University Press， 1999.2 10.
[2]Certicom Research. SEC 1: Elliptic Curve Cryptography[S]. 2005，1-133.
[3]R Schoof. Elliptic Curves over Finite Fileds and the Computation of Square Roots modp [J]. Mathematics of Computation， 1985，44:483-494.
[4]R Schoof. Counting Points on Elliptic Curves over Finite Fields[J]. Journal of Theorie des Nombres de Bordeaux， 1995，(7):219-254.
[5]Elkies N D. Elliptic and Modular Curves over Finite Fields and Rela ted Computational[A]. Buell D A， TeitelbaumJ T. Computational Perspective on Number Theory[M]. AMS/International Press， 1998.21-76.
[6]Atkine A O. The Number of Points on an Elliptic Curve Modulo a Prime[Z]. Series of E mail to the NMBRTHRY Mailing List， 1992.
[7]T Izu， J Kogure， M Noro，et al.Efficient Implementation of Schoof’s Algorithm[C]. Advances in Cryptology Asiacrypt’98， Lecture Notes in Computer Science， Springer Verlag， 1998.66-79.
[8]J M Couveignes， L Dewaghe， F Morain. Isogeny Cycles and the SchoofElkies: Atkin Algorithm[R]. Research Report LIX/RR/96/03， LIX， 1996.
[9]Elisavet Konstantinou， Yiannis C Stamatiou， Christos Zaroliagis. On the Efficient Generation of Elliptic Curves over Prime Fields[M]. Springer Verlag， 2003.333-348.
作者簡介：殷新春（1962-），男，江蘇姜堰人，教授，博士，主要研究方向為并行與分布計算、信息安全；汪彩梅（1978-），女，安徽桐城人，碩士研究生，主要研究方向為信息安全；陳決偉（1981-），男，江蘇太倉人，碩士研究生，主要研究方向為信息安全。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
