Definition 0.1 (Shared-key encryption) Let M denote a message-space, let K denote a key-space, and let l, k denote plaintext and key sizes respectively. Then, a shared-key encryption scheme is defined by the following three algorithms: (a) K KeyGen (K, k): This is a probabilistic algorithm that takes as input the key space, the key size, and outputs a key, K such that K{0, 1}k, and K = K. (b) CEncrypt(K, ME M): This is a probabilistic algorithm that takes as input a message M, such that MEM and M{0, 1}', a key K, and outputs a ciphertext C, s.t., C← {0, 1}'. (c) M Decrypt(K, C): This is a deterministic algorithm that takes in the key K, ciphertext C, and outputs the plaintext message M. Using this definition as a reference, provide a formal definition of the Keygen, Encypt, Decrypt algorithms for the Vigenère cipher over the 26-letter English alphabet. Note that you will need to carefully specify how the encryption/decryption functions work - do not define these in generic terms. There could be several plausible choices for KeyGen; choose one and state your assumptions clearly. 2. (20 points) Show that the Caesar, Vigenère ciphers are easy to break by doing a chosen-plaintext attack. How much plaintext is needed to recover the key for each of the ciphers? You might need to make some assumptions here, make sure to state them clearly. 3. (10 points) What is the effect of a single-bit error in the ciphertext when using the CBC, OFB, and CTR modes of operation? 4. (30 points) In class, we'd seen the stateful variant of CBC mode is IND-CPA insecure. However, the stateful variants of OFB and CTR modes are IND-CPA secure. Write the IND-CPA attack games for the stateful OFB and CTR modes, akin to the one for stateful CBC mode, assuming adversary knows the first IV/nonce. Briefly point out and explain why the attack games fail. 5. (20 points) Consider a stateful variant of CBC mode, where the sender simply increments the IV by 1 each time a message is encrypted (rather than choosing a random IV every time). In this case, the IVs are distinct, but not random. Write the IND-CPA game, and informally argue why the resulting scheme is IND-CPA insecure. Assume adversary knows first IV.