Fundamentals of Modular Arithmetic and Cryptography

Mathematics of Cryptography 1  CHAPTER-3

• 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 Where,n is called modulus and r is called residue Modular Arithmetic a mod n = r

• Let a,n and r are three numbers and Z is a set of integers then How mod operator works Z={……,-2,-1,0,1,2,3,4,………….} mod a n (Positive) 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 Z n and is defined as follow Z n = {0,1,2,…..n-1} Example :1. Z 2  = {0,1} 2. Z 6 = {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 Z n (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 modulo n 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 Z n • Operations in Z n The three binary operations(addition, Subtraction and Multiplication)  can be defined for the set of Z n. • The result may need to be mapped to Z n using the mod operator. Z n +   ,     - ,* mod Z n  ={0,1,2,…(n-1)} a b n c (a+b)mod n=c (a-b)mod n=c (a*b)mod n=c Operations :

Operations in Z n • Example: 1. Add 7 to 14 in Z 15 2. Subtract 11 from 7 in Z 13 3. Multiply 11 by 7 in Z 20 4. Multiply 123 by -10 in Z 19 • 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 Z n • Properties: 1. First Property :          (a+b) mod n=[(a mod n)+(b mod n)]   mod n 2. Second Property:     (a-b) mod n = [(a mod n) – (b mod n)] mod n 3. Third Property:         (a*b) mod n =[(a mod n)*(b mod n)]   mod n NOTE :1. 10 n mod x = (10 mod x) n // Applying the third property n times 2. a mod 3     =(a n +……..+ a 1 + a 0 ) mod 3

Inverse • Inverse Inverse Additive Inverse Multiplicative  Inverse

Additive Inverse • Additive Inverse In Z n two number’s a and b are additive inverse to each other if a+b ≅ 0(mod n) • In  Z n  , 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 Z 10 is 10-4=6 2. All additive Inverse pair in Z 10 are (0,0),(1,9),(2,8)(3,7)(4,6) and (5,5)

Multiplicative Inverse • Multiplicative Inverse In Z n 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 Z n if and only if gcd(n,a)=1 i.e. a and n  are relatively prime. Example :1. All multiplicative Inverse pair in Z 11 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 Z n when  n and b is given and the inverse of b exist in Z n. 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 Z n when n  and  b are given and GCD(n,b)=1 Algorithm : 1. r 1 = a; r 2  = b; 2. t 1  = 0; t 2 =  1; 3. While(r 2  > 0){ 4. q=r 1   / r 2; 5. r= r 1  - q* r 2 6. r 1 = r 2 ;  r 2 =r; 7. t= t 1  - q* t 2 8. t 1 = t 2 ;  t 2 =t; 9. }10. if(r 1 = 1) the b -1 = t 1

Extended Euclidean Algo for Multiplicative Inverse • Example : 1. Calculate Multiplicative Inverse of 11 in Z 26 r 1 = 26          r 2 = 11 So multiplicative inverse of 11 = -7+26=19 q r 1 r 2 r t 1 t 2 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

Extended Euclidean Algo for Multiplicative Inverse • Example : 1. Calculate Multiplicative Inverse of 23 in Z 100 r 1 = 100          r 2 = 23 So multiplicative inverse of 23 = -13+100=87 q r 1 r 2 r t 1 t 2 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

Extended Euclidean Algo for Multiplicative Inverse • Example : 1. Calculate Multiplicative Inverse of 12 in Z 26 r 1 = 26          r 2 = 12 So multiplicative inverse of 12 in Z 26  does not exist since  GCD(12,26) is  not 1. q r 1 r 2 r t 1 t 2 t 2 26 12 2 0 1 -2 6 12 2 0 1 -2 13 2 0 -2 13