We have taken you on a magical journey through the world of cryptography. This is our final piece, where we’ll focus on the elliptic curve cryptography in detail. We’ll also have a look at what the future holds for us.
Let’s get back to our goal of finding efficient groups for cryptographic operations. We should remind you that in order to use a group as a base for Diffie-Hellman key exchange, the task of finding discrete logarithms in it must be complex. What does a task of finding a discrete logarithm in a set of points on the elliptic curve look like?
We stated the classical discrete logarithm problem in a group Z*p, where operations are traditionally written in a multiplicative notation. Regarding the set of points of the elliptic curve, we are talking about adding, i.e. we are working with additive notation. In that case, the task for finding a discrete logarithm is not the one of finding an exponent, but finding a scalar coefficient.
Let k be a positive integer k, P a point on the elliptic curve. Denote the k times sum of the point P with itself as
The notation [k]P can, of course, be generalised to non-positive integers:
Now we can phrase the additive version of the task of a discrete logarithm for elliptic curves:
For two given elliptic curve points P and Q, find an integer k, in case of which
[k]P = Q.
It turns out that if we choose the underlying elliptic curve well, the best-known algorithms for finding discrete logarithms are the generic ones. The question we need to answer now is what kind of a curve can be called a “good” one.
Above-mentioned examples used elliptic curves that were defined over rational or real numbers. Due to their infinite nature, the operations of these fields cannot be performed on a computer.1 This is why cryptography considers elliptic curves over finite fields, mostly Zp or Z2m.2
There is quite a lot of choice when selecting elliptic curves, and even the scientists are still arguing, which is the best or what does “the best” mean in terms of elliptic curves. Without digging deeper into these discussions, we note that, for example, the Estonian ID-card uses elliptic curve with a code name P-384, which is defined over the field Zp (where the prime p = 2384 – 2128 – 296 + 232 – 1) with an equation
where
b = 2758019355995970587784901184038904809305690585636156852142
8707301988689241309860865136260764883745107765439761230575.
It turns out that this group is cyclic3 and in order to perform cryptographic operations in it, it’s reasonable to select a generator. The coordinates of this generator point G are actually fixed as global constants, and you can find them in the FIPS 186-4 standard developed by the USA standards organisation NIST.4
How difficult is it to calculate a discrete logarithm in the given group? The best-known algorithms operate in time √n, where n is group order. As we see, the elliptic curve defined over a prime field Zp has approximately p points (this argument is precisely phrased in Hasse’s theorem5). Therefore, the complexity evaluation we are searching for is
operations, which is far outside the performance limits of current computers.
How to combine a cryptographic protocol from these scattered pieces? For example, we can „translate“ the Diffie-Hellman key exchange, represented in multiplicative notation, directly to the additive one. As a common public value, Alice and Bob use the base point G of the curve. In addition, they both choose themselves a secret integer between [1, ord(G) – 1] (where ord(G) is the order of the base point and the entire group); let these be a and b, respectively. Alice sends the point [a]G to Bob, and Bob, in turn, sends the point [b]G to Alice. Alice can now calculate a([b]G) = [ab]G, and Bob can calculate b(a[G]) = ba[G]. Since
they have successfully agreed upon a common secret.
But how does the elliptic curve cryptography operate on the ID-card? Actually, it’s all very simple. ID-card functions as a secret repository for the private key, whereas the private key is a randomly chosen integer k ∈[1, ord(G)-1]. The public key corresponding to it is [k]G. Pay attention that due to the complexity of the task of finding a discrete logarithm, finding the private key from the public key is practically impossible.
Authentic distribution of public keys is a complicated subject on its own. We won’t discuss it here, but, for example, in Estonia, it is solved by one large and common Public Key Infrastructure (PKI) for all ID-cards (and Mobile-ID chips).
If Alice wants to send Bob an encrypted message, she will first search for his public key [kb]G based on Bob’s personal identification number, and choose a one-time random integer ja. Alice will use the point ja([kb]G) = [ja * kb]G on the curve as the key for encrypting the message.6 Together with the encrypted message, Alice also encloses the point [j a]G. While decrypting it, Bob uses his private key kb on his ID-card, and calculates kb([j a]G) = [kb * ja] G with it, which is the necessary key for decrypting the message.
Once again, you’re correct, if you recognise the Diffie-Hellman key exchange. The only (although in many ways important difference is that Bob will not generate a new private key each time the message is exchanged, but will use the one, which is already on his ID-card.
Actually, a more common use case for the ID-card than exchanging secret messages, is signing. Signatures are generated with the Elliptic Curve Digital Signature Algorithm (ECDSA), and in case of further interest, you can find the exact description of it in the standard SEC1.7
You may ask, what’s next? Will elliptic curve cryptography protect us from all the information security problems now and forever? Unfortunately, not. All the ciphers will just get weaker in time, and it happens for several reasons. First of all, the development of computation techniques is still surging and someday performing 2192 operations might turn out realistic, after all (though, it doesn’t seem likely in the near future). Secondly, the algorithms are also evolving, and some cryptographer might discover a more efficient method to calculate discrete logarithms on elliptic curves compared to what we know today.
At the moment, the most realistic danger for elliptic curve cryptography seems to be the arrival of the quantum computer. It could run an algorithm developed by Peter Shor in 1994 which could find discrete logarithms a lot more effectively by taking advantage of the quantum effects of elementary particles.8
Smaller quantum computers have been built in research labs for decades already, but until now, none of them is powerful enough to break the cryptosystems based on elliptic curves. It’s hard to say when a computer like this will become a reality, but, eventually, it will happen. And by that time the latest, we must have developed new cryptographic standards. The work on them is in already progress, but the race between cipher developers and breakers will probably never end. Therefore, it leaves enough riddles for cryptographers to solve for a very long time.
Written by Jan Willemson
1 It may be surprising, because we all have seen real and rational numbers used on a computer. True, but this usage is limited. For example, the greatest real number which is supported by the IEEE 754 standard double precision floating point real number type, is approximately 1,7977 x 10308. For numbers exceeding that limit, you get an overflow error. This, in turn, means that the operations with real numbers in our daily software are not closed under ordinary operations of addition and multiplication. On the other hand, to achieve the elliptic curve group structure, a closed algebraic structure is required.
2 Since these fields are not continuous, the addition operations defined by tangents and intersections must be determined a bit differently compared to the above geometric intuition. There is no problem regarding intersection – equation of a line drawn through two points works over every field. In case of the tangent, however, we must first calculate the formal derivative for the curve equation, and find the “tangent line” using it. As a result, we get addition equations defined via the coordinates of the points. Interested reader can find more information from the article by Friedl (Stefan Friedl. An elementary proof of the group law for elliptic curves. Groups Complexity Cryptology, 9(2):117–123, 2017.) or the monograph by Washington (Lawrence C Washington. Elliptic curves: number theory and cryptography. Chapman and Hall/CRC, 2003.).
3 “Cyclic?” you may wonder. “Cyclic groups are the simplest kind of groups – how can any computation be complex in them?” That’s true, but the trick is that the discrete logarithm itself is an integer, and as a mathematical object outside of the group, finding it will turn out to be a very difficult task in general.
4 Digital Signature Standard (DSS), 2013. National Institute of Standards and Technology, Federal Information Processing Standard FIPS 186-4, https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf.
5 Lawrence C Washington. Elliptic curves: number theory and cryptography. Chapman and Hall/CRC, 2003.
6 In real life, it’s actually more complicated. The coordinates of the point of the curve will not usually be directly suitable for the keys of other cryptographic algorithms, therefore, they must be processed previously. At this point, I ask the reader to trust me when I say that it is possible with simple and standard methods.
7 SEC 1: Elliptic Curve Cryptography, 2009. Certicom Research, Standards for Efficient Cryptography, https://www.secg.org/sec1-v2.pdf.
8 P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, Nov 1994.