The Project | About Us | Contribute | Donations | License

HOME

The previous module ended by exposing the crack running through everything we've built so far: AES-GCM, HMAC, even Argon2's pepper — all of it assumes the two parties already share a secret key. We've been parking the question of how that key got to both sides since 02-01. This lesson takes the biggest conceptual leap of the course: asymmetric cryptography, where keys are no longer a shared secret but a pair — one half is kept under lock and key, the other is published to the four winds. You'll see the mathematical intuition that makes it possible (one-way functions with a trapdoor), you'll build a toy RSA with small integers to understand what happens under the hood, and then you'll do it properly with pyca/cryptography: 3072-bit keys, OAEP padding, and PEM serialization. By the end, Clínica Sol will be able to send an encrypted message to MediNube without ever having agreed on a key beforehand — and you'll discover that this opens two new doors while leaving one uncomfortable question unanswered.

The paradigm shift: a pair of keys
One-way functions with a trapdoor
Toy RSA: the mathematics in miniature
Real RSA with pyca/cryptography
Why "textbook" RSA is insecure: OAEP padding
RSA's fundamental limits: size and speed
Key serialization: the PEM format
The uncomfortable question: whose public key is this?

The paradigm shift: a pair of keys

Every piece of cryptography from modules 2 and 3 is symmetric: the same key encrypts and decrypts, the same key generates and verifies the MAC. That forces sender and receiver to share a secret, and sharing secrets over a network anyone can listen in on is exactly the problem we don't know how to solve.

In 1976, Diffie and Hellman proposed breaking the symmetry: give each participant two mathematically linked keys:

The private key: generated locally, never leaves its owner's machine. It's the only secret.
The public key: derived from the private one and can be published anywhere — a website, an email, a repository. An attacker having it isn't a problem: it's designed to be public.

The magic lies in the relationship between the two: what one does, only the other can undo. From that come the two fundamental operations of asymmetric cryptography:

Operation	Who uses what	What it achieves	Goal (module 1)
Encrypt toward the owner	Anyone encrypts with the public key; only the owner decrypts with the private one	Only the recipient can read it	Confidentiality
Sign as the owner	The owner signs with the private key; anyone verifies with the public one	Anyone can check who issued it	Authenticity + non-repudiation

Notice the asymmetry in each row: with encryption, many can write, only one can read; with signing, only one can write, many can check. This is the complete map of what public-key cryptography offers — in this lesson we develop only the first row (encrypting). The second, the digital signature that owes us the non-repudiation promised since module 1, has its own lesson: 04-03.

For MediNube this changes the game: Clínica Sol can publish its public key, MediNube its own, and from then on anyone can send them encrypted data with no prior meeting, no secure channel, no shared secret.

flowchart LR
    subgraph ClinicaSol["Clínica Sol (sender)"]
        M[Plaintext message] -->|encrypts with MediNube's PUBLIC key| C[Ciphertext]
    end
    C -->|insecure network: anyone sees it, no one can read it| D
    subgraph MediNube["MediNube (recipient)"]
        D[Ciphertext] -->|decrypts with its PRIVATE key| M2[Plaintext message]
    end

One-way functions with a trapdoor

How can knowing the public key not let you deduce the private one? The answer is trapdoor one-way functions: operations that are easy to compute in one direction and computationally infeasible to reverse... unless you know one extra piece of data (the trapdoor).

RSA's trapdoor is integer factorization:

Easy (multiplying): given two large primes p and q, computing n = p × q is instant, even with thousand-digit numbers.
Infeasible (factoring): given only n, recovering p and q is a problem for which no efficient algorithm is known on classical computers. With a 3072-bit n, every computer on the planet working together wouldn't finish before the Sun burns out.

See it for yourself with plain Python:

import time

p = 1000000007          # a "small" prime (10 digits)
q = 998244353            # another prime

t0 = time.perf_counter()
n = p * q               # the easy direction
print(f"n = {n} computed in {time.perf_counter() - t0:.9f} s")

# The hard direction: given only n, find p and q by brute force.
t0 = time.perf_counter()
divisor = 3
while n % divisor != 0:
    divisor += 2
print(f"Factor {divisor} found in {time.perf_counter() - t0:.3f} s")

