8.9. What has SAT got to do with it? 227
sy^2 .modp/.y^0 /^2 .modp/thenshas exactly four square roots, namely,
s.xy/^2 .x^0 y/^2 .xy^0 /^2 .x^0 y^0 /^2 .modpq/:So, if you knowp;q, using the solution to the previous problem part, you can
efficiently find the square roots ofs! Thus, given the secret key, decoding is easy.
But what if you don’t knowp;q?SupposeNWWDpq, wherep;qare two primes
equivalent to3 .mod4/. Let’s assume that the evil message interceptor claims
to have a program that can find all four square roots of any number moduloN.
Show that he can actually use this program to efficiently find the factorization of
N. Thus, unless this evil message interceptor is extremely smart and has figured
out something that the rest of the scientific community has been working on for
years, it is very unlikely that this efficient square root program exists!
Hint:Pickrarbitrarily fromŒ1;N/. Ifgcd.N;r/ > 1, then you are done (why?)
so you can halt. Otherwise, use the program to find all four square roots ofr, call
themr; r;r^0 ; r^0. Note thatr^2 r^02 .modN/. How can you use these roots to
factorN?
(e)If the evil message interceptor knows that the message is the encoding one of
two possible candidate messages (that is, either “meet at dome at dusk” or “meet at
dome at dawn”) and is just trying to figure out which of the two, then can he break
this cryptosystem?
Problem 8.25.
You’ve seen how the RSA encryption scheme works, but why is it hard to break? In
this problem, you will see that finding secret keys is as hard as finding the prime fac-
torizations of integers. Since there is a general consensus in the crypto community
(enough to persuade many large financial institutions, for example) that factoring
numbers with a few hundred digits requires astronomical computing resources, we
can therefore be sure it will take the same kind of overwhelming effort to find RSA
secret keys of a few hundred digits. This means we can be confident the private
RSA keys are not somehow revealed by the public keys^9
For this problem, assume thatnDpqwherep;qare bothoddprimes and that
eis the public key anddthe secret key of the RSA protocol.. LetxWWDed 1.
(a)Show that .n/dividesx.(^9) This is a very weak kind of “security” property, because it doesn’t even rule out the possibility
of deciphering RSA encoded messages by some method that did not require knowing the secret key.
Nevertheless, over twenty years experience supports the security of RSA in practice.