Mathematics for Computer Science

8.9. What has SAT got to do with it? 225

5 = All your base are belong to us.

6 = Someone onourteam thinks someone onyourteam is kinda cute.

7 = Youarethe weakest link. Goodbye.

(c)Decrypt the message sent to you and verify that you received what the other
team sent!

Problem 8.23.
A critical fact about RSA is, of course, that decrypting an encrypted message al-
ways gives back the original message! That is, that rem..md/e;pq/Dm. This
will follow from something slightly more general:

Lemma 8.9.1.Letnbe a product of distinct primes anda1 .mod.n//for
some nonnegative integer,a. Then

mam .modn/: (8.19)

(a)Explain why Lemma 8.9.1 implies thatkandk^5 have the same last digit. For
example:
25 D 32 795 D 3077056399

Hint:What is.10/?

(b)Explain why Lemma 8.9.1 implies that the original message,m, equals rem..me/d;pq/.

(c)Prove that ifpis prime, then

mam .modp/ (8.20)

for all nonnegative integersa1 .modp1/.

(d)Prove that ifab .modpi/for distinct primesp 1 ;p 2 ;:::;pn, thenab
.modp 1 p 1


pn/.

(e)Combine the previous parts to complete the proof of Lemma 8.9.1.

Problem 8.24.
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.