Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

image text in transcribed

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Systems For Advanced Applications 18th International Conference Dasfaa 2013 Wuhan China April 22 25 2013 Proceedings Part 2 Lncs 7826

Authors: Weiyi Meng ,Ling Feng ,Stephane Bressan ,Werner Winiwarter ,Wei Song

2013th Edition

3642374492, 978-3642374494

More Books

Students also viewed these Databases questions

Question

8. Demonstrate aspects of assessing group performance

Answered: 1 week ago