Mathematics of Cryptography Part I: Modular Arithmetic, Congruence, and Matricesa Objectives Q To review integer arithmetic, concentrating on divisibility and finding the greatest common divisor using the Euclidean algorithm QO 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 QO To emphasize the importance of modular arithmetic and the modulo operator, because they are extensively used in cryptography QO To emphasize and review matrices and operations on residue matrices that are extensively used in cryptography O To solve a set of congruent equations using residue matrices2-1 INTEGER ARITHMETIC In integer arithmetic, we use a set and a few operations. You are familiar with this set and the corresponding operations, but they are reviewed here to create a background for modular arithmetic. 2.1.1 Set of Integers 2.1.2 Binary Operations 2.1.3 Integer Division 2.1.4 _ Divisibility 2.1.5 Linear Diophantine Equations & Network Security - Behrouza 2.1.1 Set of Integers E The set of integers, denoted by Z, contains all integral numbers (with no fraction) from negative infinity to positive infinity (Figure 2.1). Figure 2.1 The set of integersaL 2.1.2 Binary Operations = In cryptography, we are interested in three binary Operations applied to the set of integers. A binary operation takes two inputs and creates one output. Figure 2.2 Three binary operations for the set of integers 7 On en[ 2.1.2 Continued rE The following shows the results of the three binary operations on two integers. Because each input can be either positive or negative, we can have four cases for each operation. Add: 5+9=14 (-5)+9=4 5+(-9=4 (-5) + (-9) =-14 Subtract: 5-9=—-4 (-5)-9=-14 5-(-9)=14 (-5) -(-9)=+4 Multiply: 5x9=45 (-5)x9=-45 5x (-9) =-45 (-5) x (-9) = 45 hy & Network Security - Behrouz A For4 2.1.3 Integer Division In integer arithmetic, if we divide a by n, we can get q And r. The relationship between these four integers can be shown as Cryptography & Network Security - Behrouz A. ForouzanE 2.1.3 Continued P Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using the division algorithm. Figure 2.3 Example 2.2, finding the quotient and the remainder 23 11 255 | r (positive) (nonnegative) Cryptography & Network Security - Behrouz ‘A Forouzan “[ 2.1.3 Continued E Example 2.3 When we use a computer or a calculator, r and q are negative when a is negative. How can we apply the restriction that r needs to be positive? The solution is simple, we decrement the value of q by 1 and we add the value of n to r to make it positive. —255 = (-23 x 11) + (-2) o —255 =(-24x 11) + 9[ 2.1.3 Continued E Figure 2.5 Graph of division alogorithm Case of positive a r > $$ +> 0 n 2n eee qn oa r [1 oS ES (q-Wn a qn aoe 2n -n 0 Case of negative aa 2.1.4 Divisbility E If a is not zero and we let r =0 in the division relation, we get If the remainder is zero, a|n If the remainder is not zero, a+tn Cryptography & Network Security - Behrouz ‘A Forouzan e[ 2.1.4 Continued E elated a. The integer 4 divides the integer 32 because 32 = 8 x 4. We show this as 4|32 b. The number 8 does not divide the number 42 because 42 = 5 x 8 + 2. There is a remainder, the number 2, in the equation. We show this as 8442al 2.1.4 Continued E Properties Property 1: Property 2: Property 3: Property 4: if aj1, then a = +1. if alb and bja, then a = +b. if alb and bjc, then alc. if alb and alc, then al(m x b +n xc), where m and n are arbitrary integers etwork Security - Behrouz[ 2.1.4 Continued E Example 2.5 a. We have 13|78, 7/98, —6|24, 4|44, and 11|(—33). b. We have 13427, 7450, -64 23,4441, and 11 +(-32).[ 2.1.4 Continued E Example 2.6 a. Since 3|15 and 15|45, according to the third property, 3]45. b. Since 3|15 and 3|9, according to the fourth property, 3|(15 x 2 +9 x4), which means 3|66.al 2.1.4 Continued E Note] Fact 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).[ 2.1.4 Continued —E Figure 2.6 Common divisors of two integers Divisors of 140 Divisor of 12 sa 7 hop tS \ Mo 70 Common Divisors of 140 and 12 Cryptography & N y - Behrouz4 2.1.4 Continued E Note]] Greatest Common Divisor The greatest common divisor of two positive integers is the largest integer that can divide both integers. Euclidean Algorithm Fact 1: gcd (a, 0) = Fact 2: gcd (a, b) = gcd (b, r), where r is the remainder of i dividing abyb4 2.1.4 Continued —E Figure 2.7 Euclidean Algorithm a ee while (r) > 0) 1") { : i gen! i ged (a,b) =r, ged (a,b) 7 a. Process b. Algorithm Pref4 2.1.4 Continued E Cryptography & Network Security - Behrouz n A. Forouzan[ 2.1.4 Continued E clan) ward Find the greatest common divisor of 2740 and 1760. Solution We have gcd (2740, 1760) = 20. q 7a tr r 1 2740 1760 980 1 1760 980 780 1 980 780 200 3 780 200 180 1 200 180 20 9 | 180 20 0 y - Behrouz[ 2.1.4 Continued E Example 2.8 Find the greatest common divisor of 25 and 60. Solution We have gcd (25, 65) =5. q r 1 r 0 25 60 25 2 60 25 10 2 25 10 5 2 10 5 0 5 0[ 2.1.4 Continued E Extended Euclidean Algorithm Given two integers a and b, we often need to find other two integers, s and t, such that sxat+txb=gcd (a, b) The extended Euclidean algorithm can calculate the gcd (a, b) and at the same time calculate the value of s and t.[ 2.1.4 Continued —E Figure 2.8.a Extended Euclidean algorithm, part a Tr —_ ¥ ¥ ¥ ¥ rT n [5 $2 x a \ \ ‘ a | \ | | ged (a, b)=ry a. Process Cryptography & Network Security - Behrouz A. Forouzan a1[ 2.1.4 Continued E Figure 2.8.b Extended Euclidean algorithm, part b (initialization) while (7) > 0) { gory (ty (Updating r’s) (Updating s’s) (Updating ’s) } ged(a, by ry; sos tot b. Algorithm Cryptography & Network rity - Behrouz[ 2.1.4 Continued E Given a = 161 and b = 28, find gcd (a, b) and the values of s and t. Solution We get gcd (161, 28) = 7,s=-1 andt=6. q Ty M2 r Sy, 82 S t, ty t Ss [61 28 21 I 0 1 0 1 =§ 28 21 7 0 1 =i 6 3 2 7 0[ 2.1.4 Continued E le clanl el sayae he) Given a = 17 and b = O, find gcd (a, b) and the values of s and t. Solution We get gcd (17,0) = 17,s=1, andt=0. q ry 1 r S$; SD s t,t t 17 0 1 0 0 1 & Network Security - Behrouz[ 2.1.4 Continued E Given a = 0 and b = 45, find gcd (a, b) and the values of s and t. Solution We get gcd (0, 45) = 45,s=0, andt=1.[ 2.1.4 Continued —E Linear Diophantine Equation [now] Cryptography & Network Security - Behrouz A. Forouzan 864 2.1.4 Continued —E Linear Diophantine Equation [Nore] Particular solution: Xp =(c/d)s and = yp = (c/d)t General solutions: X = Xo + k (b/d) and y = yy — k(a/d) where k is an integer[ 2.1.4 Continued E l= clan] ol aan Find the particular and general solutions to the equation 21x + 14y = 35. Solution Particular: xy7=5x1=5 and yy=5x(-l1)=-5 General: x=5+kx2 and y=-S-kx3[ 2.1.4 Continued E Example 2.13 For example, imagine we want to cash a $100 check and get some $20 and some $5 bills. We have many choices, which we can find by solving the corresponding Diophantine equation 20x + 5y = 100. Since d = gcd (20, 5) = 5 and 5 | 100, the equation has an infinite number of solutions, but only a few of them are acceptable in this case The general solutions with x and y nonnegative are (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0).2-2. MODULAR ARITHMETIC The division relationship (a = q * n + r) discussed in the previous section has two inputs (a and n) and two outputs (q and r). In modular arithmetic, we are interested in only one of the outputs, the remainder r. Topics discussed in this section: 2.2.1. Modular Operator 2.2.2 Set of Residues 2.2.3. Congruence 2.2.4 Operations in Z, 2.2.5 Addition and Multiplication Tables 2.2.6 Different Sets & Network Security - Behrouz4 2.2.1 Modulo Operator The modulo operator is shown as mod. The second input (n) is called the modulus. The output r is called the residue. Figure 2.9 Division algorithm and modulo operator a Zee on ee a n Relation n Operator (positive) (positive) q r (nonnegative) r (nonnegative) Cryptography & Network Security - Behrouz[ 2.1.4 Continued E eel e) wae es Find the result of the following operations: a. 27 mod 5 b. 36 mod 12 c. -18 mod 14 d. -7 mod 10 Solution a. Dividing 27 by 5 results in r= 2 b. Dividing 36 by 12 results in r = 0. c. Dividing -18 by 14 results in r = —4. After adding the modulus r=10 d. Dividing -7 by 10 results in r = -7. After adding the modulus to-7,r=3.4 2.2.2 Set of Residues E The modulo operation creates a set, which in modular arithmetic is referred to as the set of least residues modulo n, or Z,. Figure 2.10 Some Z, sets Z,=(0.1,2,3,..., @—1) Z,= {0,1} Zo = (0, 1, 2, 3,4, 5} Z, = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}a 2.2.3 Congruence E To show that two integers are congruent, we use the congruence operator ( = ). For example, we write: 2 = 12 (mod 10) 13 =23 (mod 10) 3 =8 (mod 5) 8 = 13 (mod 5)[ 2.2.3 Continued E Figure 2.11 Concept of congruence 2 = 22 (mod 10) Congruence Relationship Cryptography & Network Security - Behrouz A. Forouzan2.2.3 Continued —E Figure 2.12 Comparison of Z and Z, using graphs -(-1) Dea ee Oss (n-1) Cryptography & Network A For| 2.2.3 Continued rE We use modular arithmetic in our daily life; for example, we use a clock to measure time. Our clock system uses modulo 12 arithmetic. However, instead of a 0 we use the number 12.a 2.2.4 Operation in Z, The three binary operations that we discussed for the set Z can also be defined for the set Zn. The result may need to be mapped to Zn using the mod operator. Figure 2.13 Binary operations in Z, Z or Z, a Operations[ 2.2.4 Continued E Example 2.16 Perform the following operations (the inputs come from Zn): a. Add 7 to 14 in Z15. b. Subtract 11 from 7 in Z13. c. Multiply 11 by 7 in 220. Solution (14+7)mod15 — (21)mod 15=6 (7-11) mod 13. 3 (4) mod 13 =9 (7X11) mod20 — (77) mod 20= 17[ 2.2.4 Continued —E Properties First Property: (a+b) mod n = [(a mod n) + (b mod n)] mod n Second Property: (a—b) mod n = [(a mod n) — (b mod n)| mod n Third Property: (a Xb) modn =[(a mod n) X (b mod 2)] modn2.2.4 Continued —E Figure 2.14 Properties of mode operator Z or Z, Z or Z, a b n z Z,={0,1,2,..- @—D} Z,= 01,2, -...@-V} a. Original process b. Applying properties & Network rity - Behrouz[ 2.2.4 Continued iE fehewlinge sao the application of the above properties: 1. (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6 2. (1,723,345 - 2,124,945) mod 16 = (8 - 9) mod 11 = 10 3. (1,723,345 x 2,124,945) mod 16 = (8 x 9) mod 11=6 Or (200+301) mod 11 = (2+4)mod11=6 (200-301) mod 11 = (2-4)mod11=9 (200*301) mod 11 = (2*4)mod11 = 84 2.2.5 Inverses When we are working in modular arithmetic, we often need to find the inverse of a number relative to an operation. We are normally looking for an additive inverse (relative to an addition operation) or a multiplicative inverse (relative to a multiplication operation).[ 2.2.5 Continue E Additive Inverse In Z,, two numbers a and b are additive inverses of each other if a+b=0 (mod n) In modular arithmetic, each integer has an additive inverse. The sum of an integer and its additive inverse is congruent to 0 modulo n. tography & Network Security - Behrouz[ 2.2.5 Continued E lecular Find all additive inverse pairs in Z10. Solution The six pairs of additive inverses are (0, 0), (1, 9), (2, 8), (3, 7), (4, 6), and (5, 5). Cryptography & Network Security - Behrouz A. Forouzan[ 2.2.5 Continue E Multiplicative Inverse In Z,, two numbers a and b are the multiplicative inverse of each other if In modular arithmetic, an integer may or may not have a multiplicative inverse. When it does, the product of the integer and its multiplicative inverse is congruent to 1 modulo n. ax b=1 (mod n) tography & Network Security - Behrouza 2.2.5 Continued E Example 2.22 Find the multiplicative inverse of 8 in Z49. Solution There is no multiplicative inverse because gcd (10, 8) = 2 #1. In other words, we cannot find any number between O and 9 such that when multiplied by 8, the result is congruent to 1. 1 clan) 6) (waves) Find all multiplicative inverses in Z,o. Solution There are only three pairs: (1, 1), (3, 7) and (9, 9). The numbers 0, 2, 4, 5, 6, and 8 do not have a multiplicative inverse.[ 2.2.5 Continued E Example 2.24 Find all multiplicative inverse pairs in Z4;. Solution We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9), and (10, 10). Cryptography & Network Security - Behrouz os A. Forouzanal 2.2.5 Continued E The extended Euclidean algorithm finds the multiplicative inverses of b in Z, when n and b are given and gcd (n, b) = 1. The multiplicative inverse of b is the value of t after being mapped to Z,.[ 2.2.5 Continued E Figure 2.15 Using extended Euclidean algorithm to find multiplicative inverse while (7) > 0) { qn [rs ) ged (n, b)= 7, Ifr,=1 ot = if (=I thenbt— 4, a. Process b. Algorithm hy & Network Security - Behrouz A Forous[ 2.2.5 Continued E Example 2.25 Find the multiplicative inverse of 11 in Z5.. Solution q ry 1 r t,t t 2 26 «11 4 0 1 =e a 11 4 3 1 -2 Sy 1 4 3 1 2 5 =i) 3 1 0 5 -7 26 The gcd (26, 11) is 1; the inverse of 11 is —7 or 19. tography & Network Security - Behrouz[ 2.2.5 Continued E Example 2.26 Find the multiplicative inverse of 23 in Zy99. Solution ty t wv ry ) IS 100 23 SI] oo} 5 o I —s a) N oo | a} 2% | plo | ol le wl] o 7 7 1 0 9 =13 100 The gcd (100, 23) is 1; the inverse of 23 is —13 or 87. tography & Network Security - Behrouz[ 2.2.5 Continued E [ecard Find the inverse of 12 in Zy¢. Solution The gcd (26, 12) is 2; the inverse does not exist. & Network Security - Behrouztion Tables Ica ipl [EL 2.2.6 Addition and Mult E Figure 2.16 Addition and multiplication table for 2,5 4 Sé6T7S35 61234 Sé7t5 o1234 Slale|efofol+ {ola Ky Slelolalalol=lels| Se Belelale|= Seles |o[elal=|= Slaleleletalelslelo es lasles late elealatal Esl Slasel=|ela[ ek g sesugss Sleleleeleleelel= SaamTwenea je aE fe Si lope No to rm 2 l= shee Bol espe Biel= alelsfaleis f= Hlalelefolole G-e- Eber SaanTeenea Multiplication Table in Zp Addition Table in Zp rity - BehrouzE 2.2.7 Different Sets E Figure 2.17 Some Z, and Z,* sets Z, = {0, 1,2, 3,4, 5} Ze = {1,5} Zy = {0, 1, 2,3, 4, 5, 6} Z," = {1, 2, 3, 4, 5, 6} Lig One oo O) oor Zio = (1, 3, 7, 9} | We need to use Zn when additive inverses are needed; we need to use Zn* when multiplicative inverses are needed. A. Forouzana 2.2.8 Two More Sets E Cryptography often uses two more sets: Z, and Z,*. The modulus in these two sets is a prime number. Z)3 = {0, 1, 2, 3, 4,5, 6, 7, 8,9, 10, 11, 12} Z13* = {1, 2, 3, 4,5, 6, 7, 8,9, 10, 11, 12}2-3. MATRICES In cryptography we need to handle matrices. Although this topic belongs to a special branch of algebra called linear algebra, the following brief review of matrices is necessary preparation for the study of cryptography. 2.3.1 Definitions 2.3.2. Operations and Relations 2.3.3. Determinants 2.3.4 Residue Matrices tography & Network Security - Behrouz4 2.3.1 Definition E Figure 2.18 A matrix of size | “m m columns 41 AyD : Z) a21 822 Matrix A: S x ay ap Cryptography & Network Security - Behrouz A. Forouzan aim 82m ama 2.3.1 Continued E Figure 2.19 Examples of matrices [2150] 2 23. 14 56 0 0 1 0 0 0 0 0 Rowmanix |4| [12 21 18 01 Pl |io 8 31 i Column 0 matrix as matrix[E 2.3.2 Operations and Relations P Figure 2.20 shows an example of addition and subtraction. Figure 2.20 Addition and subtraction of matrices 24 4) [5 2 Ly lp7 2° 3 12 30f [3 2 10 8 10 20 C=A+B 20 2 5 2 1 7 2 3 5 -§ 10} [3 2 10 8 10 20 D=A-B Cryptography & Network Security - Behrouz so A. Forouzan[ 2.3.2 Continued E 11a] °) (wae as) Figure 2.21 shows the product of a row matrix (1 * 3) by a column matrix (3 * 1). The result is a matrix of size 1x1. Figure 2.21 Multiplication of a row matrix by a column matrix MIT | In which: |53=5x7+2x8+1x2[ 2.3.2 Continued E 11a] °) (ae) Figure 2.22 shows the product of a 2 x 3 matrix by a 3 x 4 matrix. The result is a 2 x 4 matrix. Figure 2.22 Multiplication of a 2 x 3 matrix by a 3 x 4 matrix B[ 2.3.2 Continued E late) (wae Figure 2.23 shows an example of scalar multiplication. Figure 2.23 Scalar multiplication Cryptography & Network Security - Behrouza 2.3.3. Determinant E The determinant of a square matrix A of size m * m denoted as det (A) is a scalar calculated recursively as shown below: 1. Ifm=1, det (A) =a), 2. Ifm> Idet (A)= So Cb'*5 x ay x det (Ay) isl..m Where A;; is a matrix obtained from A by deleting the ith row and jth column. [ote ‘A. Forouzan