关于椭圆曲线密码的实现.pdfVIP

关于椭圆曲线密码的实现 杨君辉．藏宗铎．，扬栋毅2·刘宏伟2 中国科学院软件所．．中国科技大学研究生院(北京)，信息安全国家重点实验宣 2北京兆日科技有限公司 摘要：本文从实现的角度．封论了椭圆曲线密码设计中的一些问题。涉及有限域的选择．基 底的选择。曲线的选择．点乘的计算方法和签名方案的设计等实际问题． 关奠词：椭圆曲线．数字签名． 1引言 椭凋曲线密码是基于有限域上椭四曲线有理点群的一种密码系统．它的安全性基于有限域上 椭圆曲线离数对数问题(EcDLP)是一个困难问题。椭圆曲线密码被普遍看好，披认为是新一 代公钥密码系统．我们先比较～下攻击RS^系统，攻击ElG锄al密码以及攻击椭圆曲线密码 所需要的计算量．EcDLP比有限域上的离散对数问题(DLP)要困难的多，攻击RsA或ElGa∞1 系统存在亚指数算法，而攻击椭圆曲线密码现在只有指数算法。记 三，(Bf)=expp(Jogp)’(109logp)。9)．上P(v，c)相对于参数lo印，当v：o肘是多项 式关系：考v=l时是指数关系：而O(v1对称为亚指数关系。熟知．对于模数为n的 lls^系统，用数域筛法分解n的计算复杂性是工．(1／3，c)．其中c是某个常数．同样用数域 筛法，求有限域GF(p)上的离散对数的计算复杂性是￡P(1，3，一)t其中c’也是某个常数· 而直至目前，已知求有限域上椭圆曲线的离敌对数(EcDLP)的计算复杂性是三。(1，f)．即攻击 RsA和E1G锄al系统存在亚指数算法，而攻击椭圆曲线密码是指数算法。因而，对于相同 规模的参数．椭涸曲线密码每一比特密钥的强度要大得多．耍得到同样强度的密码．椭圆曲 线系统的参数规模可以小得多。设n．N分别表示具有相同安全性的椭圆曲线系统和ElGⅫal 系统所依附的有限域的规模，那么 n，N有下面的关系： H=4．91Ⅳ”’(109(Ⅳl092”驯’ 线系统的安全性相当于1024比特的ElG锄1系统或RSA系统等等．可见椭圆曲线系统 的参数规模要小得多，而小的参数系统在实现与应用这两方面都具有较大的优越性。椭圆曲 线密码的另一优点是它的资源极丰富，有限域GF(q)中仅有一个乘法群．但GF(q)上被此 不同构的椭圆曲线的个数却大於q。因而，椭圆曲线密玛被普遍看好，披认为是新一代公 钥密码系统．本文从实现的角度，封论了椭圆曲线密码设计中的一些问题．涉及有限域的选 国家自然科学基金资助项目69873043) 32 ———矿F磊碾『———————一一 择，曲线的选择．点乘的计算方法，签名方案的设计等实际问题。 2有限域的确定 选用何种有限域上的椭圆曲线是首先遇到的问题。选择奇特征域还是特征2的域? 椭圆曲线密码的安全性基于有限域上椭圆曲线离散对数问题(EcDLP)是一个困难阔题。就目 前所知．EcDLP的计算复杂度仅和点群的阶有关，而与域特征的奇偶性关系不大．因此，是 选择奇特征域还是选择偶特征域主要应取决于密码实现的环境。一般地说，如果采用市面上 通用的处理器，由于它们通常只具有算术运算指令而缺少特征2域的运算功能．看来选择奇 特征域要方便些。如果是用硬件集成实现，由于乘法器将是实现密码的主要功能部件．故采 用特征2的域实现起来要容易得多． 2．1奇特征域的选择． 若选择奇特征的域，一般采用素域GF(p)．由于GF(p)中的运算是整数模p的运算，所以，可 个较小的数且其二进制表示的权w(a)(非零系数的个数)也较小．这能加快整数模p的运 算．下面是计算整数x模p=6”一口的非负最小剩余的算法： x． Input：integer mod 0utput：r=x p，O≤厂≤p一1．． 1．口0七一b，扩J‰卜x一日。6“，r+-％，j+_o． do： 2．卟ile吼0 3．扎．卜b，口，6“J‰卜g，d一饥。6m， 4．，+_f+l，r+_，+r． 5．While do r≥p r卜，一p． 6．Returnr． 2．2偶特征域及其基的选择． x9．63以及ANsIx9．62的修改稿等标准里， 偶特征域可选GF(2…)，160m．在ANxI 规定m必须是素数，这是由于当m是台数时，EcDLP的