21
$\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?

Improve this question
$\endgroup$
4
  • 6
    $\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, 2013 at 15:23
  • 1
    $\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, 2013 at 11:17
  • 1
    $\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, 2017 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, 2017 at 23:23

2 Answers 2

Reset to default
24
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Jun 19, 2017 at 14:00
  • $\begingroup$ What do you mean by 'With AES, the "hard problem" happens to be the AES itself.'? Do you mean that using chosen-plaintext attack for example and construct the the algebraic system of equations that represents AES, then, this system can not be solved efficiently? $\endgroup$
    – Crypt01
    Oct 7, 2021 at 7:14
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.

Improve this answer
$\endgroup$

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