8.13. References 315
But what if you don’t knowp;q?
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 ofN. 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.83.
You’ve seen how the RSA encryption scheme works, but why is it hard to break?
In this problem, you will see that finding private keys is as hard as finding the
prime factorizations 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 private keys of a few hundred digits. This means we can be
confident the private RSA keys are not somehow revealed by the public keys^20.
For this problem, assume thatnDpqwherep;qare bothoddprimes and that
eis the public key anddthe private key of the RSA protocol.. LetcWWDed 1.
(a)Show that .n/dividesc.(b)Conclude that 4 dividesc.(c)Show that if gcd.r;n/D 1 , thenrc1 .modn/:
Asquare rootofmmodulonis an integers 2 Œ0:n/such thats^2 m .modn/.
Here is a nice fact to know: whennis a product of two odd primes, then every
numbermsuch that gcd.m;n/D 1 has 4 square roots modulon.
(^20) 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 private key.
Nevertheless, over twenty years experience supports the security of RSA in practice.