邬可可,黄国伟,孔令晶

(深圳信息职业技术学院计算机学院,广东 深圳 518172)

0 引 言

1980年代中期，Miller[1]和Koblitz[2]分别独立地提出了椭圆曲线密码体制(Elliptic Curve Cryptosystems, ECC)。相对于其它的公钥密码体制，ECC只需较短的私钥就可以达到较高的安全级别，所以，近年来ECC受到广泛关注。在ECC中，标量乘dP是最主要且最耗时的操作。通常，标量乘采用逐比特的二进制方法来计算[3]。给定一个标量d和一个椭圆曲线点P，一个标量乘是由一系列的P点的点加(A)和点倍(D)操作完成，其运行的轨迹依赖于标量d的二进制比特表达式。该标量乘结构包括3个操作级别：标量乘的算法级别、点的算术级别和域的算术级别。本文专注于使用标量乘的算法级别来加速标量乘的计算。由于逐比特的串行操作，使得它的操作时间相对较长，对于标量d(比特长度为k)，二进制方法的时间复杂度达到了(k/2)A+kD。为进一步加速标量乘，各类二进制方法的变形相继被提出，如各类快速的标量乘方法如NAF方法、窗口NAF方法，以及滑动窗口方法等[4]。

然而，这些串行的标量乘方法已不能适应于日益普及的高性能并行计算系统。为适应高性能系统，并行的标量乘方法是迫切需要的，一些并行的标量乘方法也被提出。文献[5-6]介绍了基于SIMD处理器结构的高效并行点操作，基于2个或3个并行操作，采用改进的雅可比坐标(X,Y,Z,Z2)来开发快速并行表达式。文献[7-8]提出了双处理器架构的表达式。文献[9-12]介绍了替换乘方法，它允许更高效的优先并行操作的开发，从而能并行执行3个或4个操作的快速并行表达式。……