Let's walk through the steps to solve the problem using RSA public key cryptosystem.

a. Compute Bob’s public and private keys

1. Choose the prime numbers:

   • $p = 13$
   • $q = 11$

2. Compute $n$ (the product of $p$ and $q$): $n = p \times q = 13 \times 11 = 143$

3. Compute $\phi(n)$ (Euler’s totient function): $\phi(n) = (p - 1)(q - 1) = (13 - 1)(11 - 1) = 12 \times 10 = 120$

4. Public exponent $e$:

   • Given $e = 13$, and it needs to satisfy $\gcd(e, \phi(n)) = 1$.
   • Since $\gcd(13, 120) = 1$, 13 is valid.

5. Private key $d$:

   • To find $d$, we need the modular inverse of $e$ modulo $\phi(n)$, i.e., $d \equiv e^{-1} \mod \phi(n)$.

   Using the Extended Euclidean Algorithm, we solve for $d$: $13d \equiv 1 \mod 120$ The solution is $d = 37$ (since $13 \times 37 = 481 \equiv 1 \mod 120$).

   So, Bob's private key is $d = 37$.

• Bob's public key: $(e, n) = (13, 143)$
• Bob's private key: $(d, n) = (37, 143)$

b. Compute the ciphertext that Alice will send to Bob using plaintext $m = 13$

1. Plaintext: $m = 13$

2. Ciphertext is calculated using the formula $c \equiv m^e \mod n$: $c \equiv 13^{13} \mod 143$ We can compute $13^{13} \mod 143$ step by step using modular exponentiation:

   • $13^2 \mod 143 = 169 \mod 143 = 26$
   • $13^4 \mod 143 = (13^2)^2 \mod 143 = 26^2 \mod 143 = 676 \mod 143 = 94$
   • $13^8 \mod 143 = (13^4)^2 \mod 143 = 94^2 \mod 143 = 8836 \mod 143 = 113$

   Then: $13^{13} = 13^8 \times 13^4 \times 13 \mod 143 = 113 \times 94 \times 13 \mod 143$ First, $113 \times 94 = 10622 \mod 143 = 49$. Now compute: $49 \times 13 = 637 \mod 143 = 65$ So, the ciphertext is $c = 65$.

c. Recover the actual plaintext from the ciphertext sent by Alice

To decrypt the ciphertext, we use Bob's private key $d = 37$ and compute: $m \equiv c^d \mod n$ That is: $m \equiv 65^{37} \mod 143$ We will use modular exponentiation to compute this efficiently:

• $65^2 \mod 143 = 4225 \mod 143 = 80$
• $65^4 \mod 143 = (65^2)^2 \mod 143 = 80^2 \mod 143 = 6400 \mod 143 = 101$
• $65^8 \mod 143 = (65^4)^2 \mod 143 = 101^2 \mod 143 = 10201 \mod 143 = 35$
• $65^{16} \mod 143 = (65^8)^2 \mod 143 = 35^2 \mod 143 = 1225 \mod 143 = 83$
• $65^{32} \mod 143 = (65^{16})^2 \mod 143 = 83^2 \mod 143 = 6889 \mod 143 = 31$

Now we can combine these powers of 65: $65^{37} = 65^{32} \times 65^4 \times 65 \mod 143 = 31 \times 101 \times 65 \mod 143$ First, compute $31 \times 101 = 3131 \mod 143 = 137$, and then: $137 \times 65 = 8905 \mod 143 = 13$

So, the recovered plaintext is $m = 13$.

Summary of Results:

• Public key: $(e = 13, n = 143)$
• Private key: $(d = 37, n = 143)$
• Ciphertext: $65$
• Recovered plaintext: $13$

Do you need further details or have any questions?

---

Here are 5 related questions to extend your understanding:

1. What would happen if $\gcd(e, \phi(n)) \neq 1$?
2. How would the encryption process differ with larger prime numbers for $p$ and $q$?
3. Can RSA encryption be applied to larger messages, and if so, how?
4. How does the Extended Euclidean Algorithm find the modular inverse in RSA?
5. What are potential weaknesses in the RSA algorithm, and how can they be mitigated?

Tip: In RSA, choosing large prime numbers makes the encryption more secure, as factoring large numbers becomes more difficult.