Difficulty: Intermediate | Prerequisites: Division and Modular Arithmetic notes, Primes and GCD notes
This is where the number theory from the first two topics pays off. Classical ciphers like the Caesar cipher introduce the idea of encryption as a mathematical function, and RSA shows how modular arithmetic and prime factorisation combine into a real-world encryption system used across the internet. The computing applications section (hashing and pseudorandom number generators) rounds out the picture by showing how mod arithmetic appears in everyday data structures and simulation. You need to be comfortable with modular arithmetic and the Extended Euclidean Algorithm before tackling RSA.
The Caesar cipher encrypts by shifting letters a fixed number of positions mod 26, which is easy to break but illustrates the idea of encryption as a reversible mathematical function. RSA is the real-world upgrade: it uses large primes, modular exponentiation, and the Extended Euclidean Algorithm to create a public-key system where anyone can encrypt but only the key holder can decrypt. Hashing and pseudorandom number generators are two further applications of modular arithmetic in computing, turning remainders into array indices and deterministic "random" sequences.
Plaintext
The original, readable message before encryption. Think of it as the message you want to keep secret.
Ciphertext
The encrypted, unreadable output after applying a cipher. Think of it as the scrambled version that only the intended recipient can decode.
Caesar cipher (shift cipher)
A substitution cipher that replaces each letter with the letter a fixed number of positions further in the alphabet, wrapping around at Z. In simple terms, slide every letter the same number of steps.
Public-key cryptography (asymmetric cryptography)
A cryptographic system using two keys: a public key for encryption (shared openly) and a private key for decryption (kept secret). Think of it as a mailbox: anyone can drop a letter in, but only the owner has the key to open it.
RSA cryptosystem
A public-key encryption scheme whose security rests on the difficulty of factoring large composite numbers into their prime factors. Named after Rivest, Shamir, and Adleman.
Euler's totient function, phi(N)
For N = pq where p and q are distinct primes, phi(N) = (p - 1)(q - 1). This counts how many integers from 1 to N are coprime to N. It is the modulus used when choosing and computing RSA keys.
Hash function
A function that maps data of arbitrary size to a fixed-size output (a hash value). In simple terms, it assigns each input a "slot" or "fingerprint" for fast lookup.
Collision (hashing)
When two different inputs produce the same hash value. Good hash functions minimise collisions but cannot eliminate them entirely.
Linear congruential generator (LCG)
A formula for generating a sequence of pseudorandom numbers using modular arithmetic: each number is computed from the previous one. Not cryptographically secure, but fast and widely used in simulations.
Each letter is assigned a number (A = 0, B = 1, ..., Z = 25). Encryption shifts each letter forward by a fixed key k; decryption shifts it back.
Encryption: E(x) = (x + k) mod 26
Decryption: D(c) = (c - k) mod 26
Worked example: Encrypt "MEET" with shift k = 3
M (12) becomes (12 + 3) mod 26 = 15 = P
E (4) becomes (4 + 3) mod 26 = 7 = H
E (4) becomes 7 = H
T (19) becomes (19 + 3) mod 26 = 22 = W
Ciphertext: PHHW
The Caesar cipher is trivially breakable (only 25 possible keys), but it introduces the core idea: encryption and decryption are inverse modular operations.
Key generation:
Choose two large distinct primes p and q
Compute N = pq
Compute phi(N) = (p - 1)(q - 1)
Choose an integer e such that 1 < e < phi(N) and gcd(e, phi(N)) = 1
Find d such that ed ≡ 1 (mod phi(N)), using the Extended Euclidean Algorithm
Public key: (N, e). Private key: d.
Encryption: C = M^e mod N
Decryption: M = C^d mod N
Worked example: Encrypt "STOP" with public key (2537, 13)
Convert letters to numbers (A = 00, B = 01, ..., Z = 25): S = 18, T = 19, O = 14, P = 15. Group into blocks and compute each block raised to the power e = 13, reduced mod 2537.
RSA's security rests on the fact that factoring N back into p and q is computationally infeasible for large primes, even though multiplying p × q is trivial.
A hash function maps a key to a fixed-size index, typically using the mod operator.
Example: A parking lot system hashes car plate numbers using h(k) = k mod 31, mapping each plate to one of 31 slots.
Good hash functions distribute keys uniformly across slots to minimise collisions. The choice of modulus matters: primes tend to produce better distributions than composite numbers.
The LCG produces a deterministic sequence that appears random, defined by:
x(n+1) = (a × x(n) + c) mod m
where m is the modulus, a is the multiplier, c is the increment, and x(0) is the seed.
Worked example: m = 9, a = 7, c = 4, x(0) = 3
x(1) = (7 × 3 + 4) mod 9 = 25 mod 9 = 7
x(2) = (7 × 7 + 4) mod 9 = 53 mod 9 = 8
x(3) = (7 × 8 + 4) mod 9 = 60 mod 9 = 6
And so on, cycling through values between 0 and 8
The sequence is entirely determined by the seed and parameters. Change the seed, get a different sequence. The period (how long before it repeats) depends on the choice of m, a, and c.
Caesar encryption: E(x) = (x + k) mod 26
Caesar decryption: D(c) = (c - k) mod 26
RSA key generation: Choose primes p, q. Compute N = pq, phi(N) = (p-1)(q-1). Choose e with gcd(e, phi(N)) = 1. Find d with ed ≡ 1 (mod phi(N)).
RSA encryption: C = M^e mod N
RSA decryption: M = C^d mod N
Hash function example: h(k) = k mod 31
Linear congruential generator: x(n+1) = (a × x(n) + c) mod m
RSA is the backbone of secure internet communication. When your browser shows a padlock icon, RSA (or a related public-key scheme) is negotiating the encryption. Hash functions power dictionary lookups, database indexing, and password storage (where you store the hash, never the password). Linear congruential generators are used in Monte Carlo simulations, game engines, and statistical sampling where speed matters more than cryptographic strength.
Students confuse the public key and private key. The public key (N, e) encrypts; the private key d decrypts. You never share d.
Students think RSA's security comes from keeping N secret. N is public. The security comes from the difficulty of factoring N into p and q.
Students assume the Caesar cipher is secure because the ciphertext looks random. With only 25 possible keys, brute force takes seconds.
Students think pseudorandom number generators produce truly random output. They do not. Given the seed and parameters, the entire sequence is deterministic and reproducible.
Students confuse hash functions with encryption. Hashing is one-way (you cannot recover the input from the hash); encryption is two-way (you can decrypt to recover the original).
⚠️ Be ready to encrypt and decrypt a short message using the Caesar cipher with a given shift. This is a quick, reliable exam question.
⚠️ Know the RSA key generation steps cold, including where the Extended Euclidean Algorithm fits in (finding d).
⚠️ Be able to compute C = M^e mod N for small numbers by hand. Lecturers often give manageable primes for this.
⚠️ Understand why gcd(e, phi(N)) = 1 is required: it guarantees that the modular inverse d exists.
⚠️ Be able to compute a few iterations of a linear congruential generator given m, a, c, and x(0).
Fill in the blank: To encrypt the letter G (position 6) with a Caesar shift of 5, the ciphertext letter is at position ___. (11, which is L)
True or false: In RSA, the number N = pq is kept secret. (False, N is part of the public key)
Fill in the blank: RSA decryption computes M = C^___ mod N. (d)
True or false: A hash function is reversible. (False)
Fill in the blank: In an LCG with m = 7, a = 3, c = 1, and x(0) = 2, x(1) = ___. (0, since (3 × 2 + 1) mod 7 = 0)
Q: Encrypt the word "CAB" using a Caesar cipher with k = 4.
A: C(2) becomes (2+4) mod 26 = 6 = G. A(0) becomes 4 = E. B(1) becomes 5 = F. Ciphertext: GEF.
Q: In RSA, if p = 5 and q = 11, compute N and phi(N).
A: N = 5 × 11 = 55. phi(N) = (5-1)(11-1) = 4 × 10 = 40.
Q: Why must gcd(e, phi(N)) = 1 in RSA key generation?
A: Because d is the modular inverse of e mod phi(N), and a modular inverse exists only when e and phi(N) are coprime.
Q: Given h(k) = k mod 31, what slot does key 155 map to?
A: 155 mod 31 = 0 (since 155 = 5 × 31).
Q: Compute the first three values of an LCG with m = 10, a = 3, c = 7, x(0) = 0.
A: x(1) = (3 × 0 + 7) mod 10 = 7. x(2) = (3 × 7 + 7) mod 10 = 28 mod 10 = 8. x(3) = (3 × 8 + 7) mod 10 = 31 mod 10 = 1.
The Caesar cipher is modular arithmetic applied to the alphabet, using the same mod operation from the Division and Modular Arithmetic notes. RSA key generation requires the Extended Euclidean Algorithm from the Primes and GCD notes to compute d. Hashing ties back to the division algorithm: the mod operation maps keys to indices the same way the remainder maps integers to equivalence classes. LCGs use the same recurrence structure that appears in algorithm analysis and discrete mathematics.
Caesar cipher, shift cipher, substitution cipher, plaintext, ciphertext, encryption, decryption, public-key cryptography, asymmetric cryptography, RSA, RSA cryptosystem, public key, private key, key generation, modular exponentiation, Euler's totient, phi function, hash function, hashing, hash table, collision, linear congruential generator, LCG, pseudorandom, PRNG, seed, number theory, HSK3X, Foundations of Computer Science, Purdue