301 Abstract Algebra 2:00 - 2:50 MWF Hentzel 432 Carver hentzel@iastate.edu Web Page http://www.math.iastate.edu/hentzel/class.301 Text: A First Course in Abstract Algebra, sixth Edition by John B. Fraleigh Course: Chapter 1,2,3,4,5 Wednesday, September 26, 2001 Professor Tondra is looking for a math student to be a representative in the LAS assembly. See me or Tondra for details. Main idea: You could have become world famous with what you have already learned in abstract algebra 301. Key Words: RSA, public key, private key Goal: Given a,b, find x,y such that xa+yb = GCD(a,b). Example: A farmer buys 100 animals for 100 dollars. Cows cost 10, Sheep cost 3 Pigs cost 50 cents. How many animals of each kind did he buy? c + s + p = 100 10c + 3s + 1/2 p = 100 c + s + p = 100 20c + 6s + p = 200 19c + 5 s = 100 3 5 19 15 1 4 5 4 4 1 4 4 0 3 1 4 1 3 4 19 0 1 1 5 4 5 - 1 19 = 1 400 5 - 100 19 = 100 19t 5 - 5t 19 = 0 -------------------- (400+19t)5 + (-100-5t)19 = 100 Let c = -100 - 5t s = 400 + 19t p = -200 - 14t So -100-5t >= 0 t <= -20 400+19t >=0 t >= -21.05 -200-14t>= 0 t <= -14.2 The only values possible for t are -20 and -21 t = -20 c=0 s=20 p=80 t = -21 c= 5 s= 1 p =94 3. Using an 11 cup measure and a 17 cup measure, how would you measure 3 cups? 1 11 17 11 1 6 11 6 1 5 6 5 5 1 5 5 0 1 1 1 5 1 1 2 3 17 0 1 1 2 11 2 17 - 3 11 = 1 6 17 - 9 11 = 3 11t 17 -17t 11 = 0 (6+11 t)17 +(-9-17 t)11 = 3 big = 6+11t small = -9-17t let t = -1 big = -5 and small = 8 Dump 8 small scoops into a bowl and remove 5 big scoops. Theorem: The set of elements of Zn relative prime to n form a group under multiplication. Zn# = {i in Zn | GCD(i,n) = 1}. Proof: We show that Zn# is a group. We will Show that Zn#: (a) is associative, (b) has an identity, and (c) has inverses (a) I could say that the associativity of Zn# follows from the associativity of multiplication for the integers. It does, but it is not that obvious. The problem occurs because we have not really defined what Zn is. Once we do that, (which will be much later on this semester), then the associativity will be obvious. (b) 1 is certainly relatively prime to n and 1 is the multiplicative identity. (c) Given a in Zn#, since GCD(a,n) = 1, there exists integers x and y such that ax+ny = 1. In Zn this says that ax == 1 mod n so x is the multiplicative inverse of a. x has to be relatively prime to n since from the equation ax+ny = 1, any divisor of x and n must divide 1. RSA encryption. Public Key, Private Key encryption for security. One publishes a book with two numbers. n and r next to your name. If someone wishes to send you a message, he encodes it numerically. One could use the numbers of the letters of the alphabet. Or, one could just use the ascii numbering for the characters. For a long data stream of bits, one could break it into chunks of length 8 and send the data as octal numbers. If I wanted to send the information 32 18 19 27 and r = 11 and n = 1457 (printed in the public book) I would compute Mod[32^11,1457] = 559 Mod[18^11,1457] = 338 Mod[19^11,1457] = 1157 Mod[27^11,1457] = 957 The encrypted message is 559 338 1157 957 When the message is received, The message is decoded by using the secret value x = 251 Mod[ 559^251, 1457] = 32 Mod[ 338^251, 1457] = 18 Mod[1157^251, 1457] = 19 Mod[ 957^251, 1457] = 27 Where did the secret decoding value of x = 251 come from and why is it unknown to the general public? How to break the code. --------------------- To decode the message, we factor n = 1457 = 31*47. In the RSA code n will always factor into two primes n = pq. The number of elements relatively prime to n will be (p-1)(q-1) in this case 30*46 = 1380. If a is any element of the group of elements relatively prime to n = 1457, then a^1380 = 1. This is because any element raised to the order of the group is 1. The exponent r is chosen to be any number relatively prime to 1380. Therefore there exists x and y such that x r + y 1380 = 1. If a is any element in Zn relatively prime to n, then a = a^1 = a^(xr+y1380) = (a^r)^x (a^1380)^y = (a^r)^x The encoded message is a^r and the decoding exponent is x. This proof is only good in the case where a is relatively prime to n. But it turns out that it works in the other cases as well. The order of the group is 30*46 = 1380 and 11 is relatively prime to 1380. We now use the continued fraction and the magic table to create element x. 125 11 1380 2 5 11 10 5 1 5 5 0 125 2 5 1 125 251 1380 0 1 2 11 251*11 - 2 1380 = 1 Assignment: 1. Find the smallest distance that can be measured with a (unmarked) meter stick and an (unmarked) yard stick. 1 meter = 39.37 inches. 2. Given n = 11663 and r = 7 encode the message: I A M S I C K 9 1 13 19 9 3 11 3. Break the code and decipher the message. 7133 8088 9475 8088 1577 8147