Description
Ex. 1 — Simple questions
1. Find the inverse of 17 modulo 101
2. Find all the solutions to 12x ≡ 28 mod 236.
3. Given a plaintext m modulo 31, its corresponding ciphertext is c = m7 mod 31. Explain how to
decrypt the message.
4. Factor 4883 and 4369 into a product of primes.
5. Find all the primes p such that
3 5
7 3
mod p is not invertible.
6. Let p be a prime and a and b be two integers such that ab ≡ 0 mod p. Show that either a or b
is congruent to 0 mod p.
7. Compute 22017 modulo 5, 13, and 31. What is 22017 mod 2015?
Ex. 2 — Rabin cryptosystem
1. Research and explain how the Rabin cryptosystem works.
2. To implement decryption for the Rabin cryptosystem on decides to build a machine that does the
following. When the device is given a number x, it computes the square root of x mod n. Since
there usually are more than one, it chooses one at random. If one get a meaningful message he
assumes this is the correct result and otherwise input x again.
a) Explain why a meaningful message can be expected fairly soon
b) If Eve intercepts x, can she easily determine the original message?
c) Eve has stolen the device and plans to run some attacks on it. What type of attack should
she run to recover the factorization of n. Explain the process.
Note: the computation of square roots mod n will be covered later, so there is no need to detail this
part.
Ex. 3 — CRT
A group prepares for a parade. If they arrange in rows of three, one person is left over. If they line up
four to a row, two are left over and if they try rows of five, three are left over. What are the two smallest
possible number of people in the group?
