Computer Science CSC/ECE 574 Dr. Peng Ning 1 CSC/ECE 574 Computer and Network Security Topic 5.1 Basic Number Theory -- Foundation of Public Key Cryptography Computer Science CSC/ECE 574 Dr. Peng Ning 2 Outline • GCD and Euclid’s Algorithm • Modulo Arithmetic • Modular Exponentiation • Discrete Logarithms Computer Science CSC/ECE 574 Dr. Peng Ning 3 GCD and Euclid’s Algorithm Computer Science CSC/ECE 574 Dr. Peng Ning 4 Some Review: Divisors • Set of all integers is Z = {…,-2, -1,0,1,2,…} • b divides a (or b is a divisor of a) if a = mb for some m – denoted b|a – any b ≠ 0 divides 0 • For any a, 1 and a are trivial divisors of a – all other divisors of a are called factors of a Computer Science CSC/ECE 574 Dr. Peng Ning 5 Primes and Factors • a is prime if it has no non-trivial factors – examples: 2, 3, 5, 7, 11, 13, 17, 19, 31,… • Theorem: there are infinitely many primes • Any integer a > 1 can be factored in a unique way as p1a1 • p2a2 • … ptat – where all p1>p2>…>pt are prime numbers and where each ai > 0 Examples: 91 = 131×71 11011 = 131 ×112 ×71 Computer Science CSC/ECE 574 Dr. Peng Ning 6 Common Divisors • A number d that is a divisor of both a and b is a common divisor of a and b • If d|a and d|b, then d|(a+b) and d|(a-b) • If d|a and d|b, then d|(ax+by) for any integers x and y Example: common divisors of 30 and 24 are 1, 2, 3, 6 Example: Since 3 | 30 and 3 | 24 , 3 | (30+24) and 3 | (30-24) Example: 3 | 30 and 3 | 24  3 | (2*30 + 6*24)Computer Science CSC/ECE 574 Dr. Peng Ning 7 Greatest Common Divisor (GCD) • gcd(a,b) = max{k | k|a and k|b} • Observations – gcd(a,b) = gcd(|a|, |b|) – gcd(a,b) ≤ min(|a|, |b|) – if 0 ≤ n, then gcd(an, bn) = n*gcd(a,b) • For all positive integers d, a, and b… …if d | ab …and gcd(a,d) = 1 …then d|b Example: gcd(60,24) = 12, gcd(a,0) = a Computer Science CSC/ECE 574 Dr. Peng Ning 8 GCD (Cont’d) • Computing GCD by hand: if a = p1a1 p2a2 … prar and b = p1b1 p2b2 … prbr , …where p1 < p2 < … < pr are prime, …and ai and bi are nonnegative, …then gcd(a, b) = p1 min(a1, b1) p2 min(a2, b2) … pr min(ar, br) ⇒ Slow way to find the GCD - requires factoring a and b first (which, as we will see, can be slow) Computer Science CSC/ECE 574 Dr. Peng Ning 9 Euclid’s Algorithm for GCD • Insight: gcd(x, y) = gcd(y, x mod y) • Procedure euclid(x, y): r[0] = x, r[1] = y, n = 1; while (r[n] != 0) { n = n+1; r[n] = r[n-2] % r[n-1]; } return r[n-1]; Computer Science CSC/ECE 574 Dr. Peng Ning 10 Example n rn 0 595 1 408 2 595 mod 408 = 187 3 408 mod 187 = 34 4 187 mod 34 = 17 5 34 mod 17 = 0 gcd(595,408) = 17 Computer Science CSC/ECE 574 Dr. Peng Ning 11 Running Time • Running time is logarithmic in size of x and y • Worst case occurs when ??? Enter x and y: 102334155 63245986 Step 1: r[i] = 39088169 Step 2: r[i] = 24157817 Step 3: r[i] = 14930352 Step 4: r[i] = 9227465 … Step 35: r[i] = 3 Step 36: r[i] = 2 Step 37: r[i] = 1 Step 38: r[i] = 0 gcd of 102334155 and 63245986 is 1 Computer Science CSC/ECE 574 Dr. Peng Ning 12 Extended Euclid’s Algorithm • Let LC(x,y) = {ux+vy : x,y ∈ Z} be the set of linear combinations of x and y • Theorem: if x and y are any integers > 0, then gcd(x,y) is the smallest positive element of LC(x,y) • Euclid’s algorithm can be extended to compute u and v, as well as gcd(x,y) • Procedure exteuclid(x, y): (next page…)Computer Science CSC/ECE 574 Dr. Peng Ning 13 Extended Euclid’s Algorithm r[0] = x, r[1] = y, n = 1; u[0] = 1, u[1] = 0; v[0] = 0, v[1] = 1; while (r[n] != 0) { n = n+1; r[n] = r[n-2] % r[n-1]; q[n] = (int) (r[n-2] / r[n-1]); u[n] = u[n-2] – q[n]*u[n-1]; v[n] = v[n-2] – q[n]*v[n-1]; } return r[n-1], u[n-1], v[n-1]; floor function Exercise: Show r[n]=u[n]x+v[n]y Computer Science CSC/ECE 574 Dr. Peng Ning 14 Extended Euclid’s Example n qn rn un vn 0 - 595 1 0 1 - 408 0 1 2 1 187 1 -1 3 2 34 -2 3 4 5 17 11 -16 5 2 0 -24 35 gcd(595,408) = 17 = 11*595 + -16*408 Computer Science CSC/ECE 574 Dr. Peng Ning 15 Extended Euclid’s Example n qn rn un vn 0 - 99 1 0 1 - 78 0 1 2 3 4 5 6 gcd(99,78) = 3 = -11*99 + 14*78 Computer Science CSC/ECE 574 Dr. Peng Ning 16 Relatively Prime • Integers a and b are relatively prime iff gcd(a,b) = 1 – example: 8 and 15 are relatively prime • Integers n1,n2,…nk are pairwise relatively prime if gcd(ni,nj) = 1 for all i ≠ j Computer Science CSC/ECE 574 Dr. Peng Ning 17 Review of Modular Arithmetic Computer Science CSC/ECE 574 Dr. Peng Ning 18 Remainders and Congruency • For any integer a and any positive integer n, there are two unique integers q and r, such that 0 ≤ r < n and a = qn + r – r is the remainder of division by n, written r = a mod n • a and b are congruent modulo n, written a ≡ b mod n, if a mod n = b mod n Example: 12 = 2*5 + 2  2 = 12 mod 5 Example: 7 mod 5 = 12 mod 5  7 ≡ 12 mod 5Computer Science CSC/ECE 574 Dr. Peng Ning 19 Negative Numbers • In modular arithmetic, …a negative number a is usually replaced by the congruent number b mod n, …where b is the smallest non-negative number …such that b = a + m*n Example: -3 ≡ 4 mod 7 Computer Science CSC/ECE 574 Dr. Peng Ning 20 Remainders (Cont’d) • For any positive integer n, the integers can be divided into n equivalence classes according to their remainders modulo n – denote the set as Zn • i.e., the (mod n) operator maps all integers into the set of integers Zn={0, 1, 2, …, (n-1)} Computer Science CSC/ECE 574 Dr. Peng Ning 21 Modular Arithmetic • Modular addition – [(a mod n) + (b mod n)] mod n = (a+b) mod n • Modular subtraction – [(a mod n) – (b mod n)] mod n = (a – b) mod n • Modular multiplication – [(a mod n) × (b mod n)] mod n = (a × b) mod n Example: [16 mod 12 + 8 …