Paper 2017/264

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

Thomaz Oliveira and Julio López 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 proposed prime elliptic curves. The purpose of this function is to support the Diffie-Hellman key exchange algorithm included in the coming 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 when applied on the Diffie-Hellman key pair generation step. Our function combines a right-to-left version of the Montgomery ladder with the pre-computation of multiples of the base point and, by requiring very modest memory resources and a small implementation effort, it obtains significant performance improvements on desktop architectures. Moreover, our proposal fully complies with the RFC 7748 specification. 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.