Need an explanation for the computation and proof

4 Fun with Rabin Encryption Setup. In class, we discussed how the computational hardness of taking square roots modulo a composite number N can be leveraged to obtain a digital signature scheme, namely Rabin's signatures. In fact, square roots modulo a composite are so hard that even telling whether or not a given value is a square (mod N) is unfeasible, assuming the hardness of factoring. This is at the heart of the so-called Rabin Public-Key Bit Encryption scheme, which is described below . RabinKGen(1): 1. Pick random A-bit primes p',q until p - 2p' +1 and21 are also prime 2, N ? pq 3. Output: PubKey-N, PrivKey-(p, q) 4. Message/ciphertext Space: M (N) ? {0,1}, C(N) ? . RabinEnc(PubKey, b) 2. c ?-Ibr2 mod N 3. Output: c RabinDec (PrivKey,c): 1. Compute the Legendre symbol of c modulo p: Lmod p 2. Compute the Legendre symbol of c modulo q: Lq ? cq, mod q 4. If Lp- L1, output 0 5. If Lp - L1, output 1 Questions. a) Using the ridiculously small and insecure public key N -77, carry out the computation to encrypt the bit 1, assuming the random choiceZ7 yieldsr15 b) Carry out the computation to decrypt the value 37 E J7 (Note: the factorization of 77 is c) Show that Rabin encryption is not chosen-ciphertext (CCA) secure 4 Fun with Rabin Encryption Setup. In class, we discussed how the computational hardness of taking square roots modulo a composite number N can be leveraged to obtain a digital signature scheme, namely Rabin's signatures. In fact, square roots modulo a composite are so hard that even telling whether or not a given value is a square (mod N) is unfeasible, assuming the hardness of factoring. This is at the heart of the so-called Rabin Public-Key Bit Encryption scheme, which is described below . RabinKGen(1): 1. Pick random A-bit primes p',q until p - 2p' +1 and21 are also prime 2, N ? pq 3. Output: PubKey-N, PrivKey-(p, q) 4. Message/ciphertext Space: M (N) ? {0,1}, C(N) ? . RabinEnc(PubKey, b) 2. c ?-Ibr2 mod N 3. Output: c RabinDec (PrivKey,c): 1. Compute the Legendre symbol of c modulo p: Lmod p 2. Compute the Legendre symbol of c modulo q: Lq ? cq, mod q 4. If Lp- L1, output 0 5. If Lp - L1, output 1 Questions. a) Using the ridiculously small and insecure public key N -77, carry out the computation to encrypt the bit 1, assuming the random choiceZ7 yieldsr15 b) Carry out the computation to decrypt the value 37 E J7 (Note: the factorization of 77 is c) Show that Rabin encryption is not chosen-ciphertext (CCA) secure