An obvious approach to increase the security of a symmetric algorithm is to apply the same cipher twice, i.e.:

y = ek2(ek1(x))

As is often the case in cryptography, things are very tricky and results are often dif- ferent from the expected and/ or desired ones. In this problem we show that a double encryption with the affine cipher is only as secure as single encryption! Assume two affineciphersek1 =a1x+b1 andek2 =a2x+b2.

1. Show that there is a single affine cipher ek3 = a3x + b3 which performs exactly the same encryption (and decryption) as the combination ek2(ek1(x)).

2.Findthevaluesfora3,b3 whena1 =3,b1 =5anda2 =11,b2 =7.

For verification: (1) encrypt the letter K first with ek1 and the result with ek2, and

(2) encrypt the letter K with ek3 .

Briefly describe what happens if an exhaustive key-search attack is applied to a

double-encrypted affine ciphertext. Is the effective key space increased?

Remark: The issue of multiple encryption is of great practical importance in the case of the Data Encryption Standard (DES), for which multiple encryption (in par- ticular, triple encryption) does increase security considerably.