pairing-friendly橢圓曲線的構(gòu)造及該曲線上最優(yōu)對(duì)的研究.pdf

1、1985年,Neal Koblitz與Victor Miller獨(dú)立地提出了橢圓曲線密碼算法.該密碼算法的安全性是基于有限域上橢圓曲線點(diǎn)群中的離散對(duì)數(shù)問(wèn)題.對(duì)于求解橢圓曲線離散對(duì)數(shù),Pohig-Hellman方法的復(fù)雜度為(√r)(r是橢圓曲線點(diǎn)群的階).當(dāng)r過(guò)大時(shí),該方法是計(jì)算上不可行的.1993年Menezes,Okamoto,和Scott[6]利用雙線性對(duì),將求解橢圓曲線離散對(duì)數(shù)問(wèn)題約化到有限域上來(lái)汁算離散對(duì)數(shù).當(dāng)嵌入次數(shù)比較大時(shí)

2、,該方法在計(jì)算上是不可行的.2000年,D.Boneh和M.Franklin提出了基于身份的加密[16].2001年,D.Boneh,B.Lymn和H.Shacham提出了短簽名[17].自此,基于雙線性對(duì)的橢圓曲線密碼體制成為公鑰密碼學(xué)的研究熱點(diǎn).這些密碼算法都需要雙線性對(duì)的快速計(jì)算,這就使得橢圓曲線的嵌入次數(shù)不能太大.
　　 這些密碼體制的實(shí)現(xiàn)都需要構(gòu)造既安全又能快速計(jì)算雙線性對(duì)的橢圓曲線.這種橢圓曲線,它的嵌入次數(shù)比較小,

3、并且還要有大的素?cái)?shù)階子群.然而這種"pairing-friendly"曲線是稀疏的,需要特別構(gòu)造.對(duì)于pairing-friendly曲線.Freeman[9]提出了兩個(gè)評(píng)價(jià)參數(shù):1.嵌入次數(shù)k,既要滿足安全性需要又要能快速計(jì)算該曲線上的雙線性對(duì);2.ρ=logq/log r,衡量曲線點(diǎn)群中素?cái)?shù)階子群的大小.ρ越接近于1越好.
　　 在利用CM[3]算法來(lái)構(gòu)造給定階的橢圓曲線時(shí),只需要給出滿足CM方程的q,r,t作為CM算法的輸

4、入即可.Brezing和Weng[7]利用割圓域的理論構(gòu)造了q(x),r(x),t(x),進(jìn)而利用CM算法來(lái)構(gòu)造帶參數(shù)的橢圓曲線族.
　　 在k=3,6,2l時(shí),本文利用割圓多項(xiàng)式所具有的特殊性質(zhì)對(duì)該方法進(jìn)行了改進(jìn).并得到如下結(jié)果:
　　 ·k=3時(shí).r(x)=4x2m+2xm+1,t(x)=2xm+1,q(x)=(2xm+1)2.Ρ=1.
　　 ·k=6時(shí),r(x)=4x2m-2xm+1,t(x)=2xm+1,

5、q(x)=4x2m-2xm+1.Ρ=1.
　　 ·k=2l時(shí),r(x)=x2l-1+1,t(x)=-x2+1,q(x)=1/4((x2l-1+2+x2l-1)2+(1-x2)2).ρ=1+1/2l-2.
　　 本文還提出了-D通過(guò)r(x)的二次剩余測(cè)試的概念來(lái)構(gòu)造新的橢圓曲線族.并給出了相應(yīng)的算法.
　　 最后,本文將王明強(qiáng)老師[13]的橢網(wǎng)曲線上雙線性對(duì)是最優(yōu)對(duì)的等價(jià)條件推廣到橢圓曲線族上,并得到如下定理: