5. For this question, assume Alice and Bob have R SA keys with moduli Ni-piq1 and N2- P2P where each of the pi's and gi's is a prime that is about n bits long. Again, N and N2 are public knowledge, while only Alice knows pi,qi (and only Bob knows p2, q2). (a) Explain how Eve can use the Euclidean algorithm to attack both Alice's and Bob's moduli if they happen to share a prime factor (which we cannot know in advance of the attack). That is, describe a procedure that Eve can perform that will both (1) run relatively quickly, i.e. take only a polynomial in n number of steps and (2) factor both Ni and N2 if they happen to share a prime factor. What will your procedure do if Ni and N2 do not share a prime factor? (b) Assuming that about 1.3n of all n-bit numbers are primes suitable to use for RSA (we will see later where (c) Assume that Alice and Bob pick their primes randomly uniformly from among the set of suitable primes (as (d) Now, as opposed to just Alice and Bob, suppose there are k people setting up RSA moduli Ni, N2,, N this estimate comes from), how many primes are there for Alice and Bob to choose from? in part (b)). subject to the restriction that p, / a, for each i. Estimate the probability (in terms of n) that Ni and N2 will share a prime factor, i.e. that your attack from part (a) will succeed. If n 10 (ie, the primes are between 512 and 1023), use the birthday paradox to estimate how large k must be for there to be a greater than 50% chance that some pair of people's moduli share a prime factor Repeat for n 100 and n 1000. IDo not be overprecise: it's okay to just give the approximate order of magnitude of k.l 5. For this question, assume Alice and Bob have R SA keys with moduli Ni-piq1 and N2- P2P where each of the pi's and gi's is a prime that is about n bits long. Again, N and N2 are public knowledge, while only Alice knows pi,qi (and only Bob knows p2, q2). (a) Explain how Eve can use the Euclidean algorithm to attack both Alice's and Bob's moduli if they happen to share a prime factor (which we cannot know in advance of the attack). That is, describe a procedure that Eve can perform that will both (1) run relatively quickly, i.e. take only a polynomial in n number of steps and (2) factor both Ni and N2 if they happen to share a prime factor. What will your procedure do if Ni and N2 do not share a prime factor? (b) Assuming that about 1.3n of all n-bit numbers are primes suitable to use for RSA (we will see later where (c) Assume that Alice and Bob pick their primes randomly uniformly from among the set of suitable primes (as (d) Now, as opposed to just Alice and Bob, suppose there are k people setting up RSA moduli Ni, N2,, N this estimate comes from), how many primes are there for Alice and Bob to choose from? in part (b)). subject to the restriction that p, / a, for each i. Estimate the probability (in terms of n) that Ni and N2 will share a prime factor, i.e. that your attack from part (a) will succeed. If n 10 (ie, the primes are between 512 and 1023), use the birthday paradox to estimate how large k must be for there to be a greater than 50% chance that some pair of people's moduli share a prime factor Repeat for n 100 and n 1000. IDo not be overprecise: it's okay to just give the approximate order of magnitude of k.l