RSA Comic Classroom: From Prime Numbers and Fermat's Theorem to Public-Key Cryptography

The story starts before Alice and Bob share a secret

Start with the first-key problem

Imagine that Alice owns a strong box, but locking and unlocking it require the same key. The box is useful only after Bob has a copy. Sending that key along the road does not solve the problem, because Eve can copy anything that passes her.

Adding another shared key merely moves the question back one step: how did Bob receive that key safely? The hard part is the first secret, before Alice and Bob have a protected channel.

Public-key cryptography separates locking from unlocking. Bob publishes the locking operation and keeps the private material needed to unlock. After obtaining and authenticating Bob’s public key, Alice can protect content for him without first sharing a secret key. We examine whose key it is in section 10.

Name the mathematical job

The design needs related operations with unequal capabilities. The public direction should be easy; recovering the private operation from public information alone should be impractical. Eve may know both the algorithm and public parameters. RSA is one mathematical construction for this division of capabilities. ^[1]

Return to the real system

The letter in the comic will soon become a small integer so we can inspect the mechanism. That toy integer explains the structure; it is not a recipe for placing a real document directly into a classroom formula. Real systems should use mature, reviewed cryptographic libraries rather than a hand-built version of the lesson.

Prime numbers are the building blocks

Picture primes as building blocks

A prime is a whole number greater than one with exactly two positive divisors: 1 and itself. That makes 2, 3, 5, 7, and 11 prime. The number 15 is composite because it can be taken apart as 3 × 5.

Think of primes as the indivisible building blocks of whole numbers. Every integer greater than one can be written as a product of primes, and—apart from their order—the final collection of prime factors is unique.

Factor the toy number

Try the number 55. It is not even, its digits do not sum to a multiple of three, and its final digit tells us to try five. Dividing gives 11, so 55 = 5 × 11.

That was easy because 55 is tiny. Multiplying two known primes stays straightforward as the numbers grow; receiving only an enormous product and recovering the unknown factors is a different computational task.

Computers can generate candidates and test them for primality efficiently. That does not mean they can factor every enormous composite integer equally efficiently. Finding suitable blocks and dismantling an unknown finished structure are not the same problem.

Why RSA uses this asymmetry

RSA uses this gap by publishing a product n while protecting its chosen factors. Our 5 and 11 teach that shape, but they provide no security at all—anyone can factor 55 at a glance. ^[1]

Modulo arithmetic turns a number line into a clock

Picture a wrapping clock

An ordinary number line keeps going. A clock wraps around. Modulo arithmetic asks where a number lands after complete laps have been discarded, so 17 mod 5 means: divide 17 into groups of five and keep the remainder.

Work through the remainders

Write the division first: 17 = 3 × 5 + 2. Three full laps disappear and the answer is 2. This is exactly what the compact notation 17 mod 5 = 2 records.

Addition wraps too. Since 4 + 4 = 8 and 8 leaves remainder 3 after division by 5, we write 4 + 4 ≡ 3 (mod 5). The symbol ≡ does not claim that 8 and 3 are ordinary equal integers; it says they occupy the same position on this five-step clock.

For multiplication, 3 × 4 = 12 and 12 = 2 × 5 + 2, so 3 × 4 ≡ 2 (mod 5). Every answer in this world lies among 0, 1, 2, 3, and 4.

Why RSA needs modulo

RSA uses modular exponentiation: multiply repeatedly, reducing modulo n as you go. Even when the exponent looks intimidating, the running values remain inside a finite remainder world. Those finite positions are where the useful cycles appear.

Fermat noticed a repeating pattern

Watch the cycle first

Set the clock size to the prime number seven and keep multiplying by two. The first powers land at 2, then 4, then 1 because 2³ = 8 leaves remainder 1. Continue, and the same 2, 4, 1 path begins again.

The exponent keeps increasing, but the remainders cannot wander forever. Seeing that loop first makes the theorem feel less like a line dropped from the sky.

Read the theorem with its conditions

Fermat's little theorem says: if p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). Put in p = 7 and a = 2, and it gives 2⁶ ≡ 1 (mod 7). Our shorter three-step loop reaches 1 twice by the sixth power.

Both conditions belong to the theorem. The modulus must be prime, and a must not already be a multiple of that prime. Removing either condition turns a useful statement into a misleading slogan.

This still is not RSA. It tells us how powers cycle under a prime modulus, while RSA publishes a modulus built from two primes.

Connect this gear to RSA

Euler's theorem supplies the broader cycle we need. Fermat's result is the first gear, not the whole machine.

Euler carries the cycle beyond a single prime

Start with coprime numbers

First we need one small word. Two integers are coprime when their greatest common divisor is one. Thus 7 and 55 are coprime because they share no factor except 1; 5 and 55 are not, because their greatest common divisor is 5.

