Elliptic Curve Cryptography Explained (2019) | Hacker News Reader

Elliptic Curve Cryptography Explained (2019)

fangpenlin.com

298 pointsptr44 comments

I don't know ECC at all. But a note:

Finite fields are of two types: "Prime Fields" (such as the mod 19 field discussed in this blogpost), and "Extension Fields" (which would be prime^n, such as 19^2 or 361. Or more commonly, the 2^x fields, such as 2, 4, 8, 16, 32, 64... 256... 65536 ... because the 2^x fields correspond very closely with binary numbers).

Prime fields can be taught very quickly: maybe 30 minutes of study and examples is all you really need to really get what is going on. Be it a 2, 5, or 19 field, its really cool and simple.

The "leap" from prime fields into extension fields takes a few hours of dedicated study (which probably will be done over a week to a month if you're a busy adult like me) if you plan to do it rigorously. A lot of blogposts, textbooks, and other reference material will handwave the extension field because its... really hard math.

My best advice is "believe in the textbooks", extension fields are possible. And this is one of those situations where you can just "believe in the math" and learn the details of extension fields AFTER you understand the applications of them. "Extension Fields are like prime fields but way more tricky". They behave like a prime field in almost every way that's important, but its just way harder to understand.

--------

I do recommend making the leap at some point, and truly understanding the extension fields. Once you get there, you finally understand the underlying math behind CRC32, AES, GCM mode, and ECC. Its a very worthwhile endeavor, but you really need to dedicate yourself to quiet study for some time to really get the concepts.

Do you have a recommendation for a good source to go to for making this leap?

I banged my head against Chapter 4 for "Algebraic Codes for data Transmission" by Richard E. Blahut. And you need probably Chapter 2 before you can understand Chapter 4. (Chapter 3 is on basic error-correction concepts). The rest of the book is on CRC32, Reed Solomon, and other such error correction concepts. So if you only care about extension fields, its all about Chapter 2 and 4.

I... don't know if I can "recommend" the source, but that's the chapter that finally made me understand extension fields.

Its difficult math. You need to cover groups (number systems that always have "addition"), rings (number systems that always have "addition" and "multiplication"), and fields (number systems that always have "addition", "Multiplication", and "division" ) for... some very precise definition of addition, multiplication, and division.

Once understanding the properties of groups, rings, and fields, the textbook will step you through prime fields. The proof for why prime fields work requires a deep understanding of group and ring properties (so you really can't skip the group / ring discussions).

Then extension fields start to get discussed and the fun really begins. Do you know about polynomials? Such as x^2 - 1 == (x+1) * (x-1) ?? Ever consider that because "x-1" can't be factored, that its kinda-sorta like a prime-polynomial (like prime numbers, a prime polynomial can't be factored).

Ever think about polynomial arithmetic of a polynomial over a modulo of a prime polynomial? Well... there ya go. An extension field. Obviously (/s of course, its not obvious but... that's the gist).

And you know that works because that's pretty similar to arithmetic of a integer over a modulo of a prime integer (aka: the Prime Fields).

Yeah, same thing right? Lol.

If you already have the abstract algebra background then a good Galois theory textbook like Ian Stewart’s will do.

My issue is that I was a Comp. Engineering major.

Sure, I've got some mathematical training (Fourier transforms, matricies, etc. etc.) but my classes never covered Abstract Algebra. A lot of this stuff is coming out of left-field for me: just never really studied anything in this branch of mathematics.

It's actually not that hard. An extension field of field F comes from an irreducible polynomial f(x), irreducible meaning that in any factorization f(x)=g(x)h(x), g or h is a constant. Say f(x)=x^n+cx^{n-1}+...+d. The extension field is then denoted by F[x]/(f(x)), which means that every polynomial with coefficients in F represents an element of the extension field, and you set f(x)=0, so anywhere you see x^n, you can replace it with -(cx^{n-1}+...+d).

For example, the complex numbers are represented in this notation as an extension over the reals R by R[x]/(x^2+1). In this notation, "x" is essentially acting the same as "i" in the conventional complex-number notation, because anywhere you see x^2, you can replace it with -1.

Multiplication works by multiplying polynomials as usual, then reducing the x^n terms to lower-degree polynomials. Inversion of a polynomial g(x) with degree less than n works by solving the equation g(x)h(x)=j(x)f(x)+1. Since g(x) has lower degree than f(x), and f(x) is irreducible, they are coprime, so appropriate h(x) and j(x) can be found using Euclid's algorithm (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#S...). OK, maybe that last bit is a little advanced, but Euclid's algorithm is also very simple arithmetic.

Great description. I’d say it’s also important to note that in this context, the division slash means you divide the “numerator” into equivalence classes such that the difference between any two elements in a class is divisible by the “denominator”; i.e., class elements are equivalent mod the denominator. So for instance, x^2 and -1 lie in the same class because x^2-(-1) = x^2 + 1

Yeah, that's important for quotients by more general ideals, but for a principal ideal in a polynomial ring, it's easier to speak of setting the generator to zero.

I usually explain extension fields as similar to complex numbers with regards to reals.

I've collected a lot of extension fields references while working on my own implementation: https://github.com/mratsim/constantine/tree/master/constanti...

The best likely being

- Arithmetic of Finite Fields Chapter 5 of Guide to Pairing-Based Cryptography

Jean Luc Beuchat, Luis J. Dominguez Perez, Sylvain Duquesne, Nadia El Mrabet, Laura Fuentes-Castañeda, Francisco Rodríguez-Henríquez, 2017

https://www.researchgate.net/publication/319538235_Arithmeti...

> I usually explain extension fields as similar to complex numbers with regards to reals.

Its a good analogy and the math is indeed very close to complex vs reals.

If you consider "i" to be the "polynomial variable", then a prime-integer field vs a (prime-integer)^2 extension field is pretty much identical to real vs complex.

Of course, there's a prime^3 extension field, or a prime^4 extension field, and then the analogy kind of stops working.

EDIT: Now that I think of it... I can't really decide if complex-numbers are like a prime^4 field or like a prime^2 field. i^4 == 1 after all.

In a prime^2 field, the variable x^2 == 1. In a prime^200 field, x^200 == 1. Etc. etc.

-------------

Really, the glorious thing about extension fields is that a well selected extension field follows the fundamental theorem of algebra (which is... in simple terms... "All Polynomial equations have an answer that can be represented by your number system". Ex: (x^2 + 1 == 0) not only can be solved by a complex number x = i, but all such possible equations are proven to have an answer).

So you get all the benefits of integers (such as perfectly mapping to 2^8 == 256), with none of the downsides of real (aka: uncountably infinite, rounding errors, etc. etc.). You get precision while still keeping your property of "having answers" to a huge class of important algebraic problems.

The complex numbers are a degree 2 field extension over the real numbers.

The general theorem is that for a field k, and an irreducible (meaning it can't be factored with coefficients in k) polynomial p(x) with coefficients in k, the smallest field containing a root of p(x) and k is a vector space (over k) of dimension deg p(x). The irreducible polynomial corresponding to i is x^2 + 1 = 0.

Similarly, a finite field of order q = p^r can be constructed with an irreducible polynomial of degree r with coefficients in the prime field of order p.

Please note that a field that "satisfying the fundamental theorem of algebra" is not really a thing. The term you're looking for is algebraically complete field. The fundamental theorem of algebra states that the complex numbers are algebraically complete.

Also note that every algebraically complete field is infinite. So the finite fields used in CS applications such as cryptography are never algebraically complete.

To those curious: IIRC Extension fields can be described by polynomials.

Example: F_2 = { 0, 1 }.

f(x) = x^2 + x + 1. (This is "irreducible", which basically means it's "prime" in a polynomial world.)

Note that F_2[x] is the set of polynomials with variable x and scalars in F_2.

F_2[x]/f(x) = { 0, 1, x, x + 1 } (for each polynomial, take it modulo f(x)). This is because we know that x^2 + x + 1 = 0 => x^2 = x + 1 (please read = as "equivalent" - really, these relations should be modulo x^2 + x + 1).

|F_2[x]/f(x)| = 4. 2^2 = 4. This is not a coincidence. The degree of the polynomial determines the size of the resultant field. For F_p[x]/h(x), where p is a prime and h(x) is irreducible with degree d, |F_p[x]/h(x)| = p^d.

Another Example:

g(x) = x^3 + x + 1. (This polynomial is also irreducible.)

F_2[x]/g(x) = { 0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1 }

|F_2/g(x)| = 8 = 2^3.

Edit: Also, I forgot to mention that the values in the resultant fields F_2[x]/f(x) (and F_x/g(x) correspondingly) should really have the form [v]_f(x), where v is in F_2[x]. That is, they are congruence classes modulo f(x) of values in F_2[x].

That's a decent summary. But it helps if people knew about prime fields (and I expect most people don't know enough about prime fields to learn about extension fields).

Prime Field 2 (F_2) is too small and too easy to be a good example. I prefer teaching prime fields with Prime Field 5.

5 is a prime number, which means standard math modulo 5 results in a finite field.

There are three attributes of a field:

1. An "addition" operator exists.

2. Every value "v" in the field has a value -v, also known as the "additive inverse". v + (-v) == 0 by definition. The value "0" is defined to be the "additive identity"

3. A "multiplication" operator exists.

4. EVERY value except 0 in the field has a value 1/v (where v is that arbitrary value). v * (1/v) == 1. This value "1" is defined to be the multiplicative identity. 0 has no inverse.

---------

So, lets prove that the F_5 is a field, which instead of using fancy math, can be done by exhaustion (!!!). I just show every single number on a case-by-case basis has the properties we want and we're set.

F_5 is the numbers {0, 1, 2, 3, 4}. + is normal addition mod 5, * is normal multiplication mod5. By simply describing all inverses (both additive inverses and multiplicative inverses), and proving that they operate as expected, we prove F_5 is a field by exhaustion.

Note: a proper textbook would prove this in general over all prime numbers. This shortcut to just doing F_5 by exhaustion is just me taking a shortcut in explanations.

* 0 is its own additive inverse. 0 + (-0) == 0 mod 5.

* 1 is the inverse of 4. 1 + (-1) == 1 + 4 == 5 mod 5 == 0 mod 5.

* 2 is the inverse of 3. 2 + (-2) == 2 + 3 == 5 mod 5 == 0 mod 5.

* 3 and 4 play out identically. We've proven addition. Moving onto multiplication.

* 0 has no inverse (as per definition of fields).

* 1 is its own inverse. 1 * (1/1) == 1 * 1 == 1 mod 5. Not that numbers "outside" of the field, such as 6 still hold the property. 1 * 1 == 6 * 6 == 36 mod 5 == 1 mod 5

* 2 is the inverse of 3. 2 * (1/2) == 2 * 3 == 1 mod 5.

* 3 is the inverse of 2, and plays out similarly.

* 4 is its own inverse. 4 * (1/4) == 4 * 4 == 1 mod 5.

--------------

Note that the distributed property still works.

(2 + 4) * 3 == 18 mod 5 == 3

But we can also do it distributed, as well as shortcutting to use the new "multiplicative inverses" that exist in F_5...

(2 + 4) * 3 == (2 * 3 + 4 * 3) == 2 * (1/2) + 4 * (1/2) == 1 + 2 == 3

---------

As such, F_5 is a field. It is also finite in length (consisting only of the numbers {0, 1, 2, 3, 4}. Because all numbers have both additive and multiplicative inverses, we can have assurances on the inverse of matricies that use F_5 (as long as det(matrix) != 0, we can find an inverse, because division is always possible), we can always find the roots of polynomials, we can build elliptical curves, etc. etc. Lots of useful properties.

I was hanging out with a friend of mine from high school, who is now a tenured math professor in Colorado, about a decade ago. This was just as ECC was getting popular among security people but hadn't really entered nerd mainstream yet.

He mentioned that he was working on elliptic curves, so I asked him how his work applies to ECC, and he asked me, "what's ECC?".

He had no idea his work was being used for security research. He just liked studying the properties of elliptic curves. After we chatted he did en up learning about how elliptic curves are used in cryptography.

Very likely there's no connection at all (or at least none known) between whatever he was working on and ECC. Just as there's no particular connection between RSA cryptography (which makes use of prime numbers hundreds of digits long) and most of the things pure mathematicians studying prime numbers are interested in.

(Of course it's always risky saying "no connection at all" about two things in mathematics, where sometimes very surprising connections turn up.)

Elliptic curves is a vast field of study and ECC is a subfield of it. The name kind of suggests this relationship.

It’s like hearing that someone works at Microsoft and then asking them about features in MS Word.

After he read up on ECC he realized it was the practical application of his work.

If you want to see a real implemention of arbitrary sized integer math, mbedTLS is a great example:

https://github.com/ARMmbed/mbedtls/blob/development/library/...

All of the ECC code in that library relies on this code, which can be accelerated by dedicated hardware.

Here is multi-precision multiplication:

https://github.com/ARMmbed/mbedtls/blob/f1eb4257823ae4c3b3ac...

For those interested in "Warp Speed", I've written a tutorial about how to exploit group laws to implement fast scalar multiplication: https://loup-vaillant.fr/tutorials/fast-scalarmult

As a bonus, there are remarks about secure implementations as well.

And then there is super warp speed using group endomorphisms to increase scalar multiplication by 2x over windowed methods.

Does that apply to any group? I know of a method that applies to the double scalar multiplication, but it speeds up Ed255119 only by 25%, at the cost of doubling stack usage.

Also, if a group has a structure that allows such speedups, I would fear that the same structure could also enable attacks… Ideally, you want your group to have as little structure as possible, that's what makes attacks infeasible.

Speeding 2x isn't enough to enable attacks when they already take exponential time.

It applies most commonly to curves with an equation of the form y^3 = x² + b which mathematically imply that (x, y) and (x, cuberoot(y)) are both points on a curve and so you can split a n bits scalar into two n/2 bits scalar and do double scalar multiplication.

I used this explanation back in the day when I had to explain it to moderately-technically proficient people:

Diffie-Hellman and a lot of the asymmetric crypto ecosystem can be done on /any/ multiplicative cyclic groups (special sets associated by an operation that have certain properties, namely commutativity)

obviously not all cyclic groups are equal, some happen to have one-way-ness backed by some fundamental cryptographic conjecture that it is hard to solve but easy to prove.

the OG diffie-hellman used prime number modulo cyclic groups, but you can do that in any other cyclic group provided that it is secure.

turns out when you make a cyclic group using ECC very carefully and using a crazy roundabout procedure (shown in the article), it has cryptographic security.

I can also offer this video as an explanation (personally how I understood it). https://www.youtube.com/watch?v=NF1pwjL9-DE

I was happy to see ECC become popular because finally a bunch of Mathematics I learned in college became useful.

Sometimes it feels like cryptology stuff gets invented just to make Number Theorists feel useful

I made a comment above about my friend who is a math professor studying number theory and elliptic curves, and had no idea his work was being use for cryptography. He just liked studying elliptic curves.

So I think the number theorists feel plenty useful already. :)

Or because the NSA knows an undisclosed backdoor.

> Pick two different random points with different x value on the curve, connect these two points with a straight line, let’s say A A and B B . Then you will notice the line touches the curve at a third point.

I seem to always get hung up on this part of the explanation. Looking at the graph, I can see points along the curve, where a line would only intersect with 2 points on the curve.

What do you do in that case? Is this a matter of, yes those points are there, but they are rare enough that we just pick another set of random points and try again, or is there another solution to the issue?

Yep, there are vertical lines that intersect the curve at only two points. In that case there is a special "infinity" point (also known as zero). See page 21 in this presentation which I think explains it a little bit better:

https://www.math.brown.edu/johsilve/Presentations/WyomingEll...

It holds for any two points with distinct x coordinates. Note that the third point might be outside the range of coordinates shown in the article's graphs. Particularly if the line is nearly vertical, you may need to zoom out to see the third point.

Sure seems to me that he is either unaware of or struggles with the point at infinity, so I'll add a link for him in my reply to your comment:

https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic....

When it intersect with only 2 points, one of those points is intersected "twice": the line is tangent to the curve.

You could also see the tangent as the limit when you intersect with two points, and then draw one of those points towards the other, closer and closer.

In practice, this means that P+P doesn't compute exactly the same way as P+Q where P and Q are different points. But in practice it really does mean the same thing.

> Looking at the graph, I can see points along the curve, where a line would only intersect with 2 points on the curve.

I always start out under this impression too, but then I think some more and realize that there are only two conditions where this is possible:

1. The line is vertical

2. The line is the tangent of the curve at one of the points

1 Is illegal by the rules of picking points, and for 2 I believe the tangent counts as two points, and in any case, for any arbitrary point A, there will be only three other points that will allow the line to be a tangent (one when where A is on the tangent and up to two where B is on the tangent, I believe).

So once you've picked an arbitrary point, and you don't move vertically, there will be no more than three lines that don't follow the three-point rule, and every other possible line will follow the rule.

As long as the points are not above/below each other, it will always intersect. We can see in one of the linked notes that vertical points are defined as each other's inverses, and adding them results in a type of "zero-element".

> Yes, a point adding itself holds the same rule, using the tangent line on the finite field to connect the third

How in discrete metric space do you create a tangent line on a set of points in a finite field?

I also wonder about this

Past comments: https://news.ycombinator.com/item?id=21182982

Looks like a good reference, thanks for sharing.

Another explanation I enjoyed from 2013, but have since mostly forgotten: https://arstechnica.com/information-technology/2013/10/a-rel...

Here's another great resource on the topic: https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...

Someone knowledge, does elliptic curve math and factoring math linked in any way to each other? Does solving one automatically solve the other also? I am asking because these are the only two approach securing the website transit right now.

Yes, in many subtle ways. For example, Hendrik Lenstra created a very clever algorithm (called ECM) using elliptic curves that finds “medium size” factors of integers.

> Does solving one automatically solve the other also?

No.

> I am asking because these are the only two approach securing the website transit right now.

In principle, there's also straight Diffie-Hellman in a prime field for key exchange, and straight DSA for authentication, but I don't think they're as widely used.

Reply on news.ycombinator.com