Multiplying takes nanoseconds; factoring this tiny ~60-bit n already costs seconds or minutes. And the cost of factoring grows exponentially with size, while multiplying stays cheap. RSA rests on that disproportion: whoever knows p and q (the trapdoor) can build the private key; whoever only sees n (part of the public key) cannot.

Toy RSA: the mathematics in miniature

Toy-example warning (golden rule 1). What follows uses ridiculously small primes and skips every protection. It's only meant to help you understand the mechanism. Never implement RSA by hand in production: use pyca/cryptography, as we'll do in the next section.

RSA key generation follows four steps:

# --- TOY RSA: for learning purposes only ---

# Step 1: pick two secret primes p and q.
p, q = 61, 53

# Step 2: compute the modulus n (public) and phi (secret).
n = p * q                 # 3233  -> part of the public key
phi = (p - 1) * (q - 1)   # 3120  -> computable only if you know p and q

# Step 3: pick the public exponent e (coprime with phi).
e = 17                    # in the real world, almost always 65537

# Step 4: compute the PRIVATE exponent d, the inverse of e mod phi.
d = pow(e, -1, phi)       # 2753  -> THE TRAPDOOR in action
print(f"Public key:  (n={n}, e={e})")
print(f"Private key: (n={n}, d={d})")

Key point: computing d requires phi, and computing phi requires p and q. Whoever only knows n = 3233 would have to factor it first. With n = 3233 you can do it in your head; with a 3072-bit n, no one can.

Encrypting and decrypting are the same operation with different exponents — raising to a power mod n:

m = 65                       # the "message" (a number smaller than n)

# Encrypt with the PUBLIC key (anyone can):
c = pow(m, e, n)             # 65^17 mod 3233 = 2790
print(f"Ciphertext: {c}")

# Decrypt with the PRIVATE key (only the owner can):
recovered = pow(c, d, n)     # 2790^2753 mod 3233 = 65
print(f"Decrypted: {recovered}")
assert recovered == m

It works thanks to Euler's theorem: (m^e)^d = m^(e·d) ≡ m (mod n) whenever e·d ≡ 1 (mod phi). You don't need to master the proof; you need the intuition: raising to e scrambles the message; only the exponent d — which requires the trapdoor — unscrambles it.

Also notice the structural limitation: the "message" is a number smaller than n. RSA doesn't encrypt streams of data; it encrypts a bounded-size number. Keep that in mind: it will be central to section 6.

Real RSA with pyca/cryptography

In the real world, key generation has dozens of subtleties (safe primes, primality tests, primes with the right distance apart...). pyca/cryptography handles all of that for you:

from cryptography.hazmat.primitives.asymmetric import rsa

private_key = rsa.generate_private_key(
    public_exponent=65537,   # the de facto standard; don't change it
    key_size=3072,           # bits of the modulus n
)
public_key = private_key.public_key()

print(private_key.key_size)                        # 3072
print(public_key.public_numbers().e)                # 65537
print(public_key.public_numbers().n.bit_length())   # 3072

public_exponent=65537: the e from our toy example. 65537 (2¹⁶+1) is the universal value: it makes encryption fast without weakening anything. There's no reason to use another one.
key_size: the size of n in bits, which sets the security level. 2048 bits is the minimum acceptable today (~112 bits of security); 3072 or more is recommended for new systems (~128 bits of security, our course standard per golden rule 5). Below 2048: broken or on the edge — forbidden.
The private_key object contains the public one (it's derived with public_key()); the reverse is impossible — that's the whole point.

Why "textbook" RSA is insecure: OAEP padding

Our toy example did c = m^e mod n directly on the message. That's called textbook RSA, and it's insecure for several independent reasons:

It's deterministic. The same message always produces the same ciphertext. An attacker who suspects the message is "POSITIVE" or "NEGATIVE" doesn't need to decrypt anything: they encrypt both candidates with the public key (which is public!) and compare. It's the same sin as ECB mode in 02-02 — determinism leaks information.
It's malleable. Because of the properties of powers, c · (2^e) mod n decrypts to 2m: an attacker can transform the ciphertext predictably without ever knowing it.
Small messages are fragile. With a small e and short, unpadded messages, there are direct algebraic attacks.

The fix is OAEP padding (Optimal Asymmetric Encryption Padding): before applying the RSA operation, the message is expanded with random, structured padding. Result: every encryption is different even if the message repeats, malleability is detected, and the algebraic attacks disappear. OAEP is to RSA what GCM was to AES: the correct way to use the primitive.

Let's see it with the course's thread: Clínica Sol sends MediNube a short encrypted notice, with no shared key set up beforehand:

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding

# MediNube generated its pair in the previous section and published public_key.
# Clínica Sol only needs that public key:

message = b"Patient ana.perez admission confirmed - Clinica Sol"

oaep = padding.OAEP(
    mgf=padding.MGF1(algorithm=hashes.SHA256()),  # internal mask generation function
    algorithm=hashes.SHA256(),                    # the OAEP scheme's hash
    label=None,                                   # almost never used; leave it None
)

ciphertext = public_key.encrypt(message, oaep)
print(len(ciphertext))   # 384 bytes: ALWAYS the size of n (3072 bits)

# Only MediNube, with the private key, can decrypt:
recovered = private_key.decrypt(ciphertext, oaep)
print(recovered.decode())

Points to internalize:

Padding is passed explicitly to every encrypt/decrypt call, and it must be the same on both sides. In pyca/cryptography there's no "RSA without padding" you could stumble into by accident — good.
Every run produces a different ciphertext (thanks to the random padding). Run encrypt twice with the same message and compare: they won't match, and both decrypt correctly.
The ciphertext is always the size of the modulus (384 bytes with a 3072-bit key), whether the message is 5 bytes or 300.
There's an older padding, PKCS#1 v1.5, still present in legacy protocols. For encryption, it has a history of attacks (Bleichenbacher, 1998, and its reincarnations): in new code, always OAEP.

RSA's fundamental limits: size and speed

You already saw in the toy example that RSA encrypts "a number smaller than n." With OAEP, the padding eats into part of that space; the real maximum is key_size - 2·hash_size - 2 bytes:

max_length = public_key.key_size // 8 - 2 * (256 // 8) - 2
print(max_length)   # 318 bytes with a 3072-bit key and OAEP-SHA256

full_record = b"X" * 50_000   # a real medical record
try:
    public_key.encrypt(full_record, oaep)
except ValueError as e:
    print("FAILS:", e)   # the message doesn't fit

And besides being small, it's slow. Compared with the symmetric cryptography from module 2:

	RSA-3072 + OAEP	AES-256-GCM
Key size	3072 bits (and it grows badly: 128 bits of security needs 3072; 256 would need ~15360)	256 bits
Max message per operation	318 bytes	Gigabytes, in practice
Encryption speed	Thousands of operations/s (decrypting, even fewer)	Gigabytes per second with AES-NI: thousands of times faster
Ciphertext expansion	Every message becomes 384 bytes	message + 12 (nonce) + 16 (tag)
Needs a prior shared secret	No	Yes

Conclusion worth keeping: RSA isn't for encrypting data; it's for encrypting keys. The universal pattern is to use asymmetric crypto to deliver a small symmetric key, and symmetric crypto (AES-GCM) for the real data. That pattern — hybrid encryption — is exactly lesson 04-05, where MediNube will send full record exports combining the best of both worlds. For now, hold on to the restriction.

Key serialization: the PEM format

An RSAPrivateKey object lives in a Python process's memory. To save it to disk, send the public one to a clinic, or load it at startup, you need to serialize it. The universal format is PEM: the key's bytes Base64-encoded between -----BEGIN...----- headers (recall 01-02: Base64 encodes, it doesn't encrypt — that's why the private key is, in addition, encrypted with a passphrase).

from cryptography.hazmat.primitives import serialization

# --- PRIVATE key: ALWAYS encrypted with a passphrase when saved ---
private_pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,       # the modern standard format
    encryption_algorithm=serialization.BestAvailableEncryption(
        b"a-real-long-passphrase-not-this-one"        # in real life: from a secrets manager
    ),
)
print(private_pem.decode()[:70])   # -----BEGIN ENCRYPTED PRIVATE KEY-----

# --- PUBLIC key: unencrypted, it's public ---
public_pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,  # the standard
)
print(public_pem.decode()[:30])   # -----BEGIN PUBLIC KEY-----

# --- Loading them back ---
private_key2 = serialization.load_pem_private_key(
    private_pem, password=b"a-real-long-passphrase-not-this-one"
)
public_key2 = serialization.load_pem_public_key(public_pem)

