8.13. References 311
his private key as though it was someone’s public key. That is, from a plain text
m 2 Œ0;n/, Pete would broadcast a “signed” version,sWWDrem.md; n/.
Then anyone can decrypt and read Pete’s broadcast message by using Pete’s
public key as though it were their own private key. Readers of Pete’s message can
be sure the message came from Pete if they believe that the only way to generate
such a message is by using the private key which Pete alone knows. (This belief is
widely accepted, but not certain.)
(a)Explain exactly what calculation must be performed onsto recovermusing
the public key.e;n/.
(b)Explain why the calculation of part (a) yields the plain textm.Problem 8.78.
Ben Bitdiddle decided to encrypt all his data using RSA. Unfortunately, he lost his
private key. He has been looking for it all night, and suddenly a genie emerges
from his lamp. He offers Ben a quantum computer that can perform exactly one
procedure on large numberse;d;n. Which of the following procedures should Ben
choose to recover his data?
Find gcd.e;d/. Find the prime factorization ofn. Determine whethernis prime. Find rem.ed; n/. Find the inverse ofemodulon(the inverse ofeinZn/. Find the inverse ofemodulo .n/.Class Problems
Problem 8.79.
Let’s try out RSA!
(a)Go through thebeforehandsteps.Choose primespandqto be relatively small, say in the range 10-40. In
practice,pandqmight contain hundreds of digits, but small numbers are
easier to handle with pencil and paper.