Teaching objectives
How can someone send you a secret message using a key that everyone can see? That paradox is RSA — the algorithm that still protects internet communications today. This upper-secondary/university lab walks the full journey: from the simple Caesar cipher all the way to generating public and private keys, building up every piece of modular arithmetic and number theory that makes the magic work.
What you'll learn
Students build RSA brick by brick, skipping no steps: first they crack Caesar to understand why something better is needed, then they discover modular arithmetic and Euler's φ function, and finally use Fermat's Little Theorem to see why raising to e encrypts and raising to d decrypts.
Along the way, the idea of an inverse function (decoding vs. encoding) is developed throughout.
- The Caesar cipher is explored with an interactive dial: encrypt, decrypt, and count its 25 possible keys.
- Addition and multiplication modulo m are practised, including the multiplicative inverse (5·x ≡ 1 mod 11).
- φ(n) is computed in three variants: φ(15) with a 3×5 grid, φ(77) = 6×10, φ(125) = 5³ − 5².
- The formula φ(pq) = (p−1)(q−1) is derived from those examples.
- Fermat's Theorem is discovered: a^10 ≡ 1 mod 11 for every a not a multiple of 11; and that its multiples (20, 30, 40) work too.
- RSA keys are generated step by step: choose
ecoprime to φ(n), computedas the inverse ofemodulo φ(n), and tell public key (e, n) apart from private key d. - A concrete message (m = 2, n = 55) is encrypted and decrypted using fast exponentiation by successive squarings.
- Valid (e, d) pairs are explored and students reason about why recovering d from n alone is infeasible without knowing p and q.
- The final room introduces (k−1)-bit block encoding for real messages.
Key mathematical ideas
- Inverse functions: some operations can be undone.
- Modular arithmetic: addition and multiplication are cyclic; multiplicative inverses exist when factors are coprime.
- Euler's φ function: φ(pq) = (p−1)(q−1) counts the integers less than n that are coprime to n.
- Fermat's Little Theorem / Euler's Theorem: a^φ(n) ≡ 1 mod n; this allows exponentiation to be inverted by reducing the exponent modulo φ(n).
- RSA key pair: e·d ≡ 1 mod φ(n) guarantees that (mᵉ)ᵈ ≡ m (mod n).
- Security through factorisation: knowing only n and e makes it impossible to compute φ(n) — and therefore d — without factoring n, a problem intractable for numbers hundreds of digits long.
- Fast exponentiation: repeated squaring reduces O(n) multiplications to O(log n).
Room-by-room contents
Room 1 · Cryptography: secret messages
Laboratory introduction: what cryptography is, why a brute-force attack can break weak keys, and how modular arithmetic makes RSA possible.
Student tasks
- Read the introduction and understand the challenge posed by brute force.
- Advance to begin the room-by-room journey.
Room 2 · The Caesar cipher
Interactive disc with two concentric rings (letters). Rotating the inner ring with the + and − buttons applies the shift; the student types a message and watches it encrypt letter by letter.
Student tasks
- Rotate the disc to the desired shift.
- Type a message and observe the ciphertext that appears.
Room 3 · How many keys does Caesar have?
The student receives the ciphertext "MJQQT RZSIT" and must rotate the disc to find the original message. Then they answer how many distinct keys the Caesar cipher has.
Student tasks
- Rotate the disc to decrypt "MJQQT RZSIT".
- Answer how many distinct keys Caesar has (25).
Room 4 · Inverse shift
HOLA encrypted with shift 15 produces WDAP. The student must find the inverse shift that returns WDAP to HOLA, introducing the idea of inverse operation in modular arithmetic.
Student tasks
- Calculate the shift that decrypts WDAP → HOLA (answer: 11).
Room 5 · Addition modulo m
Interactive explorer with sliders for two addends and a modulus selector. Modulus 12 visualises addition as on an analogue clock.
Student tasks
- Move the sliders and change the modulus to explore different sums.
- Answer what 8 + 6 mod 11 equals (answer: 3).
Room 6 · Multiplication modulo m
Modular multiplication explorer. The concept of multiplicative inverse is introduced: the number x such that a·x ≡ 1 (mod m).
Student tasks
- Explore modular products with different bases and moduli.
- Find the multiplicative inverse of 5 modulo 11 (answer: 9, since 5·9 = 45 ≡ 1 mod 11).
Room 7 · Euler's φ function
φ(n) counts the integers between 1 and n that are coprime with n. Visualised with a 3×5 grid for n = 15 = 3×5, colouring multiples of 3 and of 5.
Student tasks
- Observe which cells remain unmarked in the 3×5 grid.
- Calculate φ(15) by counting the coprimes (answer: 8).
Room 8 · Calculate φ(77)
Direct application of the formula φ(p·q) = (p−1)(q−1) for n = 77 = 7×11.
Student tasks
- Calculate φ(77) using the prime factors 7 and 11 (answer: 60).
Room 9 · Calculate φ(125)
Case of a prime power: 125 = 5³. Only multiples of 5 share a factor with 125, so φ(125) = 125 − 25 = 100.
Student tasks
- Count the multiples of 5 between 1 and 125.
- Calculate φ(125) (answer: 100).
Room 10 · General formula φ(pq)
Recap using the example p=3, q=5: inclusion-exclusion reasoning shows that pq − q − p + 1 = (p−1)(q−1). The student selects the correct formula from four options.
Student tasks
- Review the inclusion-exclusion reasoning from the example.
- Select the correct formula for φ(p·q): (p−1)(q−1).
Room 11 · Fermat discovered
Interactive explorer of powers modulo 11: the student adjusts the base and exponent and discovers that there exists an exponent that always yields 1 (Fermat's Little Theorem).
Student tasks
- Try different bases with exponent 10 mod 11.
- Identify the "magic exponent" that always produces 1 (answer: 10).
Room 12 · Multiples of the order
It is already known that exp = 10 always gives 1 mod 11. The student must mark, from a list of exponents, those that also work (multiples of 10).
Student tasks
- Select from the list the exponents for which a^exp ≡ 1 mod 11 for any base.
- Identify the pattern: they are 20, 30 and 40 (multiples of 10).
Room 13 · Encrypt and decrypt with Fermat
Since 7×3 = 21 ≡ 1 mod 10, raising to 7 encrypts and raising to 3 decrypts modulo 11. The student verifies this with an interactive slider and confirms that encrypting then decrypting returns the original message.
Student tasks
- Use the explorer to encrypt a number with exponent 7 mod 11.
- Apply exponent 3 to the result and verify that the original is recovered.
Room 14 · From Fermat to RSA
Explanatory room that generalises Fermat to composite numbers using Euler's theorem: a^φ(n) ≡ 1 (mod n). With n = 91 = 7×13, φ = 72, e = 5, d = 29, it is shown that e·d ≡ 1 mod φ(n) guarantees the encrypt/decrypt pair.
Student tasks
- Read the generalisation of Fermat to the RSA case with p=7, q=13.
- Verify that 5·29 = 145 ≡ 1 mod 72.
Room 15 · The public key e
With φ(n) = 40 = 2³×5, the student must choose e coprime with 40 from the candidates {2, 3, 5, 8, 10, 40}. The condition gcd(e, 40) = 1 is applied.
Student tasks
- Discard even values and multiples of 5.
- Select the only valid value as public key e (answer: 3).
Room 16 · The private key d
Given e = 3 and φ(n) = 40, the student calculates d such that 3·d ≡ 1 mod 40 by trying successive values (3×27 = 81 = 2×40 + 1).
Student tasks
- Try values of d until 3·d mod 40 = 1.
- Enter the result (answer: 27).
Room 17 · The RSA keys
Visual summary of the key pair obtained with p=5, q=11: public key (e=3, n=55) shared with everyone, and private key (d=27, n=55) known only by its owner.
Student tasks
- Observe the distinction between public key and private key.
- Advance with the already-generated key pair for the encryption block.
Room 18 · Encrypting with RSA
Application of the encryption formula c = m^e mod n with m=2, e=3, n=55. First numerical contact with the RSA encryption step.
Student tasks
- Calculate c = 2³ mod 55 (answer: 8).
Room 19 · Fast exponentiation
To calculate 8^27 mod 55 the repeated-squaring technique is used: 8² = 64 ≡ 9, 8⁴ = 9² = 81 ≡ 26 … The student calculates the intermediate step 8⁴ mod 55.
Student tasks
- Follow the repeated-squaring method.
- Calculate 8⁴ mod 55 (answer: 26).
Room 20 · Decrypting with RSA
With 27 = 16+8+2+1, 8^27 is decomposed as a product of known powers (8¹, 8², 8⁸, 8¹⁶ mod 55). The student chooses the correct operation (multiply, not add) and calculates the result.
Student tasks
- Choose between "add" or "multiply" the powers (correct: multiply).
- Calculate 8²⁷ mod 55 (answer: 2, the original message).
Room 21 · The complete cycle!
Animation of the complete RSA cycle with m=2, e=3, d=27, n=55: encrypt → c=8, decrypt → m=2. Shows why the identity m^(e·d) ≡ m (mod n) holds by Euler's theorem.
Student tasks
- Watch the animation of the complete encrypt-decrypt cycle.
- Verify that the decrypted message matches the original.
Room 22 · Why is RSA secure?
Explanation of the security foundation: to obtain d one must calculate φ(n), which requires factoring n. For n of ~617 digits, classical algorithms would take longer than the age of the universe.
Student tasks
- Read the security argument and the comparison between 55 (easy) and a 617-digit number (infeasible).
Room 23 · RSA key explorer
Free tool: the student chooses p and q from several options (11/13/17 and 17/19/23) and sees all valid (e, d) pairs for those primes, along with the table k·φ(n)+1 = e×d.
Student tasks
- Select different combinations of p and q.
- Observe how many valid key pairs each combination generates.
Room 24 · Valid key combinations
With p=3, q=11, n=33, φ=20, the student marks all (e, d) pairs from a list that form valid RSA keys (condition: gcd(e, 20)=1 and e·d ≡ 1 mod 20).
Student tasks
- Check the gcd for each candidate e.
- Calculate e·d mod 20 and mark the pairs that give 1: (3,7), (9,9), (13,17), (19,19).
Room 25 · Final challenge: discover the private key
Complete challenge with p=7, q=29, n=203, φ=168, e=5, m=2. The student must calculate d such that 5·d ≡ 1 mod 168, encrypt m and verify that decryption returns the original message.
Student tasks
- Calculate d as the inverse of 5 modulo 168 (answer: 101).
- Verify the encrypt-decrypt cycle with the values obtained.
Room 26 · Why is it hard to obtain d?
The attacker knows n and e but not φ(n). Multiple-choice question: why can't they directly apply the extended Euclidean algorithm to calculate d?
Student tasks
- Read the attacker's scenario.
- Select the correct reason: φ(n) is hard to calculate without knowing p and q.
Room 27 · Block encoding
In real practice, messages are not encrypted letter by letter: the full message is converted to bits and split into uniform blocks, each smaller than n (demo with the word "HOLA"). The student is asked what block size to use if n has k bits.
Student tasks
- Watch the block demo with the word "HOLA".
- Choose the correct block size: k−1 bits, to guarantee the block is always smaller than n.
Rooms to project
The most striking ones to show and discuss in class.