Part 5 — Asymmetric cryptography

Symmetric crypto (Part 4) is fast but has one enormous problem: both sides need the same key, and getting it to them is the whole difficulty. Asymmetric cryptography solves that, and in doing so makes HTTPS, SSH, signed software, and the entire public internet of trust possible.

Chapter 17 — The key-distribution problem and the big idea

In one sentence

Public-key cryptography gives everyone a pair of mathematically linked keys — one public, one private — so two strangers can communicate securely without ever having met.

The problem

You have AES-256. It's unbreakable in practice. Now encrypt a message to someone you've never met, over a network an attacker is watching.

   You need the recipient to have the key.
   You can't send the key over the network -- the attacker sees it.
   You can't have pre-shared it -- you've never met.
   You can't phone them -- the attacker may be on the phone line too,
       and anyway this has to work for a billion strangers at once.

This is the key-distribution problem, and for most of history there was no good answer. Militaries used couriers with locked briefcases. It did not scale.

   n people who all want to talk securely, pairwise, with symmetric keys:

        n = 10     ->  45 keys
        n = 1000   ->  499,500 keys
        n = 1e6    ->  ~500 billion keys

   Every new person needs a securely-delivered key to everyone else.

The idea in plain language

In 1976, Diffie and Hellman published an idea that sounds impossible:

What if encryption and decryption used different keys — and knowing the encryption key told you nothing useful about the decryption key?

Then you could publish the encryption key. Anyone — including your enemy — could use it to encrypt a message to you. But only you, holding the matching private key, could decrypt.

   ASYMMETRIC = a PAIR of keys

     PUBLIC KEY                          PRIVATE KEY
     - you publish it everywhere         - you never share it, ever
     - put it in DNS, on your website,   - it lives in one place
       on your business card            - losing it = losing your identity
     - anyone can have it                - leaking it = total compromise

   The two keys are linked by hard maths. What one does, only the other undoes.

The two things it lets you do

   1. ENCRYPT TO SOMEONE (confidentiality)
      Encrypt with their PUBLIC key  ->  only their PRIVATE key decrypts.
      "Anyone can put mail in the mailbox; only the owner has the key to open it."

   2. SIGN SOMETHING (authenticity + integrity)
      Sign with YOUR PRIVATE key     ->  anyone verifies with your PUBLIC key.
      "Only you can produce your wax seal; anyone can check it's yours."

Direction matters. Encrypt-to = their public key. Sign = your private key. Mixing these up is one of the most common conceptual errors — keep the mailbox and wax-seal analogies handy.

The catch: it's slow, so we use it sparingly

Asymmetric operations are hundreds to thousands of times slower than AES, and can only operate on small inputs. So the real world uses a hybrid scheme:

   1. Use asymmetric crypto ONCE to agree on a random symmetric key
        (this is called KEY ENCAPSULATION or KEY EXCHANGE)
   2. Use fast symmetric AEAD (AES-GCM / ChaCha20) for all the actual data

Every HTTPS connection you've ever made works exactly this way. Chapters 18–20 are the "step 1" options; Part 7 shows them assembled into TLS.

The three problems and which primitive solves each

Problem	Primitive	Chapters
Agree on a shared secret over a hostile network	Diffie–Hellman / ECDH	18, 20
Encrypt a small blob to a public key	RSA-OAEP / KEM	19
Prove a message came from you, unchanged	Signatures (RSA-PSS, ECDSA, EdDSA)	21
...and prove who a public key belongs to	Certificates / PKI	Part 7

That last row is the one people forget. Public-key crypto lets a stranger send you a secret — but which stranger? Binding a key to an identity is a separate problem, and it's what certificates exist for.

Practice (15 min)

mkdir -p ~/sec-lab/scratch && cd ~/sec-lab/scratch

# Make a keypair. Look at both halves.
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out priv.pem
openssl pkey -in priv.pem -pubout -out pub.pem

wc -c priv.pem pub.pem          # the private file is bigger -- it contains more
cat pub.pem                     # SHARE THIS
head -2 priv.pem; echo "..."    # NEVER share this

# The public key is DERIVED from the private key -- not the other way around
openssl pkey -in priv.pem -pubout | diff - pub.pem && echo "same public key"

Think it through: why can you regenerate the public key from the private key, but not the reverse? (That asymmetry is the entire field. Chapters 18–20 are three different hard problems that provide it.)

Common confusions

"The public and private keys are interchangeable." They are not. Each has a specific role. For RSA they happen to be structurally similar; for DH and elliptic curves they look nothing alike.
"Asymmetric crypto replaced symmetric crypto." No — it bootstraps it. Bulk data is always encrypted symmetrically.
"If I have someone's public key, I can impersonate them." No — you can encrypt to them and verify their signatures. You cannot sign as them.
"A bigger RSA key is like a bigger AES key." The numbers aren't comparable. RSA-2048 ≈ AES-112 in strength. See Chapter 20's table.

Check yourself

State the key-distribution problem in one sentence.
Which key do you use to encrypt a message to someone? Which to sign?
Why does the real world use hybrid (asymmetric + symmetric) encryption?
Public-key crypto lets a stranger send you a secret. What problem does it not solve on its own?

(Answers: Appendix F.)