International Association
for Cryptologic Research

The Montgomery ladder has a conditional statement. Existing constant time implementations of the Montgomery ladder are based on constant time conditional swaps or conditional selection of field elements. Implementations of the underlying field arithmetic require a multi-limb representation of the field elements. So, a swap or a selection of two field elements require a number of data movement operations which is proportional to the number of limbs. In this work, we introduce a new method for constant time implementation of the conditional statement. Our method does not require any swap or selection of field elements. Further, the number of involved data movement operations in our method is independent of the size of the underlying field. This leads to substantial savings in the number of data movement operations required for Montgomery ladder computation. We have implemented the new idea using 64-bit arithmetic for Curve25519 and Curve448, two elliptic curves which have been proposed in the Transport Layer Security, Version 1.3. Timing measurements on the Skylake and the Kaby Lake processors of Intel show that for Curve25519 about $11\%$ and for Curve448 about $13\%$ speed-ups are achieved.