The World Has Fallen Head over Heels for Elliptic Curve Cryptography
The World Has Fallen Head over Heels for Elliptic Curve Cryptography
One of the great 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.