Difficulty: Intermediate | Prerequisites: Basic algebra, modular arithmetic concepts
Cryptography sits at the intersection of mathematics and computer science, providing the tools that make secure digital communication possible. This topic covers how messages are scrambled (encrypted) and unscrambled (decrypted), starting with simple classical ciphers and building up to public-key systems like RSA. You should be comfortable with basic algebra and the idea of dividing integers with remainders before diving in. If you have covered modular arithmetic and prime factorisation in earlier chapters, you are ready.
Cryptography turns readable messages into unreadable ones so only the intended recipient can reverse the process. The Caesar Cipher does this by shifting each letter by a fixed number, while RSA uses the difficulty of factoring large numbers to create a public-key system where anyone can encrypt but only the key holder can decrypt. The mathematical backbone is modular arithmetic, GCD computation, and the extended Euclidean algorithm.
Cryptography
The practice of securing communication so that only the intended recipient can read the message, even if an adversary intercepts it.
In simple terms, this means turning a message into gibberish that only the right person can un-gibberish.
Encryption
The process of converting plaintext (readable data) into ciphertext (unreadable data) using an algorithm and a key.
Think of it as locking a message inside a box that only someone with the right key can open.
Decryption
The reverse of encryption: converting ciphertext back into plaintext.
In simple terms, this means unlocking the box to read the original message.
Caesar Cipher
A substitution cipher that shifts each letter in the alphabet by a fixed number of positions. Named after Julius Caesar, who reportedly used a shift of 3.
Think of it as rotating the entire alphabet by a few spots. Simple, breakable, but a good starting point.
RSA Cryptosystem
A public-key encryption system developed by Rivest, Adleman, and Shamir in 1978. Security relies on the computational difficulty of factoring the product of two large primes.
In simple terms, this means anyone can send you a locked message using your public key, but only you can unlock it with your private key.
Public Key
The key shared openly. In RSA, this is the pair (N, e). Anyone can use it to encrypt a message to you.
Private Key
The key kept secret. In RSA, this is the value d. Only the holder can decrypt messages encrypted with the corresponding public key.
Modular Arithmetic
Arithmetic where numbers "wrap around" after reaching a certain value (the modulus). Written as a mod N.
Think of it as clock arithmetic: 14:00 on a 12-hour clock is 2:00, because 14 mod 12 = 2.
Greatest Common Divisor (GCD)
The largest integer that divides two numbers without a remainder. Written gcd(m, n).
Euclidean Algorithm
An efficient method for computing the GCD of two integers by repeatedly applying division with remainder.
Euler's Totient Function
For a positive integer N, the count of integers from 1 to N that are coprime to N. Written as phi(N). For N = p * q (two distinct primes), phi(N) = (p - 1)(q - 1).
In simple terms, this counts how many numbers below N share no factors with N.
Multiplicative Inverse (mod N)
An integer b such that a * b is congruent to 1 mod N. Found using the extended Euclidean algorithm.
Think of it as the "division equivalent" in modular arithmetic, since you cannot divide directly.
Hashing Function
A function that maps data of arbitrary size to a fixed-size value (a hash). Used for fast lookups, data integrity checks, and indexing.
In simple terms, it turns any input into a short, fixed-length fingerprint.
The Caesar Cipher is the simplest substitution cipher. Each letter in the plaintext is replaced by a letter a fixed number of positions further along in the alphabet.
How it works
Encryption shifts each letter forward by a key value k (classically k = 3)
Decryption shifts each letter backward by the same key value k
The alphabet wraps around: after Z comes A
Encryption function
encrypt(c) = (c + 3) mod 26
Each letter is treated as a number (A = 0, B = 1, ... Z = 25)
Decryption function
decrypt(c) = (c - 3) mod 26
Worked example
Plaintext: MEET YOU IN THE PARK
Each letter shifts forward by 3: M becomes P, E becomes H, and so on
Ciphertext: PHHW BRX LQ WKH SDUN
Why it is insecure
Only 25 possible keys (shifts of 1 through 25), so brute force is trivial
Letter frequency analysis breaks it instantly: the most common ciphertext letter is almost certainly E shifted by k
Useful for understanding the concept of encryption, not for real-world security
RSA is a public-key cryptosystem. Unlike the Caesar Cipher, the person encrypting and the person decrypting do not need to share a secret key in advance. Anyone can encrypt using the public key, but only the private key holder can decrypt.
Key generation (step by step)
Choose two large prime numbers, p and q
Compute N = p * q (this is part of the public key)
Compute Euler's totient: phi(N) = (p - 1)(q - 1)
Choose an integer e such that 1 < e < phi(N) and gcd(e, phi(N)) = 1 (e must be coprime to phi(N))
Compute d, the multiplicative inverse of e mod phi(N), using the extended Euclidean algorithm
Public key: (N, e). Private key: d
Encryption
Given plaintext message m (as an integer), compute ciphertext: c = m^e mod N
Decryption
Given ciphertext c, recover plaintext: m = c^d mod N
Worked example
Choose p = 31, q = 59
N = 31 * 59 = 1829
phi(N) = 30 * 58 = 1740
Choose e = 7 (since gcd(7, 1740) = 1)
Compute d = 1243 (the inverse of 7 mod 1740)
Encrypt m = 1211: c = 1211^7 mod 1829 = 1027
Decrypt c = 1027: m = 1027^1243 mod 1829 = 1211 (original message recovered)
Why RSA works
The security rests on the fact that factoring N = p * q is computationally hard when p and q are large
If an attacker could factor N, they could compute phi(N) and then d, breaking the system
For real-world use, p and q are typically hundreds of digits long
Caesar Cipher encryption: encrypt(c) = (c + k) mod 26
Caesar Cipher decryption: decrypt(c) = (c - k) mod 26
RSA modulus: N = p * q
Euler's totient (two primes): phi(N) = (p - 1)(q - 1)
RSA encryption: c = m^e mod N
RSA decryption: m = c^d mod N
Multiplicative inverse condition: e * d is congruent to 1 mod phi(N)
GCD via Euclidean algorithm: gcd(a, b) = gcd(b, a mod b), with base case gcd(a, 0) = a
Hashing (example): h(k) = k mod 31
Greatest Common Divisor (GCD)
The largest integer that divides both m and n evenly
Written as gcd(m, n)
Example: gcd(12, 8) = 4
Euclidean Algorithm
An efficient recursive method for computing the GCD
Repeatedly replace gcd(a, b) with gcd(b, a mod b) until one value is 0
Example: gcd(252, 105) = gcd(105, 42) = gcd(42, 21) = gcd(21, 0) = 21
Far faster than listing all divisors, especially for large numbers
Modular Arithmetic
a mod N gives the remainder when a is divided by N
Two numbers are congruent mod N if they have the same remainder when divided by N
Arithmetic operations (addition, multiplication, exponentiation) all work within a modulus
Multiplicative Inverse mod N
b is the multiplicative inverse of a mod N if a * b is congruent to 1 mod N
Exists only when gcd(a, N) = 1 (that is, a and N are coprime)
Found using the extended Euclidean algorithm
Critical for RSA: d is the multiplicative inverse of e mod phi(N)
Hashing functions
Map data to a fixed-size value for fast lookups
Example: a car park with 31 spaces assigns spots using h(k) = k mod 31, where k is the first three digits of the licence plate
Hash collisions occur when two inputs map to the same output, and handling them is a key design concern
Pseudorandom number generation
Cryptographic systems need keys that appear random to an attacker
Pseudorandom number generators (PRNGs) produce sequences that pass statistical randomness tests but are generated deterministically from a seed
A weak PRNG can undermine an otherwise strong cryptosystem
RSA is the backbone of HTTPS, the protocol that secures web browsing. Every time you see a padlock icon in your browser, a public-key exchange (often RSA or a related system) is establishing the secure channel.
Hashing functions are used in databases, file integrity checking (checksums), password storage, and blockchain technology. The simple h(k) = k mod N form from the car-park example scales up to hash tables powering everything from compilers to search engines.
Students often think the Caesar Cipher key is the specific letter mapping. It is not. The key is the shift value (e.g. 3), and the mapping follows from that.
Students often confuse the public key and the private key in RSA. Remember: the public key (N, e) is shared freely. The private key d is never transmitted.
Students sometimes assume that e and d are the same value, or that the encryption and decryption exponents are interchangeable in any order. They are not the same. d is the multiplicative inverse of e mod phi(N), which is a separate computation.
Students often think that a larger N alone makes RSA secure. The security depends on p and q both being large primes. If either is small, N can be factored quickly.
Expect to be asked to encrypt and decrypt a short message using the Caesar Cipher by hand
RSA key generation is a common exam question: given p and q, compute N, phi(N), choose e, find d
Be ready to compute a GCD using the Euclidean algorithm step by step
Know when a multiplicative inverse exists (gcd(a, N) must equal 1) and how to find it
Modular exponentiation (computing m^e mod N for small values) is frequently tested
True or False: The Caesar Cipher with a shift of 3 turns the letter A into the letter D. (True)
Fill in the blank: In RSA, the public key consists of the pair ______ and ______. (N and e)
True or False: If gcd(e, phi(N)) is not equal to 1, you can still use e as the RSA encryption exponent. (False, e must be coprime to phi(N))
Fill in the blank: The Euclidean algorithm computes gcd(a, b) by repeatedly replacing gcd(a, b) with gcd(b, ______). (a mod b)
True or False: RSA encryption and decryption use the same exponent. (False, encryption uses e and decryption uses d)
Q: Using the Caesar Cipher with a shift of 3, encrypt the word "HELLO".
A: H becomes K, E becomes H, L becomes O, L becomes O, O becomes R. The encrypted word is KHOOR.
Q: Given p = 31 and q = 59, compute N and phi(N) for RSA key generation.
A: N = 31 * 59 = 1829. phi(N) = (31 - 1)(59 - 1) = 30 * 58 = 1740.
Q: Why must gcd(e, phi(N)) = 1 when choosing the RSA encryption exponent e?
A: Because d (the decryption exponent) is the multiplicative inverse of e mod phi(N). That inverse only exists when e and phi(N) are coprime, meaning their GCD is 1.
Q: Compute gcd(48, 18) using the Euclidean algorithm.
A: gcd(48, 18) = gcd(18, 48 mod 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6.
Q: In RSA with public key (1829, 7), you receive ciphertext c = 1027. The private key is d = 1243. What is the original message?
A: m = 1027^1243 mod 1829 = 1211.
This connects to Models of Computation because Turing machines and finite automata formalise what "computation" means, which is the foundation for understanding why RSA is hard to break (factoring is computationally expensive). Modular arithmetic and GCD computation also appear in number theory and algorithm design courses. Public-key cryptography connects directly to network security, digital signatures, and certificate authorities in later coursework.
Caesar cipher, shift cipher, substitution cipher, RSA, Rivest Shamir Adleman, public key cryptography, asymmetric encryption, private key, modular arithmetic, mod, modulus, GCD, greatest common divisor, Euclidean algorithm, extended Euclidean algorithm, Euler's totient function, phi function, multiplicative inverse, coprime, relatively prime, hashing, hash function, pseudorandom number generator, PRNG, key generation, encryption, decryption, ciphertext, plaintext, CS 101, foundations of computer science