elikaski/ecc_attacksKnown attacks on Elliptic Curve Cryptography
In recent years the Elliptic Curve Cryptography approach has become popular due to its high efficiency and strong security. The purpose of this article is to present this topic in a relatively clearer way than it exists today on the internet.
In this article I will present what elliptic curves are, the basic operations that can be performed on them, and how they can be used in cryptographic context. The majority of this article consists of examples of known attacks on incorrect implementations or wrong uses of them. Throughout the article I try to separate the explanation into an intuitive and high level part, and a mathematical part that goes into more details. The reader is invited to focus on which of the parts that interests them in that place, and skip the parts that are less.
Happy reading!
In general, an elliptic curve is some kind of curved line. An example of this is the parabola, whose equation is of the form $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ and it looks like this:
In the context of cryptography, it is customary to use elliptic curves whose equation is of the form
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
For example, an elliptic curve corresponding to the equation $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ looks like this:
The equation of the curve defines the relation between the 𝑥 coordinate of a point on the curve and its 𝑦 coordinate. In a cryptographic context, we restrict 𝑥, 𝑦, 𝑎, 𝑏 to be integers, and restrict the calculations be modulo some large prime number. So the equation of the elliptic curve is:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
This means that we have a finite number of points on the curve. In mathematical language, the curve is defined to be over a finite field of order 𝑝. As a result now not necessarily every 𝑥 coordinate will have a corresponding point on the curve, because it may be that the 𝑦 coordinate corresponding to it is not an integer.
The set of points on the curve consists of pairs of integers (𝑥, 𝑦) that satisfy the equation of the curve. In addition to these points, another special point called "Infinity" is defined, and it is denoted by 𝒪. In mathematical language, this point is the neutral element of the set of points on the curve with respect to the addition operation, which we will define in the next section. The number of points on the curve (including the point 𝒪) is called the "order of the curve".
Another observation is that elliptic curves are symmetric to the X axis. Which means that if the point 𝑃 = (𝑥, 𝑦) is on the curve, then the point −𝑃 = (𝑥, −𝑦) is also on the curve. In fact, these points are considered "inverses" of each other (hence the marking −𝑃 for the second point), and the result of the addition operation between them is defined to be the neutral element 𝒪.
A theorem called Hasse's Theorem provides an estimation of #𝐸, the order of the curve, and is the order of magnitude of Θ(𝑝). More accurately:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Given two points on the curve, it is possible to define an addition operation between them, resulting in a third point that is also on the curve. To find this point geometrically, we draw a line between the two given points, and continue it until it intersects the curve at a third point. This point is reflected in relation to the 𝑋 axis, and the resulting point is defined as the result of the addition.
Here is a diagram that shows how, given the points 𝑃 and 𝑄, the point 𝑃 + 𝑄 can be found:
A question that may arise from this description is what happens if the line that is drawn between the two points does not intersect the curve again? In this case the line is said to intersect the curve at "infinity", and the result of the addition is the point 𝒪. Notice that this case happens if the drawn line is vertical, that is, we are trying to add a point 𝑃 with its inverse point, −𝑃:
Two basic identities are derived from this. For every point 𝑃 it holds that:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Another question that arises from the geometric description is how do we add a point to itself? We saw that in order to add two different points 𝑃 and 𝑄, we draw a line between them and look at the intersection point of its continuation with the curve. Intuitively, we will leave 𝑃 constant, and look at the line that is created as we move 𝑄 "closer and closer" to 𝑃, until 𝑄 will merge with 𝑃. What we will get is a line that is more and more "tangent" to the curve at the point 𝑃, and this is exactly the line we will look at when we want to add 𝑃 to itself:
To add a point 𝑃 to itself, we draw a tangent to the curve at the point 𝑃, and continue it until it intersects the curve at a second point. This point is reflected in relation to the 𝑋 axis, and the resulting point is defined as the result of the addition. It is customary to mark the result of the addition as 𝑃 + 𝑃 = 2𝑃. Again if the tangent does not intersect with the curve at a second point then it is said to intersect the curve at "infinity", and the result of the addition in this case is the point 𝒪.
These visual geometric descriptions illustrate nicely and help us understand how point addition works. But how do we actually calculate it? Mathematical equations, of course!
Given the points $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ and $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$, the result of their addition is the point $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ such that:
