---
title: "RSA algorithm with example"
subject: "Computer Networks and Security"
chapter: 8
key: "semester_7/computer_networks_and_security:rsa-algorithm-explain"
source: https://www.bctengineer.com/q/semester_7/computer_networks_and_security/rsa-algorithm-explain
site: BCT Engineering
---

# RSA algorithm with example

Computer Networks and Security · Chapter 8: Network Security

- Asked in: 2073 Shrawan, 5 marks; 2073 Chaitra, 4 marks; 2071 Chaitra, 6 marks; 2069 Chaitra, 4 marks (asked 4 times)
- Video: [Lec-92: RSA Algorithm in Network Security with examples in Hindi rsa algorithm example in hindi](https://www.youtube.com/watch?v=VUxfDCmWM0U) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/computer_networks_and_security/rsa-algorithm-explain
- Whole chapter: https://www.bctengineer.com/md/semester_7/computer_networks_and_security/chapter-8

## Question

Explain the RSA algorithm (operation and steps) with example.

## Short answer

RSA uses public key (e,n) and private key (d,n). Key generation: n=pq, choose e coprime to φ(n), compute d=e⁻¹ mod φ(n). Example p=7,q=13: public key (5,91), private key (29,91); ciphertext 81 for M=9, decrypted back to 9.

## Answer

**RSA** (Rivest-Shamir-Adleman, 1977) is a public-key (asymmetric) cryptosystem. It uses a pair of keys: a **public key** (e, n) to encrypt and a **private key** (d, n) to decrypt. Its security depends on the difficulty of factoring a large number n = p × q into its primes.

#### Algorithm
**Key generation**
1. Choose two large distinct primes p and q.
2. Compute n = p × q.
3. Compute φ(n) = (p − 1)(q − 1).
4. Choose e with 1 < e < φ(n) and gcd(e, φ(n)) = 1.
5. Compute d such that d × e ≡ 1 (mod φ(n)).
6. Public key = (e, n); private key = (d, n).

**Encryption:** C = Mᵉ mod n (M < n)
**Decryption:** M = Cᵈ mod n

#### Example
Take p = 7, q = 13.

| Step | Calculation | Result |
|---|---|---|
| n | 7 × 13 | 91 |
| φ(n) | (7 − 1)(13 − 1) = 6 × 12 | 72 |
| e | choose e = 5, gcd(5, 72) = 1 | 5 |
| d | 5 × d ≡ 1 mod 72; 5 × 29 = 145 = 2 × 72 + 1 | 29 |

Public key = (5, 91), private key = (29, 91).

Encrypt M = 9: C = 9⁵ mod 91. 9^1 = 9, 9^2 = 81, 9^4 = 9 (all mod 91); 5 = 1 + 4, so 9^5 = 9 × 9 mod 91 = 81.
**C = 81**.

Decrypt: M = 81²⁹ mod 91. 81^1 = 81, 81^2 = 9, 81^4 = 81, 81^8 = 9, 81^16 = 81 (all mod 91); 29 = 1 + 4 + 8 + 16, so 81^29 = 81 × 81 × 9 × 81 mod 91 = 9.
**M = 9**, the original message.

```text
Sender: M=9 --(e=5,n=91)--> C=81 ----> Receiver: C=81 --(d=29,n=91)--> M=9
```

**Answer: public key (5, 91), private key (29, 91); ciphertext 81; decrypted message 9.**

#### Notes
- Real RSA uses primes of 1024 bits or more (n of 2048 bits).
- Used for key exchange and digital signatures (sign with the private key, verify with the public key).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does RSA security depend on?
   A. A shared secret key
   B. Secrecy of n
   C. Short keys
   D. Difficulty of factoring n = p x q for large primes
   Answer: D. Factoring a large n into its primes is hard. (Key point: Security basis)

2. How is the private exponent d found?
   A. d = e + phi(n)
   B. d = p x q
   C. d x e = 1 (mod phi(n))
   D. d x e = 1 (mod n)
   Answer: C. d is the inverse of e modulo phi(n) = (p-1)(q-1). (Key point: Choosing d)

3. For p = 7, q = 13, e = 5, what are n, phi(n) and d?
   A. 91, 72, 5
   B. 91, 84, 29
   C. 91, 72, 29
   D. 20, 72, 29
   Answer: C. n = 91, phi = 6 x 12 = 72, and 5 x 29 = 145 = 2 x 72 + 1 so d = 29. (Key point: Example key)

4. With public key (5, 91) the message M = 9 gives which ciphertext?
   A. 45
   B. 9
   C. 29
   D. 81
   Answer: D. 9^2 = 81 and 9^4 = 9 mod 91, so 9^5 = 9 x 9 = 81. (Key point: Encryption)

## Related in Computer Networks and Security

- [RSA steps; encrypt word CAT](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Arsa-steps-encrypt-cat) — Computer Networks and Security, chapter 8
- [RSA encrypt/decrypt OVEL](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Arsa-encrypt-ovel) — Computer Networks and Security, chapter 8
- [Data Encryption Standard operation](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Ades-algorithm) — Computer Networks and Security, chapter 8

## Related in other subjects

- [Genetic algorithm and operators](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Agenetic-algorithm-operators) — Artificial Intelligence, chapter 6, asked 4×
- [N-R load flow corrections and algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Anr-load-flow-derivation) — Power System Analysis II, chapter 2, asked 2×
- [Huffman code tree steps with example](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-code-tree-steps) — Multimedia System, chapter 5, asked 7×
- [Merge sort algorithm and trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-algorithm-trace) — Data Structure and Algorithm, chapter 7