Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / elliptic curves scalar multiplication diffie hellman

Date: received 22 Mar 2017, last revised 20 Apr 2017

Contact author: thomaz figueiredo at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170420:205445 (All versions of this report)

Short URL: ia.cr/2017/264

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]