MATH 135 S 2016: Assignment 9 Solutions 1. Prove that for any integer n, 441n43 + 374n35 + 285n23 0 (mod 55). Solution: Since 55 = 5 11 and gcd(5, 11) = 1, we may use the Splitting Modulus proposition and work with respect to modulo 5 and modulo 11 respectively. Let n Z. In modulo 5: note that 441 1 (mod 5), 374 (1) (mod 5) and 285 0 (mod 5). If n 0 (mod 5), then of course the expression 441n43 + 374n35 + 285n23 is congruent to 0 modulo 5 by the Properties of Congruence. On the other hand, if n 6 0 (mod 5), and since 5 is a prime, then we may use reduction by Fermat's `ittle Theorem, and get that n43 n410+3 n3 (mod 5) and n35 n48+3 n3 (mod 5). Thus, we get 441n43 + 374n35 + 285n23 (1)n3 + (1)n3 + 0n23 0 (mod 5). In modulo 11: note that 441 1 (mod 11), 374 0 (mod 11) and 285 (1) (mod 11), so we have 441n43 + 374n35 + 285n23 (1)n43 + 0n35 + (1)n23 (mod 11). Again, if n 0 (mod 11), the result is obviously true, so we consider the case when n 6 0 (mod 11). Then, as 11 is a prime, we use F`T again to get, n43 n104+3 n3 (mod 11) and n23 n102+3 n3 (mod 11). This means 441n43 + 374n35 + 285n23 (1)n43 + (1)n23 n3 n3 0 (mod 11). Finally, by using Splitting Modulus again, this time to recombine the modulo back to 55, we have 441n43 + 374n35 + 285n23 0 (mod 55). 2. Suppose you are given p = 7 and q = 11 for an RSA scheme. Given a public key (e, n) = (13, 77), find the corresponding private key. Make sure to justify your steps. Solution: First, we compute (p 1)(q 1) = (7 1)(11 1) = (6)(10) = 60. We need to find and integer 2 d 60 such that 13d 1 (mod 60). We may rewrite this as a linear Diophantine equation 13d + 60y = 1. Using the Extended Euclidean Algorithm (EEA) Table, we get x 1 0 1 1 2 3 5 y 0 1 4 5 9 14 23 r 60 13 8 5 3 2 1 q . . 4 1 1 1 1 Division Algorithm . . 60 = 4(13) + 8 13 = 1(8) + 5 8 = 1(5) + 3 5 = 1(3) + 2 3 = 1(2) + 1 Therefore, 60(5) + 13(23) = 1. In other words, (13)(23) 1 (mod 60). Since, (23) 37 (mod 60), we get d = 37. Hence the corresponding private key is (37, 77). Page 1 3. Professor X and Professor Zoom have both set up their own RSA keys: X's public key is (eX , nX ) = (887, 15833), and Zoom's public key is (eY , nY ) = (977, 13019). Zoom wants to send X the answer to the first exam question of MATH 135, which is M = 3141. What is the ciphertext that Zoom needs to send to X? Show the set up of the calculations and the results. You may use a computer to perform the calculations. Solution: Zoom needs to use X's public key to encrypt her message. He needs to send C M eX (mod nX ), which is C 3141887 (mod 15833). This gives us C = 2054. 4. Suppose you receive the cipher-text C = 47 (note 0 C < 55). Decrypt the message using your private key (27, 55). Show the details of your computation; do not use a calculator or a computer. Solution: We are trying to solve for R C d (mod n), that is, R (47)27 (mod 55), where we require 0 < R < n. Since 55 = 511 and gcd(5, 11) = 1, therefore to find the value of R, we would solve the simultaneous congruences R (47)27 (2)27 27 and R (47) 3 27 (mod 5) (mod 11). Since 5 and 11 are both prime numbers, we start using Fermat's little Theorem (FlT). Since 5 - 2, we get that 24 1 (mod 5). Similarly, 11 - 3 gives us 310 1 (mod 11). Using 27 = (6)(4) + 3 in the first congruence, we get R 24 \u00016 \u0001 \u0001 23 (1) 23 8 3 (mod 5). Similarly, from 27 = 2(10) + 7 , the second congruence becomes R 310 \u00012 \u0001 37 (1)(37 ) (mod 11) Now, notice that 37 = (33 ) (33 ) (3), so R (33 )(33 )(3) (27)(27)(3) (5)(5)(3) (5)(15) (5)(4) 20 9 (mod 11). So, we finally have to solve the simultaneous congruences R3 and R 9 (mod 5) (mod 11). R 9 (mod 11) gives R = 9 + 11s for some integer s. Then, simplifying the other congruence we get s 4 (mod 5). Thus, we may write s = 4 + 5t for some integer t. Consequently, R = 9 + 11(4 + 5t) = 9 + 44 + 55t = 53 + 55t. As a result, R 53 (mod 55). Since we need 0 R < 55, we obtain the decrypted message R = 53. 5. Researchers have analyzed many public RSA keys generated by some cheap routers. Suppose the ith router generates the key (ei , ni ). To their shock, the researchers recently discovered that some of the different ni 's were generated using a common prime factor. Page 2 (a) Let p, q and r be distinct odd primes. Suppose n = pq and m = pr. Given that you know that m and n share a common prime factor, but that you do not know the values of p, q, r, explain how you may obtain the prime factors of m and n without using the method of prime factorization? Solution: Suppose p, q and r are distinct primes where n = pq and m = pr. Since we have the prime factorizations of n and m, so gcd(n, m) = p. To find the GCD, we may simply run the Euclidean algorithm (which is a much faster process than prime factorization) to figure out what p is, and then we can easily obtain q and r by dividing n and m by p respectively. (b) The numbers 41685823 and 39034579 share a common prime factor. Use your method described in part (a) to factor n = 41685823 and m = 39034579. Make sure to show all your steps. Solution: Given n = 41685823 and m = 39034579, we simply run the Euclidean Algorithm to get 41685823 = (1)(39034579) + 2651244 39034579 = (14)(2651244) + 1917163 2651244 = (1)(1917163) + 734081 1917163 = (2)(734081) + 449001 734081 = (1)(449001) + 285080 449001 = (1)(285080) + 163921 285080 = (1)(163921) + 121159 163921 = (1)(121159) + 42762 121159 = (2)(42762) + 35635 42763 = (1)(35635) + 7127 35635 = (5)(7127) + 0. Hence gcd(n, m) = 7127, that is, p = 7127. Using long division, we may then find 41685823 = (7127)(5849) and 39034579 = (7127)(5477). Therefore q = 5849 and r = 5477. 6. Sam and Tim have set up their RSA keys (eS , n), (eT , n), respectively, where the n-value is the same. Furthermore, it happens that gcd(eS , eT ) = 1. Suppose that their friend Rob wants to send both Sam and Tim a message M that is coprime with n. Rob encrypts M using Sam and Tim's public keys, producing the ciphertexts CS and CT respectively. Prove that anyone who eavesdrops and obtains the values of both CS and CT can determine the message M using the public keys of Sam and Tim, without knowing their private keys or factoring n. Solution: From the RSA algorithm, CS M eS (mod n) and CT M eT (mod n). Since gcd(eS , eT ) = 1, by EEA, there exist integers x, y such that eS x + eT y = 1. Now one of x, y is positive and the other is negative. Without loss of generality, assume that y is negative. Then eS x = 1 eT y (where eT y is now positive). Then M eS x M 1eT y (mod n) or M eS x M M eT y (mod n). Then CSx M CTy (mod n). the values of CSx and CTy , so is coprime with n, and CTy We can calculate this is simply a linear congruence with M as our variable. Since M M eT y (mod n), then CTy is also coprime with n, so an integer solution exists. We can then obtain M from solving this congruence. Page 3 7. Let p and q be distinct odd primes. Define n = pq. The security of RSA relies on the fact that, given the value of n, it is difficult to find the factors p and q. However, if the value of = (p 1)(q 1) is also known, here we will see that the values of p and q may be obtained without factoring n. (a) Show that p+q =n+1 and pq = p (p + q)2 4n. Solution: Given n = pq and = (p 1)(q 1), and assuming p q, we have n + 1 = (pq) (p 1)(q 1) + 1 = pq pq + p + q 1 + 1 = p + q. and p p (p + q)2 4n = p2 + 2pq + q 2 4(pq) p p = p2 2pq + q 2 = (p q)2 = (p q). (b) Use your answer from part (a) to express the primes p and q in terms of n and . p Solution: We have p + q = n (n) + 1 and p q = (p + q)2 4n. Adding these, we get p 2p = (n (n) + 1) + (p + q)2 4n \u0012 \u0013 q 1 2 = p = (n (n) + 1) + ((n (n) + 1)) 4n . 2 Taking the difference of the two equations, we get p 2q = (n (n) + 1) (p + q)2 4n \u0012 \u0013 q 1 2 = q = (n (n) + 1) ((n (n) + 1)) 4n . 2 Page 4 MATH 135 Winter 2017: Assignment 9 Due at 8:25 a.m. on Wednesday, March 22, 2017 It is important that you read the assignment submission instructions and suggestions available on LEARN. 1. Shade the region of the complex plane defined by {2z 1 C : |z 3| 2}. Justify your answer. March 20 at 1pm: Written in a more standard way, the set above is {2z 1 : z C and |z 3| 2}. 2. Let z1 , z2 C and r R. Prove the following identity. |z1 |2 [(1 r) |z1 z2 |] + |z2 |2 (r |z1 z2 |) = |z1 z2 |(|(1 r)z1 + rz2 |2 + r (1 r) |z1 z2 |2 ). (When 0 r 1, this is Stewart's Theorem which you may have seen in the first or second lecture!) 3. Suppose n N and z C with |z| = 1 and z 2n 6= 1. Prove that zn 1+z 2n R. 4. Prove there exists m R such that the equation 2z 2 (3 3i)z (m 9i) = 0 has a real root. 5. Let z = 1 2 i 12 . Express z 26 in standard form. Show your work. 6. Use De Moivre's Theorem (DMT) to prove cos(5) = 16 cos5 20 cos3 + 5 cos for all R. You may look up and apply the Binomial Theorem to simplify an expression of the form (x + y)5 where x and y are complex numbers. \u0001 7. Let z be a nonzero complex number satisfying z +z 1 = 2 cos 15 . Determine the value of z 45 +z 45 . Give an exact answer. Show your work