一種橢圓曲線參數(shù)生成的快速算法-Read

1、一種橢圓曲線參數(shù)生成的快速算法谷勇浩劉勇(北京郵電大學(xué)通信網(wǎng)絡(luò)綜合技術(shù)研究所 )摘要：橢圓曲線密碼體制是公鑰密碼中的研究熱點(diǎn)。該文介紹了橢圓曲線密碼體制的基本概念及相關(guān)知識(shí)，討論了目前基于離散對(duì)數(shù)問題的橢圓曲線密碼的研究動(dòng)態(tài)。本文的創(chuàng)新點(diǎn)是針對(duì)目前橢圓曲線研究重點(diǎn)之一一一橢圓曲線參數(shù)生成算法，給出了一種生成參數(shù)a、b的快速算法。這種算法利用了 Jacobi符號(hào)和二次剩余的理論，并且用matlab計(jì)算出利用這種算法生成一個(gè)橢圓曲線的平均時(shí)間，最后我們分析了今后橢圓曲線密碼系統(tǒng)的研究方向和重點(diǎn)。關(guān)鍵詞：橢圓曲線；離散對(duì)數(shù)問題；Jacobi符號(hào)；二次剩余；階1976年Difie和Hellman提出公

2、鑰密碼思想以來，國際上提出了許多種公鑰密碼體制 的實(shí)現(xiàn)方案。一些已經(jīng)被攻破，一些被證明是不可行的。目前，只有3類公鑰密碼體制被認(rèn)為是安全有效的，按照其所依據(jù)的數(shù)學(xué)難題劃分為：基于大整數(shù)分解問題(IFP),如RSA體制和Rabin體制；基于有限域離散對(duì)數(shù)問題( DLP),如Diffie-Hellman 體制和 曰Gamal 體制；基于橢圓曲線離散對(duì)數(shù)問題( ECDLP),如橢圓密碼體制。橢圓曲線應(yīng)用到密碼學(xué)上 最早是由Neal Koblitz和Victor Miller在1985年分別獨(dú)立提出的。 它是目前已知的公鑰體制 中，對(duì)每一比特所提供加密強(qiáng)度最高的一種體制。它具有安全性高、密鑰量小、靈活

3、性好的特點(diǎn)，受到了國際上的廣泛關(guān)注。而 SET(Secure Electronic Transaction)協(xié)議的制定者已把它 作為下一代SET協(xié)議中缺省的公鑰密碼算法。深入研究基于橢圓曲線離散對(duì)數(shù)問題的公鑰 密碼具有很大的現(xiàn)實(shí)意義。1建立橢圓曲線公鑰密碼體制1.1橢圓曲線域的參數(shù)在基于橢圓曲線的加解密和數(shù)字簽名的實(shí)現(xiàn)方案中，首先要給出橢圓曲線域的參數(shù)來確定一條橢圓曲線。在IEEE P1363標(biāo)準(zhǔn)中，定義其參數(shù)為一個(gè)七元組：T=(q,FR,a,b,G,n,h),其中q代表有限域GF(q), q為素?cái)?shù)或2m;FR為域表示法，如f(x)為F 2m域元素的不可約23多項(xiàng)式的表不法；曲線的方程，當(dāng)q為

4、素?cái)?shù)時(shí)，方程為 y =x +ax+b,當(dāng)q為2m時(shí)，、-r .232萬程為y +xy = x +ax +b , a,b是方程中的系數(shù)；G為基點(diǎn)；n為大素?cái)?shù)并且等于點(diǎn) G 的階，h是小整數(shù)稱為余因子且 h =#E(fJ/n。主要的安全性參數(shù)是 n,因此ECC密鑰的長(zhǎng)度就定義為n的長(zhǎng)度。1.2 橢圓曲線密碼的密鑰選取了基域 fq和橢圓曲線后，得到了在有限域Fq上的曲線E確定的具體形式，即上述的橢圓曲線域參數(shù)的一個(gè)七元組。每個(gè)用戶選取一個(gè)整數(shù)d(iwdwn-i)作為其私鑰，而以點(diǎn)Q=dG(G為基點(diǎn))作其公鑰，這樣形成一個(gè)橢圓曲線公鑰密碼系統(tǒng)。在這個(gè)密碼體制中，具體的曲線，基域 Fq，基點(diǎn)G及其階n,

