橢圓曲線(xiàn)密碼體制與智能卡研究

文章出處：http://psychicreadingswithdeb.com 作者：郭艾俠   人氣： 發(fā)表時(shí)間：2011年09月18日

引言 

人們根據密鑰的特點(diǎn)，將密碼系統分為私鑰和公鑰兩大密碼系統。在私鑰密碼系統中，解密密鑰和加密密鑰相同或者很容易從加密密鑰導出，這一特點(diǎn)致使加密系統變得不安全。1976年Diffie和Hellman發(fā)表了著(zhù)名的“密碼學(xué)的新方向”一文［1］，提出公開(kāi)密鑰密碼的思想，從此開(kāi)始公鑰密碼的發(fā)展。在公鑰密碼體制中，解密密鑰和加密密鑰不同，從一個(gè)難于推出另一個(gè)，加密和解密是可分離的，通信雙方事先無(wú)須交換密鑰就可建立起保密通信。1978年由Rivest、Shamir和Adleman提出的RSA［2］方案及1984年提出的ELGamal［3］方案均屬于公鑰密碼體制。RSA的安全性依賴(lài)于大整數分解因子問(wèn)題的困難性，ELGamal的安全性則是建立在有限域上離散對數問(wèn)題困難性基礎上的。 

隨著(zhù)計算機網(wǎng)絡(luò )的迅速發(fā)展，相互之間進(jìn)行通信的用戶(hù)數量的增多，RSA與ELGamal公鑰密碼體制的公鑰位數較大（一般為512比特以上）的弱點(diǎn)逐漸暴露出來(lái)。1985年Koblitz［4］和Miller［5］分別獨立地提出利用橢圓曲線(xiàn)上離散對數代替有限域上離散對數，可以構作公鑰位數較小的ELGamal類(lèi)公鑰密碼。 

1  橢圓曲線(xiàn) 

定義1：設K=GF(q)（其中q=pd）為一有限域，K上橢圓曲線(xiàn)方程E為： 

y2=x3+ax+b       (p≥5，a,b∈K，4a3+27b2≠0) 

y2+xy=x3+ax+b    (p=2,a,b∈K) 

滿(mǎn)足橢圓曲線(xiàn)方程E的所有點(diǎn)及一個(gè)稱(chēng)為無(wú)窮遠點(diǎn)O［6］的點(diǎn)所構成的集合 

E(K)={(x,y)|(x,y)∈E,且x,y∈K}∪O 

為該曲線(xiàn)的K-有理點(diǎn)集合，它是一個(gè)有限集，元素個(gè)數稱(chēng)為該橢圓曲線(xiàn)E的階，記#E(K).我們在該有限集上定義一個(gè)加法運算［6］,使得這些點(diǎn)對于該加法運算形成一個(gè)Abel群，群的單位元為無(wú)窮遠點(diǎn)O. 

定理1(Hasse不等式)：設K=GF(q), E/K為有限域上的橢圓曲線(xiàn)，有不等式 

|#E(K)-pd-1|≤2(pd)1/2成立。 

定義5：設E/K為橢圓曲線(xiàn)，點(diǎn)P為其上的點(diǎn)，最小的滿(mǎn)足條件rP=O，正整數r稱(chēng)為點(diǎn)P的階。根據有限域的知識，我們知道這樣的r總是存在且整除橢圓曲線(xiàn)階#E(K).整數k,l，滿(mǎn)足條件kP=lP，當且僅當k=lmod(r). 

2  橢圓曲線(xiàn)上的密碼體制 

橢圓曲線(xiàn)上離散對數問(wèn)題ECDLP定義如下：給定素數p和橢圓曲線(xiàn)E，對Q＝kP，在已知P，Q 的情況下求出小于p的正整數k.可以證明由k和P計算Q比較容易，而由Q和P計算k則比較困難。ECDLP是比整數因子分解問(wèn)題IFP和離散對數問(wèn)題DLP難得多的數學(xué)難題?；谠撾y題，Neal Koblitz和Victor Miller［4］［5］在1985年分別提出了橢圓曲線(xiàn)密碼系統（ECC）.ECC既可以用于數據加密，也可以用于數字簽名。 

將橢圓曲線(xiàn)中的加法運算與離散對數中的模乘運算相對應，將橢圓曲線(xiàn)中的乘法運算與離散對數中的模冪運算相對應，我們就可以建立基于橢圓曲線(xiàn)的對應的密碼體制。 

例如，對應Diffie-Hellman公鑰系統，我們可以通過(guò)如下方式在橢圓曲線(xiàn)上予以實(shí)現：在E上選取生成元P，要求由P產(chǎn)生的群元素足夠多，通信雙方A和B分別選取a和b,a和b 予以保密，但將aP和bP公開(kāi)，A和B間通信用的密鑰為abP,這是第三者無(wú)法得知的。 

對應ELGamal密碼系統可以采用如下的方式在橢圓曲線(xiàn)上予以實(shí)現： 

