超椭圆曲线上Montgomery标量乘的快速计算公式

Fast Addition Formulae for Montgomery Ladder Scalar Multiplication on Hyperelliptic Curves

超椭圆曲线密码体制与椭圆曲线密码体制相比，具有安全性高、密钥短的特点．标量乘计算是这两个密码体制中最为核心和重要的计算，其中，Montgomery阶梯算法是计算标量乘的一种重要算法，且因为其可以抵抗简单的边带信道攻击，而被广泛研究和应用．近几年，椭圆曲线上的Montgomery阶梯算法和相应的点运算公式一直在不断改进，但是在超椭圆曲线上，直接设计快速运算公式来提高Montgomery阶梯算法的速度，却一直没有太大的进展．Lange曾经探讨过这种快速公式存在的可能性，但却并没有得到一个实用、有效的计算公式．在特征为2的域上，通过改进超椭圆曲线上的除子类加法公式来提高超椭圆曲线上的Montgomery阶梯标量乘计算，提出了一种新的思路来改进多种坐标系下的加法公式．分析和仿真结果表明，在特征为2的域上，新的运算公式的运行速度比之前的标准公式均有所提高．在某类常用曲线上，新的公式比之前的公式快了4％～8．3％．这说明，直接设计快速除子运算公式来提高Montgomery阶梯算法的速度是可行的．同时，使用新的公式实现的Montgomery阶梯算法可以抵抗简单边带信道攻击．

Comparing with elliptic curve （EC） cryptosystem, hyperelliptic curve （HEC） cryptosystem offers high level of security with shorter key size. Scalar multiplication is the most important and key operation in cryptosystems built on HEC and EC. Montgomery Ladder algorithm is an efficient and important algorithm to implement scalar multiplications for defending against side channel attacks. While Montgomery Ladder algorithm on elliptic curve is being improved in recent years, there is not much advance on hyperelliptic curves. Lange proposed a way to design faster addition formula on hyperelliptic curves but did not result in a practical solution. This paper improves the addition for divisor classes for the first time to implement faster Montgomery Ladder algorithm. New technique is applied for improving the formulae on various coordinates. The analysis and experimental results show that the new formulae are faster than previous ones. Over fields of character two and Type II curves, the new formulae is 4%-8.4% faster than the ones known before. And the Montgomery Ladder algorithm implemented in this paper is secure against side channel attacks.