Computer Network & Network Security System — Network Security, NEC licence examination syllabus (Nepal Engineering Council).
RSA Algorithm: the math that secures almost every HTTPS connection
The most important worked numerical in this entire subject — practice it until it's automatic.
RSA is asymmetric cryptography's most famous implementation — it's the actual algorithm quietly running behind countless secure connections you make every single day.
RSA Key Generation — full worked example:
Step 1: Choose two prime numbers, p = 3, q = 11
Step 2: n = p × q = 3 × 11 = 33
Step 3: φ(n) = (p−1)(q−1) = 2 × 10 = 20
Step 4: Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
Try e = 7 → gcd(7, 20) = 1 ✓
Step 5: Find d such that (e × d) mod φ(n) = 1
(7 × d) mod 20 = 1 → d = 3, since 7×3=21, 21 mod 20 = 1 ✓
Public key = (e, n) = (7, 33)
Private key = (d, n) = (3, 33)
RSA Encryption and Decryption — using the keys above:
Encrypt message M = 2 using public key (e=7, n=33):
C = M^e mod n = 2^7 mod 33 = 128 mod 33 = 29
Decrypt ciphertext C = 29 using private key (d=3, n=33):
M = C^d mod n = 29^3 mod 33 = 24389 mod 33 = 2 ✓ (matches original!)
💡 This exact style of numerical (small primes p, q → find n, φ(n), e, d → encrypt/decrypt a small message) is asked almost every year. Practice with at least 3 different small prime pairs until you can do all 5 steps without hesitation.
Finding d reliably — the step that costs marks
The example above finds d = 3 by inspection, which works when φ(n) = 20. On a harder question with larger primes, guessing is hopeless. The method you need is the extended Euclidean algorithm, which finds d directly.
Find d where (7 × d) mod 20 = 1, using extended Euclid on (7, 20):
20 = 2×7 + 6 → 6 = 20 − 2×7
7 = 1×6 + 1 → 1 = 7 − 1×6
6 = 6×1 + 0 → gcd = 1, so d exists
Now substitute backwards to express 1 in terms of 7 and 20:
1 = 7 − 1×6
= 7 − 1×(20 − 2×7)
= 7 − 20 + 2×7
= 3×7 − 1×20
So 3×7 ≡ 1 (mod 20), giving d = 3 ✓
Two facts worth carrying: the gcd must come out as 1, which is exactly the condition that makes d exist at all — and the coefficient of e in that final line is d. If it comes out negative, add φ(n) to bring it into range.
A second pair to practise on
p = 5, q = 11
n = 5 × 11 = 55
φ(n) = 4 × 10 = 40
e = 3 (gcd(3, 40) = 1 ✓)
d = 27 (3 × 27 = 81, and 81 mod 40 = 1 ✓)
Encrypt M = 8: C = 8³ mod 55 = 512 mod 55 = 17
Decrypt C = 17: M = 17²⁷ mod 55 = 8 ✓
💡 Always verify by checking (e × d) mod φ(n) = 1 before going on to encrypt. It takes seconds and catches the arithmetic slip that would otherwise wreck every step that follows.
Why the whole thing is secure
The public key gives away n and e. An attacker who could recover φ(n) would compute d exactly as you just did — so the entire security rests on φ(n) staying hidden.
Computing φ(n) = (p−1)(q−1) requires knowing p and q. Recovering them from n means factoring it — easy for 33, and computationally infeasible for the several-hundred-digit numbers used in practice. RSA is secure because multiplying two large primes is fast while reversing that multiplication is not.
💡 That asymmetry is the whole answer to "why is RSA secure?" — not that the arithmetic is complicated, but that factoring is hard while multiplying is easy. It also explains why the primes must be large and randomly chosen: small or predictable ones can simply be factored.
Syllabus points
Key generation (public/private)
Encryption & decryption
Numerical example
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.