5. Here is an example of a public key system that was proposed at a cryptography conference. It is supposed to be faster and more efficient than RSA. Alice chooses two large primes p and q and she publishes N pq. It is assumed that N is hard to factor Alice also chooses three random numbers g,r1, and r2 modulo N and computes 81-gr1 (p-1) (mod N), and 82 := gr2(q-1) (mod N). Her public key is the triple (N, 81, 82) and her private key is the pair of primes (p,q). Now Bob wants to send the message m to Alice, where m is a number modulo N. He chooses two random integers s1 and s2 modulo N and computes c1 : 111811 ( mod N ) and c2:= mg ( mod N) Bob sends the ciphertext (c1, c2) to Alice. Decryption is extremely fast and easy. Alice use the Chinese remainder theorem to solve the pair of congruences CI ( mod p) and C2 (mod q) (a) Show that Alices solution x is equal to Bobs plaintext m (b) Explain why this cryptosystem is not secure Show your work Note: The statement of this problem is long, but it is not difficult. 5. Here is an example of a public key system that was proposed at a cryptography conference. It is supposed to be faster and more efficient than RSA. Alice chooses two large primes p and q and she publishes N pq. It is assumed that N is hard to factor Alice also chooses three random numbers g,r1, and r2 modulo N and computes 81-gr1 (p-1) (mod N), and 82 := gr2(q-1) (mod N). Her public key is the triple (N, 81, 82) and her private key is the pair of primes (p,q). Now Bob wants to send the message m to Alice, where m is a number modulo N. He chooses two random integers s1 and s2 modulo N and computes c1 : 111811 ( mod N ) and c2:= mg ( mod N) Bob sends the ciphertext (c1, c2) to Alice. Decryption is extremely fast and easy. Alice use the Chinese remainder theorem to solve the pair of congruences CI ( mod p) and C2 (mod q) (a) Show that Alices solution x is equal to Bobs plaintext m (b) Explain why this cryptosystem is not secure Show your work Note: The statement of this problem is long, but it is not difficult