CY 261 Cryptography - Jordan University of Science and Technology - Fall 2023 PDF

Jordan University of Science and Technology - Fall 2023 1 CY 261 CRYPTOGRAPHY Dr. Qasem Abu Al-Haija Department Of Cybersecurity Chapter 2: Number Theory 1  The language of numbers  Natural numbers: 2 o The hist...

Jordan University of Science and Technology - Fall 2023 1 CY 261 CRYPTOGRAPHY Dr. Qasem Abu Al-Haija Department Of Cybersecurity Chapter 2: Number Theory 1  The language of numbers  Natural numbers: 2 o The history of mathematics begins with numbers used for counting things and adding things like sacks of grain, cattle in a field, and fish in a pond. o These numbers are called natural numbers (counting numbers). They are all the whole positive numbers greater than zero. o Mathematically, we can write these numbers as 1, 2, 3, …, n The three dots (…) mean a continuing sequence up to n. o For the natural numbers, n has no upper limit. o Set: When defining numbers this way, we refer to them as a set of numbers. For example, Natural numbers are the set of whole numbers greater than 0 Jordan University of Science and Technology - Qasem Abu Al-Haija  The language of numbers 3  Integer:  Integersare the set of negative and positive whole numbers, including zero. Mathematically, we can write these numbers as: ◼ –n,… , –3, –2, –1, 0, 1, 2, 3, … , n ◼ where n has no upper limit and –n has no lower limit  Subset:  From this, it is clear that natural numbers are a subset of integers. ◼ Subset is a set contained within a larger set. ◼ Every natural number is also an integer, but every integer is not always a natural number. Jordan University of Science and Technology - Qasem Abu Al-Haija  The language of numbers 4  Factor:  When one number divides exactly into another number leaving no remainder, it is said to be a factor of that number  Mathematically, we can express this as: a | b (a is a factor of b) A natural number may have several factors. ◼ For example, 12 has factors 1, 2, 3, 4, 6, and 12 since all of these will divide it exactly leaving no remainder Jordan University of Science and Technology - Qasem Abu Al-Haija  The language of numbers 5  Activity 5 (self-assessment)  What are the factors of the following? ◼ 9 : 1, 3, 9 ◼ 15 : 1, 3, 5, 15 ◼ 17 : 1, 17 ◼ 32 : 1, 2, 4, 8, 16, 32  Notes:  You should notice that in every case: ◼ one of the factors was always 1 ◼ every natural number is a factor of itself ◼ every natural number has at least two factors (1 and itself)  These rules apply for any natural number except for 1. ◼ The number 1 is unique in that it has only a single factor of 1 Jordan University of Science and Technology - Qasem Abu Al-Haija  Divisibility 6  We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers  b divides a if there is no remainder on division  The notation b|a is commonly used to mean b divides a  If b|a, we say that b is a divisor of a The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24 13 | 182; - 5 | 30; 17 | 289; - 3 | 33; 17 | 0 Jordan University of Science and Technology - Qasem Abu Al-Haija  Properties of Divisibility 7 If a | 1, then a = ±1 If a | b and b|a, then a = ±b Any b ≠ 0 divides 0 If a | b and b | c, then a | c 11 | 66 and 66 | 198 = 11 |198 If b | g and b | h, then b | (mg + nh) for arbitrary integers m and n Jordan University of Science and Technology - Qasem Abu Al-Haija  Division Algorithm 8  Given integers a and n, with n > 0, there exist unique integers q and r satisfying: a = qb + r with 0 ≤ r < b.  The integers q and r are called the quotient and remainder in the division of a and n.  The relationship between these four integers can be shown as a=q×n+r 0 ≤ r < n; q = [a/n]  Example : If a = 592; n = 7 then 592 = 84(7) + 4 then q = 84 and r = 4. Jordan University of Science and Technology - Qasem Abu Al-Haija  Division Algorithm 9 Example 1  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 Jordan University of Science and Technology - Qasem Abu Al-Haija  Division Algorithm 10 Figure 1 Division algorithm for integers Jordan University of Science and Technology - Qasem Abu Al-Haija  Division Algorithm 11 Example 2  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. Jordan University of Science and Technology - Qasem Abu Al-Haija  Introduction to Modular Arithmetic 12  Other names for modular arithmetic:  Itis also called modulo arithmetic, clock arithmetic, or remainder arithmetic. It usually involves the concept of full rotation (circular)➔ (to be clarified later)  Set: A set is a collection of objects  Modulus:  The size (that is, the number of, say, integers a set contains) is known as the modulus Jordan University of Science and Technology - Qasem Abu Al-Haija  Introduction to Modular Arithmetic 13  Generally, most cryptosystems are based on sets of numbers that are: 1. Discrete (sets with integers are particularly useful) 2. Finite (if we only compute with finitely many numbers)  Seems too abstract? --- Let‘s look at a finite set with discrete numbers we are quite familiar with a clock.  Interestingly, even though the numbers are incremented every hour, we never leave the set of integers:  1, 2, 3, … 11, 12, 1, 2, 3, … 11, 12, 1, 2, 3, …: Jordan University of Science and Technology - Qasem Abu Al-Haija  Modular Arithmetic 14  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. Jordan University of Science and Technology - Qasem Abu Al-Haija  Modulo Operator 15  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 Jordan University of Science and Technology - Qasem Abu Al-Haija  Example 2.14 16  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. Jordan University of Science and Technology - Qasem Abu Al-Haija  Set of Residues 17  The modulo operation creates a set, which is referred to as the set of least residues modulo n or Zn. Figure 2.10 Some Zn sets Jordan University of Science and Technology - Qasem Abu Al-Haija  Congruent Modulo (Equivalency Modulo ≡) 18  If two integers are congruent, we use the congruence operator ( ≡ ).  Two integers a and b are said to be congruent (modulo n, if (a mod n) = (b mod n). This is written as a ≡ b (mod n)  We say, “a and b are equivalent to each other in class modulo n” Jordan University of Science and Technology - Qasem Abu Al-Haija  Concept of congruence 19 Jordan University of Science and Technology - Qasem Abu Al-Haija  Residue Classes 20  A residue class [a] or [a]n is the set of integers congruent modulo n. Jordan University of Science and Technology - Qasem Abu Al-Haija  Congruent Modulo 21  Properties of the congruences If a ≡ b mod n, if n|(a-b) → (a-b) is devisable by n If a ≡ b mod n, implies b ≡ a mod n If a ≡ b mod n and b ≡ c mod n, implies a ≡ c mod n  Example:  23 ≡ 8 mod 5 → becouse 23-8= 15→ 5|15 = 15=5x3  -11 ≡ 5 mod 8 → becouse -11-5= -16→ 8|-16 = 16=8x(-2)  81 ≡ 0 mod 27 → becouse 81-0= 81→ 27|81 = 81=27x3  Examples: 73 ≡ 4 mod 23, then 4 ≡ 73 mod 23, because 4 mod 23 = 73 mod 23 73 ≡ 4 mod 23 and 4 ≡ 96 mod 23, then 73 ≡ 96 mod 23. Jordan University of Science and Technology - Qasem Abu Al-Haija  Congruent Modulo 22  Examples for modular reduction, property 1: Let a= 12 and n = 9 : 12 ≡ 3 mod 9 Let a= 34 and n = 9 : 34 ≡ 7 mod 9 Let a= -7 and n = 9 : -7 ≡ 2 mod 9  You should check whether the condition n divides (a-b) holds in each of the 3 cases Jordan University of Science and Technology - Qasem Abu Al-Haija  Comparison of Z and Zn using graphs 23 Jordan University of Science and Technology - Qasem Abu Al-Haija  Operation in Zn 24  The three binary operations 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. Jordan University of Science and Technology - Qasem Abu Al-Haija  Operation in Zn 25 Example :  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 Z20.  Solution Jordan University of Science and Technology - Qasem Abu Al-Haija  Operation in Zn 26  Properties Jordan University of Science and Technology - Qasem Abu Al-Haija  Properties of mode operator 27 Jordan University of Science and Technology - Qasem Abu Al-Haija  Operation in Zn 28 Example: ◼ (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6 ◼ (1,723,345 − 2,124,945) mod 11 = (8 − 9) mod 11 = 10 ◼ (1,723,345 × 2,124,945) mod 11 = (8 × 9) mod 11 = 6 How about 117 mod 13? Jordan University of Science and Technology - Qasem Abu Al-Haija  Greatest Common Divisor (GCD) 29  GCD of two or more numbers is the largest number that divides into each of them exactly (without leaving any remainder).  GCD can be found by calculating the prime factors of each number and then finding the product of those prime factors that are common  Example1: Find the GCD of 48 and 252:  48 =2×2×2×2×3  252 = 2 × 2 × 3 × 3 × 7  Common factors are highlighted➔ GCD(48, 252)= 2 × 2 × 3 =12 Jordan University of Science and Technology - Qasem Abu Al-Haija  Greatest Common Divisor (GCD) 30  Example2: Find the GCD of 84and 30:  84 = 2 × 2 × 3 × 7  30 = 2 × 3 × 5  Therefore: GCD (84, 30) = 2 × 3 = 6.  Example3: Find the GCD of 60, 84 and 150:  60 = 2 × 2 × 3 × 5  84 = 2 × 2 × 3 × 7  150 = 2 × 3 × 5 × 5  Therefore: GCD (60, 84,150)= 2 × 3 = 6. Jordan University of Science and Technology - Qasem Abu Al-Haija  Euclidean Algorithm 31 Used for determining the GCD of two positive integers. Note When GCD (a, b) = 1, we say that a and b are relatively prime. e.g. GCD(8,15) = 1, hence 8 & 15 are relatively prime Jordan University of Science and Technology - Qasem Abu Al-Haija  Euclid's GCD Algorithm 32  Euclid's Algorithm to compute GCD(a,b):  A=a, B=b  If B = 0 return A = gcd(a, b)  while B>0 ◼ R = A mod B ◼ A = B ◼ B = R  return A Jordan University of Science and Technology - Qasem Abu Al-Haija  Example GCD(1970,1066) 33 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 Stop Therefore: GCD(1970,1066) = 2 Jordan University of Science and Technology - Qasem Abu Al-Haija  Least Common Multiple (LCM) 34  Definition: A non-negative integer d is the LCM of two integers a and b, denoted d = LCM(a, b), if: i. a|d and b|d; and ii. whenever a|c and b|c, then d|c.  LCM(a, b) is the smallest non-negative integer divisible by both a and b. Jordan University of Science and Technology - Qasem Abu Al-Haija  Least Common Multiple (LCM) 35 Example  Calculate LCM (12,8) First Method: Using the GCD Method  GCD (12,18) 18 = 1 x 12 + 6 12 = 2 x 6 + 0 ➔ GCD(12, 6) = 6  Then: 18∗12 216 LCM (18,12) = = = 36 GCD (12,18) 6 Jordan University of Science and Technology - Qasem Abu Al-Haija  Least Common Multiple (LCM) 36 Example Second Method: Using Factorization Method  Find LCM(12, 18)? 18 = 2x3x3 =21x32 12 = 2x2x3 = 22x31 ➔ LCM= 22 x 32 = 4*9=36 Jordan University of Science and Technology - Qasem Abu Al-Haija  Linear Diophantine Equation (LDE) 37  LDE of two variables is ax + by = c.  Particular solution: x0 = (c/d)s and y0 = (c/d)t  General solutions: x = x0 + k (b/d) and y = y0 − k(a/d) where k is an integer, and d is GCD (a, b) Jordan University of Science and Technology - Qasem Abu Al-Haija  Linear Diophantine Equation 38 Example  Find the particular and general solutions to the equation 21x + 14y = 35.  Solution Jordan University of Science and Technology - Qasem Abu Al-Haija  Linear Diophantine Equation – Example 39  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 infinite solutions, but only a few of them are acceptable in this case.  The general nonnegative solutions with x and y are (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0) Jordan University of Science and Technology - Qasem Abu Al-Haija  Relatively Prime (Coprime) 40 Two or more numbers whose GCD is 1 are said to be coprime. Of course, when the modulus itself is a prime number, then it will be coprime with all the members of the group since, by definition, a prime number has no factors other than 1 and itself For example,  6 and 35 are relatively prime (GCD = 1)  6 and 8 are not relatively prime (GCD = 2) Jordan University of Science and Technology - Qasem Abu Al-Haija  FERMAT'S AND EULER'S THEOREMS 41  These theorems are important in public-key cryptography.  Fermat's Theorem: If p is prime and a is a positive integer relatively prime to p, then ap − 1 ≡ 1 mod p  Example: a = 7, p = 19 Jordan University of Science and Technology - Qasem Abu Al-Haija  FERMAT'S THEOREM 42  Second Version  An alternative form of Fermat’s theorem is also useful: If p is prime and a is a positive integer, then ap ≡ a mod p  This version doesn’t require that a be relatively prime to p. Jordan University of Science and Technology - Qasem Abu Al-Haija  FERMAT'S THEOREM 43 Example  Find the result of 6 10 mod 11. Solution  We have 6 10 mod 11 = 1. This is the first version of Fermat’s little theorem where p = 11. Example Find the result of 312 mod 11. Solution Here the exponent (12) and the modulus (11) are not the same. With substitution this can be solved using Fermat’s little theorem. Jordan University of Science and Technology - Qasem Abu Al-Haija  Self-Assessment 44  Find 4532 mod 11 ap − 1 ≡ 1 mod p Solution Jordan University of Science and Technology - Qasem Abu Al-Haija  Self-Assessment 45  Find 4532 mod 11 ap − 1 ≡ 1 mod p Solution 532  4 = 4 10∗53+2 10 53  4. 4 2 𝑚𝑜𝑑 11 53  1. 4 2 𝑚𝑜𝑑 11 2  1. 4 𝑚𝑜𝑑 11  16 𝑚𝑜𝑑 11 = 5 𝑚𝑜𝑑 15 Jordan University of Science and Technology - Qasem Abu Al-Haija 46  Use Fermat’s theorem to find a number between 0 and 28 with 𝑥 85 congruent to 6 modulo 29. (You should not need to use any brute-force searching.) Jordan University of Science and Technology - Qasem Abu Al-Haija  Euler's Totient Function 47  For n ≥ 1, let φ(n) denote the number of integers in the interval [1, n] which are relatively prime (coprime) to n.  The function φ is called the Euler phi of function (or Euler totient function).  Euler’s totient function plays a very important role in cryptography. Jordan University of Science and Technology - Qasem Abu Al-Haija  Euler's Totient Function 48  New problem, important for public-key systems, e.g., RSA:  Given the set of the m integers {0, 1, 2, …, n -1},  How many numbers in the set are relatively prime to n ?  Answer: Euler‘s Phi function Φ(n)  Example for the sets {0,1,2,3,4,5} (n=6), and {0,1,2,3,4} (n=5) 1 and 5 relatively prime to n =6, hence Φ(6) = 2 Φ(5) = 4 Testing one gcd per number in the set is extremely slow for large m. Jordan University of Science and Technology - Qasem Abu Al-Haija  Properties of Euller phi function: 49 Note The difficulty of finding φ(n) depends on the difficulty of finding the factorization of n. Thus, finding φ(n) is computationally easy if the factorization of n is known (otherwise, the calculation of φ(n) becomes computationally infeasible for large numbers)  General formula for Euler’s Totient Function  Where p1, p2, p3, … , pn are prime factors of n Jordan University of Science and Technology - Qasem Abu Al-Haija  Properties of Euller phi function: 50  Example: Calculate the Euler Totient Function ø(60) :  60 = 2 × 2 × 3 × 5  So, 2, 3, and 5 are the prime factors of 60  Using the general formula for Euler’s Totient Function: 1 1 1 ∅ 60 = 60 × 1 − 1− 1− 2 3 5 1 2 4 = 60 × × × = 16 2 3 5  Using another formula for Euler’s Totient Function:  We can write 60 = 22 × 31 × 51. Then f(60) = (22 −21) × (31 − 30) × (51 − 50) = (4 − 2) × (3 − 1) × (5 − 1) = (2)(2)(4) = 16 Jordan University of Science and Technology - Qasem Abu Al-Haija  Properties of Euller phi function: 51  Example:  What is the value of f(13)? Solution  Because 13 is a prime, f(13) = (13 −1) = 12.  Example:  If p=11 and q=7 and n= 11×7 = 77  What is the value of f(77)? Solution  Because 77 is a product two prime number, then: f(n) = (p −1) (q −1) f(77) = (11 −1) (7 −1)= (10)(6)=60. Jordan University of Science and Technology - Qasem Abu Al-Haija 52  What is the number of elements in Z14*?  Solution  The answer is f(14) = f(7) × f(2) = 6 × 1 = 6. The members are 1, 3, 5, 9, 11, and 13. Note Interesting point: If n > 2, the value of f(n) is even. Jordan University of Science and Technology - Qasem Abu Al-Haija  Euler’s Theorem 53  First Version : States that for every a and n that are relatively prime: af(n) ≡ 1 (mod n) ………….……..(1)  Second Version : the first form of Euler’s theorem [Equation (1)] requires that a be relatively prime to n, but this form does not. a k × f(n) + 1 ≡ a (mod n) ……….(2)  The second version of Euler’s theorem is used in the RSA cryptosystem. Jordan University of Science and Technology - Qasem Abu Al-Haija  Euler’s Theorem 54 Example Find the result of 624 mod 35. Solution We have 624 mod 35 = 6f(35) mod 35 = 1. Example 9.16 Find the result of 2062 mod 77. Solution If we let k = 1 on the second version, we have 2062 mod 77 = (20 mod 77) (20f(77) + 1 mod 77) mod 77 = (20)(20) mod 77 = 15 Jordan University of Science and Technology - Qasem Abu Al-Haija  Self-Assessment 55  Find 790 mod 15 af(n) ≡ 1 (mod n) Solution Jordan University of Science and Technology - Qasem Abu Al-Haija  Self-Assessment 56  Find 790 mod 15 af(n) ≡ 1 (mod n) Solution  Find ᵠ(15)=8 GCD (7, 15) = ? 𝟏 8  7 88 2. 7 ≡ 1 𝑚𝑜𝑑 15 7 ≡ 1 𝑚𝑜𝑑 15 8 11  7. 7 2 ≡ 1 𝑚𝑜𝑑 15 11  1. 7 2 ≡ 1 𝑚𝑜𝑑 15 2  1. 7 ≡ 1 𝑚𝑜𝑑 15  49 ≡ 1 𝑚𝑜𝑑 15 → 4 ≡ 1 𝑚𝑜𝑑 15 Jordan University of Science and Technology - Qasem Abu Al-Haija  Inverses 57  When working in modular arithmetic, we often need to find the inverse of a number relative to an operation.  We normally look for an additive inverse (relative to an addition operation) or a multiplicative inverse (relative to a multiplication operation). Jordan University of Science and Technology - Qasem Abu Al-Haija  Additive Inverse 58  In Zn, two numbers a and b are additive inverses of each other if In modular arithmetic, each integer has an additive inverse. The sum of an integer and its additive inverse is congruent to 0 modulo n. Jordan University of Science and Technology - Qasem Abu Al-Haija  Additive Inverse 59 Example  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). Jordan University of Science and Technology - Qasem Abu Al-Haija  Multiplicative Inverse 60  In Zn, 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. Jordan University of Science and Technology - Qasem Abu Al-Haija  Multiplicative Inverse 61 Example Find the multiplicative inverse of 8 in Z10. Solution There is no multiplicative inverse because gcd (10, 8) = 2 ≠ 1. In other words, we cannot find any number between 0 and 9 such that when multiplied by 8, the result is congruent to 1. Jordan University of Science and Technology - Qasem Abu Al-Haija  Multiplicative Inverse 62 Example Find the multiplicative inverse of 8 in Z10. Solution There is no multiplicative inverse because gcd (10, 8) = 2 ≠ 1. In other words, we cannot find any number between 0 and 9 such that when multiplied by 8, the result is congruent to 1. Jordan University of Science and Technology - Qasem Abu Al-Haija  Multiplicative Inverse 63 Example Find all multiplicative inverses in Z10. 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. Jordan University of Science and Technology - Qasem Abu Al-Haija  Multiplicative Inverse 64 There are set of algorithm to find the inverse, like:  Exhaustive search algorithm  Extended Euclidean algorithm  Euller’s Theorem Jordan University of Science and Technology - Qasem Abu Al-Haija  Exhaustive search algorithm 65  Choose two prime numbers (P=3, q=7)  Compute the Modula as n=p × q = 3×7=21  Compute 𝜑 𝑛 =(p-1)(q-1)→ 𝜑 𝑛 (3 -1)(7-1) = 12  Choose the public key (e) such that:  1 X=X0 + (n/d)t Since the gcd (a,n)=2, the number of solutions is 1 X=X0 + (n/d)t 18 𝑋 ≡6+ 2 𝑡 = 6 + 9𝑡 = 𝑡 = 1 = 6 + 9 = 15 ……….(7) Jordan University of Science and Technology - Qasem Abu Al-Haija  Linear Congruence 81 Example 3 Solve the equation 3x + 4 ≡ 6 (mod 13). Solution First, we change the equation to ax ≡ b (mod n). We add −4 (the additive inverse of 4) to both sides, which gives 3x ≡ 2 (mod 13). Because gcd (3, 13) = 1, the equation has only one solution, which is x0 = (2 × 3−1) mod 13 = 18 mod 13 = 5. We can see that the answer satisfies the original equation: 3 × 5 + 4 ≡ 6 (mod 13). Jordan University of Science and Technology - Qasem Abu Al-Haija  Linear Congruence 82 Self Assessment Solve the equation 8x ≡ 16 (mod 12). Solution Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 83  CRT is used to solve a set of congruent equations with one variable but different moduli, which are relatively prime, as shown below: Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 84 Example 1 The following is an example of a set of equations with different moduli:  The solution to this set of equations is given in the next section.  For now, note that the answer to this set of equations is x = 23.  This value satisfies all equations: 23 ≡ 2 (mod 3), 23 ≡ 3 (mod 5), and 23 ≡ 2 (mod 7) Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 85 Solution To the CRT 1) Find M = m1 × m2 × … × mk. This is the common modulus. 2) Find M1 = M/m1, M2 = M/m2, …, Mk = M/mk. 3) Find the multiplicative inverse of M1, M2, …, Mk using the corresponding moduli (m1, m2, …, mk). Call the inverses M1−1, M2−1, …, Mk −1. 4) The solution to the simultaneous equations is Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 86 Solution We follow the four steps. 1. M = 3 × 5 × 7 = 105 2. M1 = 105 / 3 = 35, M2 = 105 / 5 = 21, M3 = 105 / 7 = 15 3. The inverses are M1−1 = 2, M2−1 = 1, M3 −1 = 1 4. x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105 = 23 mod 105 Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 87  Assume we need to calculate z = x + y where x = 123 and y = 334, but our system accepts only numbers less than 100. Adding each congruence in x with the corresponding congruence in y gives Now three equations can be solved using the Chinese remainder theorem to find z. One of the acceptable answers is z = 457. Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 88 Self Assessment  The following is an example of a set of equations with different moduli: 𝑋 ≡ 1 𝑚𝑜𝑑 4 𝑋 ≡ 1 𝑚𝑜𝑑 3 𝑋 ≡ 0 𝑚𝑜𝑑 5 Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 89 Self Assessment  Find an integer that has a remainder of 3 when divided by 7 and 13, but is divisible by 12. Jordan University of Science and Technology - Qasem Abu Al-Haija  Chinese Remainder Theorem (CRT) 90 Solution This is a CRT problem. We can form three equations and solve them to find the value of x. If we follow the four steps, we find x = 276. We can check that 276 = 3 mod 7, 276 = 3 mod 13 and 276 is divisible by 12 (the quotient is 23 and the remainder is zero). Jordan University of Science and Technology - Qasem Abu Al-Haija  Fast Exponentiation 91 Exponentiation Algorithms:  Fast Exponentiation Algorithm for Encryption and Decryption  Repeated Square-and-Multiply Algorithm for Exponentiation in Zn  Fast decryption with CRT Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Fast Exponentiation 92  Unlike symmetric algorithms like AES, DES, or Stream ciphers, PKC algorithms are based on arithmetic with very long numbers.  Need to implement efficient computations, otherwise, too slow for practical use.  If we look at RSA encryption and decryption c = Ekpub (m) ≡ me mod n (encryption) m = Dkpr (c) ≡ cd mod n (decryption)  We see that both are based on modular exponentiation!  The problem is how we can deal with very long numbers. Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija 93  Ex: find X4 Regular way Better way X * X = X2 X * X = X2 X2 * X = X3 X2 * X2 = X4 X3 * X = X4 We do that using 3 MULT We do that using 2 SQ  Ex: find X8 Regular way Better way X * X = X2 X * X = X2 X2 * X = X3 X2 * X2 = X4 X3 * X = X4 X4 * X4 = X8 X4 * X = X5 X5 * X = X6 X6 * X = X7 X7 * X = X8 We do that using 7 MULT We do that using 3 SQ Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija 94  Ex: find X (2) ^ 1024 Regular way Better way X * X = X2 X * X = X2 X2 * X = X3 X2 * X2 = X4.. X4 * X4 = X8............ X1024 * X1024 = X (2) ^ 1024 X (2) ^ 1023 * X (2) ^ 1023 = X (2) ^ 1024 We do that using 21024 – 1 MULT We do that using 1024 SQ  Note:- In all the above examples, exponentiation can be represented by 2X, so it is better to include the Square operation. Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  95 Regular way Better way  Example: X26 X * X = X2 X * X = X2 { SQ] X 2 * X = X3 2 X *X=X 3 {MULT}.. X3 * X3 = X6 { SQ }.. 6 6 X *X =X 12 { SQ }.. 12 X * X= X 13 {MULT} X25 * X = X 26 13 X *X =X 13 26 { SQ } We do that using 25 1 MULT We do that using 2 MULT and 4 SQ  Example. This time we have the more general exponent 26, i.e., we want to compute x26. Again, the regular method would require 25 multiplications. A faster way is as follows: 𝑆𝑄 𝑀𝑈𝐿 𝑆𝑄 𝑆𝑄 𝑀𝑈𝐿 𝑆𝑄  𝑥 𝑥2 𝑥3 𝑥6 𝑥 12 𝑥 13 𝑥 26  This approach takes a total of six operations, two multiplications and four squaring  Looking at the last example, we see that we can achieve the desired result by performing two basic operations:  squaring the current result,  multiplying the current result by the base element Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Exponentiation 96 1. Fast Exponentiation Algorithm for Encryption c= me mod n c=170471 mod 3233 = 3106 Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Fast Exponentiation 97  However, we do not know the sequence where the squaring and multiplications must be performed for other exponents.  One solution is the square-and-multiply algorithm.  Systematic way for finding the sequence to perform squaring and multiplications by x for computing xH. Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Square-and-Multiply Algorithm 98  The algorithm is based on scanning the bit of the exponent from the left bit (MSB) to the right bit (LSB).  In every iteration, the current result is squared for every exponent bit.  If and only if the currently scanned exponent bit has the value 1, a multiplication of the current result by x is executed following the squaring. Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Square-and-Multiply Algorithm 99  We again consider the exponentiation x26. For the square- and-multiply algorithm (Fast exponentiation algorithm), the binary representation of the exponent is crucial: x26 = x110102 = x(h4h3h2h1h0)2.  The algorithm scans the exponent bits, starting on the left with h4 and ending with the rightmost bit h0.  Roughly speaking, the algorithm works as follows: Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Square-and-Multiply Algorithm 100 Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Left-to-right binary method For Modular Exponentiation 101  Suppose we want to calculate c ≡ be mod m:  Write ‘e’ in binary notation.  Starting from the left: for each ‘1’ in ‘e’ square, the result, then multiply by ‘b,’ and for each ‘0’ square, the result only.  In each step calculate the modular of the result. Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Example 102  413 mod 49, here b = 4, e = 13 = 11012 and the modular m = 49.  First bit is ignored, then dropped e = 1012. The last left bit is one: 𝑏 = 42 4 𝑚𝑜𝑑49 = 15  The MSB now is zero after dropping one bit: 𝑏 = 152 𝑚𝑜𝑑49 = 29  Then dropping also one bit. The last iteration now with ‘1’: 𝑏 = 292 4 𝑚𝑜𝑑49 = 32 Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Square-and-Multiply Algorithm 103  413 mod 49, here the base (b) = 4, Exponent (e) = 13 and the modular m = 49.  Step1: Convert the power to binary = 11012  Step2: Square & Multiply the base for every bit as follows:  1 → if the binary digit is 1 we have do two steps (Square & Multiply)  0 → → if the binary digit is 0 we have do only step (Square) ei process Result Comments 1 SM 12 * 4 mod 49 =4 Write down the base which is 4 or drop the MSB ➔ 101➔ start 1 SM 42 * 4 mod 49 =15 Lock at the binary digit which is 1,then we have two steps (SM). square the result then multiply by the base (b). 0 S 152 mod 49 =29 Lock at the binary digit which is 0, then we have one step (S): square the result only 1 SM 292 * 4 mod 49 =32 square the result then multiply by the base (b). Jordan University of Science and Technology---Dr. Qasem Abu Al-Haija  Orders and Primitive Roots 104 Order of x modulo m is defined to be the least positive exponent h with xh  1 (mod m) when x and m are relatively prime. Order of 4 modulo 7 = 3 → (43  1 (mod 7)) Primitive Root of m is a number x whose order h is equal to f(m). A primitive roots of 7 in Z7 are 3 and 5 since Ord7(3) = 6 = Ø (7) and Ord7(5) = 6 = Ø (7) Jordan University of Science and Technology - Qasem Abu Al-Haija