Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 40 ยท Public-Key Cryptography

Public-Key Cryptography: The Big Idea

Understand asymmetric cryptography: key pairs, one-way trapdoor functions, hybrid encryption, and why a 3072-bit RSA key and a 256-bit curve key are comparable.

Everything in the symmetric chapters rested on one uncomfortable assumption: both sides already share a secret key. That is fine for a disk you encrypt yourself, but how do you and a web server you have never contacted agree on a key when everyone on the network can listen in? For centuries the answer was "you cannot; you must meet in person or use a courier". In the 1970s that answer changed.

Public-key cryptography, also called asymmetric cryptography, replaces the single shared key with a key pair: a public key that you hand to anyone, and a private key that you never share. What one key does, only the other can undo. This lesson explains the idea, the mathematical trick that makes it work, how real systems combine it with symmetric ciphers, and how key sizes compare. The next lessons build the actual algorithms.

Two keys instead of one

A key pair gives you two different kinds of service, depending on which key you use for which side.

  • Encryption. Anyone can encrypt a message with your public key. Only your private key can decrypt it. Think of a mailbox with a slot: everybody can drop letters in, only the owner has the key to open it.
  • Digital signatures. You sign with your private key. Anyone can verify the signature with your public key. Only you could have produced it, so it proves who wrote the message and that it was not changed. This is covered in Digital Signatures.
  • Key agreement. Two parties each combine their own private key with the other's public key and arrive at the same secret, without ever sending it. See Diffie-Hellman.
flowchart LR
    subgraph Encrypt["Encryption"]
        direction LR
        M1["Message"] -->|"public key of Bob"| C1["Ciphertext"]
        C1 -->|"private key of Bob"| M2["Message"]
    end
    subgraph Sign["Signature"]
        direction LR
        M3["Message"] -->|"private key of Alice"| S1["Signature"]
        S1 -->|"public key of Alice: verify"| V["Valid or not"]
    end

The same key pair gives confidential messages to its owner and unforgeable signatures from its owner.

Note what has changed about key distribution. A public key is not secret, so it can travel over an open channel, be posted on a website or printed on a business card. What must be protected is its authenticity: you need to be sure that the public key really belongs to Bob and not to an attacker. That problem is solved by certificates, and it is why public-key cryptography does not make trust disappear; it moves it.

One-way functions and trapdoors

A key pair only works if the public key does not reveal the private key. The mathematical tool is a one-way function: easy to compute in one direction, believed to be infeasible to reverse.

Two examples carry almost all of today's public-key cryptography:

  1. Multiplying versus factoring. Multiplying two 1,500-digit primes takes microseconds. Given only the product, finding the primes is far beyond any known method. This is the basis of RSA.
  2. Exponentiation versus discrete logarithm. Computing g**x mod p is fast (see modular arithmetic). Recovering x from the result is the discrete logarithm problem. Diffie-Hellman and elliptic curve cryptography rest on it.

A plain one-way function is not enough for encryption, because the legitimate receiver must be able to reverse it. A trapdoor one-way function is easy to reverse if you know a secret (the trapdoor) and infeasible otherwise. In RSA, the secret is the factorization of the modulus. The experiment below makes the asymmetry visible by counting the work, not the time, so the result is the same on every machine.

Python Easy to multiply, hard to factor

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The work to factor grows with the size of the smaller prime, while the forward direction stays one multiplication. Smarter algorithms than trial division exist, but the best known ones are still super-polynomial in the number of digits, which is what keeps 2048-bit moduli safe today.

Hybrid encryption: the way it is really done

Public-key operations are slow, and they can only handle short inputs. RSA, for example, can encrypt at most a number smaller than its modulus. A single RSA operation on a 2048-bit key is roughly a thousand times slower than AES on the same amount of data. So no real system encrypts bulk data with a public key. Instead they use hybrid encryption:

  1. The sender generates a random one-time symmetric key.
  2. The sender encrypts the actual message with that key using an authenticated cipher.
  3. The sender encrypts (or agrees on) only the small symmetric key with the receiver's public key.
  4. The receiver recovers the symmetric key with the private key and decrypts the message.
