Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
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

1 Answer 1

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

As the best current algorithm to break RSA is subexponential (general number field sieve / GNFS) but according to moore's law, computing power grows exponentially simply increasing key size will always be an option. But beyond 256-bit security ec crypto just is significantly faster than "classic" crypto. F.ex. for 512bits, ec crypto is 64times faster than classic crypto.

If you are interested in keysizes you should read this paper.

share|improve this answer
    
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/… –  rmalayter Apr 9 at 3:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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