Attacks against RSA (2 marks) To save time, Alice and Bob decide to find one good pair of primes p and q, and then publish the same modulus n = py. Alice and Bob then choose different public exponents e and e', and generate the corresponding secret exponents d and d', respectively. Show that in this system, it is possible to decrypt a message m sent to both of them if ged(e, e')1. That is givern CA mmod n -me" m od n An adversary Oscar can compute m without knowing the secret exponent d or d'. Note that Oscar does not know p or q. (Hint: Please study Euclidean Algorithm as it provides some important facts to find the solution. You may find reading material from http://mathworld. wolfram.com/EuclideanAlgorithm.html Note: You can consider how to solve the question by using the following fact: An important consequence of the Euclidean algorithm is finding integers z and y such that ax + by ged(a, b). That is, by given a and b, we can use Euclidean Algorithm to find z and y. Note that you can use this fact directly (explain how to use it), but no need to really find a or y Attacks against RSA (2 marks) To save time, Alice and Bob decide to find one good pair of primes p and q, and then publish the same modulus n = py. Alice and Bob then choose different public exponents e and e', and generate the corresponding secret exponents d and d', respectively. Show that in this system, it is possible to decrypt a message m sent to both of them if ged(e, e')1. That is givern CA mmod n -me" m od n An adversary Oscar can compute m without knowing the secret exponent d or d'. Note that Oscar does not know p or q. (Hint: Please study Euclidean Algorithm as it provides some important facts to find the solution. You may find reading material from http://mathworld. wolfram.com/EuclideanAlgorithm.html Note: You can consider how to solve the question by using the following fact: An important consequence of the Euclidean algorithm is finding integers z and y such that ax + by ged(a, b). That is, by given a and b, we can use Euclidean Algorithm to find z and y. Note that you can use this fact directly (explain how to use it), but no need to really find a or y