VE475 Introduction to Cryptography Homework 2 Solved

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) 5. Find all the primes p such that                         mod p is not invertible.
7 3

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 ciyptosystem

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?