PKCS8 is the modern container format for private keys (you'll also see the legacy "TraditionalOpenSSL"; for new code, PKCS8).
BestAvailableEncryption(passphrase) encrypts the private PEM with the best the library offers. An unencrypted private key on disk is a naked secret: whoever reads the file is MediNube. The passphrase, as you learned in 02-04, goes through a KDF before becoming a key — the library does that for you.
SubjectPublicKeyInfo is the standard format for public keys; its name comes from the world of X.509 certificates, which we'll step into in module 5.
Where to keep the private PEM and its passphrase in production (permissions, secrets manager, HSM, rotation) is module 6's territory; here the minimum discipline is: encrypted private key, passphrase outside the repository.

The uncomfortable question: whose public key is this?

Let's close with the most important loose end. The full flow was: MediNube generates its pair, publishes public_pem, and Clínica Sol encrypts toward that key. But put yourself in the shoes of Clínica Sol's developer, who receives a medinube_public.pem file by email. How do they know that key really belongs to MediNube?

An attacker on the network (or one who compromises the email) can intercept the PEM and swap it for their own public key. The clinic would encrypt toward the attacker, who would decrypt, read the record, re-encrypt it with MediNube's authentic public key, and forward it. No one would notice a thing: encryption "works" on both legs. The mathematical confidentiality is perfect; the identity of the key is the broken link.

Asymmetric cryptography solves distributing encryption keys... and in exchange creates the problem of authenticated distribution of public keys. This problem has a solution — certificates and certificate authorities — but it needs pieces we don't have yet, so we leave it explicitly open until module 5. We'll come back to it, with more drama, in 04-04.

Common Mistakes and Tips

Confusing which key does what. You encrypt with the recipient's public key (not your own) and decrypt with your own private key. If you catch yourself encrypting with a private key, you're either signing (04-03) or confused.
Implementing RSA by hand "because the math is simple." This lesson's toy example skips safe prime generation, padding, protection against timing attacks (recall 01-04), and a dozen other things. Golden rule 1: use the library.
1024-bit keys (or smaller) in legacy code. If you're auditing MediNube and find key_size=1024, that's a security finding: factorable with serious resources. Minimum 2048, recommended 3072+.
Encrypting with PKCS#1 v1.5 in new code. It's the legacy padding with a history of attacks. For encryption, always OAEP.
Saving the private key as PEM without a passphrase (NoEncryption()). There are legitimate cases (an external secrets manager supplies the passphrase), but by default: BestAvailableEncryption.
Trying to encrypt large data with RSA by chunking it. Encrypting a file in 318-byte blocks with RSA is agonizingly slow and cryptographically fragile. The correct pattern is hybrid: patience until 04-05.
Trusting a public key received over an insecure channel. You just saw why. Until module 5, at least verify its fingerprint (SHA-256 hash of the PEM, as in 03-01) over a second channel.

Exercises

Complete toy example. With p = 11, q = 19, and e = 7, work out by hand (with Python's help for pow) the values of n, phi, and d; encrypt the message m = 8 and check that it decrypts correctly. Why does an attacker who sees n = 209 and e = 7 take mere seconds to break it, while with a 3072-bit n they can't?
The sin of determinism. Write a function guess_result_BAD(ciphertext, public_key) that demonstrates the attack on textbook RSA: using the toy RSA (no padding), and knowing the message can only be 1 ("POSITIVE") or 0 ("NEGATIVE"), recover the message without knowing the private key. Explain why OAEP makes this attack impossible.
Exchanging PEMs. Simulate the MediNube ↔ Clínica Sol integration bootstrapping: (a) generate MediNube's RSA-3072 pair and serialize it (private key with a passphrase, public key in the clear); (b) "send" the public key to Clínica Sol (a variable), which loads it with load_pem_public_key and encrypts the message b"Access request for ana.perez's record" with OAEP; (c) MediNube loads its private key from the PEM with the passphrase and decrypts. (d) Compute the maximum number of encryptable bytes and check with try/except what happens when encrypting a 400-byte message.

Solutions

p, q, e = 11, 19, 7
n = p * q                  # 209
phi = (p - 1) * (q - 1)    # 180
d = pow(e, -1, phi)        # 103  (7·103 = 721 = 4·180 + 1)
c = pow(8, e, n)           # 8^7 mod 209 = 46
assert pow(c, d, n) == 8   # 46^103 mod 209 = 8 ✔

With n = 209, the attacker tries divisors and factors it instantly (209 = 11 × 19), rebuilds phi = 180, and computes d exactly like the owner did. With 3072 bits, factoring isn't "slower": it's infeasible — the cost grows superpolynomially with size, and no efficient classical algorithm exists. RSA's security is exactly the hardness of that problem.

def guess_result_BAD(ciphertext, n, e):
    # The attacker encrypts BOTH candidates with the public key and compares.
    for candidate in (0, 1):
        if pow(candidate, e, n) == ciphertext:
            return "POSITIVE" if candidate == 1 else "NEGATIVE"

c = pow(1, 7, 209)                     # the clinic encrypts "POSITIVE"
print(guess_result_BAD(c, 209, 7))     # POSITIVE — without ever touching the private key

The attack works because textbook RSA is deterministic: encrypting the same message always gives the same result, and the attacker can encrypt (the key is public). OAEP adds random padding on every encryption: the two ciphertexts of the same candidate never match, so comparing tells you nothing. (Bonus: pow(0, e, n) == 0 and pow(1, e, n) == 1 — textbook RSA doesn't even hide 0 and 1!)

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding

# (a) MediNube
priv = rsa.generate_private_key(public_exponent=65537, key_size=3072)
pem_priv = priv.private_bytes(
    serialization.Encoding.PEM, serialization.PrivateFormat.PKCS8,
    serialization.BestAvailableEncryption(b"medinube-passphrase"))
pem_pub = priv.public_key().public_bytes(
    serialization.Encoding.PEM, serialization.PublicFormat.SubjectPublicKeyInfo)

# (b) Clínica Sol
oaep = padding.OAEP(mgf=padding.MGF1(hashes.SHA256()),
                    algorithm=hashes.SHA256(), label=None)
clinic_pub = serialization.load_pem_public_key(pem_pub)
ciphertext = clinic_pub.encrypt(b"Access request for ana.perez's record", oaep)

# (c) MediNube
priv2 = serialization.load_pem_private_key(pem_priv, password=b"medinube-passphrase")
print(priv2.decrypt(ciphertext, oaep))

# (d) Limit
print(3072 // 8 - 2 * 32 - 2)   # 318 bytes
try:
    clinic_pub.encrypt(b"X" * 400, oaep)
except ValueError as e:
    print("FAILS:", e)          # Data too long / Encryption failed

Step (b) holds the exercise's conceptual trap: Clínica Sol accepts pem_pub without verifying whose it is. It works, but it's the hole from the last section — module 5.

Conclusion

You've crossed the course's conceptual frontier. Asymmetric cryptography replaces the shared secret with a pair of keys: the private one never leaves home; the public one is handed out without fear. Its foundation is trapdoor one-way functions — for RSA, multiplying primes is easy and factoring the product is infeasible —, and you've seen it from the inside with a toy RSA (d = pow(e, -1, phi)) and from the outside with the real thing: rsa.generate_private_key (3072 bits recommended), mandatory OAEP padding because "textbook" RSA is deterministic and malleable, and PEM serialization with the private key always encrypted (BestAvailableEncryption). You also know its two limits: it only encrypts tiny messages (318 bytes with a 3072-bit key) and it's thousands of times slower than AES — RSA encrypts keys, not data (the hybrid pattern arrives in 04-05) —, and it carries an unanswered question: how do you know whose public key it is? (module 5). But before we settle any of that, there's a practical problem to discuss: RSA keys are huge and grow badly — 256 bits of security would need ~15360 bits of key. There's another family of trapdoors that gives the same guarantees with keys of only 256 bits, and it's the one that dominates modern cryptography, from your phone to TLS. It's elliptic curve cryptography, and it's waiting for you in the next lesson, 04-02. See you there.

Public-Key Fundamentals and RSA

Contents

The paradigm shift: a pair of keys

One-way functions with a trapdoor

Toy RSA: the mathematics in miniature

Real RSA with pyca/cryptography

Why "textbook" RSA is insecure: OAEP padding

RSA's fundamental limits: size and speed

Key serialization: the PEM format

The uncomfortable question: whose public key is this?

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Applied Cryptography Course

Module 1: Cryptography Fundamentals

Module 2: Symmetric Cryptography

Module 3: Hashes, MACs, and Passwords

Module 4: Asymmetric Cryptography

Module 5: PKI, Certificates, and TLS

Module 6: Cryptography in Real-World Development