將明文m嵌入到E上Pm點(diǎn)，選一點(diǎn)B∈E，每一用戶(hù)都選一整數a,0＜a＜N，N為階數已知，a 保密，aB公開(kāi)。欲向A送m,可送去下面一對數偶：［kB,Pm+k(aAB)］,k是隨機產(chǎn)生的整數。A可以從kB求得k(aAB).通過(guò)：Pm+k(aAB)- k(aAB)=Pm恢復Pm.同樣對應DSA我們可以在橢圓曲線(xiàn)上構造ECDSA. 

3  橢圓曲線(xiàn)密碼與智能卡 

智能卡通常用在安全性要求比較高的場(chǎng)合，并與密碼學(xué)的應用相結合。這首先是由于智能卡能夠保護并安全的處理敏感數據；而智能卡能保護密鑰也是相當重要的，因為“一切秘密寓于密鑰之中”，為了能達到密碼所提供的安全服務(wù)，密鑰絕對不能被泄密，但為安全原因所增加的成本卻不能太多。 

智能卡自身硬件的資源極為有限。用其實(shí)現安全系統面臨著(zhù)存儲器容量和計算能力方面受到的限制。目前市場(chǎng)上的大多數智能卡有128到1024字節的RAM，1 k到16 k字節的EEPROM，6 k到16 k字節的ROM，CPU通常為8比特的，典型的時(shí)鐘頻率為3.57 MHz.任何存儲或者是處理能力的增強都意味著(zhù)智能卡成本的大幅度提高。 

另外智能卡的數據傳送是相對慢的，為提高應用的效率，基本的數據單元必須要小，這樣可以減少智能卡與卡終端之間的數據流量，其傳送時(shí)間的減少則意味著(zhù)實(shí)用性的增強。 

將橢圓曲線(xiàn)密碼體制應用于智能卡的優(yōu)點(diǎn)是：生成私鑰公鑰方便；節省內存空間；節省帶寬，提高實(shí)用性；節省處理時(shí)間，而不需要增加硬件的處理等方面。ECC密鑰短所帶來(lái)的各優(yōu)點(diǎn)恰好彌補了智能卡硬件的各種局限，不僅能有效地降低智能卡的生產(chǎn)成本，也能提高智能卡的實(shí)用性。 

4  參數的選取 

橢圓曲線(xiàn)上的公鑰密碼體制的安全性是建立在橢圓曲線(xiàn)離散對數的基礎上，但并不是所有橢圓曲線(xiàn)都可以應用到公鑰密碼體制中，為了保證其安全性，我們必須選取安全橢圓曲線(xiàn)，即階為大素數或含大素數因子的橢圓曲線(xiàn)為安全橢圓曲線(xiàn)。一般來(lái)說(shuō)有四種尋找安全橢圓曲線(xiàn)的方法： 

1）有限域GF(q)上隨機生成一橢圓曲線(xiàn)，直接計算其階，判斷階是否為大素數或含大素數因子，若是即確定，否則繼續選取曲線(xiàn)，直至符合條件。 

2）取具有一定特殊性橢圓曲線(xiàn)的系數，計算該橢圓曲線(xiàn)的階，對該階進(jìn)行判斷，直至找到所需要的安全曲線(xiàn)。 

3）如果q=2m，其中m能被一個(gè)比較小的整數d整除，我們首先在有限域GF(q1)(q1=2d)上選擇一橢圓曲線(xiàn)E‘并計算其階，根據此值，利用Weil定理［6］計算該曲線(xiàn)在其擴域GF(q)上的階，若此階符合安全標準，我們再找曲線(xiàn)E‘在域GF(q)上的嵌入E，則E即為所需的安全橢圓曲線(xiàn)。 

4）首先給出具有安全條件的曲線(xiàn)階，然后構造一具有此階的橢圓曲線(xiàn)。 

目前國內外比較流行的計算橢圓曲線(xiàn)階的算法有complex multiplication算法、SEA算法、Satoh算法［7］,［8］均屬于上述幾種方法之一種。應用廣泛的橢圓曲線(xiàn)公鑰密碼體制中大多是基于特征2的有限域上，因此尋找特征2的有限域上的安全橢圓曲線(xiàn)必須先予以解決，Satoh算法正是為此提出的。 

5  有關(guān)Satoh算法的實(shí)現問(wèn)題 

作者使用Mathematica語(yǔ)言實(shí)現了特征2時(shí)Satoh算法。在算法實(shí)現的驗證部分用到了上述方法，為了在有限域F2160上尋求安全橢圓曲線(xiàn)，首先在有限基域F216上隨機生成一條橢圓曲線(xiàn)E，利用Satoh算法計算其Frobenius同態(tài)跡C，根據橢圓曲線(xiàn)階的計算方法可知該曲線(xiàn)的階為216+1-C.設方程x2-Cx+216=0的兩個(gè)根為α，β，根據Weil共軛［6］可知該條橢圓曲線(xiàn)在擴域上的階為：(216)10+1-(α10+β10)，如果這個(gè)階為大素數或含大素數因子，我們將E嵌入到F2160上就找到了一條符合密碼體制要求的安全曲線(xiàn)。 

