Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 80 ยท Cryptography Basics

Public-Key Cryptography

Learn how key pairs, RSA, Diffie-Hellman key exchange, elliptic curves and digital signatures work, with small runnable Python demos using toy numbers.

Symmetric encryption has a chicken-and-egg problem: both sides need the same secret key, but how do two strangers agree on one over a network that anyone can read? Public-key (asymmetric) cryptography solves this. Each party has a key pair: a public key that can be shared with the whole world, and a private key that never leaves its owner. The two keys are mathematically linked, but knowing the public key does not let you compute the private one.

Key pairs give you three tools: encryption to a recipient (anyone can lock, only the owner can unlock), digital signatures (only the owner can sign, anyone can verify) and key agreement (two parties derive a shared secret in public). This lesson shows each idea with deliberately tiny numbers that you can run and inspect. Real keys are thousands of times larger, and real libraries add padding and checks the demos leave out, so treat the code as an explanation, never as something to deploy.

flowchart LR
    subgraph Encryption
    direction LR
    M1["Message"] -->|"encrypt with<br/>recipient's PUBLIC key"| C1["Ciphertext"]
    C1 -->|"decrypt with<br/>recipient's PRIVATE key"| M2["Message"]
    end
    subgraph Signature
    direction LR
    D1["Document"] -->|"sign with<br/>signer's PRIVATE key"| S1["Signature"]
    S1 -->|"verify with<br/>signer's PUBLIC key"| V1["Valid or invalid"]
    end

The same pair is used in opposite directions: lock with public and unlock with private for secrecy, sign with private and verify with public for authenticity.

The RSA idea with toy numbers

RSA relies on the fact that multiplying two large primes is easy, but factoring the product is hard. The recipe:

  1. Pick two primes p and q, and compute n = p * q.
  2. Compute phi = (p - 1) * (q - 1).
  3. Pick a public exponent e that shares no factors with phi (65537 is the common choice).
  4. Compute the private exponent d, the inverse of e modulo phi.
  5. The public key is (n, e). The private key is d (together with n).

Encryption is c = m^e mod n and decryption is m = c^d mod n. Python's three-argument pow does modular exponentiation efficiently, and pow(e, -1, phi) computes the modular inverse.

Python Textbook RSA with tiny primes

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.

Three lessons hide in this tiny example:

  • The two Ls in HELLO produce the same number. Textbook RSA is deterministic, which leaks information. Real RSA always uses randomized padding (OAEP for encryption, PSS for signatures).
  • With a 12-bit n, an attacker factors the key instantly. Real RSA keys use 2048 bits or more, which is a number with more than 600 decimal digits. The best known factoring methods cannot handle such numbers.
  • RSA can only encrypt data smaller than n. It is far too slow for bulk data, so it is used to protect a short symmetric key instead.

That last point is the idea behind hybrid encryption, which is how almost everything works: pick a random symmetric key, encrypt the data with it (see Symmetric Encryption and Modes), then encrypt that small key with the recipient's public key.

Diffie-Hellman key exchange

Diffie-Hellman (DH) lets two parties create a shared secret by exchanging only public values. Both agree on public numbers: a prime p and a generator g. Then:

  1. Alice picks a private number a and sends A = g^a mod p.
  2. Bob picks a private number b and sends B = g^b mod p.
  3. Alice computes B^a mod p and Bob computes A^b mod p. Both equal g^(ab) mod p.

An eavesdropper sees p, g, A and B, but recovering a from A is the discrete logarithm problem, which is believed to be hard.

Python Diffie-Hellman and the man in the middle

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.

Plain DH protects against someone who only listens. It does not prove who is on the other end. That is why TLS signs the DH values with a certificate, so that Mallory cannot substitute her own (see TLS, Certificates and PKI). Modern protocols also use ephemeral keys, a fresh pair for every session, which gives forward secrecy: stealing a server's long-term key later cannot decrypt recorded traffic.

Digital signatures

A signature proves that a message came from the holder of a private key and has not changed. The signer hashes the message, then applies the private key to the hash. Anyone can apply the public key to the signature and compare the result with their own hash of the message. Hashing first means the document can be any size (see Hash Functions and Integrity).

Compared with an HMAC, a signature has an important extra property: verifiers cannot forge. It also provides non-repudiation in the sense that only the private-key holder could have produced it. The demo below uses larger toy primes so that a reduced SHA-256 hash fits inside n.

Python Sign and verify with toy RSA

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.

Real RSA signatures use PSS padding. Modern systems often prefer Ed25519 or ECDSA, which have smaller keys and signatures and are harder to misuse. Whatever the scheme, never sign data you have not fully understood, and treat the private key as the most sensitive secret you own.

Digital signatures, electronic signatures and certificates

A signature proves that someone holding a private key signed some bytes. It does not yet prove who that someone is. Two ideas fill the gap, and the terms are often confused.

Digital signature versus electronic signature

  • A digital signature is a cryptographic technique: a value computed from the data and a private key that anyone can verify with the matching public key. It gives integrity, authentication and non-repudiation, as in the demo above.
  • An electronic signature is a legal concept: any electronic data that shows a person's intent to sign, such as a typed name, a tick box, a scanned image of a handwritten signature or a click on "I agree". Many electronic signatures use no cryptography at all, and their legal weight depends on the law and on the evidence that surrounds them (logs, email verification, identity checks).

A digital signature is one way to make an electronic signature strong. Many jurisdictions recognize several levels, from simple electronic signatures to advanced or qualified signatures that require unique linkage to the signer, sole control of the key, and (for the qualified level) certified devices and identity-verified certificates from approved providers. The exact categories and their legal effects differ between countries, so ask a lawyer before relying on one for a contract.

