Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 822.1Chapter 2Mathematics of CryptographyPart I: Modular Arithmetic, Congruence,and MatricesCopyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.2.2 To review integer arithmetic, concentrating on divisibility and finding the greatest common divisor using the Euclidean algorithm To understand how the extended Euclidean algorithm can be used to solve linear Diophantine equations, to solve linear congruent equations, and to find the multiplicative inverses To emphasize the importance of modular arithmetic and the modulo operator, because they are extensively used in cryptography To emphasize and review matrices and operations on residue matrices that are extensively used in cryptography To solve a set of congruent equations using residue matricesObjectivesChapter 22.32-1 INTEGER ARITHMETIC2-1 INTEGER ARITHMETICIn integer arithmetic, we use a set and a few In integer arithmetic, we use a set and a few operations. You are familiar with this set and the operations. You are familiar with this set and the corresponding operations, but they are reviewed here corresponding operations, but they are reviewed here to create a background for modular arithmetic.to create a background for modular arithmetic.2.1.1 Set of Integers2.1.2 Binary Operations2.1.3 Integer Division2.1.4 Divisibility2.1.5 Linear Diophantine EquationsTopics discussed in this section:Topics discussed in this section:2.4The set of integers, denoted by Z, contains all integral numbers (with no fraction) from negative infinity to positive infinity (Figure 2.1). 2.1.1 Set of IntegersFigure 2.1 The set of integers2.5In cryptography, we are interested in three binary operations applied to the set of integers. A binary operation takes two inputs and creates one output. 2.1.2 Binary OperationsFigure 2.2 Three binary operations for the set of integers2.6Example 2.12.1.2 ContinuedThe following shows the results of the three binary operations The following shows the results of the three binary operations on two integers. Because each input can be either positive or on two integers. Because each input can be either positive or negative, we can have four cases for each operation.negative, we can have four cases for each operation.2.7In integer arithmetic, if we divide a by n, we can get qAnd r . The relationship between these four integers can be shown as2.1.3 Integer Divisiona = q × n + r2.8Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using the division algorithm.2.1.3 ContinuedFigure 2.3 Example 2.2, finding the quotient and the remainderExample 2.22.92.1.3 ContinuedFigure 2.4 Division algorithm for integers2.10Example 2.32.1.3 ContinuedWhen we use a computer or a calculator, When we use a computer or a calculator, rr and and qq are negative are negative when when aa is negative. How can we apply the restriction that is negative. How can we apply the restriction that r r needs to be positive? The solution is simple, we decrement the needs to be positive? The solution is simple, we decrement the value of value of qq by 1 and we add the value of by 1 and we add the value of nn to to rr to make it to make it positive.positive.2.112.1.3 ContinuedFigure 2.5 Graph of division alogorithm2.12If a is not zero and we let r = 0 in the division relation, we get2.1.4 Divisbilitya = q × nIf the remainder is zero, If the remainder is not zero,2.13Example 2.42.1.4 Continueda.a.The integer 4 divides the integer 32 because 32 = 8 × 4. We The integer 4 divides the integer 32 because 32 = 8 × 4. We show this asshow this asb. The number 8 does not divide the number 42 because b. The number 8 does not divide the number 42 because 42 = 5 × 8 + 2. There is a remainder, the number 2, in the 42 = 5 × 8 + 2. There is a remainder, the number 2, in the equation. We show this as equation. We show this as2.14Properties2.1.4 ContinuedProperty 1: if a|1, then a = ±1.Property 2: if a|b and b|a, then a = ±b.Property 3: if a|b and b|c, then a|c.Property 4: if a|b and a|c, then a|(m × b + n × c), where m and n are arbitrary integers2.15Example 2.52.1.4 Continued2.16Example 2.62.1.4 Continued2.172.1.4 ContinuedFact 1: The integer 1 has only one divisor, itself.Fact 2: Any positive integer has at least two divisors, 1 and itself (but it can have more).Note2.182.1.4 ContinuedFigure 2.6 Common divisors of two integers2.19Euclidean Algorithm2.1.4 ContinuedFact 1: gcd (a, 0) = aFact 2: gcd (a, b) = gcd (b, r), where r is the remainder of dividing a by bThe greatest common divisor of two positive integers is the largest integer that can divide both integers.Greatest Common DivisorNoteNote2.202.1.4 ContinuedFigure 2.7 Euclidean AlgorithmWhen gcd (a, b) = 1, we say that a and b are relatively prime.Note2.212.1.4 ContinuedWhen gcd (a, b) = 1, we say that a and b are relatively prime.Note2.22Example 2.72.1.4 ContinuedFind the greatest common divisor of 2740 and 1760.Find the greatest common divisor of 2740 and 1760.We have gcd (2740, 1760) = 20.We have gcd (2740, 1760) = 20.SolutionSolution2.23Example 2.82.1.4 ContinuedFind the greatest common divisor of 25 and 60.Find the greatest common divisor of 25 and 60.We have gcd (25, 65) = 5.We have gcd (25, 65) = 5.SolutionSolution2.24Extended Euclidean Algorithm2.1.4 ContinuedGiven two integers Given two integers aa and and bb, we often need to find other two , we often need to find other two integers, integers, ss and and tt, such that, such thatThe extended Euclidean algorithm can calculate the gcd (The extended Euclidean