Elliptic Curve Cryptography and ECDH

If not redirected, please click here https://www.thesecuritybuddy.com/encryption/how-does-elliptic-curve-cryptography-work/

Elliptic Curve Cryptography or ECC is a public key cryptography which uses properties of an elliptic curve over a finite field for encryption. ECC requires smaller keys compared to non-ECC cryptography to provide equivalent security. For example, 256-bit ECC public key provides comparable security to a 3072-bit RSA public key.

Let's understand how Elliptic Curve Cryptography works.

What is an Elliptic Curve ?

An elliptic curve is a set of points described by the equation :

y² = x³ + ax + b

We can define a group G, such that elements of the group are points on the elliptic curve and apply that to generate a public-private keypair to do encryption.

Public-Private Keypair in Elliptic Curve Cryptography

If d is a random integer chosen from {1, 2, ..., n}, where n is the order of a subgroup (number of elements in the subgroup) and G is the base point (beginning and ending point) of the subgroup, then we can always apply scalar multiplication and find H, which is another element of the subgroup, such that

H = dG

The random integer d can be used as a private key and H as a public key.

Does this look confusing ?

Let's understand what the above statement actually means.

A group in Number Theory is a set with the following properties :

• If a and b are any two elements of the group and + is a binary operation, then (a + b) is also a member of the group.
• If a, b and c are any three elements of the group, then (a + b) + c = a + (b + c)
• For any element a of the group, a + 0 = a
  0 is called identity element of the group.
• For any element a of the group, there will always be another element b in the group, such that
  a + b = 0

We can define such a group G, such that elements of the group are points on the elliptic curve.

If P, Q and R are three points on the elliptic curve, then

P + Q + R = 0

This means, if we join any two points P and Q on the curve with a straight line, the straight line will intersect the curve at a third point called the inverse of R or -R. And, if we take a point symmetric to -R about the x-axis, we will get R, which is also a point on the curve. Here, 0 is a point on the curve called point of infinity.

Please note that, for any three points P, Q and R :

• P + Q is a point on the curve
• (P + Q) + R = P + (Q + R) = 0
• P + 0 = P
• And, for any point P on the curve, we will always get another point on the curve called inverse of P or -P, which is symmetric of P about the x axis. And,
  
  P + (-P) = 0
  
  
  

Hence, the points on the elliptic curve satisfy the properties of a group.

A subgroup H of a group G is defined as :

• H is a group
• members of H is a subset of G
• H and G share the same binary operation

Scalar multiplication of a Point P on the curve has the property that, after a certain point the result will repeat itself.

For example,

We can take a point P on the curve and find out P, 2P, 3P ... , we will always get n such that nP = P.

So, if we look back at the theory of generating keypairs in Elliptic Curve Cryptography, we can always find a random number d as a private key and do scalar multiplication of d and the basepoint G of the subgroup to get another number H, which can be used as a public key.

H = dG

So, it turns up to be :

We can always find a point on the elliptic curve and multiply it with another number to get another point on the curve. But, even if we know the original point on the curve and the resultant point, it would be computationally infeasible to find out the number by which the original point was multiplied. And, this is the basic theory of Elliptic Curve Cryptography.

Elliptic Curve Cryptography in Diffie-Hellman Key Exchange

Elliptic Curve Cryptography can be used in Diffie-Hellman Key Exchange. In ECDH mainly the following steps are followed :

• Alice and Bob generate their respective keypairs.
  
  H_A = d_AG
  H_B = d_BG
  
  d_A and d_B are the private keys of Alice and Bob respectively. And, H_A and H_B are the corresponding private keys.
• Alice and Bob share their public keys and the common basepoint G
• Alice calculates :
  S = d_AH_B
• Bob calculates :
  S = d_BH_A
• S = d_AH_B = d_A(d_BG) = d_B(d_AG) = d_BH_A S can now be used as the secret key using which the communication can be encrypted.

Applications of Elliptic Curve Cryptography

Elliptic Curve Cryptography is used in encryption, digital signatures, pseudo-random generators etc. They are also used in several integer factorization algorithms that have applications in cryptography, like Lenstra Elliptic Curve Factorization.

The article was meant to give some basic information on Elliptic Curve Cryptography. Hope you liked it.

Read More

How does Diffie-Hellman Key Exchange Protocol work ?

What is entropy and how do entropy and randomness improve security ?

What is Symmetric Key Encryption ?

What is Quantum Computing ? 

What is the difference between Symmetric Key Encryption and Public Key Encryption ?

How does TLS protocol work ?