Chapter 8 Number Theory226
In this problem we will examine theRabin cryptosystemthat does have such
a security certification. Namely, if someone has the ability to break the Rabin
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? LetNbe a product of two very large primes
p;qsuch thatpq3 .mod4/. To send the messagex, send rem.x^2 ;N/.^8
We need to show that if the person we send the message to 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.
First some definitions. We know what it means for a number to be a square over
the integers, that issis a square if there is another integerxsuch thatsDx^2. Over
the numbers modN, we say thatsis asquare moduloNif there is anxsuch that
sx^2 .modN/. Ifxis such that 0 x < Nandsx^2 .modN/, thenxis
thesquare root ofs.
(a)What are the squares modulo 5? For each nonzero 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 findxsuch thats x^2 .modp/, you can compute
rem.s.pC1/=4;p/.
(d)The Chinese Remainder Theorem (Problem 8.17) 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 .modp/.x^0 /^2 .modp/and
(^8) We will see soon, that there are other numbers that would be encrypted by rem.x (^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.