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

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

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

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

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

5、q(x)=4x2m-2xm+1.Ρ=1.
　　 ·k=2l時,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通過r(x)的二次剩余測試的概念來構造新的橢圓曲線族.并給出了相應的算法.
　　 最后,本文將王明強老師[13]的橢網(wǎng)曲線上雙線性對是最優(yōu)對的等價條件推廣到橢圓曲線族上,并得到如下定理: