Fundamentals of Modular Arithmetic and Cryptography

CHAPTER-3 Mathematics of Cryptography 1 Modular Arithmetic • In Modular Arithmetic, we are interested in only one of the output(q i.e. quotient and r i.e. remainder)i.e. remainder r. • Modulo operator is represented as mod or %. It takes two input let say a and n, where n is called modulus. The output r is called the residue • Let a ,n and r are three numbers then the mod operation can be represented as a mod n = r Where, n is called modulus and r is called residue How mod operator works • Let a,n and r are three numbers and Z is a set of integers then Z={……,-2,-1,0,1,2,3,4,………….} a n (Positive) mod r(Non Negative) Modular Arithmetic • Example : 1. 27 mod 5=2 2. -18 mod 14=10 3. 25 mod 3=1 Set of Residue • Set of Residue : Represented by Zn and is defined as follow Zn = {0,1,2,…..n-1} Example : 1. Z2 = {0,1} 2. Z6 = {0,1,2,3,4,5} • In Cryptography we used concept of Congruence instead of equality. It is represented by symbol (≅) b≅ a(modn) Diff b/w Equality and Congruence Operator • Difference b/w Equality and congruence operator 1. An equality operator maps a member of Z(Set of Integers)to itself, but the congruence operator maps a number from Z to a member of Zn(Set of Residue). 2. Equality operator is One to One. The congruence operator is many to one. • Residue Classes A residue class [a] or [a]n is the set of integers congruent modulon i.e. it is the set of all integers such that x=a(mod n) Example : If n=5, we have five sets [0],[1],[2],[3],[4] Operations in Zn • Operations in Zn The three binary operations(addition, Subtraction and Multiplication) can be defined for the set of Zn. • The result may need to be mapped to Zn using the mod operator. Zn a b + , n - ,* mod c Zn ={0,1,2,…(n-1)} Operations : (a+b)mod n=c (a-b)mod n=c (a*b)mod n=c Operations in Zn • Example: 1. Add 7 to 14 in Z15 2. Subtract 11 from 7 in Z13 3. Multiply 11 by 7 in Z20 4. Multiply 123 by -10 in Z19 • Solution : 1. (14+7) mod 15 = 21 mod 15 = 6 Ans. 2. (7-11) mod 13 = (-4) mod 13=9 Ans. 3. (7*11) mod 20 = (77) mod 20=17 Ans. 4. (123*(-10)) mod 19 = (-1230) mod 19 = 5 Ans. Operations in Zn • Properties: 1. First Property : 2. Second Property: 3. Third Property: (a+b) mod n=[(a mod n)+(b mod n)] mod n (a-b) mod n = [(a mod n) – (b mod n)] mod n (a*b) mod n =[(a mod n)*(b mod n)] mod n NOTE : 1. 10n mod x = (10 mod x)n // Applying the third property n times 2. a mod 3 =(an +……..+ a1 + a0) mod 3 Inverse • Inverse Inverse Additive Inverse Multiplicative Inverse Additive Inverse • Additive Inverse In Zn two number’s a and b are additive inverse to each other if a+b ≅0(mod n) • In Zn , additive inverse of a can be calculated as b=n-a • In modular arithmetic, each integer has an additive inverse • The sum of an integer and its additive inverse is congruent to 0 modulus n • Additive inverse are reciprocal i.e. if a is additive inverse of b then b is additive inverse of a Example : 1. Additive Inverse of 4 in Z10 is 10-4=6 2. All additive Inverse pair in Z10 are (0,0),(1,9),(2,8)(3,7)(4,6) and (5,5) Multiplicative Inverse • Multiplicative Inverse In Zn two number’s a and b are multiplicative inverse to each other if a*b ≅1(mod n) • In modular arithmetic, an integer may or may not have a multiplicative inverse • A number a has multiplicative inverse in Zn if and only if gcd(n,a)=1 i.e. a and n are relatively prime. Example : 1. All multiplicative Inverse pair in Z11 are (1,1),(2,6),(3,4)(5,9)(7,8),(9,9) and (10,10) Extended Euclidean Algo for Multiplicative Inverse • Extended Euclidean algorithm for Multiplicative Inverse 1. Extended Euclidean algorithm can find multiplicative inverse of b in Zn when n and b is given and the inverse of b exist in Zn. 2. By extended Euclidean algorithm to calculate GCD(n,b) S*n+b*t=GCD(n,b) 3. Multiplicative inverse will exist only if GCD(n,b)=1 so, S*n+b*t=1 4. Taking (mod n) both side (S*n+b*t)mod n=1 mod n [(S*n)mod n]+[(b*t)mod n]=1 mod n 0+[(b*t)mod n] = 1 mod n (b*t) mod n = 1 Extended Euclidean Algo for Multiplicative Inverse • That means t is multiplicative inverse of b NOTE : 1. Extended Euclidean Algorithm finds multiplicative inverse of b in Zn when n and b are given and GCD(n,b)=1 Algorithm : 1. 2. 3. 4. 5. 6. 7. r1 = a; r2 = b; t1 = 0; t2 = 1; While(r2 > 0){ q=r1 / r2; r= r1 - q* r2 r1 = r2; r2 =r; t= t1 - q* t2 8. t1 = t2; t2 =t; 9. } 10. if(r1 = 1) the b-1 = t1 Extended Euclidean Algo for Multiplicative Inverse • Example : 1. Calculate Multiplicative Inverse of 11 in Z26 r1 = 26 r2 = 11 q r1 r2 r t1 t2 t 2 26 11 4 0 1 -2 2 11 4 3 1 -2 5 1 4 3 1 -2 5 -7 3 3 1 0 5 -7 26 1 0 -7 26 So multiplicative inverse of 11 = -7+26=19 Extended Euclidean Algo for Multiplicative Inverse • Example : 1. Calculate Multiplicative Inverse of 23 in Z100 r1 = 100 r2 = 23 q r1 r2 r t1 t2 t 4 100 23 8 0 1 -4 2 23 8 7 1 -4 19 1 8 7 1 -4 9 -13 7 7 1 0 9 -13 100 1 7 -13 100 So multiplicative inverse of 23 = -13+100=87 Extended Euclidean Algo for Multiplicative Inverse • Example : 1. Calculate Multiplicative Inverse of 12 in Z26 r1 = 26 r2 = 12 q r1 r2 r t1 t2 t 2 26 12 2 0 1 -2 6 12 2 0 1 -2 13 2 0 -2 13 So multiplicative inverse of 12 in Z26 does not exist since GCD(12,26) is not 1.