Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 3 Solutions - Ex3.9
- 1 min- Return to index
- Exercise 3.1
- Exercise 3.2
- Exercise 3.3
- Exercise 3.4
- Exercise 3.5
- Exercise 3.6
- Exercise 3.7
- Exercise 3.8
- Exercise 3.9
- Exercise 3.10
- Exercise 3.11
- Exercise 3.12
- Exercise 3.13
Exercise 3.9
Assume we perform a known-plaintext attack against DES with one pair of plaintext and ciphertext. How many keys do we have to test in a worst-case scenario if we apply an exhaustive key search in a straightforward way? How many on average?
Solution
This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.
Assuming that no two keys can produce the same ciphertext for the same plaintext (possibly not a realistic assumption) then the worst case is the one where you have to check all \(2^{56}\) possible keys. I.e. the correct key is the very last possible key that you check.
In the average case you will find the key exactly halfway through your search, meaning \(2^{56} \div 2 = 2^{55}\) key checks.
Thomas Busby
I write about computing stuff