Elliptic Curve Cryptography over Finite Fields
By Ayush Gupta
Cryptography underpins the present-day internet security infrastructure. Elliptic curves are extensively studied since the 18th century. Elliptic Curve Cryptography (ECC) does a great job of connecting both the fields. It was introduced by Neal Koblitz and Victor S Miller in 1985 and is one of the most widely used concepts in Public Key Cryptosystems. It is used in TLS and SSH protocols. It is also used in the blockchain protocol for address generation and authentication. ECC improves upon RSA by maintaining the same level of security with shorter key lengths.
I spent quite some time learning it from books and various online resources and finally decided to write this article. The aim of this article is to introduce ECC and build a basic mathematical intuition for it.
Introduction
Elliptic curves are represented by a common set of equations y² = x³+ax+b (ensuring that the discriminant 4a³+27b² ≠ 0 ). This image depicts a valid and an invalid curve. Invalid curves occur when the above condition is not satisfied and are marked by the presence of cusps and self-intersections (as shown in the second image below) in the graph.
You can notice that the curve is symmetric about the x-axis and for each value of x, at most 2 possible values of y exist. The additive identity is the point at infinity and is assumed to have 0 value.
In cryptosystems, a discontinuous version of this curve is used. The curve is defined over a finite field F of positive integers modulo p (where p is an odd prime number). Both x and y coordinates of each point on the curve belong to F. Thus the curve fits in a square-shaped graph with side p-1. The RHS of the equation always belongs to the set of quadratic residues of p. Quadratic residues modulo p are the integers that are congruent to some perfect square modulo p. This is because the LHS is always a perfect square!
It has been proved that the set of points in ECC always form an abelian group with the following properties:
- Closure: If points a and b belong to F, a + b also belongs to F
- Associativity: (a + b) + c = a + (b + c)
- Identity: There exists an identity element 0 such that a + 0 = a
- Inverse: Every element a has an inverse b such that a + b = 0
- Commutativity: a + b = b + a
The addition operator is described in the next section.
Point Addition
Point addition (or simply addition) of points P and Q on a given continuous elliptic curve can be interpreted as drawing a line connecting P and Q and extending it until it intersects the curve again at R. Point R is reflected across the x-axis to give the result -R. This is done to ensure that adding R to Q again should not give P. Thus P + Q + R = 0. The result can become bigger than expected and it might cause storage and computation problems. So we generally work with elliptic curves over finite fields.
In the case of finite fields, if the line reaches 0 or p-1 before intersecting again, it is warped across the borders. Thus the result of P + Q cannot get bigger than expected. The image below explains the process.
Addition can also be done algebraically using these formulas:
where m is the slope of the line joining P and Q. It has the same formula as in coordinate geometry given by :
When P = Q, the line becomes tangent to point P in the continuous ECC. The slope is calculated by evaluating the differential at point P :
A rigorous proof of the above equations in finite fields requires a thorough knowledge of the subject, so I have skipped it for now.
Multiplication
How can we multiply a point P with a scalar n (n≥0)? Similar to basic algebra, the product n*P can be realized as repeated point addition of P with itself i.e. P + P + P + P + … + P (n times). But that method is too slow for large n! For faster calculation, we represent n as a binary number and get the result in logarithmic time. For example, to evaluate 79*P, we convert 79 in its binary form as (2⁶ + 2³ + 2² + 2¹ + 2⁰)*P. Now, we can add each term separately as multiplication is distributive over point addition in elliptic curves. Thus we can evaluate the sum 2⁶*P + 2³*P + 2²*P + 2¹*P + 2⁰*P.
Now, the all the (kth power of 2)*P can be calculated in log(k) time as follows :
2*P = P + P
4*P = 2*P + 2*P
8*P = 4*P + 4*P
16*P = 8*P + 8*P and so on…
Finding n given and P and n*P is known as the elliptic curve discrete logarithm problem (ECDLP). It has no known polynomial time solution and it is the key to ECC’s security paradigm. Now you can guess what forms the public and the private key in ECC!
Order and subgroup of an elliptic curve
The number of points in an elliptic curve group is defined as its order. It becomes difficult to count even though we can reduce the search space by using quadratic residues. Schoof’s algorithm comes to our rescue! It was the first polynomial time solution to the problem and was published in this and this paper in 1985. Shank’s baby-step, giant-step method is also used to determine the order. It is a simple modification over the naive hit-and-trial method.
A subgroup is simply a subset of another group. We define a subgroup as the set of all points P can generate by multiplication with positive n. When using point P as a generator for calculating 2*P, 3*P … n*P, it is possible that the points start repeating after a few iterations. The number of iterations after which P is repeated again is called the subgroup order. It is always a divisor of the order of the group. For example, the curve y² (mod 97) = x³ + 17x + 23 (mod 97) has subgroup order 4 for the point P(17, 23). So the points visited when multiplying P by k would always be same modulo 4. Thus,
4kP = 0
(4k + 1)P = (17, 23)
(4k + 2)P = (14, 0)
(4k + 3)P = (17, 74)
You would always want to choose a P such that the subgroup size is large enough. In fact, you can choose it to be equal to the order of the group!
Application in Key Generation (Introduction)
So how to use all these concepts in designing cryptosystems?
Before all, an elliptic curve is chosen by the participants. Then, a point P is chosen such that subgroup order is large enough. As discussed above, the multiplier n is difficult to find due to the discrete logarithm problem. Thus, n it is made the Private Key while the product n*P is distributed as the Public Key. Given the public key and P, it is infeasible to guess the private key (due to the ECDLP problem).
But how do we prove the authenticity of the key holder?
Think over this a little bit! I will cover this and some interesting design problems in another article as this one is already getting too big. Meanwhile, you can find the answer to the question in this blog by Hackernoon. Moreover, this paper describes a very nice use case of ECC in authentication protocols. It also discusses several design details which must be considered while implementation of the cryptosystems.
I am concluding this section with an image which depicts the role of ECC address generation in bitcoin protocol.
Precaution while implementing Cryptosystems (Important!)
I feel that everyone should be aware of this! The vulnerability lies in the first step — choosing the curve. Certain curves are known to have a linear time solution to the discrete logarithm problem. Nigel P. Smart devised a technique, popularly known as the Smart’s attack, which exploits less secure curves. Pohlig-Hellman’s attack also exposes this vulnerability. To counter them, the chosen curve must be properly tried and tested beforehand.
RSA versus ECC
Now the question arises that why do we need ECC when there are techniques like RSA? The introduction states that ECC is better than RSA because it works well with shorter key lengths. NIST published a table comparing the key sizes required to achieve a similar level of security.
We can see that the ratio of the key sizes required in RSA and ECC goes on increasing from 6.40 in the first case to 29.48 in the last. This proves that ECC scales better than RSA. SSL usually employs RSA and keeps increasing the recommended key sizes after every few years. ECC can provide a better alternative for it. Moreover, ECC can be used in devices with limited storage and processing power. Advancements in IoT have already given rise to requirements of such systems.
Further Reading
Elliptic curves are studied in Algebraic Geometry. You can follow this book by Silverman for a more rigorous mathematical treatment. There are many other topics like Shank’s method, SEA algorithm, Pollard’s rho method etc. You can read them further from this amazing paper. I have referred to it invariably while writing this article!
If you are interested in the implementation of security systems using ECC, go through OpenSSL documents here. And lastly, if you are interested in cryptography in general, links to several useful books, articles and tools can be found here.
This is my first article on Medium. Please let me know if there are any mistakes. Looking forward to your feedback!
Thanks for reading!
