Paper 2017/264

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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Proceedings of SAC 2017
Keywords
Montgomery ladderScalar multiplicationdiffie-Hellman protocolRFC 7748
Contact author(s)
francisco @ cs cinvestav mx
History
2017-10-01: last of 9 revisions
2017-03-25: received
See all versions
Short URL
https://ia.cr/2017/264
License
Creative Commons Attribution
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.