A primer on elliptic curve cryptography(arstechnica.com)
arstechnica.com
A primer on elliptic curve cryptography
http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/3/
6 comments
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
[2] http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf
[1] http://ed25519.cr.yp.to/ed25519-20110926.pdf
[2] http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf
That's not being pedantic, that's helpfully pointing out a fairly serious attribution error. Thanks! I will fix it.
'tptacek commented 17 days ago about EC crypto (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/ ; 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.
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.
I believe the previous discussion was
https://news.ycombinator.com/item?id=6607661
( Which I only still have open because I wanted to program the article at some point...)
https://news.ycombinator.com/item?id=6607661
( Which I only still have open because I wanted to program the article at some point...)
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...
Alas, the time...
The link goes straight to page 3.
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 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).
> But there is no single-page version
For what it's worth, Ars subscribers get single-page versions of articles.
For what it's worth, Ars subscribers get single-page versions of articles.
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?
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?
I think it's 42874/1864=23. (256 and 2048 is presumably the key strength).
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.
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.
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.
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.
That's a pretty good summary.
http://blog.rongarret.info/2013/02/a-simple-solution-to-cred...