6 ms·

Primer on elliptic curve cryptography

205 points by andrewfong 13y ago

pbsd 13y ago
The performance comparison of ECDSA vs RSA is somewhat unfair. In ECDSA, signing is the cheapest operation, whereas in RSA it is the most expensive. If the timings chosen were signature verification time, RSA would be much faster. See: Doing 2048 bit private rsa's for 10s: 1266 2048 bit private RSA's in 9.98s Doing 256 bit sign ecdsa's for 10s: 22544 256 bit ECDSA signs in 9.97s Doing 2048 bit public rsa's for 10s: 42332 2048 bit public RSA's in 9.98s Doing 256 bit verify ecdsa's for 10s: 4751 256 bit ECDSA verify in 9.92s A fairer comparison would probably pitch DH-2048 against ECDH-256, which is more apples-to-apples.
- stock_toaster 13y ago
  I don't believe 2048bit rsa and 256bit ecdsa are of equivalent security though[1]. What do things look like with 3072bit rsa? [1]: http://wiki.openssl.org/index.php?title=Elliptic_Curve_Cryptography http://wiki.openssl.org/index.php?title=Elliptic_Curve_Crypt...
  - pbsd 13y ago
    OpenSSL's 'speed' utility doesn't seem to have RSA-3072 on the list, but I suppose I can downgrade to ECDSA-224 instead: Doing 224 bit sign ecdsa's for 10s: 27648 224 bit ECDSA signs in 9.94s Doing 224 bit verify ecdsa's for 10s: 5776 224 bit ECDSA verify in 10.00s
    - stock_toaster 13y ago
      there is also a huge difference between newer and older versions of openssl. # default openssl install (osx mavericks) Doing 224 bit sign ecdsa's for 10s: 39077 224 bit ECDSA signs in 9.98s Doing 224 bit verify ecdsa's for 10s: 8285 224 bit ECDSA verify in 9.98s OpenSSL 0.9.8y 5 Feb 2013 vs # homebrew openssl install Doing 224 bit sign ecdsa's for 10s: 61047 224 bit ECDSA signs in 9.99s Doing 224 bit verify ecdsa's for 10s: 15609 224 bit ECDSA verify in 9.84s OpenSSL 1.0.1e 11 Feb 2013 Both on same mac laptop.
jevinskie 13y ago
I always liked the ECC segment of a Purdue crypto course: https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture14.pdf https://engineering.purdue.edu/kak/compsec/NewLectures/Lectu...
tptacek 13y ago
Nit: the hard dependency on good randomness for ECDSA is a property of DSA in general, and not of elliptic curve cryptography. The DSA construction has what is probably the strictest randomness requirement in all of mainstream cryptography; a bias of just a few bits is, with repeated signatures, sufficient to recover private keys! (The attack that makes this work on ECDSA is extraordinarily cool). The problem with NIST Dual_EC_DRBG is simpler than the article makes it sounds. A good mental model for Dual_EC is that it's a CSRPNG specification with a public key baked into it (in this case, an ECC public key) --- but no private key. The "backdoor" in Dual_EC is the notion that NSA --- err, Clyde Frog --- who is confirmed to have generated Dual_EC, holds the private key and can reconstruct the internal state of the CSPRNG using it. I think this problem is simple enough that we may do a crypto challenge on a toy model of Dual_EC. Nobody in the real world really uses Dual_EC, but that may not always have been historically true; the circumstantial evidence about it is damning. The NIST ECC specifications are in general now totally discredited. If you want to see where the state of the art is on ECC, check out http://safecurves.cr.yp.to/ http://safecurves.cr.yp.to/. 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.
- hdevalence 13y ago
  Would it be possible to get a link to a technical exposition of the extraordinarily cool attack?
  - tptacek 13y ago
    It's a Cryptography Research paper from earlier this year and involves both a series of lattice reductions and the inverse fourier transform, which smooths out a very sharply defined bound into a much broader bound to make a search faster --- the latter trick is due to Bleichenbacher and referred to in the CRI paper as an "underground" attack. Alex Balducci in our office actually got this attack working from the paper and walked us through the code --- the lattice reduction steps take 8 hours to run, and are followed by an IFFT-aided search that I would have zero chance of getting right and so never would have bothered waiting 8 hours to try, but he did it anyways. Maybe I can get him to write it up. Moral of this story by the way: hire people smarter than you are, and give them semi-unreasonable problems to work on.
