# Will non-ECC algorithms like RSA eventually become too inefficient?

The strength of symmetric and asymmetric encryption schemes scales with the key length, but there is a difference between symmetric algorithms like AES and asymmetric algorithms like RSA.

For example, according to some sources, 128 bit symmetric keys are equivalent to 3072-4096 bit asymmetric keys; but to get 256-bit equivalent security, asymmetric keys need to be more than 15000 bits long. Elliptic curve keys, however, are often stated to be comparable to symmetric encryption keys (with a constant factor of about $1/2$).

Is there an exponential relation between the key length for symmetric/ECC and asymmetric encryption schemes, and what are the theoretical and practical implications of that? Will there be a point in time where using RSA and DH/DSA will be impossible because of the huge key sizes and the resulting computations?

How does this relate to the notion of computational security, especially the security parameter of an algorithm – is the security parameter exactly the key length, or can the key length be a (polynomial? exponential?) function of the security parameter?

• A 128 bit security level is already pretty high. It seems unlikely to be that we'll get classical computers which can break that security level before we get quantum computers which kill all of ECC, finite field DH/DSA and RSA. – CodesInChaos Mar 7 '14 at 9:06
• Inefficient implicitly indicates that the algorithm is used in a certain situation. If you say that the algorithm itself is inefficient then - in my opinion - you are suggesting that it could not be used anymore in any situation. This is reflected by the given answer and my comment. For embedded devices and smart card you could argue that RSA private key operations, RSA key pair generation and RSA signature size are already major issues. – Maarten Bodewes Jun 6 '15 at 12:27

• I agree with SOJPM here. Impractical would mean that it is not usable at all anymore. Anybody that has tried to generate a 15K key pair will probably agree that this is a process that is currently too painful compared to ECC. It however is also so far out of reach with regards to factoring $p$ & $q$ that it currently isn't necessary at all. – Maarten Bodewes Jun 6 '15 at 10:33