CSC507/609
University of Miami
3 Feb 2016
Burton Rosenberg

Updated: 9 Feb 2016

Due Date: see assignment

PROBLEM SET 2
-------------


1) Output feedback mode requires a pseudo-random function, and it might fail on encryption primitives that are not pseudo-random. The Enigma was an early cipher, used by the Axis powers during WWII, and has been the subject of many interesting biographical and historical accounts. For practical reasons, encryption by a key K was also decryption by the key K. Hence E_k(E_k(m)) = m. The encryption is an involutary permutation, let's say chosen randomly over the space of all involutary permutations from n elements to n elements but the key k.

Show that using an involutary permutation in OFB gives a completely insecure cipher.


2) Consider the following cipher, which I just made up. Choose a book. The Initial Vector is a page number. Go to that page number in the book and beginning with the first letter of the first new paragraph on that page, perform a Vernum-like shift cipher, using consecutive letters starting at said first letter. Skip any character that is not an alphabet letter, and map a to 0, b to 1, etc., for message text, ciphertext, and key encoding.

For instance, if the book is our text book, and the initial vector is 349, then decode the following message:


   oyisl xhume nreau solek tyczp anvmi syrkr vlplm zrbeh imwyz gmefo 
   guosu tmthr vhuny wgylc oeudi ujssi oqtgh nadcc pvicf qgfdu cjesu 
   gdyad iwwfk lbdwe eprtp pfvgd fswhr zuwey 

 
Does this cipher have perfect secrecy? Why or why not (refer to Shannon's theorem of Perfect Secrecy, if you wish)? If it is not perfectly secret, please suggest ways of attacking this cipher


Note: this problem has the following parts:
* Part A is to perform the decryption; 
* Part B is to answer about perfect secrecy; 
* Part C is the suggestion of ways to attack the cipher, or to state there are no attacks.

3) Problem 3.30 in the textbook.

4) Early pseudo-random numbers used a linear congruential generator. Choose an integer n,
choose integers a and b, and iterate the formula: ax+b mod n, to get a stream of values 
for x, starting at an initial x called a seed. 

Show that using CBC mode, how to attack this cipher. You may use a Chosen Plaintext Attack, if using a chosen plaintext helps.

Note: Use addition mod n, rather than XOR as the way to combine the previous ciphertext with the new message. The F_k function is the arithmetic computation ax+b mod n. So the plaintext and ciphertext space are 0, ... , n-1.


5) Use the definition of a Distinguisher to describe the experiment to distinguish a biased coin from true random bits (i.e. an unbiased coin). Give the probability that the Distinguisher will have success.


6) How to unbias a biased coin. Taking each two coin flips and making a single decision according to: if the coin flips disagree, output the value of the first flip; else discard the pair and give no output.

Prove that the output stream is unbiased.  Give the expected number of unbiased bits for every n biased bits.


7) Show the following is not a PRG. In the field of numbers 0 through p-1 mod p, where p is a prime, choose as key a non-zero vector:

    r_1, r_2, ..., r_{n+1}

where each r_i is choosen uniformly in Z_p. Given n elements

	x_1, x_2, .., x_n

chosen uniformly over Z_p, expand the n elements to n+1 elements by choosing x_{n+1} such that:

    r_1 * x_1 + r_2 * x_2 + ... + r_{n+1} * x_{n+1} = 0 mod p

Show the distinguisher and compute the probabilities.


Note: an update, the restriction on r should be that r_{n+1} is non-zero.