Exercises

3.1	How many possible internal states does the RC4 algorithm have? Hint: The state array represents a permutation of 256 values, and each of the indices i and j can have any value between 0 and 255.
3.2	Implement RC4 in your favorite language.
3.3	Draw a diagram similar to Figure 3.2 showing the CBC decryption process.
3.4	Suppose that we are using a block cipher in CBC mode to encrypt plaintext blocks <Pi> into ciphertext blocks <Ci>, and that Cj = Ck for some j k. Show that this implies that Pj Pk = Cj-1 Ck-1 What are the implications of this if the <Pi> are highly redundant text, such as English text? If we are using CTR mode instead of CBC mode and Cj = Ck, what can we say about Pj and Pk?
3.5	In Section 3.4, we saw how a block cipher can be used to generate a message authentication code. How could we use a block cipher to build a cryptographically strong pseudorandom number generator?
3.6	In Section 3.3, we observed that Alice can't use RSA to directly encrypt a 256-bit block cipher key, K, because Ke < n and so Ke mod n = Ke and an attacker could merely extract the eth root to recover K. One solution to this was for Alice to choose a large random number that she and Bob would use to generate a key K and to encrypt this random number instead of K with RSA. How could Alice and Bob generate a 256-bit key from a large random number?
3.7	Review the MD5 and SHA-1 algorithms and notice that after processing each 512-bit block of the message, the entire state of the computations so far is contained in the four (MD5) or five (SHA-1) register variables. Given m and h(K || m), show how it is possible to compute h(K || m || y), where y is arbitrary text. This is known as an extension attack. Give an example to show how this attack might be used.