特征3有限域上椭圆曲线的co-Z Montgomery算法

摘要

椭圆曲线公钥密码是公钥密码体制的主流方向之一.由于密钥短、计算速度快,该体制在智能卡和手机存储卡等受限的环境中得到了广泛的应用.椭圆曲线密码体系中最耗时的运算是标量乘.标量乘需要安全、有效、快速的实现算法.Montgomery算法是计算椭圆曲线标量乘的算法之一,它能够有效地抵抗简单能量分析.在Montgomery算法结构的基础上,文中首次利用统一Z坐标技巧和循环中间阶段不计算Y坐标的技巧,改进了有限域GF(3m)上椭圆曲线的点加和倍点公式,构造了抵抗简单能量攻击的co-Z Montgomery算法.设I,M,C分别表示有限域上的求逆、乘法、立方.当域上的平方和乘法使用相同的算法时,理论分析表明每轮循环中,co-ZMontgomery算法比仿射Montgomery算法快I+C-5M,比射影Montgomery算法快C+ 2M,比使用“Selected Areas in Cryptography”2012上快速点加、倍点公式的Montgomery算法快2C+M.在文章“特征3有限域上椭圆曲线的Montgomery算法”的模拟实验环境下,结果表明该算法比上述算法分别快26.3％、19.0％、20.6％;Sage云平台的实验结果表明该算法比上述算法分别快24.1％、20.1％、23.1％.%Elliptic curve cryptosystem is one of the main directions of public key cryptography.Because of the short key and efficient arithmetic,it has attracted increasing attention,particularly in resource-limited hardware environments such as smart cards and phone cards.Scalar multiplication is the most time-consuming operation in elliptic curve cryptosystems,which should be implemented safely,efficiently,and fast.Montgomery algorithm is a scalar multiplication algorithm on elliptic curves which is resistant to simple power analysis.Based on the structure of Montgomery algorithm,new formulas of point operations including point addition and point doubling of elliptic curves defined on finite fields GF(3m) are first introduced by using same Z-coordinate and not calculating Y-coordinate.Hence co-Z Montgomery algorithm which is resistant to simple power analysis is proposed.When squaring algorithm is implemented through multiplication algorithm over a finite field,co-Z Montgomery algorithm saves I+ C-5M more than affine Montgomery algorithm,saves C+2M more than projective Montgomery algorithm,and saves 2C+M more than Montgomery algorithm using the formulas of "Selected Areas in Cryptography 2012" where I,M,C stand for field inversion,multiplication and cube respectively.Experimental results on the platform of "Montgomery algorithm on elliptic curves over finite fields of character three" show that co-Z algorithm are 26.3％,19.0％,20.6％ faster than the previous algorithms respectively.Experimental results on Sage cloud platform indicate that co-Z algorithm are 24.1％,20.1％,23.1％ faster than the previous algorithms respectively.