椭圆曲线上标量乘法的快速实现研究

摘要

椭圆曲线密码体制(EllipticCurveCryptology,ECC)由于安全性高、存储空间小、带宽要求低等特点,特别适合应用在Smart卡和短距离无线通信领域中,从而得到了广泛研究。但是,在实现ECC的时候仍有一些关键性的问题有待解决,其中非常重要的一个方面就是ECC的快速实现问题。
　　 标量乘法是ECC实现过程中最基本、最耗时的运算,ECC的快速实现问题最终归结为标量乘法的计算。关于标量乘法的快速计算,主要有以下两条研究思路:一是对底层域算法进行研究,包括乘法、平方和求逆运算；二是找到标量的有效表示形式,从而减少点加次数。本文在前人工作的基础之上,主要对以下几点进行了详细的研究:
　　 (1)分析了底层域算法中的乘法、平方和求逆运算,并且在已有算法的基础上,提出了一种改进的无移位操作comb乘法算法。相比于原算法,新算法在保证无移位操作的情况下,需要更少的预存储空间。
　　 (2)由于在基于多基表示的标量乘算法中,需要多次用到5P的计算,所以本文设计出了一种有限域GF(q)上5P的快速算法。该算法利用转换求逆为乘法运算的思想,只用到了一次求逆运算,虽然乘法和平方运算有所增加,但是总的运算效率得到了提高。
　　 (3)通过对Dimitrov等人基于多基表示标量乘算法的分析,结合多基数系统和底层域的快速算法,提出了一种改进的基于多基表示的标量乘算法。由于对最优路径进行了分析,并且用到了2kp、3kp和5P的快速算法,使得新算法的效率要高于Dimitrov等人的算法。