[Resource Topic] 2017/264: A note on how to (pre-)compute a ladder

Welcome to the resource topic for 2017/264

A note on how to (pre-)compute a ladder

Authors: Thomaz Oliveira, Julio López, Hüseyin Hışıl, Armando Faz-Hernández, Francisco Rodrıíguez-Henrıíquez


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. Our estimates suggest that a full implementation of our pre-computable ladder should outperform state-of-the-art software implementations of the X25519 and X448 functions by a 40% speedup when working in the fixed-point scenario.

ePrint: https://eprint.iacr.org/2017/264

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .