论文部分内容阅读
1985年Miller和Koblitz分别独立提出椭圆曲线密码体制(ECC, Elliptic Curve Cryptosystem) ,由于ECC本身计算速度快,存储空间小,带宽要求低,特别适用于Smart卡和无线应用环境等优点,很快得到了广大研究者的关注。标量乘法是ECC中最基本、最耗时的运算,就是已知域内整数k和椭圆曲线上一点P ,求椭圆曲线上另一点kP的运算,其效率决定着整个椭圆曲线密码体制的性能。计算标量乘法kP的过程有两个层次:一为上层运算,即椭圆曲线上的点加与倍点运算构成的有限阿贝尔群上的运算,另一个层次是底层域运算,即在有限域中为实现上层运算而做的算术运算。这些运算包括有限域上大整数的求逆、乘法、平方和加法。相应地,标量乘法的研究思路也分为两条:上层运算又细分为两个角度:即寻求标量k的有效表示形式和标量乘法算法的并行化。底层域上主要是寻求实现点加、倍点的快速计算。在前人工作的基础上,本文主要对以下几点进行了详细研究。(1)通过将直接计算dP + Q的快速算法应用于Comb算法,对素数域上Comb标量乘算法的赋值阶段进行改进,其中计算2 P +Q只需要11次乘法和7次平方。由于使用了高效的2 P +Q运算,使Comb算法效率得到了提高。对改进算法进行分析,当密钥长度l为160、192和224以及窗口宽度w为4和8时,在赋值阶段,改进算法效率比Comb算法大约提高79%。(2)在二进制域上,通过将折半运算应用于Comb算法,提出了一种新的Comb标量乘算法,它可以提高域F2上的椭圆曲线标量乘法的效率。在预计算阶段和赋值阶段,新算法分别用高效的折半运算取代倍点运算。对新算法运行时间进行分析,并与传统的Comb算法进行比较,当窗口宽度w =4时,预计算阶段效率提高68%～74%,赋值阶段效率提高19%～24%,总运行效率提高了58%～63%。(3)通过将交错技术与Koblitz曲线上的窗口TNAF标量乘相结合,给出一种新的标量乘算法,该算法不对标量乘进行预计算,只是在赋值阶段施加交错。由于Frobenius映射效率高,加之使用交错技术,新算法的效率比传统窗口NAF标量乘法要高。在密钥长度l为160、192和224以及窗口宽度w为4和8时,对新算法运行时间进行分析,并与传统算法进行比较,新算法效率比传统窗口NAF算法大约提高60%～75%,比Comb算法大约提高70%～79%。