How to (pre-)compute a ladder: Improving the performance of x25519 and x448

Abstract

In the RFC 7748 memorandum the Internet Research Task Force specified a Montgomery-ladder scalar multiplication function based on two recently adopted elliptic curves “curve25519” and “curve448”. The purpose of this function is to support the Diffie-Hellman key exchange algorithm that will be included in the forthcoming version of the Transport Layer Security cryptographic protocol. In this paper we describe a ladder variant that permits to accelerate the fixed-point multiplication function inherent to the Diffie-Hellman key pair generation phase. Our proposal combines a right-to-left version of the Montgomery ladder along with the pre-computation of constant values directly derived from the base-point and its multiples. To our knowledge this is the first proposal of a Montgomery ladder procedure for prime elliptic curves that admits the extensive use of pre-computation. In exchange of very modest memory resources and a small extra programming effort the proposed ladder obtains significant speedups for software implementations. Moreover our proposal fully complies with the RFC 7748 specification. A software implementation of the X25519 and X448 functions using our pre-computable ladder yields an acceleration factor of roughly 1.20 and 1.25 when implemented on the Haswell and the Skylake micro-architectures respectively. © 2018 Elsevier B.V. All rights reserved.