wnevets 13y ago
Steve Gibson did a pretty good job explaining this for normal folk (like me) on his podcast IMO. Episode #374 https://www.grc.com/securitynow.htm https://www.grc.com/securitynow.htm
j2kun 13y ago
From what I understand theoretical improvements in factoring algorithms go hand in hand with theoretical improvements in discrete logarithm algorithms, and for both there are algorithms which improve slightly over the trivial approach. ECC is considered better because of the believed constant factor slowdown in arithmetic operations on elliptic curves, not because discrete logarithm is considered harder than factoring. This article implies the opposite quite directly.
- pbsd 13y ago
  You're not quite right. The hardness of the discrete logarithm depends a lot on what mathematical structure you are using below. For example, the discrete logarithm on the group of the integers modulo some prime is known to be more or less as hard as breaking an RSA modulus of the same size. Those are the two problems that seem to be linked together. However, attacking the discrete logarithm on the group of points on some good elliptic curve is a very different problem, and the same techniques that work above just don't seem to apply here. So you're stuck with the generic attacks, which are much slower. Bottom line: the discrete logarithm on elliptic curves is harder than factoring and the discrete log on the integers modulo a prime.
  - swordswinger12 13y ago
    You're right about discrete log and factoring; in fact it is possible to factor any number given a discrete log oracle which accepts composite moduli. http://crypto.stackexchange.com/questions/802/would-the-ability-to-efficiently-find-discrete-logs-have-any-impact-on-the-secur http://crypto.stackexchange.com/questions/802/would-the-abil...