5、以及每個(gè)用戶的公鑰都是該系統(tǒng)的公開參數(shù)，每個(gè)用戶的私鑰是保密的。1.3 基于橢圓曲線密碼體制的加解密假設(shè)用戶A欲將明文m加密后發(fā)送給B, A執(zhí)行以下操作：(1)查找 B 的公鑰(E( F q , G, n, QB)；(2)將m表示成一個(gè)域元素，即 mW f q ；(3)在區(qū)間1, n-1內(nèi)選取一個(gè)隨機(jī)數(shù) k;(4)計(jì)算點(diǎn) kG=(X1，y1)；(5)依據(jù)B的公鑰計(jì)算點(diǎn)kQB =(x2,y2),若x2=°，則返回到第(3)步；(6)計(jì)算C = m父x2 ；(7)傳送加密數(shù)據(jù)(x1,yi,C)給b。b收到a的密文(x1,y1,C)后，執(zhí)行以下操作。1使用私鑰dB，計(jì)算點(diǎn)dB(x1,y)=

6、(x2,y2)，再計(jì)算Fq中(x2)(2)計(jì)算m=C(x2),得到明文m。2橢圓曲線密碼的研究動(dòng)態(tài)2.1 橢圓曲線密碼的安全性ECC的安全性是建立在離散對(duì)數(shù)問題計(jì)算難度基礎(chǔ)之上，如果離散對(duì)數(shù)可以計(jì)算，從 一個(gè)用戶的公鑰就可得到他的私鑰，ECC就不安全了。對(duì)于一般的ECDLP,目前有兩種較好的求解法1: Pohlig-Hellman方法和Pollard- p方法。但是對(duì)于兩類特殊的橢圓曲線，已經(jīng) 有了其他有效的求解方法。一類特殊的橢圓曲線一一超奇異橢圓曲線2(設(shè)F q的特征為P,E / F q的q階Frobenius變換的跡t是p的倍數(shù)時(shí)，E稱為超奇異的)，采用概率亞指數(shù)算法一一MOV算法和FR

7、算法可以解決 ECDLP。另一類特殊橢圓曲線是異常 (anomalous)橢圓 m23曲線(設(shè)q = p , pw2,3為素?cái)?shù)，E / F q由萬程y = x ax b定義，Pc E( F q)的階為p。當(dāng)p=q時(shí)，異常曲線上的p階Frobenius變換的跡t=1) ,SSSA算法可以解決ECDLP。2.2 橢圓曲線的選取要保證橢圓曲線密碼的安全性，就是要使所選取的曲線能抵抗上述的關(guān)于ECDLP解決的方法和算法，所以選取一條安全的橢圓曲線，是一個(gè)深刻的數(shù)學(xué)難題， 在此，僅提供幾點(diǎn)橢圓曲線選取的安全準(zhǔn)則3：(1)為了抗擊Pollard- p攻擊，所選取EC的階#E(GF(q)的分解式中應(yīng)該包含一

8、個(gè)大的素 數(shù)因子，目前應(yīng)不小于 160bit;(2)為了抗擊 Weil對(duì)和Tate對(duì)的攻擊，對(duì)于K k< 30,n不能除(不宜選取超奇異橢圓曲線)；(3)為了抗擊Semaev-Smart-Satoh-Araki的攻擊所選曲線的階不能等于該曲線所定義的 有限域的階，即#E( F q)q (不宜選取異常橢圓曲線)；(4)對(duì)于二進(jìn)制域 GF( 2 )的度m不宜為合數(shù)。Gaudry, Hess和Smart提出，若m有小 約數(shù)l (l=4),存在比Pollard's rho算法更快求解 ECDLP的方法。下面介紹3種選擇適宜的橢圓曲線的方法：(1)僅限于有限域?yàn)?F 2m上構(gòu)造橢圓曲線。其

9、原理是將定義在特征值比較小的有限域的 橢圓曲線提升到該域的擴(kuò)域上去，并且 m能被小整數(shù)k>1整除。這種方法簡(jiǎn)單，但是得到 的曲線較少。(2) CM(Complex Multiplication)法，根據(jù)給定的階來選取符合此階的橢圓曲線。它的實(shí)現(xiàn) 速度相對(duì)較快，但這種方法產(chǎn)生的橢圓曲線具有附帶的結(jié)構(gòu)特征。從安全性角度講，這是一個(gè)潛在的威脅。32(3)隨機(jī)選取曲線。隨機(jī)選取曲線的參數(shù) a,bC Fq如果q是素?cái)?shù)，則滿足4a +27b #0；如果q=2m,則bw0,然后計(jì)算u=#E(Fq)和大素?cái)?shù)因子n,直到所選曲線滿足安全需求。這種方法比較理想，選取的曲線安全級(jí)別高，它完全依賴于橢圓曲線階的

