引言
人們根據(jù)密鑰的特點,將密碼系統(tǒng)分為私鑰和公鑰兩大密碼系統(tǒng)。在私鑰密碼系統(tǒng)中,解密密鑰和加密密鑰相同或者很容易從加密密鑰導(dǎo)出,這一特點致使加密系統(tǒng)變得不安全。1976年Diffie和Hellman發(fā)表了著名的“密碼學(xué)的新方向”一文[1],提出公開密鑰密碼的思想,從此開始公鑰密碼的發(fā)展。在公鑰密碼體制中,解密密鑰和加密密鑰不同,從一個難于推出另一個,加密和解密是可分離的,通信雙方事先無須交換密鑰就可建立起保密通信。1978年由Rivest、Shamir和Adleman提出的RSA[2]方案及1984年提出的ELGamal[3]方案均屬于公鑰密碼體制。RSA的安全性依賴于大整數(shù)分解因子問題的困難性,ELGamal的安全性則是建立在有限域上離散對數(shù)問題困難性基礎(chǔ)上的。
隨著計算機網(wǎng)絡(luò)的迅速發(fā)展,相互之間進行通信的用戶數(shù)量的增多,RSA與ELGamal公鑰密碼體制的公鑰位數(shù)較大(一般為512比特以上)的弱點逐漸暴露出來。1985年Koblitz[4]和Miller[5]分別獨立地提出利用橢圓曲線上離散對數(shù)代替有限域上離散對數(shù),可以構(gòu)作公鑰位數(shù)較小的ELGamal類公鑰密碼。
1 橢圓曲線
定義1:設(shè)K=GF(q)(其中q=p?d)為一有限域,K上橢圓曲線方程E為:
y2=x3+ax+b (p≥5,a,b∈K,4a3+27b2≠0)
y2+xy=x3+ax+b (p=2,a,b∈K)
滿足橢圓曲線方程E的所有點及一個稱為無窮遠點O[6]的點所構(gòu)成的集合
E(K)={(x,y)|(x,y)∈E,且x,y∈K}∪O
為該曲線的K-有理點集合,它是一個有限集,元素個數(shù)稱為該橢圓曲線E的階,記#E(K).我們在該有限集上定義一個加法運算[6],使得這些點對于該加法運算形成一個Abel群,群的單位元為無窮遠點O.
定理1(Hasse不等式):設(shè)K=GF(q), E/K為有限域上的橢圓曲線,有不等式
|#E(K)-pd-1|≤2(pd)1/2成立。
定義5:設(shè)E/K為橢圓曲線,點P為其上的點,最小的滿足條件rP=O,正整數(shù)r稱為點P的階。根據(jù)有限域的知識,我們知道這樣的r總是存在且整除橢圓曲線階#E(K).整數(shù)k,l,滿足條件kP=lP,當(dāng)且僅當(dāng)k=lmod(r).
2 橢圓曲線上的密碼體制
橢圓曲線上離散對數(shù)問題ECDLP定義如下:給定素數(shù)p和橢圓曲線E,對Q=kP,在已知P,Q 的情況下求出小于p的正整數(shù)k.可以證明由k和P計算Q比較容易,而由Q和P計算k則比較困難。ECDLP是比整數(shù)因子分解問題IFP和離散對數(shù)問題DLP難得多的數(shù)學(xué)難題。基于該難題,Neal Koblitz和Victor Miller[4][5]在1985年分別提出了橢圓曲線密碼系統(tǒng)(ECC).ECC既可以用于數(shù)據(jù)加密,也可以用于數(shù)字簽名。
將橢圓曲線中的加法運算與離散對數(shù)中的模乘運算相對應(yīng),將橢圓曲線中的乘法運算與離散對數(shù)中的模冪運算相對應(yīng),我們就可以建立基于橢圓曲線的對應(yīng)的密碼體制。
例如,對應(yīng)Diffie-Hellman公鑰系統(tǒng),我們可以通過如下方式在橢圓曲線上予以實現(xiàn):在E上選取生成元P,要求由P產(chǎn)生的群元素足夠多,通信雙方A和B分別選取a和b,a和b 予以保密,但將aP和bP公開,A和B間通信用的密鑰為abP,這是第三者無法得知的。
對應(yīng)ELGamal密碼系統(tǒng)可以采用如下的方式在橢圓曲線上予以實現(xiàn):
將明文m嵌入到E上Pm點,選一點B∈E,每一用戶都選一整數(shù)a,0<a<N,N為階數(shù)已知,a 保密,aB公開。欲向A送m,可送去下面一對數(shù)偶:[kB,Pm+k(aAB)],k是隨機產(chǎn)生的整數(shù)。A可以從kB求得k(aAB).通過:Pm+k(aAB)- k(aAB)=Pm恢復(fù)Pm.同樣對應(yīng)DSA我們可以在橢圓曲線上構(gòu)造ECDSA.
3 橢圓曲線密碼與智能卡
智能卡通常用在安全性要求比較高的場合,并與密碼學(xué)的應(yīng)用相結(jié)合。這首先是由于智能卡能夠保護并安全的處理敏感數(shù)據(jù);而智能卡能保護密鑰也是相當(dāng)重要的,因為“一切秘密寓于密鑰之中”,為了能達到密碼所提供的安全服務(wù),密鑰絕對不能被泄密,但為安全原因所增加的成本卻不能太多。
智能卡自身硬件的資源極為有限。用其實現(xiàn)安全系統(tǒng)面臨著存儲器容量和計算能力方面受到的限制。目前市場上的大多數(shù)智能卡有128到1024字節(jié)的RAM,1 k到16 k字節(jié)的EEPROM,6 k到16 k字節(jié)的ROM,CPU通常為8比特的,典型的時鐘頻率為3.57 MHz.任何存儲或者是處理能力的增強都意味著智能卡成本的大幅度提高。
另外智能卡的數(shù)據(jù)傳送是相對慢的,為提高應(yīng)用的效率,基本的數(shù)據(jù)單元必須要小,這樣可以減少智能卡與卡終端之間的數(shù)據(jù)流量,其傳送時間的減少則意味著實用性的增強。
將橢圓曲線密碼體制應(yīng)用于智能卡的優(yōu)點是:生成私鑰公鑰方便;節(jié)省內(nèi)存空間;節(jié)省帶寬,提高實用性;節(jié)省處理時間,而不需要增加硬件的處理等方面。ECC密鑰短所帶來的各優(yōu)點恰好彌補了智能卡硬件的各種局限,不僅能有效地降低智能卡的生產(chǎn)成本,也能提高智能卡的實用性。
4 參數(shù)的選取
橢圓曲線上的公鑰密碼體制的安全性是建立在橢圓曲線離散對數(shù)的基礎(chǔ)上,但并不是所有橢圓曲線都可以應(yīng)用到公鑰密碼體制中,為了保證其安全性,我們必須選取安全橢圓曲線,即階為大素數(shù)或含大素數(shù)因子的橢圓曲線為安全橢圓曲線。一般來說有四種尋找安全橢圓曲線的方法:
1)有限域GF(q)上隨機生成一橢圓曲線,直接計算其階,判斷階是否為大素數(shù)或含大素數(shù)因子,若是即確定,否則繼續(xù)選取曲線,直至符合條件。
2)取具有一定特殊性橢圓曲線的系數(shù),計算該橢圓曲線的階,對該階進行判斷,直至找到所需要的安全曲線。
3)如果q=2m,其中m能被一個比較小的整數(shù)d整除,我們首先在有限域GF(q1)(q1=2d)上選擇一橢圓曲線E‘并計算其階,根據(jù)此值,利用Weil定理[6]計算該曲線在其擴域GF(q)上的階,若此階符合安全標(biāo)準(zhǔn),我們再找曲線E‘在域GF(q)上的嵌入E,則E即為所需的安全橢圓曲線。
4)首先給出具有安全條件的曲線階,然后構(gòu)造一具有此階的橢圓曲線。
目前國內(nèi)外比較流行的計算橢圓曲線階的算法有complex multiplication算法、SEA算法、Satoh算法[7],[8]均屬于上述幾種方法之一種。應(yīng)用廣泛的橢圓曲線公鑰密碼體制中大多是基于特征2的有限域上,因此尋找特征2的有限域上的安全橢圓曲線必須先予以解決,Satoh算法正是為此提出的。
5 有關(guān)Satoh算法的實現(xiàn)問題
作者使用Mathematica語言實現(xiàn)了特征2時Satoh算法。在算法實現(xiàn)的驗證部分用到了上述方法,為了在有限域F2160上尋求安全橢圓曲線,首先在有限基域F216上隨機生成一條橢圓曲線E,利用Satoh算法計算其Frobenius同態(tài)跡C,根據(jù)橢圓曲線階的計算方法可知該曲線的階為216+1-C.設(shè)方程x2-Cx+216=0的兩個根為α,β,根據(jù)Weil共軛[6]可知該條橢圓曲線在擴域上的階為:(216)10+1-(α10+β10),如果這個階為大素數(shù)或含大素數(shù)因子,我們將E嵌入到F2160上就找到了一條符合密碼體制要求的安全曲線。
Satoh算法的C語言實現(xiàn)所涉及的運算領(lǐng)域有:有限域Fq,2-adic環(huán)Zq和2-adic整數(shù)環(huán)Z2,各個領(lǐng)域的元素之間的運算是大整數(shù)的基本運算,這里q=2160.2-adic整數(shù)環(huán)Z2中元素α的形式如同α=a1+a22+a322+a423+...an2n-1+...冪級形式,ai的值或為0或為1.由于算法只需要精度precision為83=[160+62],2-adic整數(shù)環(huán)Z2中元素級數(shù)不能超出83.2-adic整數(shù)環(huán)中元素的數(shù)據(jù)結(jié)構(gòu)定義為:
Typedef unsigned long BIGword;
Typedef struct{
int length
BIGword value[3]
}Z2word;
兩個元素的相加減運算為模283意義下的大整數(shù)的加減運算,相乘為模283意義下的乘法運算。求元素a的逆元運算采用牛頓迭代算法,迭代的初始值為1(該元素為奇數(shù),否則無逆元),迭代公式為x←x-x(ax-1),迭代一次精度翻倍,達到所需83的精度要迭代7次。
有限域Fq上的元素α=a1+a2t+a3t2+a4t3+...a160t159,其形式為一次數(shù)不高于159次的多項式,多項式的系數(shù)或為0或為1,兩個多項式相加為對應(yīng)次數(shù)的系數(shù)模2加,減法與加法是一個運算。相乘為模一多項式f(t)=t160+t5+t3+t2+1意義下的乘法,在實際的運算過程中采用邊乘邊模的方法,也即次數(shù)出現(xiàn)160,就用低次多項式t5+t3+t2+1代替。求逆運算采用擴展歐幾里德算法。Fq元素的數(shù)據(jù)結(jié)構(gòu)定義如下:
typedef struct {
int length
BIGword coef[5]
}Fqword
環(huán)Zq為2-adic整環(huán)Z2上的多項式Z2[t],模去多項式f(t)生成的理想[f(t)]所形成的商環(huán),即Zq:=Z2[t]/[f(t)],f(t)同上。從環(huán)Zq的構(gòu)造可知,Zq中元素的形式為一次數(shù)不高于159的多項式,系數(shù)為2-adic整環(huán)Z2上的元素,這樣,我們可以定義Zq的元素數(shù)據(jù)結(jié)構(gòu)。
typedef struct {
int length
Z2word coef[159]
}Zqword
元素的加、減法運算同一般多項式運算類似,只是對應(yīng)次數(shù)的系數(shù)進行加、減運算是2-adic環(huán)Z2上元素的加、減。乘法運算的處理方式如同有限域中元素乘法的運算處理。求元素a的逆運算采用牛頓迭代方法。迭代初始值求法為:首先將元素a系數(shù)模2,得到有限域上的一元素a‘,利用有限域上元素求逆方法計算出a‘的逆,a‘的逆即為迭代初始值。迭代多項式與2-adic整數(shù)環(huán)中元素的求逆迭代多項式相同。
在上述基本運算得到解決后,我們著手于橢圓曲線階的計算。隨機選取橢圓曲線y2+xy=x3+α(α為有限域中元素),利用Satoh算法可求出該曲線的階。每給出一個α值(實際上給出了一條曲線E),就會算出該曲線的階。
a的選取
對應(yīng)曲線的點的個數(shù)
0x40582590ac00873494fc02b180ba640130acb252
0x1000000000000000000014c3ec7372a968d0b1138
0xd80c00e8008e2021384a0243012d600554e10200
0xfffffffffffffffffffed059c32e5457a83e0314
0x8992b8ca2b70624440f6003100411646002d102c
0xffffffffffffffffffff203b8ad8bf63e2891eac
作者在攻讀碩士學(xué)位期間實現(xiàn)了素域上安全橢圓曲線構(gòu)造的SEA算法,在后期學(xué)習(xí)和工作中,分別用Mathematica和C兩種語言實現(xiàn)Satoh算法。這兩個算法的實現(xiàn)解決了有限域上安全曲線的構(gòu)造問題,對今后的研究——橢圓曲線密碼體制在移動通信領(lǐng)域中的應(yīng)用做了充分的準(zhǔn)備工作。
6 結(jié)束語
1.分析了將安全橢圓曲線引進公鑰密碼體制的優(yōu)點是,與目前應(yīng)用較普遍的RSA算法相比,在同等安全的情況下,其所需的密鑰長度遠比RSA低,因而ECC的特性更適合當(dāng)今電子商務(wù)需要快速反應(yīng)的發(fā)展潮流,在快速加密、密鑰交換、身份認證、數(shù)字簽名、移動通信、智能卡的安全保密等領(lǐng)域,具有廣闊的市場前景。
2.橢圓曲線公鑰密碼體制實現(xiàn)的關(guān)鍵是安全曲線的構(gòu)造問題,對此本文給出了實現(xiàn)Satoh算法驗證部分的技巧:首先計算小基域上一橢圓曲線階,通過Weil定理可知該曲線在其有限擴域上的階,若該階符合橢圓曲線公鑰密碼體制的要求,則將曲線嵌入到其擴域上即可求得一條安全曲線。
參考文獻:
[1] W Diffie,M E Hellman.NEW Directions in Cryptography[J].IEEE Trans Informat Theory,1976,IT-22:644-654.
[2] Rivest R L,Shamir A,Adleman L.A Method for obtaining Digital Signatures and Public-key Cryptosystem[J].Comm ACM,1978,21(2):120-126.
[3] L ElGamal.A Public Key Cryptosystem and Signature Scheme Base on Discrete Logarithm[J].IEEE Transactions of information Theory,1985,31:469-472.
[4] V Miller.Use of Elliptic Curves in Cryptography[A].A M Odlyzko.Advances in Cryptology-Proceedings of CRYPTO 1986,volume 263 of Lecture Notes in Computer Science[C].New york:Springer,1986.417-426.
[5] N Koblitz.Elliptic Curve Cryptosystems[J].Mathematics of Compution,1987,48:203-309.
[6] Joseph H Silberman.The Arithmetic of Elliptic Curves[M].New York:Springer-Verlag,1986.46-61,130-136.
[7] T Satoh.The canonical lift of an ordinary elliptic curve over a finite field and its point counting[J].Ramanujan Mathematical Society,2000,15:247-270.
[8] M Fouquet,P Gaudry,R Harley.An extention Satoh‘ algorithm and its implementation[J].Ramanujan Mathematical Society,2000,15:281-318.
人們根據(jù)密鑰的特點,將密碼系統(tǒng)分為私鑰和公鑰兩大密碼系統(tǒng)。在私鑰密碼系統(tǒng)中,解密密鑰和加密密鑰相同或者很容易從加密密鑰導(dǎo)出,這一特點致使加密系統(tǒng)變得不安全。1976年Diffie和Hellman發(fā)表了著名的“密碼學(xué)的新方向”一文[1],提出公開密鑰密碼的思想,從此開始公鑰密碼的發(fā)展。在公鑰密碼體制中,解密密鑰和加密密鑰不同,從一個難于推出另一個,加密和解密是可分離的,通信雙方事先無須交換密鑰就可建立起保密通信。1978年由Rivest、Shamir和Adleman提出的RSA[2]方案及1984年提出的ELGamal[3]方案均屬于公鑰密碼體制。RSA的安全性依賴于大整數(shù)分解因子問題的困難性,ELGamal的安全性則是建立在有限域上離散對數(shù)問題困難性基礎(chǔ)上的。
隨著計算機網(wǎng)絡(luò)的迅速發(fā)展,相互之間進行通信的用戶數(shù)量的增多,RSA與ELGamal公鑰密碼體制的公鑰位數(shù)較大(一般為512比特以上)的弱點逐漸暴露出來。1985年Koblitz[4]和Miller[5]分別獨立地提出利用橢圓曲線上離散對數(shù)代替有限域上離散對數(shù),可以構(gòu)作公鑰位數(shù)較小的ELGamal類公鑰密碼。
1 橢圓曲線
定義1:設(shè)K=GF(q)(其中q=p?d)為一有限域,K上橢圓曲線方程E為:
y2=x3+ax+b (p≥5,a,b∈K,4a3+27b2≠0)
y2+xy=x3+ax+b (p=2,a,b∈K)
滿足橢圓曲線方程E的所有點及一個稱為無窮遠點O[6]的點所構(gòu)成的集合
E(K)={(x,y)|(x,y)∈E,且x,y∈K}∪O
為該曲線的K-有理點集合,它是一個有限集,元素個數(shù)稱為該橢圓曲線E的階,記#E(K).我們在該有限集上定義一個加法運算[6],使得這些點對于該加法運算形成一個Abel群,群的單位元為無窮遠點O.
定理1(Hasse不等式):設(shè)K=GF(q), E/K為有限域上的橢圓曲線,有不等式
|#E(K)-pd-1|≤2(pd)1/2成立。
定義5:設(shè)E/K為橢圓曲線,點P為其上的點,最小的滿足條件rP=O,正整數(shù)r稱為點P的階。根據(jù)有限域的知識,我們知道這樣的r總是存在且整除橢圓曲線階#E(K).整數(shù)k,l,滿足條件kP=lP,當(dāng)且僅當(dāng)k=lmod(r).
2 橢圓曲線上的密碼體制
橢圓曲線上離散對數(shù)問題ECDLP定義如下:給定素數(shù)p和橢圓曲線E,對Q=kP,在已知P,Q 的情況下求出小于p的正整數(shù)k.可以證明由k和P計算Q比較容易,而由Q和P計算k則比較困難。ECDLP是比整數(shù)因子分解問題IFP和離散對數(shù)問題DLP難得多的數(shù)學(xué)難題。基于該難題,Neal Koblitz和Victor Miller[4][5]在1985年分別提出了橢圓曲線密碼系統(tǒng)(ECC).ECC既可以用于數(shù)據(jù)加密,也可以用于數(shù)字簽名。
將橢圓曲線中的加法運算與離散對數(shù)中的模乘運算相對應(yīng),將橢圓曲線中的乘法運算與離散對數(shù)中的模冪運算相對應(yīng),我們就可以建立基于橢圓曲線的對應(yīng)的密碼體制。
例如,對應(yīng)Diffie-Hellman公鑰系統(tǒng),我們可以通過如下方式在橢圓曲線上予以實現(xiàn):在E上選取生成元P,要求由P產(chǎn)生的群元素足夠多,通信雙方A和B分別選取a和b,a和b 予以保密,但將aP和bP公開,A和B間通信用的密鑰為abP,這是第三者無法得知的。
對應(yīng)ELGamal密碼系統(tǒng)可以采用如下的方式在橢圓曲線上予以實現(xiàn):
將明文m嵌入到E上Pm點,選一點B∈E,每一用戶都選一整數(shù)a,0<a<N,N為階數(shù)已知,a 保密,aB公開。欲向A送m,可送去下面一對數(shù)偶:[kB,Pm+k(aAB)],k是隨機產(chǎn)生的整數(shù)。A可以從kB求得k(aAB).通過:Pm+k(aAB)- k(aAB)=Pm恢復(fù)Pm.同樣對應(yīng)DSA我們可以在橢圓曲線上構(gòu)造ECDSA.
3 橢圓曲線密碼與智能卡
智能卡通常用在安全性要求比較高的場合,并與密碼學(xué)的應(yīng)用相結(jié)合。這首先是由于智能卡能夠保護并安全的處理敏感數(shù)據(jù);而智能卡能保護密鑰也是相當(dāng)重要的,因為“一切秘密寓于密鑰之中”,為了能達到密碼所提供的安全服務(wù),密鑰絕對不能被泄密,但為安全原因所增加的成本卻不能太多。
智能卡自身硬件的資源極為有限。用其實現(xiàn)安全系統(tǒng)面臨著存儲器容量和計算能力方面受到的限制。目前市場上的大多數(shù)智能卡有128到1024字節(jié)的RAM,1 k到16 k字節(jié)的EEPROM,6 k到16 k字節(jié)的ROM,CPU通常為8比特的,典型的時鐘頻率為3.57 MHz.任何存儲或者是處理能力的增強都意味著智能卡成本的大幅度提高。
另外智能卡的數(shù)據(jù)傳送是相對慢的,為提高應(yīng)用的效率,基本的數(shù)據(jù)單元必須要小,這樣可以減少智能卡與卡終端之間的數(shù)據(jù)流量,其傳送時間的減少則意味著實用性的增強。
將橢圓曲線密碼體制應(yīng)用于智能卡的優(yōu)點是:生成私鑰公鑰方便;節(jié)省內(nèi)存空間;節(jié)省帶寬,提高實用性;節(jié)省處理時間,而不需要增加硬件的處理等方面。ECC密鑰短所帶來的各優(yōu)點恰好彌補了智能卡硬件的各種局限,不僅能有效地降低智能卡的生產(chǎn)成本,也能提高智能卡的實用性。
4 參數(shù)的選取
橢圓曲線上的公鑰密碼體制的安全性是建立在橢圓曲線離散對數(shù)的基礎(chǔ)上,但并不是所有橢圓曲線都可以應(yīng)用到公鑰密碼體制中,為了保證其安全性,我們必須選取安全橢圓曲線,即階為大素數(shù)或含大素數(shù)因子的橢圓曲線為安全橢圓曲線。一般來說有四種尋找安全橢圓曲線的方法:
1)有限域GF(q)上隨機生成一橢圓曲線,直接計算其階,判斷階是否為大素數(shù)或含大素數(shù)因子,若是即確定,否則繼續(xù)選取曲線,直至符合條件。
2)取具有一定特殊性橢圓曲線的系數(shù),計算該橢圓曲線的階,對該階進行判斷,直至找到所需要的安全曲線。
3)如果q=2m,其中m能被一個比較小的整數(shù)d整除,我們首先在有限域GF(q1)(q1=2d)上選擇一橢圓曲線E‘并計算其階,根據(jù)此值,利用Weil定理[6]計算該曲線在其擴域GF(q)上的階,若此階符合安全標(biāo)準(zhǔn),我們再找曲線E‘在域GF(q)上的嵌入E,則E即為所需的安全橢圓曲線。
4)首先給出具有安全條件的曲線階,然后構(gòu)造一具有此階的橢圓曲線。
目前國內(nèi)外比較流行的計算橢圓曲線階的算法有complex multiplication算法、SEA算法、Satoh算法[7],[8]均屬于上述幾種方法之一種。應(yīng)用廣泛的橢圓曲線公鑰密碼體制中大多是基于特征2的有限域上,因此尋找特征2的有限域上的安全橢圓曲線必須先予以解決,Satoh算法正是為此提出的。
5 有關(guān)Satoh算法的實現(xiàn)問題
作者使用Mathematica語言實現(xiàn)了特征2時Satoh算法。在算法實現(xiàn)的驗證部分用到了上述方法,為了在有限域F2160上尋求安全橢圓曲線,首先在有限基域F216上隨機生成一條橢圓曲線E,利用Satoh算法計算其Frobenius同態(tài)跡C,根據(jù)橢圓曲線階的計算方法可知該曲線的階為216+1-C.設(shè)方程x2-Cx+216=0的兩個根為α,β,根據(jù)Weil共軛[6]可知該條橢圓曲線在擴域上的階為:(216)10+1-(α10+β10),如果這個階為大素數(shù)或含大素數(shù)因子,我們將E嵌入到F2160上就找到了一條符合密碼體制要求的安全曲線。
Satoh算法的C語言實現(xiàn)所涉及的運算領(lǐng)域有:有限域Fq,2-adic環(huán)Zq和2-adic整數(shù)環(huán)Z2,各個領(lǐng)域的元素之間的運算是大整數(shù)的基本運算,這里q=2160.2-adic整數(shù)環(huán)Z2中元素α的形式如同α=a1+a22+a322+a423+...an2n-1+...冪級形式,ai的值或為0或為1.由于算法只需要精度precision為83=[160+62],2-adic整數(shù)環(huán)Z2中元素級數(shù)不能超出83.2-adic整數(shù)環(huán)中元素的數(shù)據(jù)結(jié)構(gòu)定義為:
Typedef unsigned long BIGword;
Typedef struct{
int length
BIGword value[3]
}Z2word;
兩個元素的相加減運算為模283意義下的大整數(shù)的加減運算,相乘為模283意義下的乘法運算。求元素a的逆元運算采用牛頓迭代算法,迭代的初始值為1(該元素為奇數(shù),否則無逆元),迭代公式為x←x-x(ax-1),迭代一次精度翻倍,達到所需83的精度要迭代7次。
有限域Fq上的元素α=a1+a2t+a3t2+a4t3+...a160t159,其形式為一次數(shù)不高于159次的多項式,多項式的系數(shù)或為0或為1,兩個多項式相加為對應(yīng)次數(shù)的系數(shù)模2加,減法與加法是一個運算。相乘為模一多項式f(t)=t160+t5+t3+t2+1意義下的乘法,在實際的運算過程中采用邊乘邊模的方法,也即次數(shù)出現(xiàn)160,就用低次多項式t5+t3+t2+1代替。求逆運算采用擴展歐幾里德算法。Fq元素的數(shù)據(jù)結(jié)構(gòu)定義如下:
typedef struct {
int length
BIGword coef[5]
}Fqword
環(huán)Zq為2-adic整環(huán)Z2上的多項式Z2[t],模去多項式f(t)生成的理想[f(t)]所形成的商環(huán),即Zq:=Z2[t]/[f(t)],f(t)同上。從環(huán)Zq的構(gòu)造可知,Zq中元素的形式為一次數(shù)不高于159的多項式,系數(shù)為2-adic整環(huán)Z2上的元素,這樣,我們可以定義Zq的元素數(shù)據(jù)結(jié)構(gòu)。
typedef struct {
int length
Z2word coef[159]
}Zqword
元素的加、減法運算同一般多項式運算類似,只是對應(yīng)次數(shù)的系數(shù)進行加、減運算是2-adic環(huán)Z2上元素的加、減。乘法運算的處理方式如同有限域中元素乘法的運算處理。求元素a的逆運算采用牛頓迭代方法。迭代初始值求法為:首先將元素a系數(shù)模2,得到有限域上的一元素a‘,利用有限域上元素求逆方法計算出a‘的逆,a‘的逆即為迭代初始值。迭代多項式與2-adic整數(shù)環(huán)中元素的求逆迭代多項式相同。
在上述基本運算得到解決后,我們著手于橢圓曲線階的計算。隨機選取橢圓曲線y2+xy=x3+α(α為有限域中元素),利用Satoh算法可求出該曲線的階。每給出一個α值(實際上給出了一條曲線E),就會算出該曲線的階。
a的選取
對應(yīng)曲線的點的個數(shù)
0x40582590ac00873494fc02b180ba640130acb252
0x1000000000000000000014c3ec7372a968d0b1138
0xd80c00e8008e2021384a0243012d600554e10200
0xfffffffffffffffffffed059c32e5457a83e0314
0x8992b8ca2b70624440f6003100411646002d102c
0xffffffffffffffffffff203b8ad8bf63e2891eac
作者在攻讀碩士學(xué)位期間實現(xiàn)了素域上安全橢圓曲線構(gòu)造的SEA算法,在后期學(xué)習(xí)和工作中,分別用Mathematica和C兩種語言實現(xiàn)Satoh算法。這兩個算法的實現(xiàn)解決了有限域上安全曲線的構(gòu)造問題,對今后的研究——橢圓曲線密碼體制在移動通信領(lǐng)域中的應(yīng)用做了充分的準(zhǔn)備工作。
6 結(jié)束語
1.分析了將安全橢圓曲線引進公鑰密碼體制的優(yōu)點是,與目前應(yīng)用較普遍的RSA算法相比,在同等安全的情況下,其所需的密鑰長度遠比RSA低,因而ECC的特性更適合當(dāng)今電子商務(wù)需要快速反應(yīng)的發(fā)展潮流,在快速加密、密鑰交換、身份認證、數(shù)字簽名、移動通信、智能卡的安全保密等領(lǐng)域,具有廣闊的市場前景。
2.橢圓曲線公鑰密碼體制實現(xiàn)的關(guān)鍵是安全曲線的構(gòu)造問題,對此本文給出了實現(xiàn)Satoh算法驗證部分的技巧:首先計算小基域上一橢圓曲線階,通過Weil定理可知該曲線在其有限擴域上的階,若該階符合橢圓曲線公鑰密碼體制的要求,則將曲線嵌入到其擴域上即可求得一條安全曲線。
參考文獻:
[1] W Diffie,M E Hellman.NEW Directions in Cryptography[J].IEEE Trans Informat Theory,1976,IT-22:644-654.
[2] Rivest R L,Shamir A,Adleman L.A Method for obtaining Digital Signatures and Public-key Cryptosystem[J].Comm ACM,1978,21(2):120-126.
[3] L ElGamal.A Public Key Cryptosystem and Signature Scheme Base on Discrete Logarithm[J].IEEE Transactions of information Theory,1985,31:469-472.
[4] V Miller.Use of Elliptic Curves in Cryptography[A].A M Odlyzko.Advances in Cryptology-Proceedings of CRYPTO 1986,volume 263 of Lecture Notes in Computer Science[C].New york:Springer,1986.417-426.
[5] N Koblitz.Elliptic Curve Cryptosystems[J].Mathematics of Compution,1987,48:203-309.
[6] Joseph H Silberman.The Arithmetic of Elliptic Curves[M].New York:Springer-Verlag,1986.46-61,130-136.
[7] T Satoh.The canonical lift of an ordinary elliptic curve over a finite field and its point counting[J].Ramanujan Mathematical Society,2000,15:247-270.
[8] M Fouquet,P Gaudry,R Harley.An extention Satoh‘ algorithm and its implementation[J].Ramanujan Mathematical Society,2000,15:281-318.