Coprime does not mean that both numbers must be prime. It only describes the relationship between them, and that relationship is the condition for the cycle we are about to use.

Count the cycle

Euler's totient φ(n) counts how many positive integers below n are coprime to n. For n = pq with two distinct primes, we can calculate the count as φ(n) = (p−1)(q−1).

Our primes will be 5 and 11. Therefore n = 55 and φ(55) = (5−1)(11−1) = 4 × 10 = 40. The number 40 is not a secret code; it counts the usable coprime positions below 55.

Euler's theorem says that a^φ(n) ≡ 1 (mod n) when a and n are coprime. In our example, that becomes a⁴⁰ ≡ 1 (mod 55).

Use the cycle to pair exponents

RSA will choose two exponents whose product is a whole number of these forty-step cycles plus one extra step. The complete cycles collapse to 1, while that extra step preserves the original message representative.

Build the public modulus from two secret primes

Build n in Bob's workshop

Bob now chooses p = 5 and q = 11 in private. Think of this as selecting the two building blocks inside his workshop. He multiplies them to obtain n = pq = 55.

From this point on, the roles split. The product n belongs in the public key and appears in both encryption and decryption. The factors p and q stay private because they immediately reveal the cycle information used to build the private exponent.

Collect the numbers

Our scratch pad now reads p = 5, q = 11, n = 55, and φ(n) = (p−1)(q−1) = 40. We do not yet have a key pair; the two matching exponents come next.

The number 55 is deliberately, almost comically, unsafe. Its only purpose is to let a reader check every division and remainder without special software.

Keep toy and real RSA separate

Real RSA key generation uses much larger, carefully generated primes and mature libraries. 'Hard to factor' is a claim about feasible attacks, resources, and time—not a proof that factorization is mathematically impossible.

Choose two exponents that undo each other

Choose the public side

Bob first chooses the public exponent e. It must be coprime to φ(55) = 40 so that another number can pair with it on the modulo-40 clock. We choose e = 3, and gcd(3, 40) = 1, so it qualifies.

Ask the partner question before naming it: what can we multiply by 3 so that the result leaves remainder 1 after division by 40?

Solve for d

Count by threes: 3 × 1 = 3, 3 × 2 = 6, and so on until 3 × 27 = 81. Since 81 = 2 × 40 + 1, it leaves remainder 1. We have found d = 27. In mathematical language, ed ≡ 1 (mod 40), and d is the multiplicative inverse of e modulo 40.

The useful picture is ed = 81 = 1 + 2 × 40: two complete forty-step cycles, plus one step. That final step is what will leave the original message in place after a round trip.

Separate public and private material

We can now write the public key as (n, e) = (55, 3). Alice may receive it and Eve may see it.

The private side keeps d = 27 and normally retains protected factors and related implementation data. The value d is calculated from the key relationship; it is not a memorable password chosen by Bob.

Use the public key: 7 becomes 13

Give 7 a role

To keep the arithmetic visible, let Alice's teaching message be the integer m = 7. This is a message representative—a small stand-in for data—not a claim that real files are dropped unchanged into this classroom equation.

Alice has Bob's public key (n, e) = (55, 3). The public operation is c = m^e mod n, where c names the ciphertext representative.

Substitute one line at a time

Substitute first: c = 7³ mod 55. Calculate the power: 7³ = 343. Divide to expose the remainder: 343 = 6 × 55 + 13. Therefore c = 13, and the first half of our path is 7 → 13.

Watch the modulus. Modulo 40 was used to pair e and d; modulo 55 is used when the message travels through the RSA operation. Replacing 55 with 40 would calculate a different problem.

What the public operation achieves

Alice performed every step with public information. Eve can also see the public key, the algorithm, and the value 13; the construction assumes all of that is visible while the private material remains difficult to recover.

Use the private key: 13 returns to 7

Bob starts from 13

Bob receives the same visible number Eve saw: c = 13. His advantage is the private exponent d = 27, which lets him calculate m = c^d mod n = 13²⁷ mod 55.

Why the cycle returns to 7

To see why the answer returns to seven, join the two operations. Raising m to e and then to d gives m^(ed), and our exponents were chosen so ed = 3 × 27 = 81 = 1 + 2 × 40.

Because 7 is coprime to 55, Euler's theorem gives 7⁴⁰ ≡ 1 (mod 55). Then 7⁸¹ = 7 × (7⁴⁰)². Both complete cycles become 1, leaving the extra factor of 7.

You can also verify the private operation without expanding 13²⁷. Start with 13² = 169 = 3 × 55 + 4, then 13⁴ ≡ 4² = 16. Next, 13⁸ ≡ 16² = 256 = 4 × 55 + 36, and 13¹⁶ ≡ 36² = 1296 = 23 × 55 + 31.

