# Homework #1

### Problem #1 : Cryptanalysis of Vigenère Cipher.

Write a program (in any language) that performs cryptanalysis of ciphertexts encrypted using the Vigenère cipher using the method described in class (and in the book). Use your program to recover the plaintext corresponding to the following ciphertexts: first and second. (Linebreaks were inserted just for convenience; make sure to ignore them in your attack.) Hand in a printout of your program in addition to the plaintext. Also, here are the letter frequencies for the English language.

### Problem #2 : Specifying Encryption Schemes.

An encryption scheme is formally defined by algorithms Gen, Enc, and Dec, as well as a message space M. Give formal specifications for the shift cipher and the substitution cipher.

### Problem #3 : One-Time Pad with All-Zeroes [KL Ex 2.3].

When using the one-time pad encryption scheme, it can occur that k = 0l and then the ciphertext is equal to the plaintext! It has been suggested to improve the one-time pad by only choosing non-zero keys. What do you think of this improvement? In particular, is it still perfectly secret? If yes, prove it. If no, reconcile this with the fact that encryption with the all-0 key completely reveals the plaintext.

### Problem #4 : When is the Shift Cipher Secure? [KL Ex 2.4].

In this exercise, we study conditions under which the shift cipher is perfectly secret:
1. Prove that if only a single character is encrypted, then the shift cipher is perfectly secret.
2. Reconcile the above claim of perfect secrecy with the ciphertext-only attack on the shift cipher that was shown in class.

### Problem #5 : Compression vs Encryption.

Data compression is often used in data storage or transmission. Suppose you want to use data compression in conjunction with encryption. Does it make more sense to
1. Compress the data and then encrypt the result, or
2. Encrypt the data and then compress the result.