10、計(jì)算。2.3 橢圓曲線階的計(jì)算從上述橢圓曲線的安全性來看，如果曲線的階充分大，平方根攻擊如Shanks's baby-stepgaint-step或Pollard's p方法就不太有效，要能抗擊Pohlig-hellman攻擊，一個(gè)好的策略是確保曲線的階 #E(Fq)中包含有大素?cái)?shù)因子(該大素?cái)?shù)作為所選取基點(diǎn)P的階)使得P,Pohlig-hellman算法的O(而)計(jì)算量不能實(shí)現(xiàn)。由此看來，計(jì)算#E(Fq)是研究定義在有限域上的橢圓曲線的一個(gè)核心問題。對(duì)于#E(Fq)的計(jì)算是一個(gè)純粹的數(shù)學(xué)問題。目前有兩種方法可以采用：(1)隨機(jī)選取一條定義于有限域 F q的橢圓曲線，直接計(jì)算該

11、曲線的階，使其滿足#E(Fq) 中包含有大素?cái)?shù)因子。 在這方面，R. School做了開創(chuàng)性的工作， 提出了著名的School算法， 后經(jīng) Atkin 和 Elkies 的改進(jìn)，提出了 SEA(School Elkies Atkin)算法。后來， Morain,Lercier 等人又對(duì)它作了一些優(yōu)化，如今 SEA算法已成為計(jì)算橢圓曲線階的有效算法。另外， Satoh 也提出了比較有效的算法及目前對(duì)于二進(jìn)制域效率較高的Satoh-FGH算法。(2)僅限于有限域?yàn)?F 2m且它要求所定義的 F 2m有限域中的m能分解為m=de,其中d為一個(gè)小整數(shù)，通過計(jì)算子域F 2d上的#E( F 2d),從而計(jì)

12、算出#E( F 2de)。這種方法簡(jiǎn)單易實(shí)現(xiàn)，但是適用范圍較小，不能計(jì)算出任意m或固定m的#E( F 2d)o2.4 橢圓曲線的快速算法在橢圓曲線密碼體制應(yīng)用中的大量運(yùn)算是倍乘(數(shù)乘)，就是一串點(diǎn)的加法運(yùn)算，即計(jì)算k*P=P+P+ ? +P共有k個(gè)P相加。橢圓曲線密碼快速實(shí)現(xiàn)的關(guān)鍵就是快速實(shí)現(xiàn)kP的運(yùn)算(包括算法優(yōu)化和程序優(yōu)化、軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn))。其中kP的運(yùn)算主要基于兩方面的運(yùn)算：基域上域元素和曲線上點(diǎn)的運(yùn)算。這些運(yùn)算與我們所選取的有限域、采用的坐標(biāo)系、基域中的元素表示方法、選取怎樣的橢圓曲線和計(jì)算kP的方法有關(guān)。因?yàn)橥换蛑械脑乇硎痉椒ú灰粯?如F 2m中有多項(xiàng)式和通項(xiàng)表示法)；不同

