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

发布时间：2018-05-13 12:29

本文选题：余数系统 + 椭圆曲线点乘　；参考：《计算机工程与科学》2014年10期

【摘要】：椭圆曲线密码运算主要是椭圆曲线点乘,后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法,素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。(1)与传统上取两个几乎对称的余数系统不同,该方法取了两个非对称的余数系统。其中,余数系统Γ包括两个模数{2L,2L-1};余数系统Ω包括八个模数,它们都具有如2L-2 Ki+1的形式。这种选择使其模算术变得简单。(2)在上述非对称的余数系统中,大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外,计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时,需要四次余数系统下的蒙哥马利模乘,以压缩中间结果的值域。因此,计算一个N位的椭圆曲线点乘,需要的时间约为55.5 N·I,其中,I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。
[Abstract]:Elliptic curve cryptographic operation is mainly elliptic curve point multiplication, the latter is composed of a series of modular multiplication. By using the Montgomery modular multiplication algorithm in the remainder system, the modular multiplication of the module complement in the prime domain can be transformed into the base of the complementary system. A new method for computing elliptic curve point multiplication is proposed in this paper. It is different from the traditional method of taking two almost symmetric remainder systems. The method takes two asymmetric remainder systems. The remainder system 螕 includes two modules {2L ~ (2) L ~ (-1), and the remainder system 惟 includes eight modules, all of which have the form of 2L-2 Ki _ 1. This choice makes modular arithmetic simple. 2) in the above asymmetric remainder system, most of the modular multiplication operations which need to take the modules of the eigenvalues of the elliptic curve domain can be directly replaced by multiplication in the remainder system. In addition, a Montgomery ladder with only x coordinates is used to calculate the elliptic curve point multiplication. At the end of each parallel point and point addition, the Montgomery module multiplication under the system of the quaternion remainder is required to compress the range of the intermediate result. Therefore, it takes about 55.5 Ni to calculate the point multiplication of an elliptic curve with N bit, where I is a multiplication of L / 2 bits, a reserved carry-addition, and a total delay of an addition of L / 2 bits.
【作者单位】：清华大学微电子与纳电子学系;清华大学微电子学研究所;
【基金】：国家863计划资助项目(2012AA011402) 国家自然科学基金资助项目(61073173) 清华大学自主科研发展规划(20111081040)
【分类号】：TP332.2

【参考文献】