CryptographyandNetworkSecurity(CS435).ppt

Cryptography and Network Security(CS435) Part Five (Math Backgrounds) Modular Arithmetic define modulo operator “a mod n” to be remainder when a is divided by n use the term congruence for: a = b mod n when divided by n, a b have same remainder eg. 100 = 34 mod 11 b is called a residue of a mod n since with integers can always write: a = qn + b usually chose smallest positive remainder as residue ie. 0 = b = n-1 process is known as modulo reduction eg. -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7 Divisors say a non-zero number b divides a if for some m have a=mb (a,b,m all integers) that is b divides into a with no remainder denote this b|a and say that b is a divisor of a eg. all of 1,2,3,4,6,8,12,24 divide 24 Modular Arithmetic Operations is clock arithmetic uses a finite number of values, and loops back from either end modular arithmetic is when do addition multiplication and modulo reduce answer can do reduction at any point, ie a+b mod n = [a mod n + b mod n] mod n Modular Arithmetic can do modular arithmetic with any group of integers: Zn = {0, 1, … , n-1} form a commutative ring for addition with a multiplicative identity note some peculiarities if (a+b)=(a+c) mod n then b=c mod n but if (a.b)=(a.c) mod n then b=c mod n only if a is relatively prime to n Modulo 8 Addition Example Greatest Common Divisor (GCD) a common problem in number theory GCD (a,b) of a and b is the largest number that divides evenly into both a and b eg GCD(60,24) = 12 often want no common factors (except 1) and hence numbers are relatively prime eg GCD(8,15) = 1 hence 8 15 are relatively prime Euclidean Algorithm an efficient way to find the GCD(a,b) uses theorem that: GCD(a,b) = GCD(b, a mod b) Euclidean Algorithm to compute GCD(a,b) is: EUCLID(a,b) 1. A = a; B = b 2. if B = 0 return A = gcd(a, b) 3. R = A mod B 4. A = B 5. B = R 6. goto 2 Example GCD(1970,1066) 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94