1. a. Compute 2^243 mod 455. It is enough to compute 2^243 mod 5 = 2^3 mod 5 = 3 2^243 mod 7 = 2^3 mod 7 = 1 2^243 mod 13 = 2^3 mod 13 = 8 Applying Chinese remaindering, we get 2^243 = 2^3 mod 455 = 8 mod 455. [ 5 marks for getting this right ] b. We have to solve x = 3 mod 11 and x = 5 mod 13. From the first equation, I know that x = 11y + 3 for some integer y. Plugging this into the second equation, 11y + 3 = 5 mod 13, meaning y = 2*11^{-1} mod 13 = 2*(-2)^{-1} mod 13 = 12 mod 13 = 12 + 13z for some integer z. Overall, we have x = 11y + 3 = 11(12 + 13z) + 3 = 135 + 143z for some integer z. Since 900 <= x <= 1000, we have x = 993. [ 5 marks for getting it all right ] 2. I know that \phi(N) divides 3d-1, from the given information. [ 5 marks for getting here ] Now, \phi(N) is not too small, compared to N. Indeed, \phi(N) = (p-1)(q-1) >= p/2 * q/2 since p and q are at least 2. So \phi(N) >= N / 4. [ 5 marks for this observation ] Since d <= N, 3d-1 <= 3N. Thus, the quotient when dividing 3d-1 by \phi(N) is at most 3N / (N/4) <= 3 * 4 = 12. The algorithm, then, is: try dividing 3d-1 by 2,3,...,12. One of these possibilities will land up on \phi(N). [ 5 marks for getting till the end ] A final piece of work: It is easy to check whether a given number is indeed \phi(N). [ This follows from something we did in class, and I leave it as an exercise ] 3. a. Depends on what breaking means. Clearly, if c1 and c2 encrypt the same message m, then c1 = c2. So, given two ciphertexts c1 and c2, it is easy to detect if they encrypt the same message. Other than this glitch, two messages can be safely encrypted. Given two ciphertexts c1 = a*m1 + b mod p and c2 = a*m2 + b mod p for any two possible values of m1 \neq m2, there are values for the secret key (a,b) such that encrypting m1 using (a,b) gives c1, and encrypting m2 using (a,b) gives c2. thus each pair of (m1, m2) such that m1 \neq m2 is equally likely. [ 8 marks for this argument ] On the other hand, given three ciphertexts, we can deduce non-trivial relations between the underlying messages. For example, we can check if m1+m2 = 2^m3 by checking that c1+c2 = 2*c3. b. Given the ciphertexts for two KNOWN messages m1 and m2, I have two equations c1 = a*m1 + b mod p and c2 = a*m2 + b mod p so, two variables (a and b) and two equations. It is easy to solve these using Gaussian elimination and recover the secret key, namely (a,b). [ 7 marks ] 4. a. Given C1 = m^3 mod N1, C2 = m^3 mod N2, and C3 = m^3 mod N3, find by Chinese remaindering, a number C such that C = m^3 (mod N1*N2*N3). [ 8 marks for getting here ] Note that since m < min(N1,N2,N3), m^3 < N1*N2*N3. In other words, C = m^3 (mod N1*N2*N3) = m^3 (over the integers). [ 7 marks for the observation that the equality holds over the integers ] Compute the cube root of C over the integers [ How? Use binary search ], this can be done easily and it reveals the message m. b. Let C = (M1)^e mod N and C2 = (M2)^e mod N. Then C1*C2 = (M1*M2)^e mod N is an encryption of the product of the two messages M1 and M2. [ 15 marks ] 5. a. Indeed, if p is prime, then 2^{p-1} = 1 mod p. To prove the reverse direction, assume that 2^{p-1} = 1 mod p. We know that p - 1 = 2q. So, the order of 2, being a divisor of p-1, is either 1, 2, q or 2q. IT cannot be 1 or 2 [ Why? ] If the order of 2 is 2q, then we know that p is prime. Why? Because the order of any element divides the order of the group which is the size of Z_p* = \phi(p). If the order of 2 is 2q, then we have that 2q = p-1 divides \phi(p). This could only happen when p - 1 = \phi(p), or in other words, when p is prime. [ 5 marks ] The only remaining case is when the order of 2 is q. We want to show that in this case, p is prime as well. Assume, for the sake of contradiction, that p is composite. That is, p = r*s where r and s are non-trivial factors of p (that is, neither of them is 1 or p). Then, since 2^q = 1 mod p, it must be that 2^q = 1 mod r as well. Now, let w be the order of 2 in the group Z_r*. Then, w divides q. [ Why? Reason it out for yourself ] But since q is prime, w is either 1 or q. w cannot be 1. w has to be at most the size of the group Z_r* so w <= r - 1 <= p/3 - 1 < p/3 = (2q+1)/3 < q (since q > 1). [Make sure you understand why each of the steps is true ] So, w cannot be q either. This gives us the desired contradiction, meaning that p cannot be composite. Thus, in the case that the order of 2 mod p is q as well, p is prime! [ 10 marks ] b. If N is Carmichael, then it means that b^{N-1} = 1 mod N for every number b that is relatively prime to N. If N = p^2 * q, it must be that b^{N-1} = 1 mod p^2 as well for every b that is relatively prime to p. Thus, the order of b modulo p^2 divides N-1. [ 5 marks ] Since Z_{p^2}* is cyclic (by the hint), there is a b which has maximal order, namely, \phi(p^2) = p(p-1). For such a b, p(p-1) divides N-1, and thus p divides N-1. BUT, since p divides N, it cannot be the case that p divides N-1. Thus, N cannot be of the form p^2 * q, and still be Carmichael. [ 10 marks ]