Homework #4 Solutions --------------------- Book Problems: 4.3) 13x = 4 (mod 99) 15x = 56 (mod 101) Use the extended Euclidean algorithm to solve for 13^(-1) (mod 99) and 15^(-1) (mod 101): 99 = 7*13 + 8 -> 99 - 7*13 = 8 13 = 1*8 + 5 -> 13 - 8 = 5 8 = 1*5 + 3 -> 8 - 5 = 3 5 = 1*3 + 2 -> 5 - 3 = 2 3 = 1*2 + 1 -> 3 - 2 = 1 2 = 2*1 3 - (5 - 3) = 1 2*3 - 5 = 2*(8 - 5) - 5 = 1 2*8 - 3*5 = 2*8 - 3*(13 - 8) = 1 5*8 - 3*13 = 5*(99 - 7*13) - 3*13 5*99 - 38*13 = 1 so (-38)*13 = 1 mod 99 and 13^(-1) (mod 99) = 61. 13*61 = 1 (mod 99) 13*(61*4) = 4 (mod 99) 13*(244) = 4 (mod 99) 13*46 = 4 (mod 99) So the first equation can be equivalent to x = 46 (mod 99). Now, let's deal with the second equation: 101 = 6*15 + 11 -> 101 - 6*15 = 11 15 = 1*11 + 4 -> 15 - 11 = 4 11 = 2*4 + 3 -> 11 - 2*4 = 3 4 = 1*3 + 1 -> 4 - 1*3 = 1 3 = 3*1 4 - 1*3 = 4 - (11 - 2*4) = 1 3*4 - 11 = 3*(15 - 11) - 11 = 1 3*15 - 4*11 = 3*15 - 4*(101 - 6*15) = 1 27*15 - 4*101 = 1 27*15 = 1 (mod 101). 15*(27*56) = 56 (mod 101) 15*1512 = 56 (mod 101) 15*98 = 56 (mod 101) Thus, the second equation is equivalent to x = 98 (mod 101). So, we must solve the following system using the CRT: x = 46 (mod 99) x = 98 (mod 101) Let m(1) = 99, m(2) = 101. Then, we have M(1) = 101 and M(2) = 99. y(1) = 50, since 101*50 = 1 mod 99. y(2) = 50, since 99*50 = 1 mod 101. Solution is 46*101*50 + 98*99*50 (mod 9999). This is equivalent to 7471 (mod 9999). Plugging back into the original equation proves that this is indeed the solution to the system. 4.4) (a) The order of the set Z(97) is 97-1= 96 since 97 is prime. 96 = 2^5*3. We also know that the order of each element in Z(97) is a divisor of 96 from Lagrange's Theorem(pg.122). Thus, since the only prime factors of 96 are 2 and 3, it follows that the order of all elements in Z(97) is a product of 2s and 3s. Let a be an arbitrary non-primitive element of Z(97). Let the order of a be n, where n=2^i*3^j, where 0 <= i <= 5 and 0 <=j <= 1. (n != 96.) Thus we have the following: a^n = 1 (mod 97) We know that n < 96. Thus, either i < 5 or j < 1. In the first case, if i < 5, then we know that the prime factorization of n contains at most 4 2s and 1 3. But this is the prime factorization of 48. Thus, we can deduce that n | 48, since n contains only prime factors of 48, and does not contain more "copies" of any prime factor than 48 does. Since we know that n | 48, let n*m = 48, where m is an integer. Using the info above we get: a^n = 1 (mod 97) (a^n)^m = 1^m (mod 97) a^mn = 1 (mod 97) a^48 = 1 (mod 97). Our other possibility is that j=0. In this case, n=2^i where i <= 5. Clearly, using the same reasoning as above, n | 32. Let n*m = 32 in this case and we have: a^n = 1 (mod 97) (a^n)^m = 1^m (mod 97) a^mn = 1 (mod 97) a^32 = 1 (mod 97). So what we have shown is that if a is NOT a primitive element in Z(97), then either a^32 = 1 (mod 97) or a^48 = 1 (mod 97). This shows that if neither is true, then a must be primitive. (Note: if a is primitive, by defn. both of the above statements are false.) (b) 2^32 = 35 (mod 97) 2^48 = 1 (mod 97), so 2 isn't primitive. 3^32 = 35 (mod 97) 3^48 = 1 (mod 97) 4 can't be primitive if 2 is not. 5^32 = 35 (mod 97) 5^48 = -1 (mod 97) Thus, 5 is the smallest primitive root (mod 97). (c) This is the general form of the specific question in part a. Assume that a is a non-primitive element (mod p), where p-1 has the distinct prime factors p(1), p(2), ... p(n). Let the order of a be m, where m < p-1. Since this is the case, there exists at least one prime factor of p-1, say p(i), 1<=i<=n, such that p-1 contains more "copies" of that prime factor p(i) than m does. This would infer that m | ((p-1)/p(i)). (The right hand side of this equation is simply taking one copy of p(i) out of the prime factorization of p-1. Since we know that m doesn't have this many copies of p(i), and that m | (p-1), we can deduce that m | ((p-1)/p(i)). Now, let m*r = ((p-1)/p(i)). We have: a^m = 1 (mod p) (a^m)^r = 1^r (mod p) a^mr = 1 (mod p) a^((p-1)/p(i)) = 1 (mod p). This proves that if a isn't primitive, then one of the n given equations will be satisfied. 4.6) Write a simple program to try small prime factors to factorize n for both RSA systems: 18923 = 127*149, phi(18923) = 126*148 = 18648 31313 = 173*181, phi(31313) = 172*180 = 30960 In the first case, b=1261. Using a program to run the extended Euclidean algorithm, we find a=5797. In the second case, b=4913. Using the program again, we find that a=6497. Now, we are ready to decrypt. (Note that turning a string of 3 characters into a letter is fairly easy. Let P be the decrypted plaintext number. Here is one way to parse out the character values: c[1] = P/676; c[2]=(P/26)%26; c[3]=P%26;) Here is the first plaintext: I BECAME INVOLVED IN AN ARGUMENT ABOUT MODERN PAINTING A SUBJECT UPON WHICH I AM SPECTACULARLY ILL INFORMED HOWEVER MANY OF MY FRIENDS CAN BE COME HEATED AND EVEN VIOLENT ON THE SUBJECT AND I ENJOY THEIR WRANGLES IN A MODEST WAY I AM AN ARTIST MYSELF AND I HAVE SOME SYMPATHY WITH THE ABSTRACTIVEISTS ALTHOUGH I HAVE GONE BEYOND THEM IN MY OWN APPROACH TO ART I AM A LUMPIST TWO OR THREE DECADES AGO IT WAS QUITE FASHIONABLE TO BE A CUBIST AND TO DRAW EVERYTHING IN CUBES THEN THERE WAS A REVOLT BY THE VORTICISTS WHO DREW EVERYTHING IN WHIRLS WE NOW HAVE THE ABSTRACTIONISTS WHO PAINT EVERYTHING IN A VERY ABSTRACTED MANNER BUT MY OWN SMALL WORKS DONE ON MY TELEPHONE PAD ARE COMPOSED OF CAREFULLY SHADED STRANGELY SHAPED LUMPS WITH TRACES OF CUBISM VORTICISM AND ABSTRACTIONISM IN THEM FOR THOSE WHO POSSESS THE SEEING EYE AS A LUMPIST I STAND ALONE Here is the second plaintext: LAKE WOBEGON IS MOSTLY POOR SANDY SOIL AND EVERY SPRING THE EARTH HEAVES UP A NEW CROP OF ROCKS PILES OF ROCKS TEN FEET HIGH IN THE CORNERS OF FIELDS PICKED BY GENERATIONS OF US MONUMENTS TO OUR INDUSTRY OUR ANCESTORS CHOSE THE PLACE TIRED FROM THEIR LONG JOURNEY SAD FOR HAVIeB VEFT THE MOTHER LAND BEHIND AND THIS PLACE REMINDED THEM OF THERE SO THEY SETTLED HERE FORGETTING THAT THEY HAD LEFT THERE BECAUSE THE LAND WASNT SO GOOD SO THE NEW LIFE TURNED OUT TO BE A LOT LIKE THE OLD EXCEPT THE WINTERS ARE WORSE 4.7) RSA is used in a monoalphabetic technique in this example. What's worse about this use compared to the standard substitution cipher is that we know the formula used to encrypt a letter. Thus, we can encrypt all 26 letters and make a lookup table that can be used to decrypt any message. e(a) = 0^25 (mod 18721) = 0 e(b) = 1^25 (mod 18721) = 1 e(c) = 2^25 (mod 18721) = 6400, etc. Here is the lookup table: Let Val Let Val Let Val Let Val Let Val --- ----- --- ----- --- ----- --- ----- --- ----- A 0 B 1 C 6400 D 18718 E 17173 F 1759 G 18242 H 12359 I 14930 J 9 K 6279 L 2608 M 4644 N 4845 O 1375 P 13444 Q 16 R 13663 S 1437 T 2940 U 10334 V 365 W 10789 X 8945 Y 11373 Z 5116 So, the decryption of (365, 0, 4845, 14930, 2608, 2608, 0) is VANILLA. 4.8) (a)We must compute the following: y1^c1*[(y2^c2)^(-1)] mod n. y1^c1*[(y2^c2)^(-1)] = [x^(b1*c1)]*[ (x^(b2*c2))^(-1) ] (mod n) = x*[x^(b1*c1 - 1)]*[ (x^(c1*b1-1))^(-1) ] (mod n) = x (mod n), because the two terms in brackets are inverses of each other mod n. This shows that the algorithm does indeed recover the plaintext x. (b)n = 18721, b1 = 43, b2 = 7717, y1 = 12677 and y2 = 14702. (Note: Each of the inverses in this problem were computed by the function written for the first homework assignment.) So, this means that M^43 = 12677 (mod 18721) and M^7717 = 14702 (mod 18721). Step 1: Compute 43^(-1) mod 7717. 43^(-1) = 2692 (mod 7717). So, c1 = 43^(-1) mod 7717 = 2692. Step 2: c2 = (2692*43 - 1)/7717 = 15 Step 3: Compute x = y1^c1*(y2^c2)^(-1) mod n. y1^c1 = 12677^2692 = 13145 mod 18721 y2^c2 = 14702^15 = 3947 mod 18721 (3947)^(-1) = 5668 (mod 18721). x = 13145*5668 = 15001, the original plaintext. (This translates to "WEZ" if you use the convention in problem 4.6.) Extra Problems: 1) Consider all of the values in the set {1, 2, ... mn-1}. We must count the number of these values that are relatively prime to both m and n. Lay out the numbers in a grid as follows: 1 2 3 ... m m+1 m+2 m+3 ...2m . . m(n-1)+1... mn There are phi(m) values on the top row that are relatively prime to m. Consider the phi(m) rows that these columns define. We must count how many of the values in each of these columns is also relatively prime to n. (This is because each value in the column is relatively prime to m. If a is relatively prime to m, then so is a+im for any integer i. This proof was shown in class.) For now, let's consider a single column, with the minimum element a, 1 <= a < m. This column contains the n values a, a+m, a+2m, ... a+(n-1)m. Let's try to count how many of these values are relatively prime to n. I claim that these values are equivalent to 0, 1, 2, ..., n-1 (mod n). There are exactly n values. In order to prove this claim, we must show that no two values on the list are equivalent (mod n). We will prove this assertion through contradiction. Assume that two values on the list, a+im and a+jm, where i!=j and 0<=i,j= 1, thus it holds for all integers m. 3) Let M be a message such that gcd(M,n) > 1. Then we know that either p | M or q | M. Wlog, let p | M. Then M = pk, where k is an integer. Let us assume that gcd(k,n)=1. If this is not the case, then we could have q | k or p | k. If the first is the case, then n | M and the claim is trivially true since M = 0 mod n. If the second is true, we could simply express M = (p^r)*k, where r is the highest power of p that divides evenly into M. Now, imagine performing RSA encryption, followed by on M. We have the following: M^(ed) = (pk)^(ed) (mod n). = (p^ed)*(k^ed) (mod n) = (p^ed)*k (mod n), since gcd(k,n)=1 Now, let's consider reducing (p^ed) (mod n). We know by the Chinese Remainder Theorem that an unique system of equations x = (p^ed) mod p and x = (p^ed) mod q have the solution (p^ed) (mod n). These two equations simplify to the following: x = 0 mod p and x = p^(s(p-1)(q-1)+1) mod q, for some integer s. (This is because ed = 1 mod phi(n).) x = p*(p^s(q-1))^(p-1) mod q = p*1^(p-1) mod q, because phi(q) = q-1. = p mod q. Now, let's solve our two equivalent equations using the CRT: x = 0 mod p x = p mod q Solution is x = p mod n. (To verify, simply plug x back into both equations. They will be satisfied.) Now, go back to where we started: M^(ed) = (pk)^(ed) (mod n). = (p^ed)*(k^ed) (mod n) = (p^ed)*k (mod n), since gcd(k,n)=1 = pk (mod n), using the result we just derived = M (mod n) as desired. A similar analysis will yield the same result when M=(p^r)*k, where r > 1 and gcd(k,n)=1. 4) Let X = gcd(p-1,i). In order to show that b has the order (p-1)/X, we must show two things: (1) b^((p-1)/X) = 1 (mod p) (2) No integer k < (p-1)/X satisfies the equation b^k = 1 (mod p). Let's start by showing (1): b^X = (a^i)^((p-1)/X) (mod p) = a^(i(p-1)/X) (mod p) Clearly, by defn of gcd, X | i. Let i = Xc for some integer c. b^X = a^(Xc(p-1)/X) (mod p) = a^(c(p-1)) (mod p) = 1 (mod p), by Fermat's Theorem. Now, we must show (2). Assume that there exists a 0 < k < (p-1)/X such that b^k = 1 (mod p). Then we have the following: b^k = (a^i)^k = 1 (mod p) a^(ik) = 1 (mod p) Since a is primitive, we know that (p-1) | ik. Let (p-1) = Xd, for some integer d. Remember that i = Xc, and since X=gcd(p-1,i), gcd(c,d)=1. ik = (p-1)e, for some constant e. Xck = Xde ck = de k = de/c. Since gcd(c,d)=1, it follows that c | e. Furthermore, it follows that d | k, since k = d(e/c), where e/c is an int. d = (p-1)/X. But, remember that k is a multiple of d. This contradicts the fact that k < (p-1)/X. Thus, it must be the case that no such k exists. From proving (1) and (2), we have deduced that the order of b must be (p-1)/gcd(p-1,i).