Homework #1
Spring 2012
Due: Friday, Feb 3 at 1 pm
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 = 0
l 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:
- Prove that if only a single character is encrypted, then the shift cipher is perfectly secret.
- 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
- Compress the data and then encrypt the result, or
- Encrypt the data and then compress the result.
Justify your answer. (There is no right or wrong answer.)