(a) A public key encryption (PKE) scheme consists of a triple of algorithms (KGen, Enc, Dec).Describe the function of each of these algorithms and explain what is meant by the correctness of a PKE scheme.[4 marks] (b) The standard notion of security for a PKE scheme is indistinguishability under chosen cipher text attack, or IND-CCA for short. Give an informal description of this security notion and explain why it is important in practice that a PKE scheme should meet it. You may use a diagram to illustrate your answer.[6 marks] (c) The naïve RSA-based encryption scheme has ciphertexts C' in which C = MC mod N. Here M is a message interpreted as a number between 0 and N−1; (N, e) is the public encryption key; d is the private decryption key; and N modulus, that is, a product of two large primes p and q.=pq is an RSA (i) Describe the algorithm Dec for this scheme. (ii) Explain why, if an attacker can factorise N, he can then efficiently recover the private decryption key d. Illustrate your answer for N = 15 and e = 3. [4 marks] (iii) What bit-size should p, q, and N have in order to make the cost of factorisation on the order of 280 operations? Justify your answer.[3 marks] (d) The naïve RSA-based encryption scheme is usually replaced with one that uses randomised encoding before application of the RSA encryption operation. Explain why.[4 marks] (e) Consider the following RSA-based encryption algorithm for encrypting 256-bit mes-sages m: suppose N has n > 257 bits. We place m as the least significant 256 bits of M, and fill up the next (n-1) - 256 bits of M with a random bit-string R. Thus,M has n - 1 bits and (thinking of M as a bit-string with most significant bits on the left), we have M = R||m. We then interpret M as an integer in the usual way and compute C = M mod N as in naïve RSA. (i) Describe a suitable decryption algorithm for this scheme. (ii) Explain why the most significant bit of M is equal to 0 with probability 1/2.[1 marks] (iii) Suppose C* is a cipher text encrypting some unknown 256-bit message m*.Using a decryption oracle, show how to recover 255 bits of m* with probability 1/2. You are not permitted to query C* itself to the decryption oracle. [4 marks] o(f) Suppose the same RSA key-pair is used for both naïve RSA-based encryption and for creating Full-Domain Hash RSA signatures (in which = H (m) mod N).Suppose further that an attacker has a decryption oracle for the encryption scheme.What impact, if any, does this have on the security of the signature scheme? Justify your answer.[4 marks]