Introduction To Algebraic Structures
Introduction To Algebraic Structures MAT 421
Popular in Course
Popular in Mat Mathematics
This 5 page Class Notes was uploaded by Florian Watsica on Thursday October 15, 2015. The Class Notes belongs to MAT 421 at Murray State University taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/223604/mat-421-murray-state-university in Mat Mathematics at Murray State University.
Reviews for Introduction To Algebraic Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/15/15
Cryptography and the cyclic group Z Rob Donnelly Notes from the MSU course MAT 421 Intro to Algebraic Structures Fall 2002 By now I think we have a fairly good understanding of the modular arithmetic groups77 Zn Here are some things we know 0 Each Z is a cyclic group under addition I ll use 6 to denote a typical element of Zn this is the set of all integers equivalent to the integer a modulo n The two equations a E 1 mod n and a E in Z mean the same thing 0 Each Zn has a multiplication operation thus making it a ring 0 De ne Z to be the set of all elements in Z which are invertible under multiplication ie all 6 for which there is an element 3 in Z such that 63 T It is not hard to prove that Z is a group under multiplication c When n p is prime then Z consists of all non zero elements of Zp In particular Z is a multiplicative group of order p 7 1 and Z1 is a eld Most of this handout is aimed at understanding and applying the following theorem Theorem Letp be a prime Then Z is a cyclic group of orderp 7 1 Guided Discovery Proof Instead of offering an explicit proof I ll give you a guided discovery77 proof in which you ll be asked to ll in details at each step 1 Let F be any eld and let x akxk ak1xk 1 alx a0 be a polynomial with coef cients a taken from F Suppose that x has degree k so ak 7 0 Prove that x has at most k distinct roots in F HINT Use induction on k and the fact that if c 0 then x 7 c is a factor of to Now let m be a positive integer and consider the polynomial x x 7 l where we think of the coefficients of f as elements of Zp Prove that x has at most m distinct roots from ZX 7 03 Now use exercise 46 from 23 p 128 of F raleigh s Abstract Algebra 6th ed to conclude that Z is cyclic AN IMPORTANT NOTE It should be noted that this proof is non constructive since it does not produce a generator for the group Z but only proves the existence of such a generator However there are fairly fast algorithms for nding generators for Z Before proceeding it might be worthwhile to try a couple of computational problems Exercise Find a generator for Z Exercise For the prime p 6133 the number I 2507 generates Zglgg What is 2507855 in Z6133 Application 1 Di e Hellmdn key exchange So here s a problem suppose Ann and Bob wish to communicate a secret message over an insecure line They must assume that everything that they say can be overheard by the enemy Even with the enemy listening in7 is it possible for them to 1 agree on an encryption method and then 2 exchange encoded messages which only the two of them can decode One approach is for Ann and Bob to exchange a key which they can then use to encode and decode messages This key might be a number which would specify a particular code to be used So how can they exchange this key with the enemy listening in The Di ie Hellman answer is to perform certain computations in the group ZS H Ann and Bob publicly agree on a large prime p and a generator 3 for ZS to Ann privately picks an integer in between 0 and p 7 1 inclusive which she keeps to herself Bob picks an integer it between 0 and p 7 1 inclusive which he keeps to himself 3 quot 03 Ann sends Bob the integer and Bob sends Ann hm They must assume the enemy can 7 intercept this information q Ann computes Bob computes Then hm is the key Exercise For the prime p 79197 the number I 1003 generates 219 lf Ann chooses m 20 and Bob chooses n 327 what is the Di ie Hellman key Where is the security in this key exchange The enemy knows the numbers E hm and U Clearly if enemy elements could solve these equations for m and n7 then they would be able to determine the key Here s a little more perspective on these two equations we have an isomorphism of groups 1 2111 a Z given by ME b7 Here7 2171 is a group under addition and Z is a group under multiplication The reader should con rm that this exponential function is indeed an isomorphism Since this exponential func tion77 is a bijection7 we can refer to its inverse as a discrete logarithm77 The inverse 171 is normally denoted mlogb That is7 U h ltgt mlong m ltgt mlogbi n The difficulty is that the function 1 is known to be a one way77 function That is7 it is easy to compute in the forward direction7 but is difficult to compute in the inverse direction This is not uncommon the squaring function x gt gt 2 is easier to calculate than its inverse z gt gt How difficult is it to calculate discrete logarithms Of course7 the difficulty is dependent on the size of the prime number p The best algorithm right now requires 5V1DP1nh1z7 steps to compute mlogby Exercise How long would it take to compute the discrete logarithm if we used a prime p with 100000 digits and we used a computer which could compute 100000000 mips One mip is one million instructions per second Assume each step in the algorithm for computing discrete logarithms corresponds to one computer instruction It is not known if it is possible to nd a faster algorithm although it is widely believed that the problem of computing discrete logarithms is intractable A HISTORICAL NOTE The Di ie Hellman public key encryption scheme was invented in the mid 1970 s Di ie was a subversive 60 s radical and along with Al Gore was an early user and proponent of the internet He envisioned privacy of information exchange free from the prying eyes of government ANOTHER APPLICATION OF ONE WAY FUNCTIONS Let me describe one other possible use of oneway functions ie functions that are easy to compute in the forward direction but dif cult to compute in the inverse direction Suppose you have a computer network with access limited to members only Each member has a personal password which they enter in order to log in It would not be wise for the network manager to store the passwords in a le because if a hacker found the password le he would be able to have access to the network and to individual accounts Instead the network manager only keeps a le of encoded passwords which can be made publicly available So how should passwords be encoded At log in the computer can take the password and then apply a oneway function to encode the password If the encoded version of the password appears in the list of encoded passwords the user is allowed in Now even if a hacker knows the encoded passwords the oneway function prevents him from guring out the original passwords and hence keeps him out Application 2 The RSA encryption scheme Suppose you are an internet vendor and you want to have a secure way for customers to exchange nancial information with you You could use a secure public key exchange method but such key exchanges do involve some risk So here s the idea rather than sending out keys you will send out padlocks You freely distribute padlocks to anyone including potential enemies because there is no risk in losing a padlock The customer takes the padlock and uses it to secure the information he will send Only you the vendor have the key to the padlock so you are the only one who can unlock the customer s information A mathematical method that accomplishes this was invented by MIT mathematicians Rivest Shamir and Adleman in 1977 Vendor 1 For large primes p and q 100 digits or more compute n pg 2 Set m LCMp71q 71 3 Pick 7 6 22 and let E 7 1 4 Publicly announce T and n Customer H Convert the message to be sent into a sequence of non negative integers M1 M2 Mk each less than n such that Mi is relatively prime to n for each i This is usually easy since it is very large and has only two prime factors to Compute in Zn 03 Send the numbers R1 R2 Rk Vendor 1 Compute E5 in Zn Remarkably this will equal 2 Assemble the Mi s to recover the message In the appendix we work through an example where we have p 37 q 73 and r 5 and we use the RSA method to send the message BAD We use MAPLE to facilitate the computations Exercise With p 71 q 131 and r 43 use the RSA method to send the message WOW Of course at this point you should be asking yourself two questions 1 Why does the method work 2 Why is it secure To answer the rst question we will prove that for the Mi s and Ri s described above we have if M in Zn Theorem Letp and q be prime and let in LCMp71q 71 Set it pq Suppose W 1 in Zm and pick M relatively prime to n Then MM M in Zn Guided Discovery Proof Again we ll prove this in steps 1 Use the fact that M is relatively prime to p and q why to see that M is in both Z and Z3 Now say how to use the fact that Z and Z are cyclic to obtain integers 1 m1 2 and 2 such that M bfl mod p M I2 mod q 2 Observe that p 7 1lmm1 and q 7 1lmm2 Now show that Mm 1 in Zn 3 Use this to help conclude that MTS M in Zn D To answer the second question think about how an enemy might be able to take the padlock of RSA namely the numbers F and n and determine the key If the enemy can factor n to determine p and q then the enemy can easily nd m and therefore the key E Where is the security It turns out that multiplication is another example of a one way function That is it is much easier to multiply than it is to factoriat least that is what we believe Given the best algorithms for factoring the time it would take to factor the large number 71 would be prohibitive It is possible however that we just don t yet know how to think about factoring in the right way and that someday it might be possible to factor a number just as easily as it is to multiply two numbers together Exercise Knowing that it is hard to factor a large number and assuming that p and q are large primes how do you think one should go about computing m LCMp 7 1 q 7 1 A HISTORICAL NOTE It has recently been learned that Rivest Shamir and Adleman were not the rst to discover the encryption technique that now bears their name In the late 1960 s a man named James Ellis worked for the British Government Communications Headquarters GCHQ the British equivalent of the American National Security Agency NSA and began to think about this problem of padlock distribution In 1973 British mathematicians Cox and Williamson came to GCHQ and Ellis enlisted their help on the problem which they quickly solved However their work was classi ed and remained classi ed for years well after the RSA method was being widely used to secure internet communications Ellis became gravely ill in 1997 and a move was made at GCHQ to declassify the work of Ellis Cox and Williamson so that they could get the credit they deserved for their work on the solution to one of the most important problems of the Information Age Sadly Ellis died three weeks before any public announcement was made More of the details of this story and of the history of cryptography can be found in Simon Singh s The Code Book A NOTE ON ALGORITHMS The problem of understanding the complexity or ef ciency of algorithms has been a subject of intense study since the 1960 s and the advent of computers A problem which can be solved with a polynomial time algorithm is said to be in the class P A problem is NP if you can check whether a proposed solution is actually a solution in polynomial time Certainly the integer factoring problem is NP It is known that P C NP but it is not known whether NP C P If so then it follows that many seemingly intractable problems 7 like integer factoring 7 could then be resolved in polynomial time Thus for example BSA would no longer be secure In fact in the 1998 article Mathematical Problems for the Next Century appearing in the Math Intelligencer Steve Smale a prominent name in the study of chaos and fractals proposed that the P NP question is one of the seven most important mathematical problems of the 21st century This is a hugely important question because as I understand it most secure internet communications use the RSA encryption method For more information about algorithms and the P vs NP problem visit wwwclaymathorgprizeproblemspvsJiphtm and look for the expository paper The P versus NP Problem by Stephen Cook By the way Smale s article is a sequel of sorts At the turn of the last century the German mathematician David Hilbert famously proposed a list of 23 problems as among the most important problems for the 20th century and these continue to spur many great and important advances in mathematics