Chapter 8 Number Theory314
cryptosystem efficiently, then they also have the ability to factor numbers that are
products of two primes.
Why should that convince us that it is hard to break the cryptosystem efficiently?
Well, mathematicians have been trying to factor efficiently for centuries, and they
still haven’t figured out how to do it.
What is the Rabin cryptosystem? The public key will be a numberN that is a
product of two very large primesp;qsuch thatpq3 .mod4/. To send the
messagem, send rem.m^2 ; N/.^19
The private key is the factorization ofN, namely, the primesp;q. We need to
show that if the person being sent the message knowsp;q, then they can decode
the message. On the other hand, if an eavesdropper who doesn’t knowp;qlistens
in, then we must show that they are very unlikely to figure out this message.
Say thatsis asquare moduloN if there is anm 2 Œ0;N/such thatsm^2
.modN/. Such anmis asquare root ofsmoduloN.
(a)What are the squares modulo 5? For each square in the intervalŒ0;5/, how
many square roots does it have?
(b)For each integer inŒ1;15/that is relatively prime to 15, how many square roots
(modulo 15) does it have? Note that all the square roots arealsorelatively prime to
- We won’t go through why this is so here, but keep in mind that this is a general
phenomenon!
(c)Suppose thatpis a prime such thatp3 .mod4/. It turns out that squares
modulophave exactly 2 square roots. First show that.pC1/=4is an integer.
Next figure out the two square roots of 1 modulop. Then show that you can find a
“square root mod a primep” of a number by raising the number to the.pC1/=4th
power. That is, givens, to findmsuch thatsm^2 .modp/, you can compute
rem.s.pC1/=4; p/.
(d)The Chinese Remainder Theorem (Problem 8.58) implies that ifp;qare dis-
tinct primes, thensis a square modulopqif and only ifsis a square modulopand
sis a square moduloq. In particular, ifsx^2 .x^0 /^2 .modp/wherex¤x^0 ,
and likewisesy^2 .y^0 /^2 .modq/thenshas exactly four square roots modulo
N, namely,
s.xy/^2 .x^0 y/^2 .xy^0 /^2 .x^0 y^0 /^2 .modpq/:So, if you knowp;q, then using the solution to part (c), you can efficiently find the
square roots ofs! Thus, given the private key, decoding is easy.
(^19) We will see soon, that there are other numbers that would be encrypted by rem.m (^2) ; N/, so we’ll
have to disallow those other numbers as possible messages in order to make it possible to decode this
cryptosystem, but let’s ignore that for now.