Saying Goodbye to Napier’s Logs, and Hello To Elliptic Curves

A Bluffer’s Guide to converting discrete log problems into elliptic curve ones — it’s all about point adding and point multip

Saying Goodbye to Napier’s Logs, and Hello To Elliptic Curves

A Bluffer’s Guide to converting discrete log problems into elliptic curve ones — it’s all about point adding and point multiplying

Before we start … let’s do some basics. John Napier found:

a^b a^d = a^{b+d}

and that:

(a^b)^c = a^{bc}

And, as every schoolchild should know:

5³ x 5⁷ = 5¹⁰

and that:

(6⁴)⁶=6²⁴

The Problem With Discrete Log Public Key

So, where is public-key encryption just now? Well, it all started with discrete logarithms (g^x mod p) and exponential ciphers (M^e mod p), and where people like Whitfield Diffie and Ron Rivest showed how a hard problem can be derived from exponentials. But that hard problem has become a bit easier as computing power has increased, so the prime number (p) has inflated itself to 2,048 bits and more. On the horizon, too, are quantum computers, and which don’t see our existing hard problems as hard anymore.

So, we are in-between, and the solution is to find something that works for all, and, especially allows limited processing devices to cope with things like digital signing. All the solution is … Elliptic Curve Cryptography (ECC). Basically, it has been the savour of public key encryption, and without it, we would struggle to secure the Internet. Overall RSA and the Diffie-Hellman methods have been shown off the stage, and ECC has replaced them in virtually every application area.

So, let’s say you are a researcher, and you read an original research paper from the 1990s, and now want to convert it to ECC. How do you do that? Well, it’s quite easy … we take an exponential operation (g^x) and then change it into a point multiplicative operation (xG). When we perform multiplication in discrete logs (g^x g^y = g^{x+y}), we convert this to a point addition operation (xG + yG). And so an operation of:

g^x (mod n)

becomes:

So, if we have:

(g^x) y = g^{xy}

then, in ECC, rather than raising to the power of y, we perform a point multiplication:

y (xG) = xyG

And for multiplication, we have the form:

g^x g^y = g^{x+y}

and which gets converted into point addition in ECC:

xG + yG = (x+y)G

And that’s it! Our powers become point multiplications, and our multiplications become point additions. So let’s take an example with both point multiplications and point additions.

A discrete log problem

The Diffie-Hellman key method is weak from a security point-of-view, as Eve can perform an Eve-in-the-middle attack, and Alice does not authenticate the value received from Bob, and vice-versa. One way to overcome this is MTI/AO key agreement [1,2], and where Bob and Alice perform a trusted key exchange for a one-time setup. This passes za and zb, and then each session passes public keys of apub and bpub. An outline is:

The first phase is a one-time setup, and where Alice and Bob agree on a generator value (g) and a prime number (p). Next Alice generates a private key of a and Bob generates a private key of b. Alice then passes her public key of:

za=ga(modp)

Bob passes his public key of:

zb=gb(modp)

When Bob and Alice want to generate a new key, Alice generates a random value x and Bob generates a random value y. Alice sends a public key value to Bob of:

apub=g^x (modp)

Bob sends a public key value to Alice of:

bpub=g^y (modp)

Alice then generates a shared key of:

Kalice=(bpub)^a (zb)^x (mod p)

and Bob generates:

Kbob=(apub)^b (za)^y (mod p)

These will be the same as:

Kalice=(bpub)^a (zb)^x (modp)=(gb)^a (gy)^x (modp)=g^{ba}g^{yx}(modp)=g^{ab+xy}(modp)

and Bob generates:

Kbob=(apub)^b (za)^y (modp)=(ga)^b (gx)^y (mod p)=g^{ab} g^{xy}(modp)=g^{ab+xy}(modp)

Elliptic Curve conversion

The first phase is a one-time setup, and where Alice and Bob agree on secp256k1. Alice generates a private key of a and Bob generates a private key of b. Alice then passes her public key of:

