Cryptology ePrint Archive: Report 2017/264

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

Thomaz Oliveira and Julio López and Hüseyin Hışıl and 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.

Category / Keywords: Montgomery ladder, Scalar multiplication, diffie-Hellman protocol, RFC 7748

Original Publication (with minor differences): Proceedings of SAC 2017

Date: received 22 Mar 2017, last revised 1 Oct 2017

Contact author: francisco at cs cinvestav mx

Available format(s): PDF | BibTeX Citation

Note: This version shows a significantly improved differential addition formula

Version: 20171001:201612 (All versions of this report)

Short URL: ia.cr/2017/264