[HN Gopher] Elliptic Curve Cryptography Explained (2019)
___________________________________________________________________
Elliptic Curve Cryptography Explained (2019)
Author : ptr
Score : 184 points
Date : 2021-05-27 11:23 UTC (1 days ago)
(HTM) web link (fangpenlin.com)
(TXT) w3m dump (fangpenlin.com)
| RcouF1uZ4gsC wrote:
| > 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]
| SamBam wrote:
| > 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.
| eat_veggies wrote:
| 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...
| dlubarov wrote:
| 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 wrote:
| 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.
| ...
| loup-vaillant wrote:
| 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.
| johbjo wrote:
| 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".
| imiric wrote:
| 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...
| dragontamer wrote:
| 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 wrote:
| Do you have a recommendation for a good source to go to for
| making this leap?
| dragontamer wrote:
| 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.
| senderista wrote:
| If you already have the abstract algebra background then a
| good Galois theory textbook like Ian Stewart's will do.
| dragontamer wrote:
| 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.
| AlexCoventry wrote:
| 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_Eu
| clidean_algorithm#S...). OK, maybe that last bit is a little
| advanced, but Euclid's algorithm is also very simple
| arithmetic.
| mratsim wrote:
| 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-Castaneda, Francisco Rodriguez-
| Henriquez, 2017
|
| https://www.researchgate.net/publication/319538235_Arithmeti...
| dragontamer wrote:
| > 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.
| ducttapecrown wrote:
| 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.
| rackjack wrote:
| 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].
| dragontamer wrote:
| 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.
| hatsunearu wrote:
| 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.
| zoltane0 wrote:
| Here's another great resource on the topic:
| https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...
| alpb wrote:
| I can also offer this video as an explanation (personally how I
| understood it). https://www.youtube.com/watch?v=NF1pwjL9-DE
| dboreham wrote:
| I was happy to see ECC become popular because finally a bunch of
| Mathematics I learned in college became useful.
| TchoBeer wrote:
| Sometimes it feels like cryptology stuff gets invented just to
| make Number Theorists feel useful
| amelius wrote:
| Or because the NSA knows an undisclosed backdoor.
| jedberg wrote:
| 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.
| :)
| kuharich wrote:
| Past comments: https://news.ycombinator.com/item?id=21182982
| jedberg wrote:
| 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 wrote:
| 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.)
| SavantIdiot wrote:
| 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...
| loup-vaillant wrote:
| 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.
| mratsim wrote:
| And then there is super warp speed using group endomorphisms to
| increase scalar multiplication by 2x over windowed methods.
| loup-vaillant wrote:
| 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.
| ramshanker wrote:
| 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 wrote:
| 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.
___________________________________________________________________
(page generated 2021-05-28 23:00 UTC)