# The World Has Fallen Head over Heels for Elliptic Curve Cryptography

## One of the greatest advancements in human kind?

Elliptic Curve cryptography (ECC) is on the top of the world just now, whether it is in signing transactions (ECDSA), or proving identity, or in generating a shared secret (Elliptic Curve Diffie Hellman — ECDH). It is the true king of the hill, and can do little wrong. While it’s public key peers —especially RSA — just seem so cumbersome, it trumps all with its sheer simplicity, and its beauty of operation is something to behold. Out of the box it does everything that we need in creating a truly trusted world.

When you connect to your corporate wi-fi network, you are likely to be using ECDH to generate your session key. ECDH is the method of choice too in the new WPA-3 standard and which finally gets rid of the horrible four-way handshake in WPA-2 for home wi-fi networks.

In Blockchain, too, we create the keys for our wallet by generating a random 256-bit value, and then derive the elliptic curve public key from this, and which is used to create our public address. It is sheer beauty in action.

In TLS 1.2, the horrible passing of a shared key with the RSA public key of the server (and which can lead to a long-term hack of all the keys used) has been dumped in TLS 1.3, and replaced of ECDH. There’s no more key generation with RSA in TLS 1.3, and the era of RSA is rapidly fading as its keys become ever larger and its flaws in key exchange are finally fully exposed.

In the Tor network — the way that the Internet should have been created — the key for each relay node is created by ECDH, and then these secret keys are then used to wrap data with protection. Each node has a uniquely generated key for every new session, and where it would be almost impossible to break the keys.

ECC is in your bank card, your smart watch, and virtually every other well designed IoT device.

So, in this article, I will cover the truly wonderful ECDH method, but if you want a background in Elliptic Curve Cryptography, please click here.

#### The secret generator that can do little wrong — ECDH

Elliptic Curve Diffie Hellman (ECDH) is used to create a shared secret key (and which will likely be used to encrypt some data using a method such as AES). In this case we use the elliptic curve defined as secp256k1 to generate points on the curve. Bob generates a public key (*QB*) and private key (*dB*), as will Alice (*QA* and *dA*). They then exchange their public keys, and the shared key will then be *dA*×*dB*×*G*, and where *G* is the generator point on the elliptic curve. Another popular curve is Curve 25519, and which is used by Tor nodes [here].

In this example we use secp256k1 (as used in Bitcoin) to generate points on the curve. Its format is:

*y²*=*x³*+7

with a prime number (p) of 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

and which is 2^256−2^32−2^9−2^8−2^7−2^6−2^4−1

And where all our operations will be (mod p)

Bob will generate a public key and a private key by taking a point on the curve. The private key is a random number (*dB*) and the Bob’s public key (*QB*) will be:

*QB*=*dB*×*G*

Alice will do the same and generate her public key (*QA*) from her private key (*dA*):

*QA*=*dA*×*G*

They then exchange their public keys. Alice will then use Bob’s public key and her private key to calculate:

SharekeyAlice=*dA*×*QB*

This will be the same as:

SharekeyAlice=*dA*×*dB*×*G*

Bob will then use Alice’s public key and his private key to determine:

SharekeyBob =*dB*×*QA*

This will be the same as:

SharekeyBob=*dB*×*dA*×*G*

And the keys will thus match.

The following illustrates the process:

A sample run is:

G: (55066263022277343669578718895168534326250603453777594175500187360389116729240L, 32670510020758816978083085130507043184471273380659243275938904335757337482424L)

P: 115792089237316195423570985008687907853269984665640564039457584007908834671663

Alice's secret key: 11302873530277286977317330088775295887228613968519091334644437952622729383175

Alice's public key: (43762022694931184757492607356752180905518342017728551120282167112666275442351L, 114384988717018399469597034834957578408750274128921832447140766594105794755401L)

Bob's secret key: 57357023452856094330375933847127925090028363431260832480927591194583881325524

Bob's public key: (55091946369527979001134485845266995342724549818123857460791054009076326226426L, 97187020471842083008659802753584322405090644904628617139758459912605661136781L)

==========================

==========================

Alice's shared key: (57532214745918139757345382685094974834256492408547750418623750043147069440196L, 96501482835335029014756728397878054304682795886955595404840493797142776000789L)

Bob's shared key: (57532214745918139757345382685094974834256492408547750418623750043147069440196L, 96501482835335029014756728397878054304682795886955595404840493797142776000789L)

==========================

The shared value is the x-value: 57532214745918139757345382685094974834256492408547750418623750043147069440196

Here is the code to generate this:

import collections

import hashlib

import random

import binascii

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve(

'secp256k1',

# Field characteristic.

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,

# Curve coefficients.

a=0,

b=7,

# Base point.

g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,

0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),

# Subgroup order.

n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,

# Subgroup cofactor.

h=1,

)

# Modular arithmetic ##########################################################

def inverse_mod(k, p):

"""Returns the inverse of k modulo p.

This function returns the only integer x such that (x * k) % p == 1.

k must be non-zero and p must be a prime.

"""

if k == 0:

raise ZeroDivisionError('division by zero')

if k < 0:

# k ** -1 = p - (-k) ** -1 (mod p)

return p - inverse_mod(-k, p)

# Extended Euclidean algorithm.

s, old_s = 0, 1

t, old_t = 1, 0

r, old_r = p, k

while r != 0:

quotient = old_r // r

old_r, r = r, old_r - quotient * r

old_s, s = s, old_s - quotient * s

old_t, t = t, old_t - quotient * t

gcd, x, y = old_r, old_s, old_t

assert gcd == 1

assert (k * x) % p == 1

return x % p

# Functions that work on curve points #########################################

def is_on_curve(point):

"""Returns True if the given point lies on the elliptic curve."""

if point is None:

# None represents the point at infinity.

return True

x, y = point

return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0

def point_add(point1, point2):

"""Returns the result of point1 + point2 according to the group law."""

assert is_on_curve(point1)

assert is_on_curve(point2)

if point1 is None:

# 0 + point2 = point2

return point2

if point2 is None:

# point1 + 0 = point1

return point1

x1, y1 = point1

x2, y2 = point2

if x1 == x2 and y1 != y2:

# point1 + (-point1) = 0

return None

if x1 == x2:

# This is the case point1 == point2.

m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)

else:

# This is the case point1 != point2.

m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

x3 = m * m - x1 - x2

y3 = y1 + m * (x3 - x1)

result = (x3 % curve.p,

-y3 % curve.p)

assert is_on_curve(result)

return result

def scalar_mult(k, point):

"""Returns k * point computed using the double and point_add algorithm."""

assert is_on_curve(point)

if k % curve.n == 0 or point is None:

return None

if k < 0:

# k * point = -k * (-point)

return scalar_mult(-k, point_neg(point))

result = None

addend = point

while k:

if k & 1:

# Add.

result = point_add(result, addend)

# Double.

addend = point_add(addend, addend)

k >>= 1

assert is_on_curve(result)

return result

# Keypair generation and ECDSA ################################################

def make_keypair():

"""Generates a random private-public key pair."""

private_key = random.randrange(1, curve.n)

public_key = scalar_mult(private_key, curve.g)

return private_key, public_key

print "Basepoint:\t",curve.g

aliceSecretKey, alicePublicKey = make_keypair()

bobSecretKey, bobPublicKey = make_keypair()

print "Alice\'s secret key:\t", aliceSecretKey

print "Alice\'s public key:\t", alicePublicKey

print "Bob\'s secret key:\t", bobSecretKey

print "Bob\'s public key:\t", bobPublicKey

print "=========================="

sharedSecret1 = scalar_mult(bobSecretKey,alicePublicKey)

sharedSecret2 = scalar_mult(aliceSecretKey,bobPublicKey)

print "=========================="

print "Alice\'s shared key:\t",sharedSecret1

print "Bob\'s shared key:\t",sharedSecret2

print "=========================="

print "The shared value is the x-value:\t", (sharedSecret1[0])

Here is a presentation:

#### Conclusions

The sheer beauty of ECC and ECDH is something to behold, and it has basically tipped up the world of computer security, and put privacy at the core of our Internet. I think it is one of the most wonderful pieces of engineering ever created.