Practice Quiz 3, M203E

Instructions: The quiz is open book (any books) and open notes (any notes or written material).

[1] (a) What is the remainder if you divide 34657863295 by 9? Show your work or explain how you get your answer.
(b) What is the remainder if you divide 3213418 by 5? Show your work or explain how you get your answer.

Solution: (a) Add up the digits and cast out 9's and repeat until you get down to a single digit: 4 is the remainder.
(b) The largest multiple of 5 less than or equal to 3213418 is 3213415, so the remainder is 3.

[2] Decipher the following message, given that it was encrypted using a Caesar cipher (i.e., the letters of the alphabet are just shifted): ju xbt uif cftu pg ujnft, ju xbt uif xpstu pg ujnft.

Solution: We just try various shifts. If we shift back by 1, j becomes i, u becomes t, etc., so we get: it was the best of times, it was the worst of times.

[3] Note that 97 is a prime number.
(a) Find the remainder when you divide 385 = 5*77 by 96.
(b) Compute 45385 mod 97. Explain how you obtain your answer.

Solution: (a) Using long division we get 385 = 4*96 + 1, so the remainder is 1.
(b) If we take e = 5 as the encryption exponent with encryption formula y = x5 mod 97, then d = 77 is the decryption exponent, so we get x = y77 mod 97. I.e., x = y77 = (x5)77 = x5*77 = x385 mod 97. Thus 45385 mod 97 = 45, since what we're really doing here is encrypting 45 and then decrypting it, so we're back where we started.

[4] In the cipher using the formula y = x5 mod 17, the encryption exponent is e = 5. Find the decryption exponent d (thus the decryption formula is x = yd mod 17.) Explain how you get your answer.

Solution: We must solve de = 1 mod p-1, where p = 17 and e = 5. Thus we want to solve 5d - m16 = 1 or 5d = 1+16m. So we try various m's until we get 1+16m to be a multiple of 5. We eventually get m = 4: 1 + 4*16 = 65 = 5d so d = 13.

[5] In the RSA cipher using the formula y = x3 mod 33, the encryption exponent is e = 3. Find the decryption exponent d (thus the decryption formula is x = yd mod 33.) Explain how you get your answer.

Solution: We must solve de = 1 mod (p-1)(q-1), where pq = 33 for primes p and q and where e = 3. Thus p = 3 and q = 11, and (p-1)(q-1) = 20. Thus we want to solve 3d - m20 = 1, and we see d = 7, m = 1 works.

[6] For the encryption formula y = xe mod p where p is a prime, give an example of an appropriate prime p and an appropriate encryption exponent e > 1, if the numbers associated to plaintext characters could be as big as 50.

Solution: You need a prime bigger than 50, so we want p > 50, so we can take p = 53 say. Then we need an exponent e such that gcd(e,52) = 1. Thus we can take any e not divisible by 2 or 13 (since 2*2*13 = 52), say e = 3.

[7] For the encryption formula y = xe mod pq where p and q are different primes, give an example of appropriate primes p and q and an appropriate encryption exponent e > 1, if the numbers associated to plaintext characters could be as big as 50.

Solution: You need a prime bigger than 50, so we want pq > 50, so using p = 5 and q = 11, gives pq=55 > 53. Then we need an exponent e such that gcd(e,(p-1)(q-1)) = 1. But (p-1)(q-1) = 40 = 2*2*2*5, so we can take any e not divisible by 2 or 5, say e = 3.