Answer Happy

Problem 5 Let Krsa be an RSA generator with security parameter k, and let & be an addi- tional parameter. We require that k and are both multiples of 8, and that ≤ k - 16. Let H: {0,1}-16 {0,1}16 be a hash function which compresses to 16 bits. Consider the key- generation algorithm X and encryption algorithm & defined below: Alg E((N, e), M) // M = {0,1}*--16 Alg K R {0, 1}/2 Z← 0²/2 (N, p, q, e, d) Krsa Return ((N, e), (N, d, p, q)) X + (M || R || Z) Y + (H(X) || X) mint(Y); c← m² mod N Return c The notation int(Y) indicates that we are converting the binary string Y to an integer. 1. Specify in pseudocode an O(³)-time decryption algorithm D such that AE = (K, E, D) is an asymmetric encryption scheme satisfying the correct decryption requirement. Note that your algorithm D must return if the input ciphertext could not have been produced by the E algorithm. 2. What are the conditions for C-2 mod N (where C is a ciphertext output by the algorithm above) to be a valid ciphertext? 3. Show that the probability of D((N, d, p, q), C. 2 mod N) = 1 is greater than 0.5. 4. Show that AE = (K, E, D) is not IND-CCA-secure by presenting an O(k³)-time adversary A making at most 131072 LR and Dec queries, and achieving Advind-cca (A) ≥ 0.9.