Groups Modular Arithmetic and Cryptography Jean Mark Gawron Linguistics San Diego State University gawron mail sdsu edu http www rohan sdsu edu gawron 2004 July 24 2 Preface The inspiration for this compilation of mathematical material comes from W W Sawyer s Prelude to Mathematics an eclectic and beautiful tour of some of the most important ideas in mathematics among them matrices groups and non Euclidean geometry The book is unique both in the sophistication of its presentation and in the little background it assumes Basically what is assumed is a reader willing to work a little The topics Sawyer discusses are chosen in part on aesthetic grounds They all represent areas of what mathematicians call great mathematical beauty To acheive that status a mathematical idea requires a certain amount of purity distance from any of those crude particulars that infect mathematical applications Yet in another sense what endows Sawyer s diverse ideas with their power is precisely that they have applications It is the fact that these simple structural elments plug into so many diverse apparently unrelated areas that makes the mathematics beautiful Non Euclidean geometry is the root of a body of work that shows that geometries other than Euclidean are both coherent and conceptually fruitful Both of Einstein s theories of relativity may be understood as such alternative geometries Matrices have numerous mathematical lives To mention just a random sample they are used as operators in 3D geometry as representations of Hidden Markov Models as representations of permutations discussed in Chapter 1 It is thus a paradoxical combination of purity and applicability that makes the mathematics interesting There is probably no clearer example of this than the applicability of modular arithmetic to public key cryptography Certainly before the advent of modern cryptography modular arithmetic could lay claim to being one of the purest that is most application free areas of mathematics It was also in its deep relationships to group and field theory one of the most beautiful With the advent of public key cryptography particularly the RSA discussed here applications of modular arithmetic and similar applications in polynomial fields elliptic curves and finite state automata renewed interest on a number of mathematical fronts Schneier 1996 provides an excellent survey A little more explanation of pb key cryptography and its importance 3 factors in the growth of PK crypto a processing power old days chips b dsitributed computing Lotic Iris Notes c internet Contents 1 Introduction 7 2 Groups 9 2 1 2 2 2 3 Introduction to Groups 9 2 1 1 Group Axioms 10 2 1 2 Exercises 14 Examples 15 2 2 1 Reals and Complex Numbers under Multiplication 15 2 2 2 Truth values under the operation Exclusive Or 16 2 2 3 Roots of x3 1 0 16 2 2 4 Permutations 18 2 2 5 Exercises 26 Subgroups 27 2 3 1 Exercises 29 2 3 2 Morphisms 29 3 Modular Arithmetic 3 1 33 Modular Arithmetic 33 3 1 1 33 Remainders 3 4 CONTENTS 3 1 2 3 2 3 3 3 4 Exercises 36 Grouphood 36 3 2 1 Grouphood of complete residue systems under addition mod n 37 3 2 2 Modular Arithmetic Groups with Multiplication 40 3 2 3 Exercises 42 Euclid s Algorithm and Euclid s Extended Algorithm 42 3 3 1 Euclid s Algorithm 43 3 3 2 Exercises 46 3 3 3 Euclid s Extended Algorithm 46 3 3 4 Exercises 50 Theorems about modular inverses 51 4 Group Properties of Multiplicative Groups 53 Grouphood of Z n 53 4 1 1 Exercises 53 4 2 Subgroups and Cosets of Multipicative Groups 54 4 3 LaGrange s Theorem 56 4 4 Fermat s Little Theorem and Euler s Theorem 58 4 4 1 Euler s Totient Function 58 4 4 2 Fermat s Little Theorem 58 4 4 3 Euler s Theorem 59 4 4 4 Exercises 62 4 1 5 Cryptography and Public Keys 63 5 1 Subject Matter of Cryptography 63 5 2 One way functions 64 5 2 1 64 Fair play A coin tossing game problem CONTENTS 5 3 5 5 2 2 A solution A one way function 65 5 2 3 The solution to several problems Encryption 66 5 2 4 Verifiable key exchange A practical almost one way almost function 68 5 2 5 Three true to life one way functions 70 5 2 6 Verifiable key exchange A one way function protocol 71 5 2 7 Diffie Hellman Protocol 72 5 2 8 Exercises 74 5 2 9 RSA protocol 74 5 2 10 Exercises 79 Practice versus Textbook 79 6 Appendix 83 6 1 Computing Euler s Totient Function 83 6 2 RSA Algorithm What if m is not relatively prime to n 87 6 CONTENTS Chapter 1 Introduction This compilation of mathematical material tries to assume very little It is designed to be presented as part of a discrete mathematics course after some very introductory material has been presented Thus the elements of set theoretic notation and definitions are assumed along with for example the notion of an equivalence relation The general mathematical background assumed is that of introductory college math No knowledge of calculus is assumed but knowledge of high school algebra is essential as is the ability to stare at equation in several unknowns without breaking into a cold sweat This book is not intended to function as an independent introduction either to Group Theory or to modular arithmetic The focus is on introducing some mathematical ideas in enough depth to understand their relationship to the cryptographic application Thus in many cases methods of computing and manipulating the mathematical systems involved have been excluded For example the chapter on modular arithmetic does not cover the Chinese Remainder Theorem The one case where computational method and mathematical idea seem to be inseparable covered in some detail is Euclid s Algorithm Each chapter develops applications of the ideas in the previous chapter The material needs to be covered in roughly the order presented The modular arithmetic chapter builds on and develops material in the groups chapter The cryptography chapter presents a number of ideas that are independent of the mathematical developments but ultimately the presentation of the DiffieHillman and RSA protocols rely on key ideas in modular arithmetic The RSA protocol in particular is based on the concept of a multiplicative group in modular arithmetic the set of the integers less than and relatively prime to some n under the operation of multiplication modulo n Theorems in both group 7 8 theorem and modular arithmetic apply CHAPTER 1 INTRODUCTION Chapter 2 Groups In this chapter we discuss a fairly abstract mathematical notion the notion of a group A group is a very simple kind of mathematical system