sequenceDiagram
    participant A as Alice
    participant B as Bob
    A->>A: Generate random session key K
    A->>A: Encrypt message with K (fast, symmetric)
    A->>B: Public-key encryption of K + symmetric ciphertext
    B->>B: Recover K with the private key
    B->>B: Decrypt the message with K

Public-key cryptography moves the small key; symmetric cryptography moves the data.

This is the structure of TLS, PGP, age, S/MIME and almost every other encryption protocol. The demo below uses a famously tiny textbook key (n = 61 * 53 = 3233, public exponent 17, private exponent 2753) to wrap each byte of a session key. It is far too small to be secure, and the next lesson explains why this raw per-byte wrapping is not how RSA is used for real, but it shows the shape of the protocol.

Python A toy hybrid encryption flow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only the 16-byte key went through the slow public-key step. The message could have been a gigabyte and the cost of the public-key part would not change.

Comparing key sizes

Public-key sizes cannot be compared with symmetric ones directly. A 256-bit AES key is a random string of 256 bits; breaking it needs about 2^256 guesses. A 2048-bit RSA modulus is a very special number, and attacks on it exploit its structure, so it offers far less than 2048 bits of security. Cryptographers speak of security strength in bits, meaning the work factor of the best known attack.

Security strength Symmetric key RSA / DH modulus Elliptic curve key
112 bits 3-key 3DES (legacy) 2048 bits 224 bits
128 bits AES-128 3072 bits 256 bits (P-256, Curve25519)
192 bits AES-192 7680 bits 384 bits
256 bits AES-256 15360 bits 512 bits (P-521 in practice)

These figures follow the usual guidance (for instance from NIST) and will shift as attacks improve. Two points follow from the table. First, elliptic curves reach the same strength with much smaller keys and faster operations, which is why they dominate new designs. Second, a system is only as strong as its weakest link: a 256-bit AES key wrapped with a 1024-bit RSA key has roughly the strength of the RSA key.

What can go wrong

  • Wrong public key. If an attacker substitutes their own public key for Bob's, you encrypt to the attacker. Authenticity of public keys is the central problem of PKI.
  • Quantum computers. Shor's algorithm would break both factoring and discrete logarithms on a large enough quantum machine. Symmetric ciphers only lose half of their strength bits. See Post-Quantum Cryptography.
  • Using the primitive raw. Textbook RSA without padding has serious weaknesses, covered in RSA Padding and Common Pitfalls.
  • Private key leakage. The private key is the identity. Protect it as described in Key Derivation and Key Management.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a public-key encryption system, who can decrypt a message encrypted with Bob's public key?

    The public key can encrypt but not decrypt. The matching private key, held only by Bob, is the trapdoor that reverses the operation.
  2. 2. What is a trapdoor one-way function?

    Reversing it is hard for everyone except the holder of the trapdoor secret, such as the prime factors of an RSA modulus.
  3. 3. Why do real systems use hybrid encryption?

    The public-key step moves a small session key, and a fast authenticated symmetric cipher encrypts the data itself.
  4. 4. Roughly which RSA modulus size matches the strength of AES-128?

    Factoring-based keys have structure that attacks exploit, so they need far more bits than a symmetric key for the same security. 3072-bit RSA is about 128-bit strength.
  5. 5. Which problem does public-key cryptography NOT solve by itself?

    You still need a trustworthy way to bind a public key to an identity. Certificates and a public-key infrastructure address that.

Summary

  • A key pair has a shareable public key and a secret private key; encryption, signatures and key agreement all build on it.
  • It rests on trapdoor one-way functions: multiplication versus factoring, and modular exponentiation versus discrete logarithm.
  • Public-key operations are slow and size-limited, so real protocols use hybrid encryption: a random symmetric key encrypts the data, and the public key protects only that key.
  • Compare keys by security strength: about 3072-bit RSA or a 256-bit elliptic curve key for 128-bit strength.
  • Public keys need authentication, and the raw algorithms need careful padding and parameter choices.

Next: Diffie-Hellman Key Exchange, the first public-key algorithm and still the heart of TLS.