Demystifying Elliptic Curve Cryptography
If you ever had even the slightest interaction with a cryptography related subject then I bet you have already heard the term “Elliptic Curve”. Indeed elliptic curves are dominating the cryptography landscape but for people other than Mathematicians the logic behind this may not be so obvious. I am therefore writing this post to give a gentle introduction in elliptic curves for people with basic mathematical background and explain why they are so popular amongst cryptographers.
Abstract Algebra Definitions
Let’s start off with a brief introduction with some terminology from abstract algebra.
Group: A group is an abstract mathematical object consisting of a set S together with an operation ○defined on pairs of elements of S (Note that the choice of symbol for the group is arbitrary) where:
- It is closed under the operation ○, that is, when a○b = c for any pair of elements a,b in S then c must also be in c.
- Operation is associative (a ○ ( b ○ c)) = (( a ○ b ) ○ c).
- There exists an identity element e in S such that: e ○ a = a = a ○ e (for all a in S).
- For each a in S there exists inverse element a⁻¹○ a = e = a ○ a⁻¹.
- The order of the group is the number of elements in S.
Abelian Group: An abelian group G is a group which also satisfies the commutative law. That is, for all a,b ∈ G, a ○ b = b ○ a
An example of a group is the following:
Field: A field F is a set with two closed operations, addition and multiplication where:
- (F,+) is an abelian group under addition
- Let F* = F-{0}, (F*, *) is an abelian group under multiplication
- Addition and multiplication are compatible. In other words, it satisfies the distributive law: Given x,y,z ∈ F, (x+y)z = zx+zy
Elliptic Curves
An elliptic curve is simply a curve like the ones illustrated below when defined over the real numbers.
I explicitly stated real numbers because in a finite field it looks completely different:
Although an elliptic curve(EC) can be generally defined over any finite field, in this post, we will only be working with elliptic curves defined over Zp ( integers modulo p) where p is prime greater than 3 for the sake of simplicity. The reason for this is a more technical property called the characteristic of a Finite Field where things are slightly different when this is equal to 2 or 3, but let’s forget about that for now.
Formally, an elliptic curve E over Zp is defined by an equation of the form:
along with a distinguished point ∞, called the point at infinity.
Given these, we can define a set E(Zp) which consists of all points (x, y) (where x,y in Zp) which satisfy equation (1), together with ∞.
Point Addition
In general, the addition of two points on an elliptic curve E(Zp) gives a third point on the curve and can be defined with a simple rule. More formally, let P=(x₁, y₁) ∈ E(Zp) and Q=(x₂, y₂) ∈ E(Zp) where P ≠ -Q then:
What’s more, if P=(x, y) ∈ E(Zp) then (x, y) + (x, -y) = ∞ ( point at infinity ). In fact, the point (x, -y) is denoted as -P and it is the inverse of P. (Geometrically, it is symmetric to P over the x-axis)
Lastly, adding ∞ to any point P in E(Zp) we always get P back. Formally:
P+∞ = ∞+P=P for all ∈ E(Zp)
Coming back to our group definition from above, the addition operation, inverse points and the set E(Zp) forms a group with ∞ as its identity element. This is exactly where elliptic curves become relevant in cryptography. These groups formed by elliptic curves are the groups used for building elliptic curve cryptosystems.
But, why?
Well, all these seem to make sense but one can wonder, why bothering with elliptic curve groups when we can clearly use finite fields? Let’s explain the reason with a simple real-world example.
Discrete Logarithm Problem (DLP)
In very simple terms, the discrete logarithm problem is defined as follows:
The discrete logarithm problem (DLP) is a well-known problem used in a variety of cryptographic protocols (DH, ElGamal, DSA), and of course, the security of those protocols underlies in the hardness of the problem.
Now, the difficulty of the problem depends on group G. That being said, the problem is very easy in (Zn, +), hard (Fp, *) or very hard ( Elliptic Curve groups).
Elliptic Curve Discrete Logarithm Problem (ECDLP)
If the above statement raises some question marks as to why it is harder on different groups let’s examine how the Discrete Logarithm Problem is defined over an elliptic curve group.
In other words, we are looking for a scalar to multiply P so that the product equals Q. Remember, we defined how a point addition is conducted over elliptic curves. Multiplication by n is thus n consecutive addition operations
This is considered more trusted since the known algorithms for solving the problem achieve an exponential time complexity. On the contrary, DLP is known to be solved in subexponential time with index calculus algorithms.
To put that in a cryptographic context, the security of a 1024-bit DLP key can equivalently be achieved with a 160-bit elliptic curve key.
For practical cryptography that is a huge improvement when it comes to implementing cryptographic protocols where efficiency/memory usage needs to be optimal ( especially for specific hardware implementations).
