EVOPEDIA

← all systems · see it in The System

Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys: a public key that can be openly distributed and a corresponding private key kept secret, generated with algorithms based on one-way functions (src:wp:public-key-cryptography). In its founding paper, a public key cryptosystem is one in which enciphering and deciphering are governed by distinct keys E and D such that computing D from E is computationally infeasible, so E can be published (Diffie and Hellman 1976). Walked here as the technology: the built system (keys, hard problems, schemes, protocols, the trust infrastructure), how it works and is used, its history and its people, and the contest with cryptanalysis.

Properties published scienceour proposal

Sourced fields, and our own readings.

born at1970 conceived (classified, GCHQ); 1973-1974 built in secret; 1976 first published (Diffie-Hellman)
born precisionyear
boundaryInside: key pairs and how they are generated (randomness, primes), the hard problems they rest on (integer factorisation, discrete logarithms in finite fields and on elliptic curves, module lattices), the schemes (public-key encryption, key agreement and key encapsulation, digital signatures), the protocols that carry them (TLS, SSH, PGP, S/MIME, Bitcoin's transactions), and the trust infrastructure that binds keys to names (certificate authorities, webs of trust, certificate transparency logs), with the people who design, standardise and run them. Outside: the public channels it runs over (the Internet, radio), the computers it runs on, the symmetric ciphers it hands bulk data to, the people who use it, and the cryptanalysts and quantum computers that attack it. Where it ends and cryptography as a whole begins is not sharp: it is the asymmetric branch of one field.
nested levelA branch of cryptography (rung 11-12) carried by people and organisations, running as algorithms on computers and over the Internet; a protection mechanism inside computer security; its mathematics drawn from number theory, algebraic geometry and linear algebra.
scaletechnological

Measures (26) published science

potential private pairs among n users(n^2 - n)/2 pairs
RSA 1978 recommended modulus length200 decimal digits
1978 estimate: time to factor a 200-digit n (Schroeppel's method, one microsecond per operation)3.8 x 10^9 years
random candidates tested before finding a 100-digit primeabout 115 numbers
RSA encryption cost growthno faster than the cube of the number of digits of n per block
cost to factor RSA-250about 2700 (2450 sieving, 250 linear algebra) core-years
key size growth with security parametercubic (RSA, finite-field DH); linear (elliptic curves) growth law
cost to factor RSA-240about 1000 core-years (Xeon Gold 6130 reference)
equivalent key sizes: elliptic curve and RSA256-bit EC ~ 3072-bit RSA bits
share of TLS certificates with RSA signatures (Nov-Dec 2019)90 (certificates); 7 (connections using RSA key exchange) %
quantum resources to factor RSA-2048 (2019 estimate)20 million noisy qubits, 8 hours qubits; hours
quantum resources to factor RSA-2048 (2025 estimate)less than 1 million noisy qubits, less than a week qubits; days
characteristic clock: assumed surface code cycle time for quantum factoring estimates1 microsecond
Logjam: discrete log time after precomputationabout 1 minute (after a week-long precomputation) minutes
share of vulnerable servers using one 512-bit group82 %
HTTPS sites passively readable after one 1024-bit group precomputation (estimate)18 % of popular HTTPS sites
TLS certificates sharing keys from low entropy (2012)0.75 % of TLS certificates
TLS hosts whose RSA private keys were recovered from shared factors (2012)0.50 (TLS); 0.03 (SSH) % of hosts
time to compute pairwise GCDs of 11 million RSA moduliless than 2 hours
users able to sign and encrypt with PGP 5.0 in 90 minutesone third (of 12) participants
HTTPS share of web traffic at one backbone sample pointabout 20 to about 40 (Jan 2014 - Jan 2017) %
Let's Encrypt active certificates (January 2017)more than 20,000,000 certificates
characteristic clock: public-key certificate validityseveral years
NIST draft transition dates for quantum-vulnerable systemsdeprecated after 2030; disallowed after 2035 year
characteristic clock: TLS 1.3 session keys (ephemeral, per connection)one per connection session
DigiNotar: Iranian Gmail users identified as the main target300,000 users

Open contentions (4) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (15)

Sits inside / holds (4)

Trades with (valence) (18)

expressed by (24)

floor filled by (27)

represents (1)

Kinds (11)

wired (1)

Notes published science

Layers

The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.

public-key cryptography: bits on a public channel up to private, authentic communication between strangers (reader's view)

  1. L1: The public channel: bits on links that anyone may overhear or inject into (telephone, radio, the Internet), plus the public directory of keys
  2. L2: The key pair: generated from random numbers (random primes for RSA, random exponents for Diffie-Hellman); the public half published, the private half kept
  3. L3: The hard problem and its trap door: integer factorisation, discrete logarithms in finite fields and on elliptic curves, module lattices with noise
  4. L4: The schemes: public-key encryption (multiple access), digital signature (broadcast), key agreement and key encapsulation
  5. L5: The protocols: TLS handshakes, SSH, PGP and S/MIME, combining public-key exchange with symmetric ciphers (hybrid), with forward secrecy
  6. L6: Trust and standards: certificate authorities and root lists, webs of trust, key servers, certificate transparency logs; standards bodies choosing algorithms and key sizes
  7. L7: What people get and do with it: private conversation between strangers, signed contracts and software, HTTPS, digital cash

the boardroom (shared floors)

  1. L4: The schemes at work: key generation, encryption and decryption, encapsulation and decapsulation, signing and verification
  2. L5: Protocols: handshakes that negotiate algorithms, authenticate and establish keys, then hand the session to symmetric ciphers (hybrid), with forward secrecy
  3. L6: Trust and standards: which keys belong to whom (CAs, root lists, webs of trust, transparency logs) and which algorithms and sizes are trusted (standards bodies, national standards)
  4. L7: Assurance for people: confidentiality and authenticity of communications and stored data between parties who never met

way in: Cryptanalysis (published attacks and records)

  1. L1: Published attacks, records and surveys arriving in the literature
  2. L2: Algorithmic advances: the number field sieve, Schroeppel's method in 1978, timing attacks
  3. L3: The attack applied to the hard problem itself: factoring or discrete logs of record size
  4. L4: The attack applied to deployed schemes and keys: shared factors, shared groups
  5. L5: The attack applied to protocols: downgrade to export-grade groups

way in: Identity claims (requests for certificates)

  1. L1: A person or organisation claiming that a key belongs to a name
  2. L2: Registration: the identity checked by a registration or certificate authority, or endorsed by acquaintances (web of trust)
  3. L3: Automated issuance: free, automated certificate authorities
  4. L4: The certificate signed: a digital signature binding key to name
  5. L5: Logged: the certificate submitted to transparency logs, which return a signed promise

way in: Incoming messages: ciphertexts, key shares and signed messages

  1. L1: Ciphertexts, key shares and signed messages arriving over an insecure channel
  2. L2: Received and parsed by the protocol endpoint (TLS record and handshake layers)
  3. L3: The private key (decapsulation key) or the sender's public key applied to it: the trap door used

way in: Law and policy (export rules, mandates, deprecation dates)

  1. L1: Laws and regulations on cryptography
  2. L2: Rules turned into permitted strengths and dates: export grades then; deprecation after 2030 and disallowance after 2035 in NIST's draft now
  3. L3: Parameter sets kept in deployed software (export-grade 512-bit groups)
  4. L4: Groups and keys actually configured on servers
  5. L5: Protocols negotiating them (downgrade possible)

way in: Other parties' public keys and certificates

  1. L1: Public keys placed in a public file, on key servers, or sent in certificates
  2. L2: Retrieved: from the directory, a key server, or a certificate chain in a handshake
  3. L3: Parsed into the hard-problem instance it encodes (modulus and exponent, curve point, lattice key)

way in: Quantum computing progress

  1. L1: Physical qubits on a planar grid, gate error 0.1%, surface code cycle 1 microsecond (the assumed hardware)
  2. L2: Error-corrected logical qubits (surface code)
  3. L3: Shor's period finding on factoring and discrete logs
  4. L4: Resource estimates against deployed key sizes: RSA-2048 in under a week with under a million noisy qubits
  5. L5: Threat to recorded sessions: harvest now, decrypt later

way in: Randomness (the entropy keys are drawn from)

  1. L1: Unpredictable events collected by the device's random number generator; scarce at boot on headless and embedded devices
  2. L2: Random numbers drawn: odd 100-digit candidates for RSA primes, uniform exponents for Diffie-Hellman
  3. L3: Primality tested; the hard-problem instance formed (n = p q; Y = alpha^X mod q)

way in: The user's commands and choices

  1. L1: A person at a screen and keyboard, reading key and lock icons
  2. L2: The interface's buttons: Encrypt, Sign, Encrypt & Sign, Decrypt/Verify
  3. L3: Key management exposed to the user: generate a key pair with a pass phrase, publish it, fetch others' keys
  4. L4: The chosen operation run on the message (sign, encrypt)

way out: Ciphertexts and key shares sent

  1. L1: The ciphertext on the channel: garbage to an eavesdropper, metadata still visible
  2. L4: Encryption with the recipient's public key (or encapsulation)
  3. L5: The protocol establishes or uses a session key
  4. L7: A person wants to send privately

way out: Migration and revocation (algorithms, sizes, CAs changed)

  1. L1: New software and configurations deployed on servers and clients
  2. L5: Protocols changed: static RSA removed, short groups rejected
  3. L6: Standards and browsers decide what is no longer trusted

way out: Public key published (the door opened ahead of time)

  1. L1: The key in the public file, for any sender
  2. L2: The public half of the pair released, the private half kept
  3. L6: The owner decides where to publish (directory, key server, website, certificate)

way out: Signatures and certificates issued

  1. L1: The signed object released for anyone to verify
  2. L4: Signing with the private key
  3. L6: A CA or publisher decides to vouch for a key or an update

way out: Unintended leakage (timing, metadata)

  1. L1: Timing differences and message metadata observable on the channel
  2. L4: Private-key operations whose running time depends on the key

Who fills each layer

Sources (27) published science

Public-key cryptography (Wikipedia)
Boudot, Gaudry, Guillevic, Heninger, Thome and Zimmermann, Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment, CRYPTO 2020 (arXiv:2006.06197) (behind its links)
Adrian et al., Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, ACM CCS 2015 (doi:10.1145/2810103.2813707) (behind its links)
Laurie, Langley and Kasper, Certificate Transparency, RFC 6962, IETF, 2013 (behind its links)
Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits, arXiv:2505.15917 (2025, preprint) (behind its links)
Zhang et al., Research on Development Progress and Test Evaluation of Post-Quantum Cryptography, Entropy 27(2):212, 2025 (doi:10.3390/e27020212; PMC11854752) (behind its links)
Felt, Barnes, King, Palmer, Bentzel and Tabriz, Measuring HTTPS Adoption on the Web, 26th USENIX Security Symposium, 2017 (behind its links)
Heninger, Durumeric, Wustrow and Halderman, Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, USENIX Security 2012 (extended version) (behind its links)
Diffie and Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory 22(6), 1976 (doi:10.1109/TIT.1976.1055638) (behind its links)
Digital signature (Wikipedia) (behind its links)
James H. Ellis (Wikipedia) (behind its links)
Stoddard, Kilner and Town, Pattern recognition algorithm reveals how birds evolve individual egg pattern signatures, Nature Communications 5:4117, 2014 (doi:10.1038/ncomms5117) (behind its links)
Rivest, Shamir and Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM 21(2), 1978 (doi:10.1145/359340.359342) (behind its links)
Elliptic-curve cryptography (Wikipedia) (behind its links)
Gidney and Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, arXiv:1905.09749v3 (2021) (behind its links)
Whitten and Tygar, Why Johnny Can't Encrypt: A Usability Evaluation of PGP 5.0, USENIX Security 1999 (behind its links)
Rescorla, The Transport Layer Security (TLS) Protocol Version 1.3, RFC 8446, IETF, August 2018 (behind its links)
DigiNotar (Wikipedia) (behind its links)
NIST, FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 2024 (doi:10.6028/NIST.FIPS.203) (behind its links)
Alvarez, Caballero-Gil, Santonja and Zamora, Algorithms for Lightweight Key Exchange, Sensors 17(7):1517, 2017 (doi:10.3390/s17071517; PMC5551094) (behind its links)
Nakamoto 2008, Bitcoin: A Peer-to-Peer Electronic Cash System (behind its links)
Authentication (Wikipedia, via Wikimedia Enterprise snapshot) (behind its links)
Sporny, Longley, Sabadello, Reed, Steele and Allen (eds.) 2022, Decentralized Identifiers (DIDs) v1.0, W3C Recommendation 19 July 2022 (behind its links)
RSA cryptosystem (Wikipedia) (behind its links)
Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, arXiv:quant-ph/9508027v2 (1996; preliminary version FOCS 1994) (behind its links)
Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO 1996 (doi:10.1007/3-540-68697-5_9) (behind its links)
Cryptography (Wikipedia, via Wikimedia Enterprise snapshot) (behind its links)