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 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?

share|improve this question
3  
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. $\;\;\;$ –  Ricky Demer Sep 20 '13 at 15:23
    
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) –  tylo Sep 23 '13 at 11:17

2 Answers 2

up vote 12 down vote accepted

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.

share|improve this answer
    
Given the recent NSA scandal - I think that last point is more pertinent than ever. –  hunter Sep 20 '13 at 20:54
    
From the time between when the winner Rijndael was selected and when AES was published as a standard, what changes were made to the algorithm by NIST? Rijndael won not because it had the best security but because it was slightly faster and because of other "design considerations". What were these other considerations and why are they more important than security? If high security was priority, Serpent or Twofish should've been chosen regardless of if they were a bit slower. It's interesting to note that Keccak (the SHA3 winner) also had Daemen as an author. Winning twice in a row seems odd... –  NDF1 Sep 21 '13 at 11:50
2  
Rijndael was not changed between selection and publication as standard (NIST rewrote the text, though; and they defined that AES always had 128-bit blocks whereas Rijndael also supported larger blocks, up to 256 bits). Also, Rijndael was not considered as "less secure"; it was part of Serpent propaganda to claim that "yeah, it is slower, but that's because it is more secure" but that claim was never substantiated. In fact, out of the 15 candidates, only two were found to be less than optimally secure. Rijndael was chosen mainly because there was no arch where it would be abysmally slow. –  Thomas Pornin Sep 21 '13 at 12:32
    
I had a suspicion that this might be the only answer. Well, DES was deemed secure based on the same principles. (Except the "American" argument). I hoped there might be some mathematical basis, rather than "no one cracked it yet" argument. Anyway I will wait a day and accept this answer if no other answer comes up. –  Eiver Sep 23 '13 at 6:49

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.

share|improve this answer

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.