Lecture notes on Computer and network security: Lecture 4 - Avinash Kak

Lecture 4: Finite Fields (PART 1) PART 1: Groups, Rings, and Fields Theoretical Underpinnings of Modern Cryptography Lecture Notes on “Computer and Network Security” by Avi Kak (kak@purdue.edu) January 21, 2016 1:21am 2016 Avinash Kak, Purdue University Goals: • To answer the question: Why study finite fields? • To review the concepts of groups, rings, integral domains, and fields CONTENTS Section Title Page 4.1 Why Study Finite Fields? 3 4.2 What Does It Take for a Set of Objects to? 6 Form a Group 4.2.1 Infinite Groups vs. Finite Groups (Permutation 8 Groups) 4.2.2 An Example That Illustrates the Binary Operation 11 of Composition of Two Permutations 4.2.3 What About the Other Three Conditions that Sn 13 Must Satisfy if it is a Group? 4.3 Infinite Groups and Abelian Groups 15 4.3.1 If the Group Operator is Referred to as Addition, 17 Then The Group Also Allows for Subtraction 4.4 Rings 19 4.4.1 Rings: Properties of the Elements with Respect to 20 the Ring Operator 4.4.2 Examples of Rings 21 4.4.3 Commutative Rings 22 4.5 Integral Domain 23 4.6 Fields 24 4.6.1 Positive and Negative Examples of Fields 25 4.7 Homework Problems 26 2 Computer and Network Security by Avi Kak Lecture 4 4.1: WHY STUDY FINITE FIELDS? • It is almost impossible to fully understand practically any facet of modern cryptography and several important aspects of general computer security if you do not know what is meant by a finite field. • For example, without understanding the notion of a finite field, you will not be able to understand AES (Advanced Encryption Standard) that we will take up in Lecture 8. As you will recall from Lecture 3, AES is supposed to be a modern replacement for DES. The substitution step in AES is based on the concept of a multiplicative inverse in a finite field. • For another example, without understanding finite fields, you will NOT be able to understand the derivation of the RSA algorithm for public-key cryptography that we will take up in Lecture 12. • And if you do not understand the basics of public-key cryptogra-phy, you will not be able to understand the workings of several modern protocols (like the SSH protocol you use everyday for 3 Computer and Network Security by Avi Kak Lecture 4 logging into other computers) for secure communications over networks. You will also not be able to understand what has be-come so important in computer security — user and document authentication with certificates. • Another modern concept that will befuddle you if you do not un-derstand public key cryptography is that of digital rights man-agement. And, as I mentioned earlier, you cannot understand public key cryptography without coming to terms with finite fields. • For yet another example, without understanding finite fields, you will never understand the up and coming ECC algorithm (ECC stands for Elliptic Curve Cryptography) that is already in much use and that many consider to be a replacement for RSA for public key cryptography. We will take up ECC in Lecture 14. • As you yourself can see, if you do not understand the concepts in this and the next three lectures, you might as well give up on learning computer and network security. • To put it very simply, a finite field is a set of numbers in which you can carry out the operations of addition, subtraction, mul-tiplication, and division without error. In ordinary computing, division particularly is error prone and what you see is a high- 4 Computer and Network Security by Avi Kak precision approximation to the true result. Lecture 4 Such high-precision approximations do not suffice for cryptography work. All arith-metic operations must work without error for cryptography. • The starting point for learning finite fields is the concept of a group. That’s where we begin in the next section. 5 ... - tailieumienphi.vn