Paper 2017/264
How to (pre-)compute a ladder
Thomaz Oliveira and Julio López and Hüseyin Hışıl 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)
- Publication info
- Preprint. MAJOR revision.
- 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
-
CC BY