13 ms·

Elliptic Curve Cryptography Explained

471 points by fangpenlin 7y ago

kk58 7y ago
Well written
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
ColinWright 7y ago
So, to summarise: * Choose an Elliptic Curve (EC) and a large prime; * The rational points on the EC modulo the prime give you a group; * Your private key is a large integer N; * Perform Diffie-Hellman-Merkle-Williamson (DHMW) in the group; * You now have a shared point in the EC; * Use a symmetric cipher using the shared point as the key. Performing DHMW goes as follows: * A and B agree on a point P in the EC; * A and B each choose a large number as their secret key; * For simplicity, or confusion, we'll say that X's secret key is X; * They compute AP and BP as their public keys and exchange them; * When A receives BP they compute A(BP), B does likewise; * Now they share a point: (AB)P. If you have the language of groups, and understand DHMW in that context, ECDHMW is trivial, as is (this version of) EC PK-Cryptography. TL;DR : ECC is simply Symmetric Cryptography using a key that's been agreed by using DHMW in an Elliptic Curve group.
- archgoon 7y ago
  For those like me, who are confused by the acronym DHMW, it's another name for 'Diffie-Helman'. Diffie and Helman felt that the entire scheme was based on work that Ralph Merkle did (same guy as Merkle Trees), and so should be included in the scheme name, and I think that Williamson refers to Malcolm J. Williamson, a GHCQ employee, who had secretly developed the same system 7 years before Diffie and Helman. What I don't know is why Williamson and not Cocks and Ellis are part of the acronym.
  - ColinWright 7y ago
    Cocks and Ellis developed what we know as RSA, Malcolm Williamson developed what most people call Diffie-Hellman. I did give the full version before the acronym on the fifth line of my comment, so if people are confused it might be why I'm referring to DHMW and not just DH. Reading up about it all it's pretty clear that Merkle and Williamson should get more credit than they do.
    - dwoozle 7y ago
      Nobody should get credit for inventing something in secret. You make your decision — invent for corporations or the military industrial complex and get the big bucks or the jingoistic frisson, or for academia and get the accolades. No way a person should double dip.
      - ZenPsycho 7y ago
        so you would revoke credit from Turing?
        cortesoft 7y ago
        Did anyone else discover what he did before his work became public?
        ZenPsycho 7y ago
        yep, eniac and univac were the the first publicly known computers. it became known later that turing’s work predated eniac.
        dTal 7y ago
        Credit for what? The theoretical work for which Turing is most known - the concept of Turing machines and undecidability - was published publicly and before the war. He did not contribute to the design of a physical computer until after the war. Colossus, the code-breaking "computer", was not of his design (and the man who did design it is not at all famous for it).
GordonS 7y ago
This is really helpful! I find RSA really simple to understand, but ECC has always seemed a lot harded to grok - I think I finally get it!
simonebrunozzi 7y ago
This [0] was also a very good introduction to elliptic curve cryptography written by a friend of mine in 2015. Highly recommended. [0]: https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...
- AlexCoventry 7y ago
  That's a better introduction, imo
- thr0w__4w4y 7y ago
  Yes absolutely, I have Andrea's whole series on the topic bookmarked, it is very well done. Another, slightly more topical / simple explanation [0] was posted by Cloudflare almost exactly 6 years ago, I still point people to it as well. [0] https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://blog.cloudflare.com/a-relatively-easy-to-understand-...
thisisnico 7y ago
I was at a Graduation in London, Ontario Canada, This lady had given a speech to the new graduates. Known for her contributions to ECC https://en.wikipedia.org/wiki/Kristin_Lauter https://en.wikipedia.org/wiki/Kristin_Lauter
- nick_ 7y ago
  UWO?
  - thisisnico 7y ago
    Yup!
