Abstract: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.