ECC and RSA 10K stronger claim

There are a lot of websites where it is claimed something akin to this but no explanation on the basis.

"ECC key size of 256 bits is equivalent to a 3072-bit RSA key and 10,000 times stronger than a 2048-bit RSA key"

Q: What is the basis of this claim about the 10K factor? Where does the 10K come in?

I see the comparable key sizes from this table (this is referred everywhere).

Also, a link where the claim is made. BTW: This is not the only site that makes this claim.

• RSA-3072 is roughly 128 bit security, RSA-2048 is roughly 112 bit security -> 2^128 / 2^112 = 65536 which is roughly 10k? – SEJPM Jul 30 '15 at 20:31
• yes I understand that but 10K? Still a mystery. :-) – Khanna111 Jul 30 '15 at 21:25

These estimates are very crude and, arguably, don't make sense.

Asymmetric cryptographic algorithms, like RSA and ECDSA, are based on mathematical structures, and breaking them requires unraveling that structure. Generally speaking, the difficulty of doing so raises with the size of the underlying objects (i.e. the "key size"), but not in an easy, simple, exponential rule.

A lot of efforts have been expanded into making some "strength estimates" to be able to compare RSA key sizes with ECDSA key sizes, and also key sizes for symmetric algorithms (like AES). It is very hard to even define properly, because breaking a RSA key through integer factorization with the best known algorithms for that task (General Number Field Sieve) requires not only a lot of computations, but also handling an awful lot of data with access patterns that are not amenable to serialization and parallelism -- to say things plainly, you need a computer with a really large amount of very fast RAM (we are not talking mere terabytes here). This does not compare directly with, say, AES-key breaking, which needs a lot of CPU but has no need for RAM, and is embarrassingly parallel.

Nevertheless, some smart people still have produced estimates, and there is a nice Web site that presents them and let you tweak the parameters. For instance, if you look at the NIST recommendations, a 2048-bit RSA key is deemed "somehow equivalent" to a 112-bit key for a symmetric algorithm, while a 3072-bit RSA key would rate as a 128-bit symmetric key. Symmetric keys are just bunch of bits with no special structure, so an n-bit key means "can be broken in effort 2n-1 on average" (by enumerating possible combinations of n bits until the right one is found). Therefore, per the NIST estimates, RSA-3072 is deemed to be about 65536 times stronger than RSA-2048 (because 128-112 = 16 and 216 = 65536).

Other equations yield different results. The method explained in RFC 3766 rates RSA-2048 as equivalent to a 103-bit symmetric key, and RSA-3072 up to 125-bit. Now these estimates would imply that RSA-3072 would be more than 4 million times harder to break than RSA-2048 (2125/2103 = 4194304). Let's also note that RFC 3766 says that RSA-2048 is then half a million times weaker than what NIST says it is.

I can also be said that a simple statement such as "RSA-3072 is X times harder to break than RSA-2048" can make sense only if you can quantify the hardness of breaking RSA-2048 and RSA-3072. The quantification is: how much money would it take ? And, right now and also for the foreseeable future (i.e. within the next 40 years), the only sane answer is "forget it". No amount of money on Earth, even with all the existing money taken together, will buy you a RSA-2048 key break or a RSA-3072 key break. This is simply out of reach of our technology.

This does not mean that RSA-2048 will be forever unbreakable; it only says that if (or when) it is broken, it will be through a qualitative enhancement (an algorithmic breakthrough) whose characteristics are, by definition, totally unknown.

Correspondingly, any assertion about RSA-3072 being "10 thousand times" stronger than RSA-2048 are mostly unsubstantiated speculation. Or, at best, a mathematical extrapolation from existing data points, raised to levels that make no physical sense.

• Thanks Thomas. This is what I was thinking and your answer has confirmed that. – Khanna111 Jul 30 '15 at 21:58

I just found one source that claims this 10K you mentioned, however there is a study from Symantec here stating the following:

While key lengths for current encryption methods using RSA increase exponentially as security levels increase, ECC key lengths increase linearly . For example, 128-bit security requires a 3,072-bit RSA key, but only a 256-bit ECC key . Increasing to 256-bit security requires a 15,360- bit RSA key, but only a 512-bit ECC key 3....

Here you can find a "relatively easy to understand" primer on elliptic curve cryptography.

A comparison between the cryptosystems can be found here:

Elliptic curve cryptography is probably better for most purposes, but not for everything.

ECC's main advantage is that you can use smaller keys for the same level of security, especially at high levels of security (AES-256 ~ ECC-512 ~ RSA-15424). This is because of fancy algorithms for factoring like the Number Field Sieve.

• Smaller keys, ciphertexts and signatures.
• Very fast key generation and signatures.
• Moderately fast encryption and decryption.
• Binary curves are really fast in hardware.

• Complicated and tricky to implement securely, particularly the standard curves.
• Standards aren't state-of-the-art, particularly ECDSA which is kind of a hack compared to Schnorr signatures.
• Signing with a broken random number generator compromises the key.
• Still has some patent problems, especially for binary curves.
• Newer algorithms could theoretically have unknown weaknesses. Binary curves are slightly scary. Don't use DUAL_EC_DRBG, since it has a back door.