5 ms·

Elliptic Curve Cryptography Explained (2019)

298 points by ptr 5y ago

RcouF1uZ4gsC 5y ago
> 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?
- deleted 5y ago
  [deleted]
- eat_veggies 5y ago
  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/WyomingEllipticCurve.pdf https://www.math.brown.edu/johsilve/Presentations/WyomingEll...
- dlubarov 5y ago
  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.
  - hh3k0 5y ago
    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_multiplication#Point_at_infinity https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic....
- loup-vaillant 5y ago
  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.
- SamBam 5y ago
  > 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.
- johbjo 5y ago
  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".
loup-vaillant 5y ago
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 https://loup-vaillant.fr/tutorials/fast-scalarmult As a bonus, there are remarks about secure implementations as well.
- mratsim 5y ago
  And then there is super warp speed using group endomorphisms to increase scalar multiplication by 2x over windowed methods.
  - loup-vaillant 5y ago
    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.
    - mratsim 5y ago
      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.
dboreham 5y ago
I was happy to see ECC become popular because finally a bunch of Mathematics I learned in college became useful.
- TchoBeer 5y ago
  Sometimes it feels like cryptology stuff gets invented just to make Number Theorists feel useful
  - jedberg 5y ago
    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. :)
  - amelius 5y ago
    Or because the NSA knows an undisclosed backdoor.
dragontamer 5y ago
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.
- lisper 5y ago
  Do you have a recommendation for a good source to go to for making this leap?
  - dragontamer 5y ago
    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.
kuharich 5y ago
Past comments: https://news.ycombinator.com/item?id=21182982 https://news.ycombinator.com/item?id=21182982
SavantIdiot 5y ago
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/bignum.c 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/f1eb4257823ae4c3b3ac4a0b0ae1876df4e8b643/library/bignum.c#L1652-L1688 https://github.com/ARMmbed/mbedtls/blob/f1eb4257823ae4c3b3ac...
alpb 5y ago
I can also offer this video as an explanation (personally how I understood it). https://www.youtube.com/watch?v=NF1pwjL9-DE https://www.youtube.com/watch?v=NF1pwjL9-DE
imiric 5y ago
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-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://arstechnica.com/information-technology/2013/10/a-rel...
ramshanker 5y ago
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.
- williamstein 5y ago
  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.
- AlexCoventry 5y ago
  > 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.
hatsunearu 5y ago
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.
jedberg 5y ago
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.
- gjm11 5y ago
  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.)
- concreteblock 5y ago
  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.
  - jedberg 5y ago
    After he read up on ECC he realized it was the practical application of his work.
zoltane0 5y ago
Here's another great resource on the topic: https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...
ac42 5y ago
> 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?
- Tistron 5y ago
  I also wonder about this

298 points by ptr 5y ago

> 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?

deleted 5y ago
[deleted]
eat_veggies 5y ago
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/WyomingEllipticCurve.pdf https://www.math.brown.edu/johsilve/Presentations/WyomingEll...
dlubarov 5y ago
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.
- hh3k0 5y ago
  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_multiplication#Point_at_infinity https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic....
loup-vaillant 5y ago
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.
SamBam 5y ago
> 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.
johbjo 5y ago
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".

loup-vaillant 5y ago

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 https://loup-vaillant.fr/tutorials/fast-scalarmult As a bonus, there are remarks about secure implementations as well.

mratsim 5y ago
And then there is super warp speed using group endomorphisms to increase scalar multiplication by 2x over windowed methods.
- loup-vaillant 5y ago
  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.
  - mratsim 5y ago
    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.

dboreham 5y ago

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

TchoBeer 5y ago
Sometimes it feels like cryptology stuff gets invented just to make Number Theorists feel useful
- jedberg 5y ago
  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. :)
- amelius 5y ago
  Or because the NSA knows an undisclosed backdoor.

dragontamer 5y ago

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.

lisper 5y ago
Do you have a recommendation for a good source to go to for making this leap?
- dragontamer 5y ago
  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.

kuharich 5y ago

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

SavantIdiot 5y ago

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/bignum.c 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/f1eb4257823ae4c3b3ac4a0b0ae1876df4e8b643/library/bignum.c#L1652-L1688 https://github.com/ARMmbed/mbedtls/blob/f1eb4257823ae4c3b3ac...

alpb 5y ago

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

imiric 5y ago

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-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://arstechnica.com/information-technology/2013/10/a-rel...

ramshanker 5y ago

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.

williamstein 5y ago
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.
AlexCoventry 5y ago
> 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.

hatsunearu 5y ago

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.

jedberg 5y ago

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.

gjm11 5y ago
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.)
concreteblock 5y ago
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.
- jedberg 5y ago
  After he read up on ECC he realized it was the practical application of his work.

zoltane0 5y ago

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

ac42 5y ago

> 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?

Tistron 5y ago
I also wonder about this