Lecture 5 Notes; April 9, 1997; Notetaker: Christina Chang Modular Arithmetic: * solve ax mod n = 1 by the Extended Euclidean algorithm Note a*x + n*y = g at each step e.g. to solve 5x mod 7 = 1: g=gcd(5,7); a = 5, n = 7 g x y q a*x + n*y 7 0 1 5*0 + 7*1 = 7 5 1 0 1 5*1 + 7*0 = 5 2 -1 1 2 5*(-1)+7*1 = 2 1 3 -2 2 5*3 + 7*(-2) = 1 0 so x = 3 * solve x in: ax mod n = b if we can find x0 s.t. ax0 mod n = 1, then we have a(x0b mod n) = b thus x = x0b is the solution Cipher: * transposition cipher: diffusion effect (suggested by Shannon) can be detected by frequency count (digram, trigram etc.) * substitution cipher: confusion effect (suggested by Shannon) simple substitution: one mapping applied to all components e.g. Caesar cipher Mathematically, f(m)=(m+k) mod 26 where k is the key is an affine transformation: f(m)=(km + k') mod n where gcd(k,n) = 1 can be attacked by comparing the shift with frequency distribution of normal English text (example given in handout) * homophonic substitution multiple mapping for each character/symbol