mrcactu5 13y ago
Why do ECC when RSA-2048 works just fine? One argument I keep hearing is that as we keep factoring the RSA numbers we just come up with bigger ones. Not a cryptography expert here, I don't know how to respond to these.
- tptacek 13y ago
  ECC is significantly faster than RSA at equivalent security levels. In case it isn't immediately clear: RSA-2048 doesn't provide 2048 "bits of security"; the 2048 describes the modulus size, but the security level is closer to 115 bits. A 256 bit ECC curve provides more security than a 2048 bit RSA key. Another reason is that progress against ECC has been slower than it has against crypto in the integer mod prime groups. ECC is based on a variant of the discrete log problem that defines multiplication in way that isn't amenable to index calculus algorithms, which are making progress against integer DLP. It may be that in the future, it won't be sufficient to steadily ramp up RSA or DH modulus sizes. ECC is thought to be more future-proof. Finally, ECC constructions happen to be quite amenable to modern crypto protocols; it is easy to do DH with ECC, and easy to sign with ECC, and DH+signatures forms the backbone of a number of modern protocols (because it's a design that provides forward secrecy).
picomancer 13y ago
The article says that the two functions, f : x -> pow(x, pubkey) mod m g : x -> pow(x, privkey) mod m being inverses of each other was a big breakthrough when it was discovered. The article implies, but does not directly state, that this "big breakthrough" was part of what separated the "classical" era of cryptography (pre-1977 as defined by the article) from the "modern" era (post-1977). The "big breakthrough" result was actually proven by Euler hundreds of years ago! [1] The innovation of RSA was building a working public-key cryptosystem around Euler's result, not the result itself. [1] http://en.wikipedia.org/wiki/Euler%27s_theorem http://en.wikipedia.org/wiki/Euler%27s_theorem
- acjohnson55 13y ago
  I've usually heard it referred to as http://en.wikipedia.org/wiki/Fermat%27s_little_theorem http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
  - wging 13y ago
    Fermat's little theorem is Euler's theorem in the special case that m is prime. The condition on Euler's theorem is that x and m must be relatively prime... which is certainly true if m is prime.
wfunction 13y ago
The NIST document was a backdoor, there's no question about it. http://www.wired.com/threatlevel/2013/09/nsa-backdoor/all/ http://www.wired.com/threatlevel/2013/09/nsa-backdoor/all/
chime 13y ago
Can someone explain why 7 and 13 (max 91) with 5 as public key, gives 29 as the private key for RSA? I wish he had explained that bit too.
- nhaehnle 13y ago
  Say e=5 is your public key. Since the encryption step is computing x^e (mod pq), you want your private key to be a number d such that (x^e)^d = x (mod pq). Basic algebra (Fermat's theorem) says that the last equation holds if you have ed = 1 (mod phi(pq)). Here, phi(pq) is the size of the multiplicative group mod pq, where the multiplicative group is simply the set of elements that have an inverse modulo pq. More basic algebra tells you that phi(pq) = (p-1)(q-1), or, in your case, 72. So, you need to find the inverse of 5 modulo 72. You can find that using the extended Euclidean algorithm for computing gcds: A number e is invertible modulo N if and only if gcd(e,N) = 1, and in this case, there exist integers a and b such that ae + bN = 1; the extended Euclidean algorithm will find them, and the number a is what you're looking for (check the definition of modular arithmetic). To verify that the number 29 makes sense, just compute 5 * 29 (mod 72): you'll get 1. I don't know if that helped at all. If it didn't, you'll have to start asking more specific questions :-)
  - tptacek 13y ago
    That's a tight little explanation.
  - chime 13y ago
    That's a superb explanation. I just plugged all that into a spreadsheet to get this: http://pastebin.com/z32SB1Z4 http://pastebin.com/z32SB1Z4 I can see that e*d mod phi = 1 when d = 29, 101, 173 etc. I understood the rest of the article except this part so thanks a lot for it!
acjohnson55 13y ago
I realize the point of the article is to make cryptography accessible, but if I'm not mistaken, their example of the use of RSA is to use it just as a substitution cypher, which would be easily decrypted by frequency analysis....
- mritun 13y ago
  That's correct. RSA (like everything else) is a deterministic encryption. That is why we must do one of the two: 1. Use a random padding 2. or always encrypt a random number. the former is PKCS#5, the latter is what https does.
weavie 13y ago
So if decrypting an RSA encoded message just involves multiplying the message by itself x amount of times, couldn't you just do keep multiplying until the result message makes sense, then you have discovered x? Sure in the example the key was so small it could only do one character at a time. With a larger key you wouldn't know the length of bytes to decode in one go. But that would only slow things down a bit. There must be more to it than that?
- ColinWright 13y ago
  If you could do a multiply in a nano-second, you could do about 3 x 10^16 multiplies in a year. Keys are about 10^300, so it would take 10^84 years. Sort of. In practice it's more complicated than that, but the numbers involved are HUGE. Doing the math with small examples always gives completely the wrong impression, like doing hill-climbing in 3D.
  - weavie 13y ago
    Yes I see. So, I assume there must be a quicker way to work out x ^ n that incorporates wrapping than just doing x = x * x % y repetitively. Darn it, my maths is getting rusty in my old age.
    - ColinWright 13y ago
      There is a fast exponentiation that is effectively Russian Peasant Multiplication, and it works in time proportional to number of bits in the exponent. Look up "fast exponentiation" or similar.
      - weavie 13y ago
        Got it. This has been very enlightening. Thanks.
    - sluukkonen 13y ago
      There is. x^n = (x^(n/2))^2 if n is even, (x^(n-1/2))^2 if n is odd, so it's possible to exponentiation in logarithmic time.
arc_of_descent 13y ago
If its too TL;DR for you to read right now, just read the first page. It's a great introduction to RSA and the use of prime numbers with real examples.

205 points by andrewfong 13y ago

pbsd 13y ago

The performance comparison of ECDSA vs RSA is somewhat unfair. In ECDSA, signing is the cheapest operation, whereas in RSA it is the most expensive. If the timings chosen were signature verification time, RSA would be much faster. See: Doing 2048 bit private rsa's for 10s: 1266 2048 bit private RSA's in 9.98s Doing 256 bit sign ecdsa's for 10s: 22544 256 bit ECDSA signs in 9.97s Doing 2048 bit public rsa's for 10s: 42332 2048 bit public RSA's in 9.98s Doing 256 bit verify ecdsa's for 10s: 4751 256 bit ECDSA verify in 9.92s A fairer comparison would probably pitch DH-2048 against ECDH-256, which is more apples-to-apples.

stock_toaster 13y ago
I don't believe 2048bit rsa and 256bit ecdsa are of equivalent security though[1]. What do things look like with 3072bit rsa? [1]: http://wiki.openssl.org/index.php?title=Elliptic_Curve_Cryptography http://wiki.openssl.org/index.php?title=Elliptic_Curve_Crypt...
- pbsd 13y ago
  OpenSSL's 'speed' utility doesn't seem to have RSA-3072 on the list, but I suppose I can downgrade to ECDSA-224 instead: Doing 224 bit sign ecdsa's for 10s: 27648 224 bit ECDSA signs in 9.94s Doing 224 bit verify ecdsa's for 10s: 5776 224 bit ECDSA verify in 10.00s
  - stock_toaster 13y ago
    there is also a huge difference between newer and older versions of openssl. # default openssl install (osx mavericks) Doing 224 bit sign ecdsa's for 10s: 39077 224 bit ECDSA signs in 9.98s Doing 224 bit verify ecdsa's for 10s: 8285 224 bit ECDSA verify in 9.98s OpenSSL 0.9.8y 5 Feb 2013 vs # homebrew openssl install Doing 224 bit sign ecdsa's for 10s: 61047 224 bit ECDSA signs in 9.99s Doing 224 bit verify ecdsa's for 10s: 15609 224 bit ECDSA verify in 9.84s OpenSSL 1.0.1e 11 Feb 2013 Both on same mac laptop.

jevinskie 13y ago

I always liked the ECC segment of a Purdue crypto course: https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture14.pdf https://engineering.purdue.edu/kak/compsec/NewLectures/Lectu...

tptacek 13y ago

Nit: the hard dependency on good randomness for ECDSA is a property of DSA in general, and not of elliptic curve cryptography. The DSA construction has what is probably the strictest randomness requirement in all of mainstream cryptography; a bias of just a few bits is, with repeated signatures, sufficient to recover private keys! (The attack that makes this work on ECDSA is extraordinarily cool). The problem with NIST Dual_EC_DRBG is simpler than the article makes it sounds. A good mental model for Dual_EC is that it's a CSRPNG specification with a public key baked into it (in this case, an ECC public key) --- but no private key. The "backdoor" in Dual_EC is the notion that NSA --- err, Clyde Frog --- who is confirmed to have generated Dual_EC, holds the private key and can reconstruct the internal state of the CSPRNG using it. I think this problem is simple enough that we may do a crypto challenge on a toy model of Dual_EC. Nobody in the real world really uses Dual_EC, but that may not always have been historically true; the circumstantial evidence about it is damning. The NIST ECC specifications are in general now totally discredited. If you want to see where the state of the art is on ECC, check out http://safecurves.cr.yp.to/ http://safecurves.cr.yp.to/. 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.

hdevalence 13y ago
Would it be possible to get a link to a technical exposition of the extraordinarily cool attack?
- tptacek 13y ago
  It's a Cryptography Research paper from earlier this year and involves both a series of lattice reductions and the inverse fourier transform, which smooths out a very sharply defined bound into a much broader bound to make a search faster --- the latter trick is due to Bleichenbacher and referred to in the CRI paper as an "underground" attack. Alex Balducci in our office actually got this attack working from the paper and walked us through the code --- the lattice reduction steps take 8 hours to run, and are followed by an IFFT-aided search that I would have zero chance of getting right and so never would have bothered waiting 8 hours to try, but he did it anyways. Maybe I can get him to write it up. Moral of this story by the way: hire people smarter than you are, and give them semi-unreasonable problems to work on.

wnevets 13y ago

Steve Gibson did a pretty good job explaining this for normal folk (like me) on his podcast IMO. Episode #374 https://www.grc.com/securitynow.htm https://www.grc.com/securitynow.htm

j2kun 13y ago

From what I understand theoretical improvements in factoring algorithms go hand in hand with theoretical improvements in discrete logarithm algorithms, and for both there are algorithms which improve slightly over the trivial approach. ECC is considered better because of the believed constant factor slowdown in arithmetic operations on elliptic curves, not because discrete logarithm is considered harder than factoring. This article implies the opposite quite directly.

pbsd 13y ago
You're not quite right. The hardness of the discrete logarithm depends a lot on what mathematical structure you are using below. For example, the discrete logarithm on the group of the integers modulo some prime is known to be more or less as hard as breaking an RSA modulus of the same size. Those are the two problems that seem to be linked together. However, attacking the discrete logarithm on the group of points on some good elliptic curve is a very different problem, and the same techniques that work above just don't seem to apply here. So you're stuck with the generic attacks, which are much slower. Bottom line: the discrete logarithm on elliptic curves is harder than factoring and the discrete log on the integers modulo a prime.
- swordswinger12 13y ago
  You're right about discrete log and factoring; in fact it is possible to factor any number given a discrete log oracle which accepts composite moduli. http://crypto.stackexchange.com/questions/802/would-the-ability-to-efficiently-find-discrete-logs-have-any-impact-on-the-secur http://crypto.stackexchange.com/questions/802/would-the-abil...

mrcactu5 13y ago

Why do ECC when RSA-2048 works just fine? One argument I keep hearing is that as we keep factoring the RSA numbers we just come up with bigger ones. Not a cryptography expert here, I don't know how to respond to these.

tptacek 13y ago
ECC is significantly faster than RSA at equivalent security levels. In case it isn't immediately clear: RSA-2048 doesn't provide 2048 "bits of security"; the 2048 describes the modulus size, but the security level is closer to 115 bits. A 256 bit ECC curve provides more security than a 2048 bit RSA key. Another reason is that progress against ECC has been slower than it has against crypto in the integer mod prime groups. ECC is based on a variant of the discrete log problem that defines multiplication in way that isn't amenable to index calculus algorithms, which are making progress against integer DLP. It may be that in the future, it won't be sufficient to steadily ramp up RSA or DH modulus sizes. ECC is thought to be more future-proof. Finally, ECC constructions happen to be quite amenable to modern crypto protocols; it is easy to do DH with ECC, and easy to sign with ECC, and DH+signatures forms the backbone of a number of modern protocols (because it's a design that provides forward secrecy).

picomancer 13y ago

The article says that the two functions, f : x -> pow(x, pubkey) mod m g : x -> pow(x, privkey) mod m being inverses of each other was a big breakthrough when it was discovered. The article implies, but does not directly state, that this "big breakthrough" was part of what separated the "classical" era of cryptography (pre-1977 as defined by the article) from the "modern" era (post-1977). The "big breakthrough" result was actually proven by Euler hundreds of years ago! [1] The innovation of RSA was building a working public-key cryptosystem around Euler's result, not the result itself. [1] http://en.wikipedia.org/wiki/Euler%27s_theorem http://en.wikipedia.org/wiki/Euler%27s_theorem

acjohnson55 13y ago
I've usually heard it referred to as http://en.wikipedia.org/wiki/Fermat%27s_little_theorem http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
- wging 13y ago
  Fermat's little theorem is Euler's theorem in the special case that m is prime. The condition on Euler's theorem is that x and m must be relatively prime... which is certainly true if m is prime.

wfunction 13y ago

The NIST document was a backdoor, there's no question about it. http://www.wired.com/threatlevel/2013/09/nsa-backdoor/all/ http://www.wired.com/threatlevel/2013/09/nsa-backdoor/all/

chime 13y ago

Can someone explain why 7 and 13 (max 91) with 5 as public key, gives 29 as the private key for RSA? I wish he had explained that bit too.

nhaehnle 13y ago
Say e=5 is your public key. Since the encryption step is computing x^e (mod pq), you want your private key to be a number d such that (x^e)^d = x (mod pq). Basic algebra (Fermat's theorem) says that the last equation holds if you have ed = 1 (mod phi(pq)). Here, phi(pq) is the size of the multiplicative group mod pq, where the multiplicative group is simply the set of elements that have an inverse modulo pq. More basic algebra tells you that phi(pq) = (p-1)(q-1), or, in your case, 72. So, you need to find the inverse of 5 modulo 72. You can find that using the extended Euclidean algorithm for computing gcds: A number e is invertible modulo N if and only if gcd(e,N) = 1, and in this case, there exist integers a and b such that ae + bN = 1; the extended Euclidean algorithm will find them, and the number a is what you're looking for (check the definition of modular arithmetic). To verify that the number 29 makes sense, just compute 5 * 29 (mod 72): you'll get 1. I don't know if that helped at all. If it didn't, you'll have to start asking more specific questions :-)
- tptacek 13y ago
  That's a tight little explanation.
- chime 13y ago
  That's a superb explanation. I just plugged all that into a spreadsheet to get this: http://pastebin.com/z32SB1Z4 http://pastebin.com/z32SB1Z4 I can see that e*d mod phi = 1 when d = 29, 101, 173 etc. I understood the rest of the article except this part so thanks a lot for it!

acjohnson55 13y ago

I realize the point of the article is to make cryptography accessible, but if I'm not mistaken, their example of the use of RSA is to use it just as a substitution cypher, which would be easily decrypted by frequency analysis....

mritun 13y ago
That's correct. RSA (like everything else) is a deterministic encryption. That is why we must do one of the two: 1. Use a random padding 2. or always encrypt a random number. the former is PKCS#5, the latter is what https does.

weavie 13y ago

So if decrypting an RSA encoded message just involves multiplying the message by itself x amount of times, couldn't you just do keep multiplying until the result message makes sense, then you have discovered x? Sure in the example the key was so small it could only do one character at a time. With a larger key you wouldn't know the length of bytes to decode in one go. But that would only slow things down a bit. There must be more to it than that?

ColinWright 13y ago
If you could do a multiply in a nano-second, you could do about 3 x 10^16 multiplies in a year. Keys are about 10^300, so it would take 10^84 years. Sort of. In practice it's more complicated than that, but the numbers involved are HUGE. Doing the math with small examples always gives completely the wrong impression, like doing hill-climbing in 3D.
- weavie 13y ago
  Yes I see. So, I assume there must be a quicker way to work out x ^ n that incorporates wrapping than just doing x = x * x % y repetitively. Darn it, my maths is getting rusty in my old age.
  - ColinWright 13y ago
    There is a fast exponentiation that is effectively Russian Peasant Multiplication, and it works in time proportional to number of bits in the exponent. Look up "fast exponentiation" or similar.
    - weavie 13y ago
      Got it. This has been very enlightening. Thanks.
  - sluukkonen 13y ago
    There is. x^n = (x^(n/2))^2 if n is even, (x^(n-1/2))^2 if n is odd, so it's possible to exponentiation in logarithmic time.

arc_of_descent 13y ago

If its too TL;DR for you to read right now, just read the first page. It's a great introduction to RSA and the use of prime numbers with real examples.