Binding an identity to a key: the signer's certificate

Verification needs the signer's public key. If it arrives with the signed document, an attacker could swap in their own pair, so the key must come with proof of whose it is. That proof is the digital certificate: a document in which a certificate authority (CA) signs a statement "this public key belongs to this person or organization" (the fields and the chain of trust are explained in TLS, Certificates and PKI). The signature on a document is therefore checked in two steps: first the certificate chain up to a trusted CA, then the document signature with the certificate's key.

How a CA issues a certificate:

  1. The applicant generates a key pair (the private key never leaves their device or hardware token) and creates a certificate signing request (CSR) containing the public key and requested identity.
  2. The CA performs validation appropriate to the type of certificate: control of a domain or an email address, or a stricter identity check with documents for individuals and organizations.
  3. The CA signs and issues the certificate with its own private key, which includes the subject, public key, validity period and permitted uses.
  4. The certificate is published and can be revoked if the private key is lost or the details change (through certificate revocation lists or OCSP).

Certificate classes

Some certificate programs, especially national and enterprise signing schemes, group certificates into classes by the strength of identity checking and what they may be used for. The names and numbers are not universal, but a common pattern is:

Class (typical pattern) Identity checking Typical use
Class 1 Minimal: control of an email address or similar Low-risk email signing, personal testing
Class 2 Identity checked against documents or a trusted database Business paperwork, tax filings, internal approvals
Class 3 Strict, often in person or with a registration authority, keys on a hardware token High-value contracts, e-tendering, code signing, qualified signatures

Always read the CA's own policy to see what each class means in practice. Related distinctions: signing certificates differ from encryption certificates (each has its own key usage), and code-signing and document-signing certificates have different rules.

Timestamps and long-term validity

A certificate expires, but a signature made while it was valid should still count. A trusted timestamp from a time-stamping authority proves the document existed, and was signed, before a given moment, so verifiers can accept the signature even after the certificate has expired. Long-term formats also embed the revocation evidence at signing time.

The next demo walks the whole path with the same toy RSA as before: a CA signs a certificate, a signer uses the certified key on a document, and a verifier checks both steps, including an attempt to substitute another key. It is not secure (tiny keys, no padding).

Python Certificate-backed signature: two-step verification

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.

Notice that Mallory's signature is mathematically correct for his key, but without a CA signature on the certificate nobody believes the key belongs to Alice. That is exactly the job of the certificate, and why protecting the CA's private key matters so much.

Elliptic curves in one page

Elliptic-curve cryptography (ECC) provides the same tools as RSA and DH with much smaller keys: a 256-bit elliptic-curve key gives roughly the security of a 3072-bit RSA key. The math lives on a curve such as y^2 = x^3 + ax + b over a finite field. Points on the curve can be added, and adding a point G to itself k times gives the point k*G. Computing k*G is fast, but recovering k from k*G is the elliptic-curve discrete logarithm problem, believed to be very hard.

The demo uses a famous textbook curve with 19 points so you can see everything. Real curves such as P-256 and Curve25519 work the same way with 256-bit numbers.

Python A tiny elliptic curve and ECDH

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.

Both sides arrive at the same point because a*(b*G) equals b*(a*G). With only 19 possible private values, an attacker could try them all. With a real curve, the number of possibilities is about 2^256.

Practical guidance

  • Use high-level libraries and standard protocols (TLS, SSH, age, libsodium, WebAuthn). Do not implement RSA or ECC yourself.
  • Prefer X25519 for key agreement, Ed25519 for signatures, and RSA 2048+ with OAEP/PSS only when compatibility requires it.
  • Authenticate public keys. A public key is only useful if you know whose it is. Certificates and key fingerprints solve this.
  • Quantum computers running Shor's algorithm would break RSA, DH and ECC. Standardized post-quantum algorithms (ML-KEM for key exchange, ML-DSA for signatures) are being rolled out, often combined with classical ones in a hybrid.
  • Protect private keys in hardware (HSMs, TPMs, security keys) or a managed key service, never in source code.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In RSA encryption, which key does the sender use to lock a message for Bob?

    Anyone may encrypt with Bob's public key, but only Bob's private key can decrypt. Using a private key to lock would be a signature, not secrecy.
  2. 2. Why is the RSA in the first demo insecure for real use?

    A 12-bit modulus is factored instantly, and without randomized padding equal inputs give equal outputs. Real RSA uses 2048+ bit keys and OAEP/PSS padding.
  3. 3. What does unauthenticated Diffie-Hellman NOT protect against?

    DH hides the secret from passive listeners, but without authentication Alice and Bob cannot tell whether the public value came from the right person. TLS fixes this with certificates and signatures.
  4. 4. Who can create and who can verify a digital signature?

    Signing needs the private key and verifying needs only the public key. That asymmetry is what separates signatures from HMACs, where every verifier could also forge.

Summary

  • Public-key cryptography uses a public/private key pair so strangers can encrypt to you, verify your signatures and agree on secrets without sharing a secret first.
  • RSA relies on the difficulty of factoring; Diffie-Hellman and elliptic curves rely on discrete logarithms. Elliptic curves reach the same security with much smaller keys.
  • In practice public-key cryptography protects a short symmetric key (hybrid encryption); the symmetric cipher handles the bulk data.
  • A signature is a hash signed with the private key and checked with the public key. Unlike an HMAC, verifiers cannot forge it.
  • Key exchange must be authenticated, otherwise a man in the middle can substitute public values.
  • Use standard libraries, ephemeral keys for forward secrecy and well-protected private keys. Plan for post-quantum algorithms.

Next: TLS, Certificates and PKI, where signatures and key exchange come together to secure the web.