Math 431 Final Exam, FALL 1996

This exam is to be completed using only scratch paper and pencil or pen (no calculators, books, or notes). The time for the exam is 120 minutes. Please note that these questions are in English, and your answers should also be in English.

Problem 1 (5 points). Let e_k: P -> C be the encryption function for a block cipher. Describe how such an encryption function can be used in Cipher Block Chaining mode (CBC).

Problem 2 (9 points). Define a block cipher as follows: let p be a large prime, P = C = Z_p x Z_p, K = Z_p, and define e_k(x₁, x₂) = (kx₁ - x₁ mod p, x₁+ k²x₂ mod p).

a) Derive the decryption function d_k(y₁, y₂). Are all keys possible?

b) Describe how to carry out a chosen plaintext attack on this cipher to recover the key.

Problem 3 (8 points). Let P be a random variable that takes on the values {0,1,2} with probabilities {1/2, 1/4, 1/4}, respectively.

a) Calculate the entropy of the random variable P.

b) Let the same P denote a plaintext distribution, and define an encryption system with K = {1,2}, C = {0,1,2}, and e_k(x) = x + k (mod 3). Calculate the key equivocation H(K | C), assuming equally likely keys.

Problem 4 (9 points). Define a stream cipher as follows. Let n be a large integer, and define P = Z_n,

C = Z_n, K = Z_{n ,}and L = Z_n. Let k in K be the key, and let x₁, x₂, x₃, ... denote the sequence of plaintext from the message. Define the keystream sequence by

z₁ = k,

z_i = kz_i-1 + x_i-1 (mod n), if i > 1.

Define the encryption function by e_k(x_i) = x_i + z_i mod n.

a) Describe how to carry out a chosen plaintext attack against this encryption system.

b) If a ciphertext letter c_i is garbled in transmission, what happens to the message that is received?

Problem 5 (6 points). Use the Chinese remainder theorem to determine all solutions x with 0<x<713 for the congruence x² = 4 (mod 713) . How many solutions are there? HINT: 713=23*31.

Problem 6 (8 points).

a) State the definition of the order of a modulo n.

b) What is the order of 2 modulo 33 ?

Problem 7 (16 points). Let A and B be sets.

a) State the definition of a strongly collision-free hash function f: A -> B.

b) State the definition of a weakly collision-free hash function f: A -> B

c) If a hash function f is not weakly collision free, and a signature scheme is used to sign a message m by signing f(m) instead, what kind of attack can be mounted against the scheme?

d) Let p be a large prime for which 2 is a primitive root modulo p. Define a hash function f: Z -> Z_p by f(x) = x + 2^x (mod p). Is this function weakly collision free? Is it strongly collision free? Why or why not?

Problem 8 (12 points).

a) Describe the ElGamal encryption scheme.

b) State the definition of the perfect secrecy property for an encryption system.

c) Does the ElGamal encryption scheme have the perfect secrecy property?

Problem 9 (12 points). Suppose that Bob has an RSA public key of n = 55 and b = 7.

a) Find Bob's private key a.

b) If the ciphertext produced using Bob's key is 3, what is the corresponding plaintext?

c) What message has 4 as a signature using Bob's key in the RSA digital signature scheme ?

Problem 10 (15 points). Answer each statement as true or false, and give a reason to justify your answer.

a) The one-time pad is not vulnerable to a chosen plaintext attack.

b) CBC mode of DES is generally safer than Electronic codebook mode. c) When a message is signed twice using the same key under the ElGamal signature scheme, the two signatures will be the same.

return to the CS 431 home page