3 ms·

A primer on elliptic curve cryptography

53 points by amboar 13y ago

andrewcooke 13y ago
If you understand DH key exchange (the one where you multiply numbers modulo something) then you know what the discrete logarithm problem (DLP) is. All that EC crypto is, is a way of doing the same maths, but replacing integers with points on a curve. If you remember a bit of maths theory you know that you can define groups and things with multiplication and the like. It's that kind of idea. The advantage is that the known best approaches to solving the DLP for integers don't carry across to the points on a curve (because the points don't work like integers for all of maths - they support enough to the crypto, but not enough for the attack). So you can use smaller keys. AFAICT. IMHO. IANAM/C.
- theboss 13y ago
  Except there are a few added difficulties of EC that don't exist in DH due to the maths. There is also the matter of mapping your numbers to points on the curve. Lot's of extra maths for saving time and space. The important take-away from the extra math is that, unless you are a cryptographer then you should leave the implementation up to someone else.
- pbsd 13y ago
  That's a pretty good summary.
Buge 13y ago
The link goes straight to page 3.
- chimeracoder 13y ago
  I thought that was weird too. But there is no single-page version, and the first page doesn't really have much content on there (just a basic walkthrough of modular division).
  - taspeotis 13y ago
    > But there is no single-page version For what it's worth, Ars subscribers get single-page versions of articles.
- amboar 13y ago
  Err, whoops... that was unintended. I read the article, reached the end, thought it was interesting and hit share. Damn Ars and their pagination! I will pay more attention in the future.
lisper 13y ago
Another one: http://blog.rongarret.info/2013/02/a-simple-solution-to-credit-card-fraud_28.html http://blog.rongarret.info/2013/02/a-simple-solution-to-cred...
- pbsd 13y ago
  I'm going to be a little pedantic here: the trick of using a PRF (hashing with a secret) to obtain the DSA nonce was not invented by Dan Bernstein. In the Ed25519 paper it's attributed to George Barwood and John Wigley in 1997. Also published in [2] around the same time. [1] http://ed25519.cr.yp.to/ed25519-20110926.pdf http://ed25519.cr.yp.to/ed25519-20110926.pdf [2] http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf
  - lisper 13y ago
    That's not being pedantic, that's helpfully pointing out a fairly serious attribution error. Thanks! I will fix it.
startswithaj 13y ago
Doing 256 bit sign ecdsa's for 10s: 42874 256 bit ECDSA signs in 9.99s Doing 2048 bit private rsa's for 10s: 1864 2048 bit private RSA's in 9.99s That's 23 times as many signatures using ECDSA as RSA. 42 874 256 18 642 048 23 times as many signatures?
- sandstrom 13y ago
  I think it's 42874/1864=23. (256 and 2048 is presumably the key strength).
yk 13y ago
I believe the previous discussion was https://news.ycombinator.com/item?id=6607661 https://news.ycombinator.com/item?id=6607661 ( Which I only still have open because I wanted to program the article at some point...)
- j2kun 13y ago
  See I've got a working program, and have been hoping to publish a primer of my own with the implementation and experiments :) Alas, the time...
sillysaurus2 13y ago
'tptacek commented 17 days ago about EC crypto (https://news.ycombinator.com/item?id=6608163 https://news.ycombinator.com/item?id=6608163): You should never, ever, never, nevern, nervenvarn build your own production ECC code. ECC is particularly tricky to get right. But if you want to play with the concepts, a great place to start is the Explicit Formulas Database at http://www.hyperelliptic.org/EFD/ http://www.hyperelliptic.org/EFD/ ; the fast routines for point multiplication are mercifully complicated, so copying them from the EFD is a fine way to start, instead of working them out from first principles. He went on to say that only Adam Langley or Daniel Bernstein should be implementing ECC. Probably because there are so many ways to slip up; few others would have the experience necessary to avoid all the pitfalls. 'theboss agreed: I've implemented ECC and you are 100% correct. Nobody should implement ECC unless you really really know what you're doing. Mapping points to the curve, multiplying points, point addition, there is too much math stuff to mess up on. Just don't do it. If you read one thing tptacek says, read the last paragraph.

53 points by amboar 13y ago

If you understand DH key exchange (the one where you multiply numbers modulo something) then you know what the discrete logarithm problem (DLP) is. All that EC crypto is, is a way of doing the same maths, but replacing integers with points on a curve. If you remember a bit of maths theory you know that you can define groups and things with multiplication and the like. It's that kind of idea. The advantage is that the known best approaches to solving the DLP for integers don't carry across to the points on a curve (because the points don't work like integers for all of maths - they support enough to the crypto, but not enough for the attack). So you can use smaller keys. AFAICT. IMHO. IANAM/C.

theboss 13y ago
Except there are a few added difficulties of EC that don't exist in DH due to the maths. There is also the matter of mapping your numbers to points on the curve. Lot's of extra maths for saving time and space. The important take-away from the extra math is that, unless you are a cryptographer then you should leave the implementation up to someone else.
pbsd 13y ago
That's a pretty good summary.

Buge 13y ago

The link goes straight to page 3.

chimeracoder 13y ago
I thought that was weird too. But there is no single-page version, and the first page doesn't really have much content on there (just a basic walkthrough of modular division).
- taspeotis 13y ago
  > But there is no single-page version For what it's worth, Ars subscribers get single-page versions of articles.
amboar 13y ago
Err, whoops... that was unintended. I read the article, reached the end, thought it was interesting and hit share. Damn Ars and their pagination! I will pay more attention in the future.

lisper 13y ago

Another one: http://blog.rongarret.info/2013/02/a-simple-solution-to-credit-card-fraud_28.html http://blog.rongarret.info/2013/02/a-simple-solution-to-cred...

pbsd 13y ago
I'm going to be a little pedantic here: the trick of using a PRF (hashing with a secret) to obtain the DSA nonce was not invented by Dan Bernstein. In the Ed25519 paper it's attributed to George Barwood and John Wigley in 1997. Also published in [2] around the same time. [1] http://ed25519.cr.yp.to/ed25519-20110926.pdf http://ed25519.cr.yp.to/ed25519-20110926.pdf [2] http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf
- lisper 13y ago
  That's not being pedantic, that's helpfully pointing out a fairly serious attribution error. Thanks! I will fix it.

startswithaj 13y ago

Doing 256 bit sign ecdsa's for 10s: 42874 256 bit ECDSA signs in 9.99s Doing 2048 bit private rsa's for 10s: 1864 2048 bit private RSA's in 9.99s That's 23 times as many signatures using ECDSA as RSA. 42 874 256 18 642 048 23 times as many signatures?

sandstrom 13y ago
I think it's 42874/1864=23. (256 and 2048 is presumably the key strength).

yk 13y ago

I believe the previous discussion was https://news.ycombinator.com/item?id=6607661 https://news.ycombinator.com/item?id=6607661 ( Which I only still have open because I wanted to program the article at some point...)

j2kun 13y ago
See I've got a working program, and have been hoping to publish a primer of my own with the implementation and experiments :) Alas, the time...

sillysaurus2 13y ago

'tptacek commented 17 days ago about EC crypto (https://news.ycombinator.com/item?id=6608163 https://news.ycombinator.com/item?id=6608163): You should never, ever, never, nevern, nervenvarn build your own production ECC code. ECC is particularly tricky to get right. But if you want to play with the concepts, a great place to start is the Explicit Formulas Database at http://www.hyperelliptic.org/EFD/ http://www.hyperelliptic.org/EFD/ ; the fast routines for point multiplication are mercifully complicated, so copying them from the EFD is a fine way to start, instead of working them out from first principles. He went on to say that only Adam Langley or Daniel Bernstein should be implementing ECC. Probably because there are so many ways to slip up; few others would have the experience necessary to avoid all the pitfalls. 'theboss agreed: I've implemented ECC and you are 100% correct. Nobody should implement ECC unless you really really know what you're doing. Mapping points to the curve, multiplying points, point addition, there is too much math stuff to mess up on. Just don't do it. If you read one thing tptacek says, read the last paragraph.