za=aG

Bob passes his public key of:

zb=bG

When Bob and Alice want to generate a new key, Alice generates a random value x and Bob generates a random value y. Alice sends a public key value to Bob of:

apub=xG

Bob sends a public key value to Alice of:

bpub=yG

Alice then generates a shared key of:

Kalice=a(bpub)+x(zb)

and Bob generates:

Kbob=b(apub)+y(za)

These will be the same as:

Kalice=a(bpub)+x(zb)=a(bG)+x(yG)=abG+xyG=(ab+xy)G

and Bob generates:

Kbob=b(apub)+y(za)=b(aG)+y(xG)=abG+xyG=(ab+xy)G

Coding

The following is the code [here]:

from secp256k1 import curve,scalar_mult,point_add
import random

print("Basepoint:\t", curve.g)

a  = random.randrange(1, curve.n)
aG = scalar_mult(a, curve.g)
b = random.randrange(1, curve.n)
bG = scalar_mult(b, curve.g)

x  = random.randrange(1, curve.n)
xG = scalar_mult(x, curve.g)
y  = random.randrange(1, curve.n)
yG = scalar_mult(y, curve.g)

k_a = point_add(scalar_mult(a,bG),scalar_mult(x,yG))
k_b = point_add(scalar_mult(b,aG),scalar_mult(y,xG))

print("\nAlice\'s secret key (a):\t", a)
print("Alice\'s public key:\t", aG)
print("\nBob\'s secret key (b):\t", b)
print("Bob\'s public key:\t", bG)

print("==========================")

print("\nAlice\'s session secret key (x):\t", x)
print("Alice\'s  session public key (xG):\t", xG)
print("\nBob\'s  session secret key (y):\t", y)
print("Bob\'s  session public key (yG):\t", yG)

print("\n==========================")
print("Shared Alice: abG+xyG: \t", (k_a[0]))
print("Shared Bob: baG+yxG: \t", (k_b[0]))

print("\n\n======Checking=========")
res=(a*b+x*y) % curve.n

res=scalar_mult(res, curve.g)

print("\n(ab+xy)G \t", (res[0]))

And a sample run [here]:

Basepoint:   (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

Alice's secret key (a):  78415154667220249194754078918779762453056721468760306709254177946012547971141
Alice's public key:  (99105229714153207673156985070193448370065961398966381789878734693715465172209, 110624902362275410698479512352481561725899665806375931075445037591290365955025)

Bob's secret key (b):    54561616670816631735058850292883594875584010720685581360400314879317249503108
Bob's public key:    (113733186086318903761015041328623689948056538055691950119005093813948221458090, 107903521773313888319620134964700827003653413067839301511388495653810557170752)
==========================

Alice's session secret key (a):  76616834241497302450896773294650589907854814474518231453401510983257719855837
Alice's  session public key:     (24023634351058590672106977617527332391972478575360369234145700134892339616865, 100885767930009484943614670462898176000583227593861181472494539077386853703775)

Bob's  session secret key (b):   71626425417421697561804712872377867220787646273545079991058910835106706879356
Bob's  session public key:   (5390516305312861583780866553511006508889363046035935478179214543880844748571, 108167309578588334529715598304887530494245835449345803403114120670801894220810)

==========================
Shared Alice: abG+xyG:   81373250065694576718644623930446201904803357573717034878729887795363849635428
Shared Bob: baG+yxG:     81373250065694576718644623930446201904803357573717034878729887795363849635428

======Checking=========

(ab+xy)G     81373250065694576718644623930446201904803357573717034878729887795363849635428

So, elliptic curves are where we are, but now we must also look to a post-quantum computer world …

References

[1] Matsumoto, Tsutomu, Youichi Takashima, and Hideki Imai. “On seeking smart public-key-distribution systems.” IEICE TRANSACTIONS (1976–1990) 69.2 (1986): 99–106.

[2] Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (2018), Handbook of applied cryptography. CRC press, Page 517–518.