- Thread starter
- #1

- Feb 5, 2012

- 1,621

Here's a question I encountered in one of my computer science classes.

- How many tests are necessary to break a DES encryption by brute force attack?
- What is the expected number of tests to break a DES encryption by brute force attack?
- How many tests are necessary to break a 128-bit key AES encryption by brute force attack?
- What is the expected number of tests to break a 128-bit key AES encryption by brute force attack?

And here's my answer. I just want to know whether you think it's correct. It seems ambiguous to me what is meant by necessary and expected in these questions. I hope I did it correctly but want some confirmation.

**My Answer:**

The number of bits in the key of the DES algorithm is 64. However only 56 bits are used in encryption; giving a total number of $2^{56}$ keys. Therefore the

**expected**number of tests to break a DES encryption by brute force is $2^{56}$.

However DES has the property that the compliment of the plaintext gives the compliment of the ciphertext under the compliment of the key. That is if the encryption is given as, $c=E(p,\,k)$ then, $\neg c=E(\neg p,\,\neg k)$. Therefore in each test (each application of the decryption algorithm) we can take the compliment of the plaintext that is produced and check whether it makes sense. This means instead of running the decryption algorithm $2^{56}$ times we only need to run the algorithm $2^{56}\div 2=2^{55}$ times. Hence the

**necessary**number of tests to break a DES encryption by brute force is $2^{55}$.

Both expected and necessary number of tests to break a 128-bit AES encryption by brute force is $2^{128}$. This stems from the fact that the AES encryption scheme does not have the complimentary key weakness as the DES algorithm. So each key will have to be tested separately applying the decryption algorithm over and over again.