I got asked this question today and I didn't know the answer, AES-128 is considered secure, the key size is 2^128, so you would need in average 2^127 tries to break the key. Why does RSA need at least a 1024-bit modulus to be considered secure, If we consider a bruteforce attack on the private exponent, it would take 2^1019 tries (lets consider the private exponent is 1020-bit in length). Is the difference because of a much less complex attack that exists on RSA but doesn't exist in AES?

  • $\begingroup$ If you take a look at keylength.com then you quickly find out that a modulus of 1024 bits is considered rather weak nowadays. $\endgroup$ – Maarten Bodewes Feb 11 '16 at 13:56

It's because with the key to determining the secret private key in RSA is to factor the public modulus into its two prime factors p and q and need a very large number (2^1024, 2^2048) to make this is computationally difficult.

| improve this answer | |
  • 1
    $\begingroup$ Actually, to answer the question: while factoring the modulus may be difficult, it is significantly easier than trying to brute force the private exponent, or even trying possible primes $p$ to look for a factor... $\endgroup$ – poncho Feb 10 '16 at 22:34
  • $\begingroup$ Of course. A brute force over the od numbers (not necessary primes) factor space require "only" 2^511 trial divisions. $\endgroup$ – Robert NACIRI Feb 11 '16 at 15:03

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