I have started learning about Elliptic Curve Cryptography (ECC). Since the key size required in ECC is relatively smaller than the key size in RSA (to provide the same encryption strength), I wonder whether the smaller key size of ECC makes it vulnerable to brute force attack. Does it?

I'm not very knowledgeable about the ways in which a key can be cracked. But, basically, fewer bits means the number of possibilities can be more quickly guessed or tried!

  • 2
    $\begingroup$ Why do people refer to "ECC" as if it were an algorithm? $\endgroup$ – fkraiem Nov 26 '15 at 13:00
  • $\begingroup$ @fkraiem, arguably the same could be said about RSA. $\endgroup$ – otus Nov 26 '15 at 14:25
  • 1
  • $\begingroup$ @fkraiem Because we humans need to simplify the world in our brains to be able to get a grip. That's not a problem as long as the experts in the specific field do not start to do the same. That would be called populism (in politics). Instead we need to explain the difference between the field of ECC cryptography and the particular algorithms when required. That's probably not needed here though. $\endgroup$ – Maarten - reinstate Monica Nov 27 '15 at 12:39

Yes a brute force key-guessing attack would be faster, but:

  1. It would be ridiculously slow for either. E.g. see this for 256-bit keys.
  2. There are faster attacks on both and those attacks break larger RSA sizes than ECC sizes.

Related: Why can ECC key sizes be smaller than RSA keys for similar security?

  • 1
    $\begingroup$ I like the distinction between key size and key space that has been offered by PYZH. Furthermore, some (future) attacks that use quantum computing may be more efficient for comparable security levels (where QC is not taken into account yet, obviously). Maybe these notions can be incorporated in the answer? $\endgroup$ – Maarten - reinstate Monica Nov 27 '15 at 12:31
  • $\begingroup$ @MaartenBodewes, I don't think that distinction gets at the actual issue. For example, you can look at Diffie–Hellman (or IES, if you don't consider DH values keys) and find that the possible key space is pretty dense, but you still need larger public keys than with elliptic curves. $\endgroup$ – otus Nov 27 '15 at 13:37
  • $\begingroup$ Regarding quantum attacks, is there something relevant to say beyond that Shor's algorithm would break both systems? $\endgroup$ – otus Nov 27 '15 at 13:40

The ECC cryptographic scheme isn't itself more vulnerable to brute force attack than RSA, to the contrary it is much less vulnerable. What is vulnerable to brute force attack is the often bad copy/paste implementation of Elliptic curve multiplication and the bad usage of pseudo random number generators. When devs just copy/paste the formulas without understanding what the function and parameters really do they open the door to brute force attacks. This has happened already with bad wallet implementations of Bitcoin. Biased Nonce Sense: Lattice Attacks againstWeak ECDSA Signatures in CryptocurrenciesJoachim Breitner1[0000−0003−3753−6821]and Nadia Heninger21DFINITY Foundation, Zug,joachim@dfinity.org2University of California, San Diego,nadiah@cs.ucsd.edu https://eprint.iacr.org/2019/023.pdf

  • $\begingroup$ could you add some links to your claims? $\endgroup$ – kelalaka Sep 12 at 12:30
  • $\begingroup$ You can edit your answer to include those. $\endgroup$ – kelalaka Sep 12 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.