RSA with p = 11, q = 13 and e = 7. Compute n, phi(n) and the private exponent d, then encrypt m = 9 and verify the decryption. Show the modular inverse working.

RSA with p = 11, q = 13 and e = 7. Compute n, phi(n) and the private exponent d, then encrypt m = 9 and verify the decryption. Show the modular inverse working.

Approach: Form n and phi(n) from the two primes, invert e modulo phi(n) with the extended Euclidean algorithm, then exponentiate by repeated squaring.

d = 103. n = 11 * 13 = 143 and phi(n) = 10 * 12 = 120. To find d, invert 7 modulo 120 using the extended Euclidean algorithm: 120 = 17 * 7 + 1, so 1 = 120 - 17 * 7, giving -17 * 7 ≡ 1 mod 120 and d = -17 + 120 = 103. Check: 7 * 103 = 721 = 6 * 120 + 1, so the inverse is right. Encrypting m = 9 needs the exponentiation c = 9^7 mod 143. By repeated squaring, 9^2 = 81, 9^4 = 81^2 = 6561 = 45 * 143 + 126, so 9^4 ≡ 126 ≡ -17 mod 143. Then 9^7 = 9^4 * 9^2 * 9 ≡ (-17) * 81 * 9 mod 143. First (-17) * 81 = -1377, and 1377 = 9 * 143 + 90, so -1377 ≡ -90 ≡ 53 mod 143. Then 53 * 9 = 477 = 3 * 143 + 48, so c = 48. Decrypting, 48^103 mod 143 returns 9, which follows from Euler's theorem since m^(ed) = m^(1 + k*phi(n)) ≡ m mod n whenever gcd(m, n) = 1, and gcd(9, 143) = 1.

Follow-up: Take p = 11, q = 13 and e = 5 instead. What goes wrong and what does that tell you about choosing e?

Key concepts: modular inverse, euler totient, rsa, exponentiation.