MATH135 Lecture Notes - Lecture 2: Chinese Remainder Theorem, Extended Euclidean Algorithm, Encryption

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Robert Hill

Document Summary

Without the help of a computer (or a calculator), solve the following problems (a) if p = 211, q = 241 and e = 67, find the associated rsa public and private keys. Given e = 67, then we want to solve for d z such that. We convert the given linear congruence into the corresponding linear diophantine equation and use the extended euclidean algorithm to solve for d: 50400(21) + 67( 15795) = 1, that is, 67( 15795) 1 (mod 50400). As gcd(67, 50400) = 1 by assumption, therefore the unique solution to 67d 1 (mod 50400) is given by d ( 15797) 34603 (mod 50400). Therefore, the public key is (e, n) = (67, 50851) and the private key is (d, n) = (34603, 50851). (b) in an rsa scheme, the private key is (d; n) = (871; 1147). Remainder theorem, decrypt the ciphertext c = 765 using the key.