047-有限域 上sea算法的几个问题

《047-有限域 上sea算法的几个问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、m*有限域GF(p)上SEA算法的几个问题赵涛顾纯祥祝跃飞张亚娟解放军信息工程大学信息工程学院训练部郑州450002解放军信息工程大学信息工程学院网络工程系郑州450002E-mail:gcxiang5209@hotmail.com摘要有限域(m)GFp上椭圆曲线密码体制具有自身特色特别是OEFOptimalExtensionFields的提出使对(m)GFp上椭圆曲线密码体制的研究具有一定的现实意义本文通过对(m)mGFp上SEA算法的实现的研究解决了GF(p)上安全椭圆曲线的选取问题在此过程中着重探讨了三个问题1(m)

2、F上平方GFp上平方根算法本文把p根算法平移到(m)GFp中并对平移后的算法作了改进提出了自己的算法2l-th模多项式c(x,j(E))mΦ在GF(p)[x]中的分解模式的计算本文针对OEF域特征较小一般l小于32比特的特点设计了具体算法3简单探讨了可除多项式的计算过程中分母出现零的问题最后我们给出了在OEF上SEA算法的实现效率及几组OEF上安全椭圆曲线参数实例关键字椭圆曲线Frobenius映射SEA算法OEF一引言近年来对椭圆曲线密码体制ECC实现技术的研究成为密码学界和产业界的一个热点椭圆曲线密码体制是基于有限域上

3、椭圆曲线离散对数问题的依据有限域的不同可分为两大类(2m)GF上ECC和GF(p)上ECC近年来文献[6]提出了OEFOptimalExtensionFields的概念文献[7]对它作了进一步研究并把它应用到公钥密码及ECC技术上来OEF上的ECC具有自身特色特别适用于智能卡等处理器字长较短的资源受限的环境另外和GF(p)上ECC相比在签名速度等方面还具有一定的优势因此对有限域(m)GFp上ECC的研究具有一定的现实意义对ECC的实现首先面临的问题*本文得到国家973项目G1999035804国家自然科学基金1993101

4、0河南省杰出青年基金0212001400资助便是安全椭圆曲线的选取问题从1998年起一些国际标准化组织便开始了对椭圆曲线密码体制的标准化工作制定了一系列标准化或草案文件[15]而各级安全层次上具体的椭圆曲线参数是这些标准的核心内容对于安全椭圆曲线的选取其核心步骤是对椭圆曲线阶的计算在这方面R.Schoof[6]做了开创性工作提出了著名的Schoof算法经Elkies[8]和Atkin[7]的改进该算法成为计算GF(p)上椭圆曲线阶的有效算法被称作SEA算法Morain,Lercier[9,14]等人又对它作了一些优化并把它

5、扩展到(2m)GF后来T.Satoh[18]及B.Skjernaa[19]又提出的Satoh算法该算法可以很好的计算出较小特征如p=2或3的扩域上的椭圆曲线阶目前已有许多工作小组实现了上述全部或部分算法并形成了可用的产品如[20]但是这些工作主要集中在(2m)GF上ECC和GF(p)上ECC我们小组在实现了GF(p)上SEA算法(2m)GF上SEA算法及Satoh算法后开展了对OEF上的ECC的研究因为Satoh算法并不适用于实用中的OEF域因此我们仍选用SEA算法本文以对(m)mGFp上SEA算法的实现为主线讨论了GF(

6、p)上的ECC实现技术中的几个问题1(m)GFp上平方根算法该算法是计算椭圆曲线上点坐标的必备算法本文把GF(p)上平方根算法平移到(m)GFp中并对平移后的算法作了改进提c出了自己的算法2l-th模多项式Φ(x,j(E))在GF(p)[x]中的分解模式的计算该算l法的效率对SEA算法效率极为关键本文针对OEF域特征较小一般小于32比特的特点设计了具体算法3本文还简单探讨了可除多项式的计算过程中分母出现零的问题最后我们给出了本小组在OEF上SEA算法的实现效率及几组OEF上安全椭圆曲线参数实例二SEA算法的简单介绍设E为有

7、限域F上的椭圆曲线本文中F的特征p皆为奇素数qq2332y=x+ax+b其中ab∈Fq∆=4a+27b≠0223记E(Fq)={(x,y)∈Fq

8、y=x+ax+b}∪{0}为E的Fq有理点群j(E)为E的j_不变量除特殊声明本文涉及的椭圆曲线都是扩域F上的这种形式椭圆曲线q对素数l(l<

9、,

10、t

11、<2qq因此如果找到tl(0≤tl≤l−1)满足2φ(P)+[q](P)=[t]φ(P)∀P∈E[l]---(1)l我们就可得到t≡tlmodl选取足够多的li使∏li>4p则由中国剩余定理i2(CRT)即可计算出#E(F)记l_th可除多相式为f(x)degf=(l−1)/2其根qll恰为E[