Three Dimensional Montgomery Ladder, Differential Point Tripling on Montgomery Curves and Point Quintupling on Weierstrass' and Edwards Curves

摘要

Elliptic Curve Cryptography is an important alternative to traditional public key schemes such as RSA. This paper presents (i) a simultaneous triple scalar multiplication algorithm to compute the x-coordinate of kP + lQ + uR on a Montgomery Curve E_m defined over F_p which is about 15 to 22% faster than the straight forward method of doing the same. The algorithm, motivated by Bernstein's paper on Differential Addition Chains, where the author proposes various 2-dimensional differential addition chains and asks for 3-dimensional versions to be constructed, can be generalized to other elliptic curve forms with differential addition formula, (ii) a formula for Differential point tripling on Montgomery Curves which is slightly better than computing 3P as 2P + P and relevant in the implementation of Montgomery's PRAC and (iii) an improvement in Mishra and Dimitrov's point Quintupling algorithm for Weierstrass' curves and an efficient Quintupling algorithm for Edwards Curves.