Converting from John Napier’s Logarithms to Elliptic Curve Methods

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:

Now we convert to an elliptic curve:

We can see that the equivalence of the discrete log operation of g^x g^y in elliptic curve is a point add of xG + yG.

And that’s it. A sample run is:

Basepoint:   (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

Alice's private key:     112182946620095569313068193106676310957375623164976451752524757253399026715484330367307294625816278429414289459642113197237829111557118058464192847241596032297449187921128586528053754317950460274975438961933055849279960178942038178689394456375036655714306
Alice's public key:  (10665621333288112755013999333279623506032022287483445436500062192195137992261, 58087694570156162510209133003888730576005574255076918153317115930430271013098)

Bob's private key:   1468988400836128377421999167682421150352307983577137687590413218473080056222120777491053235068994917070676042106516175884578705431385693240344591844207481084161254087750678837037307095400106225527063136356179376479055205440596025739632025197568863059840571
Bob's public key:    (114781454701692031014020444918679178602807615038807261920001814037487990109703, 101749329057776542100848869379951481940093225037188581639788957889258085110222)
==========================
Alice's secret:  15676117802605500
Bob's secret:    9984497725715983

Alice passes:    (7588724046693894569412404779979229554789162286461724200993531586242150963559, 28434372896987165674720660999060654812396567367411485914818574690274023924527)
Bob passes:  (62103473263706976269069651027295469527060460943160998201863776592384240638574, 30553090632228810467699975753637193469152704161936665236587260632253288832148)
==========================

Alice's shared key:  79976801751791747837746155366814286293378413853532278453516279836430659630209
Bob's shared key:    79976801751791747837746155366814286293378413853532278453516279836430659630209

Now here is the code with the sep256k1 curve (as used with Bitcoin):

And here is a demo:

Conclusions

There you go … we convert from discrete logs (g^x) to an elliptic curve (xG).