Advanced Systems Lab

Elliptic Curve Diffie-Hellman Key Exchange (ECDHE) is a popular method for establishing shared secrets using public key cryptography. Curve25519 is widely adopted for ECDHE because of its various advantages like fast modular arithmetic and short but secure public keys. Generally, the public keys generated are ephemeral in nature, and so speed of generation is critical and fast computations are vital.
Public key generation using Curve25519 requires arithmetic in the field F_2²⁵⁵-19. Fast arithmetic in this field is commonly done using so-called radix representations, in particular radix-2⁵¹ and radix-2^25.5.
We implemented a public key generation algorithm using Curve25519 and introduced a new radix representation, radix-2¹⁷. We hypothesized that a higher speedup is achievable using the radix-2¹⁷ representation because of its higher operational intensity as compared to the previously introduced radix representations.
In the process of optimizing the radix-2¹⁷ implementation we discussed the various grounds for optimizations and the main challenges we faced. By comparing the speedup of the optimized implementations of the various radix representations, we concluded that our hypothesis holds.

Our implementation can be found here and a written report can be found here.