RSA Cryptosystem with p=11 and q=7

RSA is an asymmetric encryption algorithm where the public key is used for encryption and the private key for decryption, based on the difficulty of factoring large prime numbers.

---

Given:

• $p = 11$, $q = 7$

Step A: Compute n and φ(n)

$$n = p \times q = 11 \times 7 = 77$$

$$\phi(n) = (p-1)(q-1) = 10 \times 6 = 60$$

---

i. Public Key Pair (e, n)

Choose e such that:

• $1 < e < \phi(n)$
• $\gcd(e, \phi(n)) = 1$ (e must be coprime with 60)

Let's try $e = 7$:

$$\gcd(7, 60) = 1 \quad$$

Public Key = (e, n) = (7, 77)

---

ii. Private Key Pair (d, n)

Find d such that:

$$d \times e \equiv 1 \pmod{\phi(n)}$$

$$d \times 7 \equiv 1 \pmod{60}$$

We need to find multiplicative inverse of 7 mod 60.

Using Extended Euclidean Algorithm:

• $60 = 8 \times 7 + 4$
• $7 = 1 \times 4 + 3$
• $4 = 1 \times 3 + 1$
• $3 = 3 \times 1 + 0$

Back substitution:

• $1 = 4 - 1 \times 3$
• $1 = 4 - 1 \times (7 - 1 \times 4) = 2 \times 4 - 1 \times 7$
• $1 = 2 \times (60 - 8 \times 7) - 1 \times 7 = 2 \times 60 - 17 \times 7$

So $d = -17 \equiv 60 - 17 = 43 \pmod{60}$

Verification: $43 \times 7 = 301 = 5 \times 60 + 1 \equiv 1 \pmod{60}$

Private Key = (d, n) = (43, 77)

---

iii. Ciphertext for M = 6

Encryption formula:

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

$$C = 6^7 \mod 77$$

Computing step by step:

• $6^1 = 6$
• $6^2 = 36$
• $6^4 = 36^2 = 1296 \mod 77 = 1296 - 16 \times 77 = 1296 - 1232 = 64$
• $6^7 = 6^4 \times 6^2 \times 6^1 = 64 \times 36 \times 6$

Now:

• $64 \times 36 = 2304 \mod 77 = 2304 - 29 \times 77 = 2304 - 2233 = 71$
• $71 \times 6 = 426 \mod 77 = 426 - 5 \times 77 = 426 - 385 = 41$

Ciphertext C = 41

---

Summary Table

Parameter	Value
n	77
φ(n)	60
Public Key (e, n)	(7, 77)
Private Key (d, n)	(43, 77)
Plaintext M	6
Ciphertext C	41

---

Conclusion: RSA security relies on the difficulty of factoring $n$ back into $p$ and $q$. The public key encrypts the message, and only the holder of the private key can decrypt it.