RSA Encryption and Decryption

RSA is an asymmetric encryption algorithm where encryption is done using the receiver's public key and decryption using the receiver's private key, based on the mathematical difficulty of factoring large prime numbers.

---

How Encryption and Decryption is Done in RSA

Key Generation:

• Choose two large prime numbers p and q
• Compute $n = p \times q$
• Compute Euler's totient: $\phi(n) = (p-1)(q-1)$
• Choose public key e such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$
• Compute private key d such that $e \times d \equiv 1 \pmod{\phi(n)}$

Encryption:

• Sender obtains receiver's public key (e, n)
• Plaintext message M is converted to integer (where $M < n$)
• Ciphertext is computed as:

$$C = M^e \mod n$$

Decryption:

• Receiver uses their private key (d, n)
• Plaintext is recovered as:

$$M = C^d \mod n$$

---

Numerical Solution

Given: Public key = (e, n) = (3, 55)

Step A: Find private key d

Since $n = 55$, we find p and q:

• $n = p \times q = 5 \times 11 = 55$
• So p = 5, q = 11

Compute Euler's totient:

$$\phi(n) = (p-1)(q-1) = (5-1)(11-1) = 4 \times 10 = 40$$

Find d such that $e \times d \equiv 1 \pmod{\phi(n)}$:

$$3 \times d \equiv 1 \pmod{40}$$

We need $d$ such that $3d \mod 40 = 1$

• Try $d = 27$: $3 \times 27 = 81 = 2 \times 40 + 1$ ✓

Private key d = 27

---

Step B: Find Ciphertext for M = "hi"

Convert characters to numeric values (using position: a=1, b=2, ... h=8, i=9):

• h = 8, i = 9

Encrypt 'h' (M = 8):

$$C_1 = 8^3 \mod 55 = 512 \mod 55$$

$512 \div 55 = 9$ remainder $17$

$$C_1 = 17$$

Encrypt 'i' (M = 9):

$$C_2 = 9^3 \mod 55 = 729 \mod 55$$

$729 \div 55 = 13$ remainder $14$

$$C_2 = 14$$

---

Final Answer

Item	Value
Private key d	27
Ciphertext for 'h'	17
Ciphertext for 'i'	14
Ciphertext C	17, 14

---

Conclusion: RSA's security relies on the difficulty of factoring large numbers. The public key (e, n) encrypts data, while only the holder of private key (d) can decrypt it, making it ideal for secure communication and digital signatures.