Since 27 = 16 + 8 + 2 + 1, combine the required pieces: 13²⁷ ≡ 31 × 36 × 4 × 13 (mod 55). Reduce after each multiplication: 31 × 36 ≡ 16, then 16 × 4 ≡ 9, and 9 × 13 ≡ 7.

Read the round trip

The complete toy machine is now visible: the public operation sends 7 → 13, and the private operation sends 13 → 7. Anyone can do the first; only the holder of the protected private material should be able to do the second efficiently.

This demonstrates the key relationship, not production security.

A public key still needs a trusted name tag

A public key has no built-in name

Public means that everyone may see and use a key. It does not mean that the key arrives with an unforgeable name tag. Eve could replace Bob's public key with her own and simply label it 'Bob.'

Alice's calculation would still succeed. The secret would be locked correctly—just for Eve. Nothing in the multiplication itself can detect that Alice trusted the wrong owner.

Check identity, not arithmetic

Alice therefore needs an authentic copy of Bob's public key. She might compare a fingerprint through another trusted channel, or rely on a certificate whose name, validity period, issuer, and trust path are checked. ^[4]

A certificate is evidence inside a verification process, not a magic badge that should always be accepted. Software has to perform the checks that connect the key to the intended identity.

Keep two questions separate

Keep two questions separate. Mathematics asks whether a public and private key form a working pair. Authentication asks whether the matching private key is controlled by Bob. A secure connection needs both answers.

'Key exchange' can describe two different stories

Picture two ways to share

First picture Alice choosing a small secret K, placing it in a box only Bob can open, and sending the box to him. Both sides end with K, but Alice chose the whole value. This pattern is called key transport, and RSA can participate in this kind of one-sided delivery. ^[2]

Now picture Alice and Bob each bringing one ingredient to a public table. They exchange allowed information and independently derive the same final mixture. Neither person selected the complete secret alone. This is key agreement; Diffie–Hellman is the classic historical example. ^[3]

Ask who chose the secret

You do not need another equation to tell them apart. Ask who determined the final shared secret. If one party chose K and delivered it securely, that is transport. If both parties contributed and derived K locally, that is agreement.

Casual conversation often calls both patterns 'key exchange' because their endpoint looks similar: Alice and Bob share a secret. The path matters, however, because the responsibilities and security properties are not identical.

Return to Alice and Bob

This brings us back to the opening problem. Public-key techniques help two parties establish a first shared secret over a watched channel, but identity checks, protected private material, good randomness, and trusted implementations are still part of the answer.

Walk the RSA story from beginning to end

Retell the idea

In plain language, Bob built a lock that anyone may close while keeping the opening ability to himself. Prime factors create the useful asymmetry, modular arithmetic supplies a finite clock, and Fermat and Euler explain why powers return to predictable positions.

Retell the arithmetic

The full scratch pad is p = 5, q = 11, n = 55, and φ(n) = 40. Choose e = 3 and calculate d = 27 because 3 × 27 = 81 = 1 + 2 × 40. The public key is (55, 3); the private side protects d and the related secret material.

Alice computes 7³ mod 55 = 13. Bob computes 13²⁷ mod 55 = 7. That gives the complete classroom round trip 7 → 13 → 7, with a reason for every number instead of a list of magic constants.

Return to a reliable system

The equations answer one question: why do these public and private operations fit together? A reliable system must also generate and protect keys, authenticate the public key's owner, choose the right way to establish a shared secret, and use a mature implementation.

If you can retell both halves—the human problem and the number cycle—you understand the foundation. Deeper protocol engineering can wait until this picture feels solid.

Five points to keep

1. RSA begins with the first-key problem: make the locking operation public while keeping the way back private.
2. Prime factors build n; modular arithmetic, Fermat, Euler, and φ(n) reveal the cycles used to pair the exponents.
3. The teaching values are p = 5, q = 11, n = 55, φ(n) = 40, e = 3, and d = 27; d is a calculated modular inverse, not a password, and the data path is 7 → 13 → 7.
4. Bob may publish (n, e), but he protects d and the prime factors—and Alice must verify that the public key really belongs to Bob.
5. Key transport lets one party choose the secret; key agreement lets both parties contribute to deriving it.

Continue with the Shor classroom when you want to see why a large quantum computer would change the factoring assumption behind RSA.

References

1. Rivest, Shamir, and Adleman (1978), Communications of the ACM 21(2): The original RSA paper: key construction, modular exponentiation, and the factoring-based trapdoor idea.
2. NIST SP 800-56B Rev. 2: Official terminology and requirements for integer-factorization key-establishment schemes, including RSA-based key transport.
3. Diffie and Hellman, New Directions in Cryptography (1976): The landmark paper introducing public-key concepts and a two-party key-agreement method.
4. RFC 5280, Internet X.509 Public Key Infrastructure Certificate and CRL Profile: Certificate structures that bind public keys to named subjects through a trust chain.