quadyeast 7y ago
"Time limited offer expires on Sep 31 2019, " does that mean it never expires?
andrewla 7y ago
The thing I like best about this article is that it touches on elliptic curves over finite fields in more than a cursory way. But I would love to see an introduction to elliptic curves that completely ignores the behavior in the real numbers, and instead focuses on driving the motivations from the finite field perspective. There are elements that seem particularly interesting to me around this, especially since even elliptic curves with no rational points on them still have points in finite fields, and how to think about what it means for points to be on a line, and derive things like point addition and point doubling from that perspective. I'm familiar enough with EC math to hand wave around these issues, but it's still something that I struggle with.
- empath75 7y ago
  > even elliptic curves with no rational points on them still have points in finite fields That’s interesting. How is that possible?
  - andrewla 7y ago
    Take the elliptic curve y^2 = x^3 - 5 that has no rational solutions [1]. But it's easy to see (from brute force) that, for example, 3^2 - 5 = 22 = 27^2 (mod 101). [1] https://kconrad.math.uconn.edu/blurbs/gradnumthy/mordelleqn1.pdf https://kconrad.math.uconn.edu/blurbs/gradnumthy/mordelleqn1...
- frutiger 7y ago
  I can recommend https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number/dp/0691151199 https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number.... It goes in-depth into the motivating use cases for elliptic curves (as well as their group law) and explains some very elegant theorems (Bézout's theorem) as well as open problems in Maths (the Birch-Swinnerton-Dyer conjecture).
jimmysong 7y ago
Tooting my own horn just a little bit, I spend the first 3 chapters of my book on exactly this topic: https://www.amazon.com/Programming-Bitcoin-Learn-Program-Scratch/dp/1492031496/ref=sr_1_3 https://www.amazon.com/Programming-Bitcoin-Learn-Program-Scr... There are exercises that can help you learn it from scratch.
- AlexCoventry 7y ago
  I've led a number of people through these exercises at this point. They're good for making the math concrete.
nullc 7y ago
It's great that people enjoy this-- but I've never seen explanations that centered on the group law as actually being especially useful for building insight producing understandings complex cryptosystems. I think it's a lot more useful to start from a generic group: e.g. you have some group G generated by g, and a group operator ... plus a way to (de)serialize members, a method to identify the additive identity, maybe a hash function and not much else. From that point you can build a pretty solid understanding of real cryptosystems. Knowledge of how to implement a particular group law is necessary to build one from scratch-- which people should almost never be doing, esp as it requires a serious amount of number theory to do well-- but it doesn't give any real insight into the cryptography, not even any intuition as to why the DL problem in some groups is believed to be hard. I think that understanding ECC starting at group law is kind of like understanding quick sort by studying CMOS logic: you can't implement quicksort in practice without (someone) building some digital logic, but if you're down in the trees it's not particularly easy to see the forest. When I've trained people on the subject I've enjoyed using a sequence that goes like: 1. Generic group, how we can construct efficient 'multiplication' from only addition (I prefer to call the group operator addition, but I talk about both notations and how both are equally valid). General intuition about how algebra essentially JustWorks(tm) in finite fields. 2. CDH and Diffe-hellman, the fact that the hardness of the DL problem (in particular groups) is a strong assumption. 3. Constructing a pedersen commitment using the additive homomorphism 'in the exponent', establishing the security assumption in pedersen commitments that the two generators have an unknown DL between them. 4. Constructing a chameleon hash function-- a trap-door hash function where someone knowing a secret can freely construct collisions at will-- by violating the pedersen security assumption. 5. Constructing a schnorr digital signature by feeding the output of a chameleon hash back into itself, creating an impossible causal loop that can only be resolved using the trapdoor. 6. Extending the causal loop: creating an OR proof (A signature that shows I know at least one of two secrets). [FWIW, we cover 4,5,6 in this paper https://pdfs.semanticscholar.org/4160/470c7f6cf05ffc81a98e8fd67fb0c84836ea.pdf https://pdfs.semanticscholar.org/4160/470c7f6cf05ffc81a98e8f... for the purpose of describing a more efficient than typical OR proof.] 7. From there extending into other more elaborate protocols like range proofs (built from OR proofs of related secrets), private set-intersection (built from polynomial evaluation in-the-exponent), etc. 8. And critically, interesting attacks on these systems, with a particular focus on how fragile they can be: 8a. Linearly related nonce attacks against signatures. (unfortunately, these attacks are easier taught if the signature algorithm is understood as a hidden linear system, then the attack is just a 'as many knows as unknowns attack', but I strongly prefer the causal loop understanding of signatures for the intuition it creates for more complex protocols). 8b. Random-modular-subset sum attacks on naive blind signatures and naive multi-signature. 8c. At least one attack that break the generic group abstraction. I'm fond of invalid key attacks on DH with twist-insecure curves. (This is probably the only example that I think is important to teach that requires some group law understanding). If I do get into group law, I think it's interesting to talk about optimizations. Particularly, projective coordinates, precomputation, addition/subtraction ladders and signed digit representations, doubling sharing for multi-exp. Bos-coster for sum-of-many products is an especially fun and easy algorithm to implement (similar kind of fun as implementing the peeling algorithm for decoding sparse linear codes in F(2)). I'd like to have a 9 on that list that goes into the building blocks of proof techniques for these systems e.g. programmable oracles/forking lemma... but that is enough out of my area of expertise that I don't know how to teach it effectively.
pryce 7y ago
I don't have much experience in cryptography, so this may be a stupid question, but I've always wondered about whether Elliptic Curve cryptography opens up some possibilities for partially decentralizing encryption standards. My understanding is that end-users of ECC have to decide which curves to use, and constructing a curve de-novo isn't a choice laymen or crypto end-users should ever make, so a set of standardized curves are issued by standards bodies, such as NIST. Cryptographers endorse the math of ECC as not known to be decipherable, provided that the chosen curve (defined eg by 4 points) isn't specifically constructed to be easily compromised; and the problem becomes whether the curve-issuing standards bodies, such as NIST, are acting in the interests of state security agencies (for argument's sake, lets say NSA) who have vested interests in crypto users adopting curves that NSA can break. Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure?
- Klathmon 7y ago
  While I don't know enough about this stuff to answer your main question, I will point out that there are some popular curves which aren't tied to any one nation or agency. Ed25519 specifically has major contributions from 5 different people from multiple nationalities. It's not quite the decentralized ideal you talk about, but it's somewhat close! https://ed25519.cr.yp.to/ https://ed25519.cr.yp.to/
  - chmike 7y ago
    ed25519 is the signature system based on curve25519
- cipherboy 7y ago
  > Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure? The process would be a little more complicated than simply choosing 4 points, but yes you could do something close enough to this in theory. In actual practice there's really only two sets of curves most people [0] implement, and just about everyone agrees to use: - The NIST p curves - Curve25519/Curve448 by Bernstein &c. Which you use tends to fall on what side of the crypto divide you fall on: - NIST p curves if you care about governmental compliance such as FIPS - Bernstein &c's curves if you care about security and distrust NIST created curves. I personally fall on the latter side but spend most of my time doing software for the former. :) A promised later revision to FIPS will standardize Bernstein &c's curves. Almost nobody implements negotiating arbitrary curves. That's really unsafe. So, as 'tptacek would say... just use Curve25519. [0]: I'm talking about major software such as TLS, VPNs, SSH, Kerberos... etc.
chmike 7y ago
This is the best explanation I have seen so far. Some aspects are still left in the shadow, but most points are now connected.
- makach 7y ago
  second that! great article.
NohatCoder 7y ago
That certainly got me some of the way, now I'm wondering how signatures work.
kzrdude 7y ago
Is ECC threatened by quantum c. or not?
- kzrdude 7y ago
  (self-answer) Ok, Scott says yes https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317
Stevvo 7y ago
Further reading: https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627 https://medium.com/@VitalikButerin/exploring-elliptic-curve-...

471 points by fangpenlin 7y ago

kk58 7y ago

Well written

deleted 7y ago

[deleted]

deleted 7y ago

[deleted]

ColinWright 7y ago

So, to summarise: * Choose an Elliptic Curve (EC) and a large prime; * The rational points on the EC modulo the prime give you a group; * Your private key is a large integer N; * Perform Diffie-Hellman-Merkle-Williamson (DHMW) in the group; * You now have a shared point in the EC; * Use a symmetric cipher using the shared point as the key. Performing DHMW goes as follows: * A and B agree on a point P in the EC; * A and B each choose a large number as their secret key; * For simplicity, or confusion, we'll say that X's secret key is X; * They compute AP and BP as their public keys and exchange them; * When A receives BP they compute A(BP), B does likewise; * Now they share a point: (AB)P. If you have the language of groups, and understand DHMW in that context, ECDHMW is trivial, as is (this version of) EC PK-Cryptography. TL;DR : ECC is simply Symmetric Cryptography using a key that's been agreed by using DHMW in an Elliptic Curve group.

archgoon 7y ago
For those like me, who are confused by the acronym DHMW, it's another name for 'Diffie-Helman'. Diffie and Helman felt that the entire scheme was based on work that Ralph Merkle did (same guy as Merkle Trees), and so should be included in the scheme name, and I think that Williamson refers to Malcolm J. Williamson, a GHCQ employee, who had secretly developed the same system 7 years before Diffie and Helman. What I don't know is why Williamson and not Cocks and Ellis are part of the acronym.
- ColinWright 7y ago
  Cocks and Ellis developed what we know as RSA, Malcolm Williamson developed what most people call Diffie-Hellman. I did give the full version before the acronym on the fifth line of my comment, so if people are confused it might be why I'm referring to DHMW and not just DH. Reading up about it all it's pretty clear that Merkle and Williamson should get more credit than they do.
  - dwoozle 7y ago
    Nobody should get credit for inventing something in secret. You make your decision — invent for corporations or the military industrial complex and get the big bucks or the jingoistic frisson, or for academia and get the accolades. No way a person should double dip.
    - ZenPsycho 7y ago
      so you would revoke credit from Turing?
      - cortesoft 7y ago
        Did anyone else discover what he did before his work became public?
        ZenPsycho 7y ago
        yep, eniac and univac were the the first publicly known computers. it became known later that turing’s work predated eniac.
      - dTal 7y ago
        Credit for what? The theoretical work for which Turing is most known - the concept of Turing machines and undecidability - was published publicly and before the war. He did not contribute to the design of a physical computer until after the war. Colossus, the code-breaking "computer", was not of his design (and the man who did design it is not at all famous for it).

GordonS 7y ago

This is really helpful! I find RSA really simple to understand, but ECC has always seemed a lot harded to grok - I think I finally get it!

simonebrunozzi 7y ago

This [0] was also a very good introduction to elliptic curve cryptography written by a friend of mine in 2015. Highly recommended. [0]: https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...

AlexCoventry 7y ago
That's a better introduction, imo
thr0w__4w4y 7y ago
Yes absolutely, I have Andrea's whole series on the topic bookmarked, it is very well done. Another, slightly more topical / simple explanation [0] was posted by Cloudflare almost exactly 6 years ago, I still point people to it as well. [0] https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://blog.cloudflare.com/a-relatively-easy-to-understand-...

thisisnico 7y ago

I was at a Graduation in London, Ontario Canada, This lady had given a speech to the new graduates. Known for her contributions to ECC https://en.wikipedia.org/wiki/Kristin_Lauter https://en.wikipedia.org/wiki/Kristin_Lauter

nick_ 7y ago
UWO?
- thisisnico 7y ago
  Yup!

quadyeast 7y ago

"Time limited offer expires on Sep 31 2019, " does that mean it never expires?

andrewla 7y ago

The thing I like best about this article is that it touches on elliptic curves over finite fields in more than a cursory way. But I would love to see an introduction to elliptic curves that completely ignores the behavior in the real numbers, and instead focuses on driving the motivations from the finite field perspective. There are elements that seem particularly interesting to me around this, especially since even elliptic curves with no rational points on them still have points in finite fields, and how to think about what it means for points to be on a line, and derive things like point addition and point doubling from that perspective. I'm familiar enough with EC math to hand wave around these issues, but it's still something that I struggle with.

empath75 7y ago
> even elliptic curves with no rational points on them still have points in finite fields That’s interesting. How is that possible?
- andrewla 7y ago
  Take the elliptic curve y^2 = x^3 - 5 that has no rational solutions [1]. But it's easy to see (from brute force) that, for example, 3^2 - 5 = 22 = 27^2 (mod 101). [1] https://kconrad.math.uconn.edu/blurbs/gradnumthy/mordelleqn1.pdf https://kconrad.math.uconn.edu/blurbs/gradnumthy/mordelleqn1...
frutiger 7y ago
I can recommend https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number/dp/0691151199 https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number.... It goes in-depth into the motivating use cases for elliptic curves (as well as their group law) and explains some very elegant theorems (Bézout's theorem) as well as open problems in Maths (the Birch-Swinnerton-Dyer conjecture).

jimmysong 7y ago

Tooting my own horn just a little bit, I spend the first 3 chapters of my book on exactly this topic: https://www.amazon.com/Programming-Bitcoin-Learn-Program-Scratch/dp/1492031496/ref=sr_1_3 https://www.amazon.com/Programming-Bitcoin-Learn-Program-Scr... There are exercises that can help you learn it from scratch.

AlexCoventry 7y ago
I've led a number of people through these exercises at this point. They're good for making the math concrete.

nullc 7y ago

It's great that people enjoy this-- but I've never seen explanations that centered on the group law as actually being especially useful for building insight producing understandings complex cryptosystems. I think it's a lot more useful to start from a generic group: e.g. you have some group G generated by g, and a group operator ... plus a way to (de)serialize members, a method to identify the additive identity, maybe a hash function and not much else. From that point you can build a pretty solid understanding of real cryptosystems. Knowledge of how to implement a particular group law is necessary to build one from scratch-- which people should almost never be doing, esp as it requires a serious amount of number theory to do well-- but it doesn't give any real insight into the cryptography, not even any intuition as to why the DL problem in some groups is believed to be hard. I think that understanding ECC starting at group law is kind of like understanding quick sort by studying CMOS logic: you can't implement quicksort in practice without (someone) building some digital logic, but if you're down in the trees it's not particularly easy to see the forest. When I've trained people on the subject I've enjoyed using a sequence that goes like: 1. Generic group, how we can construct efficient 'multiplication' from only addition (I prefer to call the group operator addition, but I talk about both notations and how both are equally valid). General intuition about how algebra essentially JustWorks(tm) in finite fields. 2. CDH and Diffe-hellman, the fact that the hardness of the DL problem (in particular groups) is a strong assumption. 3. Constructing a pedersen commitment using the additive homomorphism 'in the exponent', establishing the security assumption in pedersen commitments that the two generators have an unknown DL between them. 4. Constructing a chameleon hash function-- a trap-door hash function where someone knowing a secret can freely construct collisions at will-- by violating the pedersen security assumption. 5. Constructing a schnorr digital signature by feeding the output of a chameleon hash back into itself, creating an impossible causal loop that can only be resolved using the trapdoor. 6. Extending the causal loop: creating an OR proof (A signature that shows I know at least one of two secrets). [FWIW, we cover 4,5,6 in this paper https://pdfs.semanticscholar.org/4160/470c7f6cf05ffc81a98e8fd67fb0c84836ea.pdf https://pdfs.semanticscholar.org/4160/470c7f6cf05ffc81a98e8f... for the purpose of describing a more efficient than typical OR proof.] 7. From there extending into other more elaborate protocols like range proofs (built from OR proofs of related secrets), private set-intersection (built from polynomial evaluation in-the-exponent), etc. 8. And critically, interesting attacks on these systems, with a particular focus on how fragile they can be: 8a. Linearly related nonce attacks against signatures. (unfortunately, these attacks are easier taught if the signature algorithm is understood as a hidden linear system, then the attack is just a 'as many knows as unknowns attack', but I strongly prefer the causal loop understanding of signatures for the intuition it creates for more complex protocols). 8b. Random-modular-subset sum attacks on naive blind signatures and naive multi-signature. 8c. At least one attack that break the generic group abstraction. I'm fond of invalid key attacks on DH with twist-insecure curves. (This is probably the only example that I think is important to teach that requires some group law understanding). If I do get into group law, I think it's interesting to talk about optimizations. Particularly, projective coordinates, precomputation, addition/subtraction ladders and signed digit representations, doubling sharing for multi-exp. Bos-coster for sum-of-many products is an especially fun and easy algorithm to implement (similar kind of fun as implementing the peeling algorithm for decoding sparse linear codes in F(2)). I'd like to have a 9 on that list that goes into the building blocks of proof techniques for these systems e.g. programmable oracles/forking lemma... but that is enough out of my area of expertise that I don't know how to teach it effectively.

pryce 7y ago

I don't have much experience in cryptography, so this may be a stupid question, but I've always wondered about whether Elliptic Curve cryptography opens up some possibilities for partially decentralizing encryption standards. My understanding is that end-users of ECC have to decide which curves to use, and constructing a curve de-novo isn't a choice laymen or crypto end-users should ever make, so a set of standardized curves are issued by standards bodies, such as NIST. Cryptographers endorse the math of ECC as not known to be decipherable, provided that the chosen curve (defined eg by 4 points) isn't specifically constructed to be easily compromised; and the problem becomes whether the curve-issuing standards bodies, such as NIST, are acting in the interests of state security agencies (for argument's sake, lets say NSA) who have vested interests in crypto users adopting curves that NSA can break. Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure?

Klathmon 7y ago
While I don't know enough about this stuff to answer your main question, I will point out that there are some popular curves which aren't tied to any one nation or agency. Ed25519 specifically has major contributions from 5 different people from multiple nationalities. It's not quite the decentralized ideal you talk about, but it's somewhat close! https://ed25519.cr.yp.to/ https://ed25519.cr.yp.to/
- chmike 7y ago
  ed25519 is the signature system based on curve25519
cipherboy 7y ago
> Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure? The process would be a little more complicated than simply choosing 4 points, but yes you could do something close enough to this in theory. In actual practice there's really only two sets of curves most people [0] implement, and just about everyone agrees to use: - The NIST p curves - Curve25519/Curve448 by Bernstein &c. Which you use tends to fall on what side of the crypto divide you fall on: - NIST p curves if you care about governmental compliance such as FIPS - Bernstein &c's curves if you care about security and distrust NIST created curves. I personally fall on the latter side but spend most of my time doing software for the former. :) A promised later revision to FIPS will standardize Bernstein &c's curves. Almost nobody implements negotiating arbitrary curves. That's really unsafe. So, as 'tptacek would say... just use Curve25519. [0]: I'm talking about major software such as TLS, VPNs, SSH, Kerberos... etc.

chmike 7y ago

This is the best explanation I have seen so far. Some aspects are still left in the shadow, but most points are now connected.

makach 7y ago
second that! great article.

NohatCoder 7y ago

That certainly got me some of the way, now I'm wondering how signatures work.

kzrdude 7y ago

Is ECC threatened by quantum c. or not?

kzrdude 7y ago
(self-answer) Ok, Scott says yes https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317

Stevvo 7y ago

Further reading: https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627 https://medium.com/@VitalikButerin/exploring-elliptic-curve-...