Converting from John Napier’s Logarithms to Elliptic Curve Methods

Around ten years ago, discrete log and RSA methods were riding right. But both of these methods have struggled with increasing levels of security. For discrete log and RSA methods, we are now looking at 2K prime numbers. So, elliptic curve techniques have come along, and with relatively small prime numbers of 256-bits, and which have much-improved performance levels.

So how do we convert from a discrete log problem to an elliptic curve problem? Well, discrete logs are in the form of power:

Pub = g^x (mod p)

and where x is the secret, g is the generator value, and p is the prime number. For elliptic curves, we take a base point (G), and a secret value (x) and generate:

Pub = xG (mod p)

and where Pub is a point on the elliptic curve. And so we convert from logs to multiplication. The base operation in elliptic curves is to use point addition (P+P) and point doubling (2P).

So, let’s take an example. In our case we will implement the discrete log method for authenticated key exchange: