8.13. References 313
(a)Explain why (8.51) follows very simply from Euler’s theorem whenmisrel-
atively prime ton.
All the rest of this problem is about removing the restriction thatmbe relatively
prime ton. That is, we aim to prove that equation (8.51) holds forallm 2 Œ0::n/.
It is important to realize that, even if it was theoretically necessary, there would
be no practical reason to worry about—or to bother to check for—this relative pri-
mality condition before sending a messagemusing RSA. That’s because the whole
RSA enterprise is predicated on the difficulty of factoring. If anmever came up that
wasn’t relatively prime ton, then we could factornby computing gcd.m;n/. So
believing in the security of RSA implies believing that the probability of a message
mturning up that was not relatively prime tonis negligible.
But let’s be pure, impractical mathematicians and rid of this technically unnec-
essary relative primality side condition, even if it is harmless. One gain for doing
this is that statements about RSA will be simpler without the side condition. More
important, the proof below illustrates a useful general method of proving things
about a numbernby proving them separately for the prime factors ofn.
(b)Prove that ifpis prime anda1 .modp 1/, thenmaDm .Zp/: (8.52)(c)Give an elementary proof^18 that ifab .modpi/for distinct primespi,
thenabmodulo the product of these primes.
(d)Note that (8.51) is a special case of
Claim.Ifnis a product of distinct primes anda1 .mod .n//, then
maDm .Zn/:Use the previous parts to prove the Claim.
Homework Problems
Problem 8.82.
Although RSA has successfully withstood cryptographic attacks for a more than a
quarter century, it is not known that breaking RSA would imply that factoring is
easy.
In this problem we will examine theRabin cryptosystemthat does have such
a security certification. Namely, if someone has the ability to break the Rabin
(^18) There is no need to appeal to the Chinese Remainder Theorem.