Satoh算法的C語(yǔ)言實(shí)現所涉及的運算領(lǐng)域有：有限域Fq，2-adic環(huán)Zq和2-adic整數環(huán)Z2，各個(gè)領(lǐng)域的元素之間的運算是大整數的基本運算，這里q=2160.2-adic整數環(huán)Z2中元素α的形式如同α=a1+a22+a322+a423+...an2n-1+...冪級形式，ai的值或為0或為1.由于算法只需要精度precision為83=［160+62］，2-adic整數環(huán)Z2中元素級數不能超出83.2-adic整數環(huán)中元素的數據結構定義為： 

Typedef unsigned long BIGword； 

Typedef  struct{ 

int  length 

BIGword  value［3］ 

}Z2word； 

兩個(gè)元素的相加減運算為模283意義下的大整數的加減運算，相乘為模283意義下的乘法運算。求元素a的逆元運算采用牛頓迭代算法，迭代的初始值為1（該元素為奇數，否則無(wú)逆元），迭代公式為x←x-x(ax-1)，迭代一次精度翻倍，達到所需83的精度要迭代7次。 

有限域Fq上的元素α=a1+a2t+a3t2+a4t3+...a160t159，其形式為一次數不高于159次的多項式，多項式的系數或為0或為1，兩個(gè)多項式相加為對應次數的系數模2加，減法與加法是一個(gè)運算。相乘為模一多項式f(t)=t160+t5+t3+t2+1意義下的乘法，在實(shí)際的運算過(guò)程中采用邊乘邊模的方法，也即次數出現160，就用低次多項式t5+t3+t2+1代替。求逆運算采用擴展歐幾里德算法。Fq元素的數據結構定義如下： 

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的構造可知，Zq中元素的形式為一次數不高于159的多項式，系數為2-adic整環(huán)Z2上的元素，這樣，我們可以定義Zq的元素數據結構。 

typedef  struct { 

int  length 

Z2word  coef［159］ 

}Zqword 

元素的加、減法運算同一般多項式運算類(lèi)似，只是對應次數的系數進(jìn)行加、減運算是2-adic環(huán)Z2上元素的加、減。乘法運算的處理方式如同有限域中元素乘法的運算處理。求元素a的逆運算采用牛頓迭代方法。迭代初始值求法為：首先將元素a系數模2，得到有限域上的一元素a‘，利用有限域上元素求逆方法計算出a‘的逆，a‘的逆即為迭代初始值。迭代多項式與2-adic整數環(huán)中元素的求逆迭代多項式相同。 

在上述基本運算得到解決后，我們著(zhù)手于橢圓曲線(xiàn)階的計算。隨機選取橢圓曲線(xiàn)y2+xy=x3+α（α為有限域中元素），利用Satoh算法可求出該曲線(xiàn)的階。每給出一個(gè)α值（實(shí)際上給出了一條曲線(xiàn)E），就會(huì )算出該曲線(xiàn)的階。 

a的選取 
 對應曲線(xiàn)的點(diǎn)的個(gè)數 
  
0x40582590ac00873494fc02b180ba640130acb252 
 0x1000000000000000000014c3ec7372a968d0b1138 
  
0xd80c00e8008e2021384a0243012d600554e10200 
 0xfffffffffffffffffffed059c32e5457a83e0314 
  
0x8992b8ca2b70624440f6003100411646002d102c 
 0xffffffffffffffffffff203b8ad8bf63e2891eac 
  


作者在攻讀碩士學(xué)位期間實(shí)現了素域上安全橢圓曲線(xiàn)構造的SEA算法，在后期學(xué)習和工作中，分別用Mathematica和C兩種語(yǔ)言實(shí)現Satoh算法。這兩個(gè)算法的實(shí)現解決了有限域上安全曲線(xiàn)的構造問(wèn)題，對今后的研究——橢圓曲線(xiàn)密碼體制在移動(dòng)通信領(lǐng)域中的應用做了充分的準備工作。 

6  結束語(yǔ) 

1.分析了將安全橢圓曲線(xiàn)引進(jìn)公鑰密碼體制的優(yōu)點(diǎn)是，與目前應用較普遍的ＲＳＡ算法相比，在同等安全的情況下，其所需的密鑰長(cháng)度遠比ＲＳＡ低，因而ＥＣＣ的特性更適合當今電子商務(wù)需要快速反應的發(fā)展潮流，在快速加密、密鑰交換、身份認證、數字簽名、移動(dòng)通信、智能卡的安全保密等領(lǐng)域，具有廣闊的市場(chǎng)前景。 

2.橢圓曲線(xiàn)公鑰密碼體制實(shí)現的關(guān)鍵是安全曲線(xiàn)的構造問(wèn)題，對此本文給出了實(shí)現Satoh算法驗證部分的技巧：首先計算小基域上一橢圓曲線(xiàn)階，通過(guò)Weil定理可知該曲線(xiàn)在其有限擴域上的階，若該階符合橢圓曲線(xiàn)公鑰密碼體制的要求，則將曲線(xiàn)嵌入到其擴域上即可求得一條安全曲線(xiàn)。 

參考文獻： 

［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. 

本文作者：華南農業(yè)大學(xué)理學(xué)院計算機系 郭艾俠