最优素数域的优化蒙哥马利算法:设计、分析与实现

Optimized Montgomery Algorithms for Optimal Prime Fields: Design, Analysis and Implementation

蒙哥马利算法是公钥密码实现的基础算法,在椭圆曲线加密中的标量乘法和RSA算法中的模幂运算以及基于双线性对的密码中都有重要的应用.在基本的素数域运算中,高效实现多精度模乘法对于基于RSA和椭圆曲线的相关协议的效率至关重要.最优素数域是在2006年提出的一种特殊的素数域,所有的最优素数域都有一个为M=m2~k+l的形式,其中m和l的取值远远小于2~k.这种低汉明重量的素数域使得基于该域的域运算非常快.本文提出了几种特别为最优素数域设计的新的优化蒙哥马利算法,我们命名为最优素数域蒙哥马利算法,并且从理论上分析了新提出的最优素数域蒙哥马利算法的计算复杂性.为了评估新提出算法的性能,我们用C语言在AVR 8位微处理器上进行了实验.实验结果表明:与标准的蒙哥马利算法比较(操作数长度为160位到256位),最优素数域蒙哥马利算法最多可以节省36.5%到41.5%的执行时间.

The Montgomery algorithm is one of the corner-stones of public-key cryptography, with important applications in scalar multiplication in elliptic curve cryptography, and modular exponentiation in the RSA algorithm as well as pairing-based cryptography. Among the fundamental field arithmetic operations, efficient implementation of the multi-precision modular multiplication is crucial for the performance of protocols based on RSA and ECC. Optimal Prime Field(OPF) is a family of prime field proposed in 2006, it is defined by a prime of the form M=m2~k+l, whereby m and l are much smaller than 2~k. Computation on OPF is significantly fast thanks to the low Hamming weight. This paper presents several new Montgomery algorithms specially designed for OPFs, namely, OPFs Montgomery algorithms. We then theoretically analyze the computation complexity of the proposed OPFs Montgomery algorithms. In order to evaluate the performance of OPFs Montgomery algorithms, we implement the proposed algorithms in C language on AVR Studio for the 8-bit microcontroller. A comparison with the normal Montgomery algorithms shows that, for the best OPFs Montgomery algorithm, a speedup of 36.5% to 41.5% can be achieved over the fastest general Montgomery multiplication from 160-bit to 256-bit length operands.