13、的坐標(biāo)系(如仿射坐標(biāo)和射影坐標(biāo))下，都會(huì)影響 kP的計(jì)算量。對(duì)于一些特殊的曲線，如 Koblitz curves ,已經(jīng)有了較好 的算法，但是對(duì)一般隨機(jī)的橢圓曲線，如何快速計(jì)算kP仍是一個(gè)需要研究的問題。3橢圓曲線參數(shù)快速生成算法3.1產(chǎn)生橢圓曲線的傳統(tǒng)算法通常情況下，從特定秩生成曲線組中隨機(jī)選取一個(gè)作為橢圓曲線。下面的算法生成基于GF(p)域的橢圓曲線參數(shù)，而且能夠生成足夠的信息能使其他人驗(yàn)證這樣的曲線的確是隨機(jī) 生成的。選定如下參數(shù)4：素?cái)?shù)模p；基點(diǎn)秩的上下界r max和min ；輸出長(zhǎng)為 B比特的 .$八函數(shù)H,其中 max minB- 1210g2(rminj以及Hash函數(shù)的輸入比特

14、長(zhǎng)L, L士B。=(v - 1)B ； w = v -Bs -1還要使用如下的符號(hào)v =，lOg2P I； s算法輸入：P，min，max，l max (用于測(cè)試的除數(shù)的上限，滿足l max min)；算法輸出：比特串 X; EC參數(shù)q=p, a, b, r, G(1)選擇長(zhǎng)為L(zhǎng)的比特串X;(2)計(jì)算 h=H(X);(3) 選取h的最右面的w比特串計(jì)為 W 0;(4) 將字符串X轉(zhuǎn)換為整數(shù)z;(5) I從1到s,作如下循環(huán)(5.(1) 數(shù) 億+i)mod( 2、轉(zhuǎn)化為長(zhǎng)為L(zhǎng)的比特串 X i ；(5.(2) Wi=H( Xi)；(6) 將所有的 W i以如下形式合并成 W:W =WollW1ll

15、-IIWs|代表連接(8)(9)將長(zhǎng)對(duì)為v-1的字符串W轉(zhuǎn)換為整數(shù)c；如果c=0或4c+27三0(mod p)則返回到(1);23選擇整數(shù)a, bwGF(p),滿足cb三a (mod p)；(最簡(jiǎn)單的方式是選擇a=c,(1。)給定基于GF(p)的橢圓曲線E: y3=X +ax + b,計(jì)算它的秩u；(11)(13)(14)測(cè)試u的素性概率；如果u幾乎不可能是素?cái)?shù)，則返回(1);否則通過？的輸出中含有k, r；生成秩為r的曲線輸出 X, a, b, r,E上的點(diǎn)G;Gob=co但是，出于性能的考慮，我們要選擇其他的a,b)-2為了計(jì)算(9)中cb三a3.2改進(jìn)的a、b生成算法3,(mod p),

16、已經(jīng)有很多中算法(例如，進(jìn)化算法) ，但是生成參數(shù)a, b仍然需要花費(fèi)很長(zhǎng)時(shí)間。根據(jù) IEEE 1363中介紹的方法生成橢圓曲線參數(shù)的時(shí) 間大約為15s,所以，生成一個(gè)橢圓曲線需要的時(shí)間仍然是一個(gè)有待解決的問題。為了解決橢圓曲線生成時(shí)間上的問題，本文將介紹一種新的方案，來解決23cb三a (mod p)計(jì)算上的問題。這種方法是基于雅可比符號(hào)( Jacobi Symbol)和二次剩 余(Quadratic Residue)理論。算法步驟如下：(1) 選定一個(gè)迭代數(shù)；(2) 隨機(jī)生成參數(shù)c (長(zhǎng)度為256比特)；(3) 生成向量M (a, b, f),其中a (長(zhǎng)度為256比特)是隨機(jī)的，b=0,

17、 f為一個(gè)大整數(shù)；(4) 處理向量M的過程：、一 1(4.(1) c(mod p);a3)1(4.(2) (行 (mod p)(4.(3) Jacobi 符號(hào)(h); p(4.4)如果(h) =1,prt r 2則 b 三 hmod p ；h、(4.5)如果(一)*1,則隨機(jī)生成新的a (長(zhǎng)度為256比特)，返回(4.1);p23(5) 計(jì)算 f = c b (mod p) - a (mod p)；如果 f = 0 ,則向量(a, b, c)就是生成的結(jié)果；(6) 返回(4),知道向量M中所有的EC都處理完;(7) 隨機(jī)生成新的c (長(zhǎng)度為256比特)，返回(3)。以上算法通過 Matlab運(yùn)

18、算，有如下結(jié)果:向量中EC數(shù)目生成所有EC的時(shí)間(s)生成每個(gè)EC的時(shí)間(s)1000670.06720001280.06450003090.0618有了這種算法，可以加快a、b的生成，再結(jié)合參考文獻(xiàn)4中介紹的其他參數(shù)的生成算法，就可以快速生成安全而且有效的橢圓曲線，并且可以把它用于生成抗攻擊的密碼系統(tǒng)中。4結(jié)束語橢圓曲線密碼是一種能適應(yīng)未來通信技術(shù)和信息安全技術(shù)發(fā)展的新型密碼體制，它在運(yùn)算速度和存儲(chǔ)空間方面占有很大的優(yōu)勢(shì)，目前它已成為公鑰密碼體制中的研究熱點(diǎn)。實(shí)際上橢圓曲線密碼算法還有幾個(gè)地方有待完算，今后主要的研究方向有3個(gè)方面5:(1) 如何快速選取安全性高的橢圓曲線。(2) 如何有效計(jì)算橢圓曲線的階。因?yàn)檫x取安全橢圓曲線的核心步驟是對(duì)橢圓曲線階的計(jì)算，對(duì)計(jì)算橢圓曲線階的有效算法的研究也是實(shí)現(xiàn)安全橢圓曲線密碼體制的 一個(gè)極其重要的環(huán)節(jié)。(3) 在橢圓曲線密