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.
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).
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.
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.
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/ ; 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.
15 comments
[ 3.7 ms ] story [ 49.9 ms ] threadIf 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.
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.
For what it's worth, Ars subscribers get single-page versions of articles.
http://blog.rongarret.info/2013/02/a-simple-solution-to-cred...
[1] http://ed25519.cr.yp.to/ed25519-20110926.pdf
[2] http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf
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?
https://news.ycombinator.com/item?id=6607661
( Which I only still have open because I wanted to program the article at some point...)
Alas, the time...
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/ ; 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.