3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Mar 7, 2014 at 9:06
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Jun 6, 2015 at 12:27

1 Answer 1

Reset to default
1
$\begingroup$

RSA will never become "impractical" until it gets broken. (in polynomial-time)

As the best current algorithm to break RSA is sub-exponential (general number field sieve / GNFS). According to Moore's law computing power grows exponentially however. So simply increasing key size will always be an option.

Beyond 256-bit security EC crypto just is significantly faster than "classic" crypto. For example, for 512bits, EC crypto is 64 times faster than classic crypto (compared to private key operations using RSA).

If you are interested in key sizes you should read this paper.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The linked paper is dated 2001; a much more recent 2012 survey conducted by ECRYPT contains estimates based on more recent cryptanalytic improvements. cordis.europa.eu/docs/projects/cnect/6/216676/080/deliverables/… $\endgroup$
    – rmalayter
    Apr 9, 2015 at 3:16
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Jun 6, 2015 at 10:33

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.