Suppose that Alice encrypted a message with a secure cipher that uses a 40-bit key. Trudy can see the ciphertext and knows the algorithm that Alice used. However, Trudy does not know the plaintext or key. Trudy plans to launch am exhaustive search attack to find the correct key. How many keys, on average, must Trudy try before she finds the correct one?

1. 2^40

2. 2^39

3. 2^20

4. None of the above