Public Key Encryption (RSA) · Computer Networking Interactive

For two thousand years, encrypted conversation required a secret agreed in advance. Public key cryptography removed that requirement.

Words you will meet

Public key encryption — two keys, one published and one kept.
Public key K⁺ — known to the whole world, and used to encrypt.
Private key K⁻ — known only to its owner, and used to decrypt.
RSA (Rivest–Shamir–Adleman) — the algorithm that became almost synonymous with public key cryptography.
Modular arithmetic — ordinary arithmetic, with every result replaced by its remainder after dividing by n.
Session key — a cheap symmetric key, sent once under the expensive public key.

Why this matters

Everything in section 8.2.1 had one problem in common, and it was not the cipher. Alice and Bob had to agree on a secret key, and agreeing on it securely requires a secure channel — which is the thing they were trying to build.

Two of Caesar’s centurions could meet at the Roman baths. Two machines on the Internet may never meet, and may never communicate except over the network they are trying to protect.

In 1976 Diffie and Hellman showed that the requirement could simply be dropped. Every secure protocol in the rest of this chapter rests on that.

The idea, before any arithmetic

Bob has two keys instead of one.

His public key K_B⁺ is published to the entire world, Trudy included. His private key K_B⁻ is known to nobody but him.

Alice encrypts with the public key. Bob decrypts with the private one: K_B⁻(K_B⁺(m)) = m. They have never met, and no secret has ever crossed the channel.

Figure 8.6 — one key locks, the other unlocks

Bob makes one key public and keeps the otherstep 1 of 4

The public key K⁺ is available to everyone in the world, Trudy included. The private key K⁻ is known only to Bob. Nothing secret has to be agreed with anyone.

The strange step is the first one. Bob publishes half his key pair to the entire world, including Trudy, and that is what makes the rest work.

Read all steps as text

Bob makes one key public and keeps the other — The public key K⁺ is available to everyone in the world, Trudy included. The private key K⁻ is known only to Bob. Nothing secret has to be agreed with anyone.
Alice encrypts with the public key — Alice looks up Bob's public key and computes K⁺(m). She and Bob have never met and have never shared a secret.
Only Bob can undo it — Bob applies his private key: K⁻(K⁺(m)) = m. Trudy has the public key and the ciphertext and still cannot read it, because undoing needs the half Bob never published.
And it works in the other order too — K⁺(K⁻(m)) = m as well. That symmetry looks like a curiosity here and turns out to be the whole basis of digital signatures in section 8.3.

The fourth panel is worth pausing on. The two keys also work in the other order: K_B⁺(K_B⁻(m)) = m. Applying the private key first produces something anyone can undo — which sounds useless, until you notice that only Bob could have produced it. Section 8.3 turns that into a signature.

What public key encryption gives up

With one shared secret key, the fact that the sender could encrypt the message identifies them. Only two people hold the key.

With public key encryption that disappears. Bob’s encryption key is public, so anyone can send him an encrypted message — including someone claiming to be Alice. Confidentiality is gained and sender identity is lost, and getting it back is what section 8.3 is for.

Symmetric against public key

	Symmetric key§8.2.1	Public key§8.2.2
How many keys, and who holds them
What must be agreed in advance
Cost
Does the ciphertext identify the sender?

Cells marked ⓘ have a reason behind them — click to read it.

Neither replaces the other, and section 8.5 onward uses both together in every protocol. Click any cell.

RSA

RSA (Rivest–Shamir–Adleman) is named after Ron Rivest, Adi Shamir and Leonard Adleman. It rests entirely on modular arithmetic, so start there.

x mod n is the remainder when x is divided by n. So 19 mod 5 = 4. Addition, multiplication and exponentiation all work as usual, except that each result is replaced by its remainder after division by n. Three facts make that manageable:

[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) − (b mod n)] mod n = (a − b) mod n
[(a mod n) × (b mod n)] mod n = (a × b) mod n

From the third comes the identity the whole algorithm turns on: (a mod n)ᵈ mod n = aᵈ mod n.

One more thing before the steps. A message is a bit pattern, and every bit pattern is an integer — the pattern 1001 is the number 9. Encrypting a message with RSA means encrypting the integer that represents it.

Bob generates his keys — the five steps

Step	What Bob does	In the book's example

Cells marked ⓘ have an explanation — click to read it.

Steps 3 and 4 are the ones people skip. They are what make decryption possible at all.

Encryption and decryption are then one line each. Alice sends c = mᵉ mod n, using the public key. Bob recovers m = cᵈ mod n, using the private one. The message must satisfy m < n.

RSA, on your own choices

Bob generates his keys

1. two primes — pand q3. e, sharing no factor with zAlice’s message

2. n = pq: 35
z = (p−1)(q−1): 24
5. public key (n, e): (35, 5)
private key (n, d): (35, 29)

Step 4 found d = 29, because 5 × 29 − 1 = 144 divides exactly by z = 24.

letter	m	m^e	c = m^e mod n	c^d	c^d mod n
l	12	248832	17	481968572106750915091411825223071697(36 digits)	12 ✓
o	15	759375	15	12783403948858939111232757568359375(35 digits)	15 ✓
v	22	5153632	22	851643319086537701956194499721106030592(39 digits)	22 ✓
e	5	3125	10	100000000000000000000000000000(30 digits)	5 ✓

