16
$\begingroup$

The security of RSA is based on the integer factorization problem, which is a very well defined and understood mathematical problem. This problem must be solved in order to fundamentally break RSA.

What about AES (and others based on the same idea)?
Why is it difficult to break?
Is there any mathematical principle that ensures its security?

$\endgroup$
  • 4
    $\begingroup$ It's not actually known that the integer factorization problem "must be solved in order to fundamentally break RSA". $\:$ It could be that there's a not-too-slow computation on its public keys that yields information sufficient to do the private operation almost as fast as that can be done with the private key, but can't be used to get a factorization. $\;\;\;$ $\endgroup$ – user991 Sep 20 '13 at 15:23
  • $\begingroup$ RSA is probably easier to break than integer factorization, but it is not proven. However, we don't even know that integer factorization is really hard. We only know no efficient algorithm yet. The problem is well understood, but we mostly rely on assumptions (aka educated guesses) $\endgroup$ – tylo Sep 23 '13 at 11:17
  • $\begingroup$ @RickyDemer RSA may be easier to break than integer factorization; however, if it is easier to break, then the computation won't be done on the keys, but the ciphertexts. In fact, it has been proven that finding the private key d from (n, e) is as hard as factoring n into (p, q) – assuming the extended Riemann hypothesis. $\endgroup$ – dionyziz Apr 14 '17 at 22:32
  • $\begingroup$ @dionyziz : ​ ​ ​ That only means the ​ "information sufficient ... with the private key" ​ would have to not be sufficient for finding a valid private exponent. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Apr 14 '17 at 23:23
20
$\begingroup$

AES is deemed secure because:

  • Its building blocks and design principles are fully specified.
  • It was selected as part of an open competition.
  • It has sustained 15 years of attempted cryptanalysis from many smart people, in a high-exposure situation, and it came out relatively unscathed.

Another reason, which is not as good but felt important by many people:

  • It was designed by non-American cryptographers.

In asymmetric cryptography we often (try to) reduce security to a "known hard problem", a luxury which is not often encountered in symmetric cryptography, but this does not change the conceptual root of the issue: at some level, there is some "problem" for which no efficient solving algorithm is known, despite decades of research. It is not proven that the problem is necessarily hard, or even that there can exist such as thing as a necessarily hard problem, but we are just stumped when it comes to finding a solving algorithm. With AES, the "hard problem" happens to be the AES itself.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jun 19 '17 at 14:00
4
$\begingroup$

There is no hard problem to which AES can be provably be reduced. It is believed to be difficult to break because lots of smart people have tried for more than a decade now, using the best (publically known) techniques, and so far the only successes have been marginal improvements compared to brute force.

$\endgroup$

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