Rubber-Ducking: Elliptic Curve Cryptography

[Nytro]

Rubber-Ducking: Elliptic Curve Cryptography

There’s a time-honored debugging method known as “Rubber Duck Debugging” in which one explains a process to others, or sometimes even to an inanimate object. The goal isn’t to get comments or notes during the explanation, but rather to come to a better understanding of the subject (or to find bugs) solely via the act of explaining itself. It’s pretty effective at a lot of things. This is the first in what I expect to be a long series of “Rubber-Ducking” posts in which I attempt to grasp a concept better by explaining it to you, a random reader somewhere on the internet. When reading these articles keep in mind that I’m explicitly stating right there in the title that I’m not an expert on the subject matter. If you know something that I don’t, if you’ve spotted a mistake in the article, point it out in the comments and I’ll revise it. Unlike many of my other articles, all of my corrections in Rubber-Ducking articles will be in strikethrough and my additions will be underlined so as to preserve the process for myself and future readers. Without further ado, let’s tackle our first project, shall we?

The subject of this first post is elliptic curve cryptography (ECC). I’m not going to delve into specific implementations like ECDSA, just the basic underlying concepts. The Wikipedia article I linked to above is a good rundown of the math, but ECC is a geometrically-based concept and I find it much easier to grasp such concepts visually. Why the good folks at Wikipedia chose not to include any graphs or diagrams, I’ll never know.

ECC begins with a simple equation in the form y²=x³+ax+b where x, y, a and b are real numbers. Different values of a and b yields a different elliptic curve. The equation y²=x³-5x+7 yields the following curve, for example:

It should be noted that certain values of a and b create curves which are not well-suited for use in ECC. If x³+ax+b contains no repeated factors (or equivalently, if 4a³+27b²?0) then it should be valid. The equation defines a group of points, all real numbers, which satisfy the equation. There is also a special point O called the “point at infinity” which is included in ECC sets to satisfy a couple of edge cases.

Once we’ve defined our curve, there are a few interesting things we can do with points on the curve. For example, we can select any two points P and Q which fall along the curve and add them to find a third point, R. For all values of P and Q, there is a P+Q=R which falls on the curve. Here’s how the addition works, geometrically speaking:

It’s relatively simple: Draw a line intersecting both P and Q. For all P and Q there will be one (and only one) additional point at which the line intersects the curve. This is -R. To find R we simply mirror -R on the y-axis since, for all values of -R there should be one (and only one) value of R. It’s worth noting that we have a valid reason for this -R and R y-axis mirroring nonsense: If we didn’t do this then P+Q=R would define a point R which, when added to P would create Q again. We wouldn’t move about the curve at all when performing such addition, just define a few interesting points.

Now this is all interesting and useful, but in order to build a useful cryptosystem we need a hard mathematical problem that is sufficiently difficult to solve (with current technology) as to be, for all practical purposes, impossible. Scalar addition such as P+Q=R oesn’t seem to be such a problem. So what else can we do with such an elliptic curve group? Let’s have a look at point-doubling…

Here we’ve taken a point P and drawn a

tangent line through it. Such a tangent line will intersect the curve at one additional point, -R which we then mirror along the y-axis to find R. In this case we’re looking at a diagram for P+P=2P=R. From this point we can use our first method to continue adding P to itself: 2P+P=3P, 3P+P=4P and so on. Now my instincts tell me we’re on to something here, but I’ve also got to admit that I’m having somewhat of a reality-check: computers are very bad at working with real numbers. We’ve got to make this work with integers somehow…

Let’s look at our original equation: y²=x³+ax+b for a moment. Now this defines a very large (infinite, actually) set of points, but we don’t want points which aren’t integers. Instinct tells me that this is a good case for the modulo operation. As it happens, instinct is right again. y² mod p = x³ + ax + b mod p yields a field of size p with finitely many inter points and any operation on said points also result in integer points.

The field F₂₃, (p=23) for example will yield a functional field of 0 to 23 on both the x and y axis and contains p-1=22 points which satisfy the elliptic curve equation – and here they are:

Note that we’ve lost all semblance of the original curvatures, but that there is still symmetry along the y-axis at the point p/2=11.5. Since our nice clean geometric procedures are irrevocably destroyed in this set, now would be the time to break out the equations which describe the lines and points we were drawing earlier.

P+Q=R where:

and 2P=R where:

This is the point that most ECC documents start at: a big long list of equations. In this case, I find it’s much easier to grasp the equations if you first grasp the geometry so hopefully you were prepared for that jumbled pile of math better than I was the first time I read it…

Now at this point we’ve got a collection of strange, though symmetrical, points across a field of size F₂₃ and a series of equations describing the rules for scalar multiplication (finding nP for a given P). ECC is based on the intractability of scalar multiplication products. Imagine that we’re still working in the field (F₂₃) we defined above and I give you two pieces of information: two points, R and Q. I ask you to find a value n for which R=nQ mod p. This is called the Elliptic Curve Discrete Logarithm Problem (ECDLP) and it’s every bit as difficult to solve as the

other discrete logarithm problem.

Of course we can brute-force ECC like anything else and even worse, nP will eventually circle back to the original P and form a big loop, so it wouldn’t be hard to solve our F₂₃ example; we’d just make a value of every possible nP until nP=P again. In reality, however, F₂₃ is an extremely small field. In practice field sizes would be more like 2¹²⁸ or 2²⁵⁶ and as such highly resilient to brute force. The most efficient algorithms for solving the ECDLP run in O(?n) time, where factorization runs in O(exp((64/9)

^1/3(log ^2/3) time (for a b-bit number) so ECC should be much more difficult to solve at a given key size than integer-factorization or finite-field cryptography which can be solved much more efficiently. It’s also worthy of note than fields over F₂m (binary fields) with non-prime m are vulnerable to Weil descent attacks [PDF warning] so best practice is to keep the field size prime.

There’s one more thing I forgot to mention: our special “point at infinity” O. O comes into play in a scenario like this one:

In this case our point P is on the x-axis (y_P=0) and so its tangent line is vertical. Such a line will never intersect with any other point on the curve, so in this case 2P=O. O is also the answer to a P+Q problem where x_P=x_Q, thus making the line PQ perfectly vertical. Wherever possible, such points should be avoided since if 2P=O then 3P=P, 4P=O, 5P=P and so on – not the makings of a very secure cryptosystem…

So there you have it, the basics of elliptic curve cryptography. For the specifics of implementation, well you’ll have to either ask someone else or wait until I get around to rubber-ducking ECDSA. I will note that several DLP-based protocols have been adapted to ECDLP by replacing the group Z_p with an elliptic curve, so there should be no shortage of study material out there.

Hopefully you learned as much as I did (and believe me I learned a lot – this article has taken days to complete) and hopefully I haven’t made any grievous errors or omissions. If you spot one, point it out in the comments and it’ll be fixed ASAP.

Thanks, and happy rubber-ducking to you all!

Sursa: Rubber-Ducking: Elliptic Curve Cryptography