It starts on the book's own toy example: p = 5, q = 7, e = 5, sending "love". Change e and watch d change with it. Choose p = q, or an e that shares a factor with z, and watch step 4 fail — those constraints are load-bearing, not decoration.

Worked: the book’s own example

Bob picks p = 5 and q = 7, which are far too small to be secure but small enough to print. Then n = 35 and z = 24. He picks e = 5, which shares no factor with 24, and finds d = 29, because 5 × 29 − 1 = 144 divides exactly by 24.

Alice sends the letters of “love”, numbering them a = 1 to z = 26.

letter	m	mᵉ	c = mᵉ mod 35
l	12	248,832	17
o	15	759,375	15
v	22	5,153,632	22
e	5	3,125	10

Notice o and v: their ciphertext equals their plaintext. That is not a bug, and with numbers this small it is not even unlikely. It is one more reason the example is a toy.

Three numbers in Table 8.3 are wrong in the printed book

The book’s decryption table prints the full value of cᵈ for each letter. Three of those four numbers do not match the arithmetic, and the errors were confirmed against the page image rather than the text extraction.

c	printed	actual	what went wrong
17	40 digits	36 digits	a four-digit group duplicated
15	39 digits	35 digits	a four-digit group duplicated
22	39 digits	39 digits	correct
10	10³¹	10²⁹	two extra zeros

The recovered column — 12, 15, 22, 5 — is correct in every row, so the example still teaches what it should. But the book invites the reader to check the arithmetic, and a reader who does will fail to reproduce three of these numbers. The widget above computes them correctly, and tools/check-rsa-ch08.mjs verifies all of it.

Why it works

The derivation is four lines, and each one is an equality you can check.

Encrypting then decrypting gives (mᵉ mod n)ᵈ mod n. By the identity above with a = mᵉ, that equals m^(ed) mod n.

Now the one result the book borrows from number theory: if p and q are prime, n = pq and z = (p−1)(q−1), then xʸ mod n is the same as x^(y mod z) mod n. Applying it with x = m and y = ed gives m^(ed mod z) mod n.

And e and d were chosen precisely so that ed mod z = 1. So the whole thing is m¹ mod n, which is m.

Press “Show why the round trip closes” in the widget and those four values are computed for whatever keys you chose. They are equal because the algebra says so, not because the widget was told to say they are.

In plain words

Step 4 looks like an arbitrary condition on d. It is not.

ed mod z = 1 is exactly the condition that makes the exponent vanish at the end of the derivation. Everything else in RSA is arithmetic; that one line is where the private key is defined to be the thing that undoes the public one.

Session keys, because RSA is slow

Exponentiating large numbers is expensive. Look at the cᵈ column in the widget: even with p = 5 and q = 7, the numbers run to dozens of digits.

So RSA is almost never used to encrypt the data. Instead:

Alice chooses a random symmetric session key K_S — the kind of key section 8.2.1 uses, for a cipher such as DES (Data Encryption Standard) or AES (Advanced Encryption Standard) .
She encrypts K_S with Bob’s public key: c = (K_S)ᵉ mod n.
Bob decrypts c with his private key and now knows K_S.
Everything after that is symmetric, and cheap.

The expensive algorithm is used once, on a very small message, to bootstrap the cheap one. Watch for this pattern in PGP (Pretty Good Privacy) , in TLS (Transport Layer Security) and in IPsec (IP Security) — it is the same three lines every time.

The mental model

Symmetric cryptography is a lock where the same key locks and unlocks, so the key has to travel. Public key cryptography is a lock where the key that closes it cannot open it, so the closing key can be given to everybody.

RSA builds that from modular exponentiation with two exponents chosen so that applying both, in either order, returns you to where you started.

And because it is slow, it is used to carry a symmetric key rather than to carry data. That is why both halves of section 8.2 are present in every real protocol that follows.

Check yourself

0 of 7 answered

1.What problem does public key cryptography remove, that every symmetric scheme has?
2.Bob chooses p = 5 and q = 7. What are n and z?
3.Step 3 requires e to share no factor with z. What happens if you ignore it?
4.predictIn the book's example, Alice encrypts the letter o (m = 15) and gets ciphertext 15. Is something wrong?
5.Why does RSA's round trip return the original message?
6.Why is RSA almost never used to encrypt the data itself?
7.Applying the private key first, K⁻(m), produces something anyone can undo with the public key. What is that good for?

What to remember

The keys work in both orders, and the second order is not a curiosity. K⁻(K⁺(m)) = K⁺(K⁻(m)) = m, and applying the private key first produces something anyone can check but only Bob could have made — which is a signature.
Public key encryption gains confidentiality and loses sender identity. Anyone can encrypt to Bob, so the ciphertext no longer says who wrote it, and section 8.3 exists to bind a sender back to a message.
RSA is used to carry a key, not to carry data. The exponentiation is expensive, so the public key encrypts one small session key and a symmetric cipher does everything else — the pattern every protocol in this chapter repeats.