---
title: "RSA steps; encrypt word CAT"
subject: "Computer Networks and Security"
chapter: 8
key: "semester_7/computer_networks_and_security:rsa-steps-encrypt-cat"
source: https://www.bctengineer.com/q/semester_7/computer_networks_and_security/rsa-steps-encrypt-cat
site: BCT Engineering
---

# RSA steps; encrypt word CAT

Computer Networks and Security · Chapter 8: Network Security

- Asked in: 2072 Chaitra, 8 marks
- Video: [RSA Algorithm in Cryptography and Network Security](https://www.youtube.com/watch?v=rlJTMUBXhKE) — Abhishek Sharma
- 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-steps-encrypt-cat
- Whole chapter: https://www.bctengineer.com/md/semester_7/computer_networks_and_security/chapter-8

## Question

Write down the steps involved in the RSA encryption algorithm. Encrypt the word CAT using the RSA algorithm, choosing suitable data for encryption by yourself according to the RSA algorithm.

## Short answer

RSA steps: choose primes p and q, compute n=pq and phi=(p-1)(q-1), choose e coprime to phi, compute d as inverse of e mod phi; public key (e,n), private key (d,n); encrypt C=M^e mod n, decrypt M=C^d mod n. With p=7, q=11, e=13, d=37, CAT (3,1,20) encrypts to 38, 1, 69 and decrypts back to CAT.

## Answer

#### Steps of the RSA algorithm
1. Choose two distinct prime numbers p and q.
2. Compute n = p × q (the modulus; n is part of both keys).
3. Compute Euler's totient φ(n) = (p − 1)(q − 1).
4. Choose a public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
5. Compute the private exponent d with d × e ≡ 1 (mod φ(n)).
6. Public key KU = (e, n); private key KR = (d, n).
7. **Encryption:** C = Mᵉ mod n, where M < n.
8. **Decryption:** M = Cᵈ mod n.

#### Encrypting CAT
Convert letters to numbers: A = 1, B = 2, ... so C = 3, A = 1, T = 20.

| Step | Calculation | Value |
|---|---|---|
| p, q | choose p = 7, q = 11 | |
| n | 7 × 11 | 77 |
| φ(n) | 6 × 10 | 60 |
| e | choose e = 13, gcd(13, 60) = 1 | 13 |
| d | 13 × d ≡ 1 mod 60; 13 × 37 = 481 = 8 × 60 + 1 | 37 |

Public key = (13, 77); private key = (37, 77). All values are less than 77.

| Letter | M | Encryption C = M¹³ mod 77 | Decryption M = C³⁷ mod 77 |
|---|---|---|---|
| C | 3 | 3¹³ mod 77 = 38 | 38³⁷ mod 77 = 3 |
| A | 1 | 1¹³ mod 77 = 1 | 1³⁷ mod 77 = 1 |
| T | 20 | 20¹³ mod 77 = 69 | 69³⁷ mod 77 = 20 |

#### Working
- C: encrypt: 3^1 = 3, 3^2 = 9, 3^4 = 4, 3^8 = 16 (all mod 77); 13 = 1 + 4 + 8, so 3^13 = 3 × 4 × 16 mod 77 = 38. Decrypt: 38^1 = 38, 38^2 = 58, 38^4 = 53, 38^8 = 37, 38^16 = 60, 38^32 = 58 (all mod 77); 37 = 1 + 4 + 32, so 38^37 = 38 × 53 × 58 mod 77 = 3.
- A: encrypt: 1^1 = 1, 1^2 = 1, 1^4 = 1, 1^8 = 1 (all mod 77); 13 = 1 + 4 + 8, so 1^13 = 1 × 1 × 1 mod 77 = 1. Decrypt: 1^1 = 1, 1^2 = 1, 1^4 = 1, 1^8 = 1, 1^16 = 1, 1^32 = 1 (all mod 77); 37 = 1 + 4 + 32, so 1^37 = 1 × 1 × 1 mod 77 = 1.
- T: encrypt: 20^1 = 20, 20^2 = 15, 20^4 = 71, 20^8 = 36 (all mod 77); 13 = 1 + 4 + 8, so 20^13 = 20 × 71 × 36 mod 77 = 69. Decrypt: 69^1 = 69, 69^2 = 64, 69^4 = 15, 69^8 = 71, 69^16 = 36, 69^32 = 64 (all mod 77); 37 = 1 + 4 + 32, so 69^37 = 69 × 15 × 64 mod 77 = 20.

Ciphertext = 38, 1, 69. Decrypting gives 3, 1, 20 = **CAT**.

Note: the letter A = 1 always gives 1ᵉ = 1, a weakness of encoding single letters; real RSA pads the message.

**Answer: public key (13, 77), private key (37, 77); CAT encrypts to 38, 1, 69 and decrypts back to CAT.**

## Check yourself

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

1. What condition must e satisfy?
   A. e divides phi(n)
   B. e = p
   C. e = n
   D. 1 < e < phi(n) and gcd(e, phi(n)) = 1
   Answer: D. e must be coprime to phi(n). (Key point: e condition)

2. For p=7, q=11, e=13: n, phi, d?
   A. 77, 70, 37
   B. 77, 60, 37
   C. 77, 60, 13
   D. 18, 60, 37
   Answer: B. 13 x 37 = 481 = 8 x 60 + 1. (Key point: Keys)

3. What is CAT (3, 1, 20) encrypted to?
   A. 69, 1, 38
   B. 3, 1, 20
   C. 38, 1, 69
   D. 38, 2, 69
   Answer: C. C = M^13 mod 77. (Key point: Ciphertext)

4. Why is A=1 a weakness of single-letter encoding?
   A. It breaks d
   B. It is too large
   C. 1^e = 1 always, so A is unchanged
   D. It fails gcd
   Answer: C. Real RSA uses padding. (Key point: Weakness)

## Related in Computer Networks and Security

- [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
- [RSA algorithm with example](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Arsa-algorithm-explain) — Computer Networks and Security, chapter 8, asked 4×
- [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

- [IC manufacturing steps; top-down F = xz + y](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aic-manufacturing-steps-topdown-xz-y) — Embedded System, chapter 8
- [Short note: Routing algorithm in data communication](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Arouting-algorithm-data-comm) — Telecommunications, chapter 8, asked 2×
- [Total station features and data recording steps](https://www.bctengineer.com/question.md?key=semester_4%2Fsurveying_ii%3Atotal-station-features-data-recording) — Surveying II, chapter 9
- [ADC804 with 8255 control word and program](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Aadc804-8255-program) — Instrumentation II, chapter 4