CSE 321, Sp '09: Assignment #7, Due: Wednesday, May 27, 2009

In practice, people typically set up RSA cryptosystem keys something like this: pick a random 500 bit odd number p', run a ``primality'' test on the successive numbers p', p'+2, p'+4, ... until a ``prime'' is found; call this p. Repeat to find a second ``prime'' q. Set n=pq, etc.
I said ``prime'' in quotes, because the ``primality'' testing algorithms usually used are probabilistic ones like Miller-Rabin that have some nonzero (albeit very small) probability of erroneously declaring a composite number to be ``prime.'' (If they answer ``composite'', they are certainly right, but if they answer ``prime'' then there's always some small probability of error.)
Suppose this very unlikely error occurs, and p or q or both are actually composite. What happens to the RSA system? For example, is it still possible to find appropriate e and d? Will encryption/decryption always fail? Sometimes fail? Can the Bad Guys & Gals always decrypt your messages? Etc. (If it matters, it's probably fair to assume that the primality algorithm never makes a gross error like declaring p to be prime if p is even, or has other ``small'' factors.)
5.1, #16
5.1, #20
5.1, #46
5.1, #58
5.2, #12
5.2, #42
5.3, #30
5.3, #36
5.4, #10

Always show work to justify your answers. E.g., your answer to 5.1 #16 shouldn't just be one number, but should include supporting calculations.


	Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX