Suppose you are a cyptanalyst and you have intercepted a ciphertext c = 4 that has been sent to Alice. You find Alice’s RSA public key in a key directory: (e, n) = (5, 247). You assume this key has been used to produce the ciphertext. Find Alice’s private key. Show all your working.

To find Alice's private key, we need to use the RSA encryption and decryption formula:

Encryption: c = m^e mod n
Decryption: m = c^d mod n

We know the ciphertext c = 4 and the public key (e, n) = (5, 247). We need to find the private key d.

To find d, we need to use the following formula:
d = e^-1 mod φ(n)

where φ(n) = (p-1)(q-1) is the Euler's totient function of n and p and q are prime factors of n.

To find p and q, we need to factorize n. Since n is relatively small, we can do this manually:
n = 247 = 13 * 19

Now we can calculate φ(n):
φ(n) = (p-1)(q-1) = (13-1)(19-1) = 12 * 18 = 216

To find the inverse of e modulo φ(n), we can use the extended Euclidean algorithm:

φ(n) = 216
e = 5

216 = 5 * 43 + 1
1 = 216 - 5 * 43

1 = 216 - 5 * (φ(n) - e * q)
1 = 5 * e * (-43) + φ(n) * 1

Therefore, d = -43 mod 216 = 173

Now we can use the decryption formula to find the plaintext m:
m = c^d mod n = 4^173 mod 247 = 25

Therefore, Alice's private key is d = 173 and the plaintext message is m = 25.