Question 1 (10 marks) This question tests your knowledge of what constitutes a group. Let n be a composite number. Let X = {1, 2, . . . , n − 1}. (a) Let x ∈ X. Show that if there are integers a, b such that ax + bn = 1, then gcd(x, n) = 1. (2 marks) (b) Let x ∈ X. Show that if gcd(x, n) 6= 1 then ax ≡ 1 (mod n) has no solution for any integer a. (2 marks) (c) Show that there is at least one element x ∈ X, such that gcd(x, n) 6= 1. (2 marks) (d) Let ∗ be multiplication modulo n. That is, for x, y ∈ X, x ∗ y = xy (mod n). Prove that (X, ∗) is not a group. (2 marks) (e) Let n = 13424. Let a = 13314 and let b = 5889. What are the multiplicative inverses of a and b modulo n? Show how you obtained the result. (2 marks) Question 2 (5 marks) Recall that a Carmichael number n is any composite number which satisfies Fermat’s little theorem, i.e., a n−1 ≡ 1 (mod n), for every a such that gcd(a, n) = 1. Such a number is also called a pseudoprime. Write a PARI/GP script that finds and prints all Carmichael numbers less than or equal to 10,000. (Hint: You may use the isprime() command in PARI/GP). (5 marks) Question 3 (5 marks) The discrete logarithm problem (DLP) is not always hard. In particular, we cannot simply choose any group G with an operation (addition or multiplication; appropriately defined), and assume that DLP is hard in that group. The following questions highlight this. (a) Show that the discrete logarithm problem (DLP) is easy on the group of integers modulo a prime n under addition, i.e., the group (Zn, +). More precisely, given g, h ∈ Zn, find an x such that x · g ≡ h (mod n). (3 marks) (b) Let n = 1, 200, g = 23 and h = 25. Find x such that x · g ≡ h (mod n). (Hint: You may use the gcdext() command in PARI/GP). (2 marks) Question 4 (6 marks) An encryption system is considered malleable if given a ciphertext of some unknown plaintext, it is possible to obtain a valid ciphertext of a related plaintext without even knowing the contents of the plaintext. This is problematic depending on the application. For instance, in bidding for a contract, a company might outbid its competitor by simply multiplying it’s rival company’s encrypted bid by 0.9, without even knowing the bid [DDN03]. The following questions relate to the malleability of versions of RSA and Elgamal cryptosystems taught in the lectures. 3 (a) Given the ciphertext c of an unknown message m encrypted using RSA with public key (e, N), show how can you obtain a valid encryption of 2m under (e, N) without knowing m? (2 marks) (b) Given the following ciphertext c of some message m encrypted using RSA (parameters below), show the steps to obtain the ciphertext c 0 of 2m using PARI/GP. c = 2753530075851447763243109653595159359042630876252568885 N = 3611071334998558413568664531648678147429348805583447333 e = 3521903392012306527486431544128257140903969440488848271 (2 marks) (c) Consider now the randomized Elgamal cryptosystem. We are given the ciphertext (r, c) of some unknown message m computed as r = g k for some random integer k, and c = m × h k , where h is the public key. Can we obtain the ciphertext of the message 2m? (2 marks) Question 5 (4 marks) Let S be a set of size n, and let f be a random one-to-one map from S to itself. Starting with a random element x0 ∈ S, define: xi+1 = f(xi), for i ≥ 0. This creates the sequence x0, x1, x2, x3, . . .. The birthday paradox tells us that if we keep track of these values, we will find a pair such that xi = xj , with i 6= j after O( √ n) evaluations of f. After this the sequence repeats itself, i.e., creates a cycle. Let t be the smallest i for which we can find some j such that the above is true. Then, the sequence x0, x1, . . . , xt−1 forms a “tail” of length t, and for all i ≥ t, we have xi = xi+T , where T is the length of the cycle. In Figure 1, the tail is of length t = 4 and the length of the cycle is T = 11. Furthermore, for all i ≥ t, we see that xi = xi+T . Thus, if xi = xj , then j = i + T. (a) In Pollard’s rho algorithm, we try to find an m such that xm = x2m. Show that if the sequence is cyclic, i.e., xi = xj for some i ≥ t and j 6= i, then there must exist an i, call it m, such that xm = x2m. (2 marks) (b) Why does Pollard’s rho algorithm, which seeks to find an m such that xm = x2m, only require constant space? (2 marks)