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

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

##### 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. 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.

Note: This version shows a significantly improved differential addition formula

Available format(s)
Publication info
Published elsewhere. MINOR revision.Proceedings of SAC 2017
Keywords
Contact author(s)
francisco @ cs cinvestav mx
History
2017-10-01: last of 9 revisions
See all versions
Short URL
https://ia.cr/2017/264

CC BY

BibTeX

@misc{cryptoeprint:2017/264,
author = {Thomaz Oliveira and Julio López and Hüseyin Hışıl and Armando Faz-Hernández and Francisco Rodrıíguez-Henrıíquez},
title = {A note on how to (pre-)compute a ladder},
howpublished = {Cryptology ePrint Archive, Paper 2017/264},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/264}},
url = {https://eprint.iacr.org/2017/264}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.