一种新的余数系统下快速计算素域椭圆曲线点乘的方法

椭圆曲线密码运算主要是椭圆曲线点乘,后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法,素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。(1)与传统上取两个几乎对称的余数系统不同,该方法取了两个非对称的余数系统。其中,余数系统Γ包括两个模数{2L,2L-1};余数系统Ω包括八个模数,它们都具有如2L-2 Ki+1的形式。这种选择使其模算术变得简单。(2)在上述非对称的余数系统中,大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外,计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时,需要四次余数系统下的蒙哥马利模乘,以压缩中间结果的值域。因此,计算一个N位的椭圆曲线点乘,需要的时间约为55.5 N·I,其中,I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。