Alice wants to send a plaintext message 𝑚 = 13 to Bob secretly using RSA public key
cryptosystem. Bob selects 𝑝 = 13, and 𝑞 = 11 with 𝑒 = 13. You have to perform following tasks:
a. Compute and list Bob’s public and private keys.
b. Compute the ciphertext that Alice will send to Bob using plaintext message 𝑚 = 13.
c. Recover the actual plaintext from the ciphertext sent by Alice.


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.

Alice wants to send a plaintext message m = 13 to Bob secretly using RSA public key cryptosystem. Bob selects p = 13, and q = 11 with e = 13. You have to perform the following tasks: a. Compute and list Bob’s public and private keys. b. Compute the ciphertext that Alice will send to Bob using plaintext message m = 13. c. Recover the actual plaintext from the ciphertext sent by Alice.

Discover how to use RSA cryptography to send encrypted messages. Learn to compute Bob’s public and private keys using prime numbers p = 13 and q = 11, encrypt a message with the RSA algorithm, and decrypt the ciphertext to recover the original message. This step-by-step solution is ideal for cryptography students.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation