You should be familiar to handcuffed briefcases in spy movies. Most probably, shared secret key is in the briefcase and the agent transfers the secret key between parties in old fashioned way. Either courier’s hand is cut or he is kidnapped to steal the briefcase. So, handcuffs could not guarantee the security of the briefcase and key. In this post, we are going to perform Elliptic Curve Diffie-Hellman algorithm in python from scratch.
Vlog
High level explanation of Elliptic Curve Diffie Hellman
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Elliptic Curve Diffie-Hellman (ECDH) in Python From Scratch
Elliptic Curve Diffie-Hellman Scheme
Public key cryptography gives us opportunity to securely transfer secret keys in insecure channels such as internet or broadcasting. Alternative public key algorithms depend on exponential computations and they work on large numbers. That’s why, they have high computation costs. Herein, elliptic curves offer faster computations for key exchange operations. Previous posts related to elliptic curves are described theoretically. Now, we’ll put the theory into the practice as a real world example. Basically, key exchange could be applied by point addition and scalar point multiplication.
Suppose that Alice picks up her private key ka. Alice would compute her public key with multiplying her private key and public base point G. Then, Bob multiplyies Alice’s public key (Bob knows Alice’s public key because its public) and his private key kb. Likewise, Bob would compute his public key with multiplying his private key and public base point G. After then, Alice will multiply Bob’s public key and her private key ka. Finally, Alice and Bob both retrieves same shared secret key. This algorithm is also called as Elliptic Curve Diffie Hellman.
The Curve
We will adopt an elliptic curve in Weierstrass form in this experiment. Notice that bitcoin protocol adopts same curve in its implementation.
# Secp256k1: y^2 = x^3 + ax + b = y^2 = x^3 + 7
a = 0; b = 7
# base point
G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424)
# modulo
p = pow(2, 256) - pow(2, 32) - pow(2, 9) - pow(2, 8) - pow(2, 7) - pow(2, 6) - pow(2, 4) - pow(2, 0)
# order of the elliptic curve group
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
You can adopt Koblitz, Edwards or Twisted Edwards curves in your experiments. You will have to modify addition law for these curves then.
Addition Law
Now, we will implement addition law of Weierstrass curves. To find the point k x G faster where k is an integer and G is a point on that curve, we will use double and add method. Notice that point P = k x G can be calculated very fast for known k and G but extracting key k from known P and G is computationally hard. This is called elliptic curve discrete logarithm problem.
def add_points(P, Q, p):
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == y2:
beta = (3*x1*x2 + a) * pow(2*y1, -1, p)
else:
beta = (y2 - y1) * pow(x2 - x1, -1, p)
x3 = (beta*beta - x1 - x2) % p
y3 = (beta * (x1 - x3) - y1) % p
is_on_curve((x3, y3), p)
return x3, y3
def is_on_curve(P, p):
x, y = P
assert (y*y) % p == ( pow(x, 3, p) + a*x + b ) % p
def apply_double_and_add_method(G, k, p):
target_point = G
k_binary = bin(k)[2:] #0b1111111001
for i in range(1, len(k_binary)):
current_bit = k_binary[i: i+1]
# doubling - always
target_point = add_points(target_point, target_point, p)
if current_bit == "1":
target_point = add_points(target_point, G, p)
is_on_curve(target_point, p)
return target_point
Notice that we moved denominators in the addition law to numerators with their multiplicative inverse values for our modulo p. Extended Euclidean algorithm finds the multiplicative inverse of a number for some modulo. In that way, calculations will be integer always. This is called elliptic curves over finite fields.
Key Generation
Alice and Bob will generate a random integer. Recommended key size for ECC is 256 bits. This is equivalent to 3072-bit RSA.
# alice private key ka = random.getrandbits(256) # bob private key kb = random.getrandbits(256) # alice public key Qa = apply_double_and_add_method(G = G, k = ka, p = p) # bob public key Qb = apply_double_and_add_method(G = G, k = kb, p = p)
Key Exchange
Finally, we can monitor the key exchange between two parties. Alice knows her own private key and Bob’s public key. Similarly, Bob knows his own private key and Alice’s public key. They both find the corresponding point their own private key times other’s public key. Then, they will have same point!
# alice performs this calculation Sa = apply_double_and_add_method(G = Qb, k = ka, p = p) # bob performs this calculation Sb = apply_double_and_add_method(G = Qa, k = kb, p = p) assert Sa == Sb
Elliptic Curve Integrated Encryption Scheme
Elliptic Curve Diffie-Hellman is not the only way for secure messaging. Elliptic curve integrated encryption scheme (ECIES) offers both key exhange and symmetric key encryption.
High Level Explanation of ECIES
ECIES in Python From Scratch
How Secure?
Of course, computing Alice’s private key from her public key is possible. However, computation time would last too long with brute force attack in worst case scenario. The following code applies sample brute force attack. It starts from base point G and applies point addition repeatedly until it reaches to the public key. Basically, private key equals to the iteration count. Let’s look at the computational cost of attacking over private key value.
As demonstrated above, computation time of key exchange operation remains stable while private key value increased. In contrast, computation time of successful attack (in worst case) increases linearly while private key value increased. Maximum scale of the illustration equals to the 20 bit integer (1M), and successful attack approximately lasts 2 minutes. Minimum length of 256 bit private keys are strongly suggested by NIST for elliptic curve cryptosystems to offer same level security of AES-128. Moreover, trendline equation of the successful attack line is y = (6.0808x/50000) + 0.8818. This means 128 bit key requires more than 13×1026 years to solve with a single computer in the worst case scenario. If 1T (1012) computers run in parallel, then private key could be solved in 13×1014 years. As known, the age of the universe is 13×109.
To sum up, elliptic curves offer faster computations for key exchange operations. Moreover, known attacking algorithms run very slowly for elliptic curve cryptography. Thus, elliptic curves provide to transfer information securely on insecure channels.
Bonus: I’ve also shared the example of public key generation on finite fields in python on GitHub. In this case, public and shared keys are generated as integer.
Illustration: Scarlett Johansson with handcuffed briefcase in Lucy (2014)
Support this blog if you do like!
1 Comment
Comments are closed.