← 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 at | 1970 conceived (classified, GCHQ); 1973-1974 built in secret; 1976 first published (Diffie-Hellman) |
| born precision | year |
| boundary | Inside: 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 level | A 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. |
| scale | technological |
Measures (26) published science
| potential private pairs among n users | (n^2 - n)/2 pairs |
| RSA 1978 recommended modulus length | 200 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 prime | about 115 numbers |
| RSA encryption cost growth | no faster than the cube of the number of digits of n per block |
| cost to factor RSA-250 | about 2700 (2450 sieving, 250 linear algebra) core-years |
| key size growth with security parameter | cubic (RSA, finite-field DH); linear (elliptic curves) growth law |
| cost to factor RSA-240 | about 1000 core-years (Xeon Gold 6130 reference) |
| equivalent key sizes: elliptic curve and RSA | 256-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 estimates | 1 microsecond |
| Logjam: discrete log time after precomputation | about 1 minute (after a week-long precomputation) minutes |
| share of vulnerable servers using one 512-bit group | 82 % |
| 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 moduli | less than 2 hours |
| users able to sign and encrypt with PGP 5.0 in 90 minutes | one third (of 12) participants |
| HTTPS share of web traffic at one backbone sample point | about 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 validity | several years |
| NIST draft transition dates for quantum-vulnerable systems | deprecated 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 target | 300,000 users |
Open contentions (4) open contention
Where sources or readings disagree. Both stay on the map.
- C-1317 Is modern encryption truly unbreakable?
booked: The map records that it rests on maths problems believed hard but never proven hard, and keeps the readings that they will hold, or fall to new maths or to quantum computers, alongside.
the other reading: hard for classical computers; may fall to new classical mathematics (warnings noted in src:wp:public-key-cryptography); falls to quantum computers (Shor) - C-1334 Was 1024-bit Diffie-Hellman encryption broken by intelligence agencies?
booked: The map records the researchers' reading that leaked documents are consistent with it, and notes no source confirms it.
the other reading: a 1024-bit group precomputation was achieved; the leaks admit other explanations - C-1335 Who invented public-key cryptography?
booked: The map keeps both: it was conceived first at Britain's GCHQ, in secret until 1997, and invented independently and published in the US in 1976-77.
the other reading: credit to the GCHQ inventors as first; credit to Merkle, Diffie, Hellman, Rivest, Shamir and Adleman as the inventors of the field as it exists - C-1337 When will quantum computers break today's encryption?
booked: No date is settled. The map records the standards' 2030 and 2035 switch-over dates as precautions.
the other reading: threat 'increasingly imminent' (src:zhang-2025-pqc); large quantum computers not expected by 2030; deprecation so security does not depend on slow progress (src:gidney-2025-preprint)
Partners and parts published science
Built from / builds (15)
- Cryptography
- Digital signatures and certificates
- Key pair (public key and private key)
- Trap-door one-way function
- Integer factorisation (the hard problem under RSA)
- Discrete logarithm (the hard problem under Diffie-Hellman, DSA, elliptic curves)
- Key agreement and key encapsulation
- Protocols: TLS (and SSH, PGP, S/MIME)
- Public key infrastructure and certificate authorities
- Certificate transparency logs
- Web of trust
- Cryptographers and standards bodies (people)
- Random number generator
- Factoring records against RSA key sizes
- Cryptanalysts factoring record numbers against cryptographers choosing prime key sizes
Sits inside / holds (4)
Trades with (valence) (18)
- Cryptography via sys:written-record · Public-key cryptography gain
- Human (Homo sapiens) via sys:sensory-environment · Public-key cryptography mixed
- Government via sys:law · Public-key cryptography mixed
- Internet via sys:electromagnetic-field · Public-key cryptography mixed
- Bitcoin (cryptocurrency) via sys:written-record · Public-key cryptography gain
- Computer via sys:sensory-environment · Public-key cryptography mixed
- Algorithm (the practice of step-by-step procedures and the structure they compute) via sys:written-record · Public-key cryptography mixed
- Linear algebra (the practice of solving, transforming and taking apart linear systems with vectors and matrices, and the structures it works with) via sys:written-record · Public-key cryptography gain
- Quantum computing via sys:quantum-computing · Public-key cryptography loss
- Cryptographic hash function via sys:written-record · Public-key cryptography gain
- Cryptanalysis (the attack side of the practice) via sys:written-record · Public-key cryptography mixed
- Computer security via sys:electromagnetic-field · Public-key cryptography gain
- Symmetric-key cryptography via sys:written-record · Public-key cryptography gain
- Certificate authorities (trust anchors) via sys:written-record · Public-key cryptography mixed
- Digital signatures and certificates via sys:written-record · Public-key cryptography gain
- Authentication via sys:electromagnetic-field · Public-key cryptography gain
- Digital identity via sys:human-society · Public-key cryptography gain
- Prime numbers (the practice of number theory that finds, proves and uses them, and the structure of the primes it works on) via sys:sensory-environment · Public-key cryptography gain
expressed by (24)
- Generation/Synthesis
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Quality Improvement/Refinement
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Evolvability/Plasticity Engineering (Design for Future Variation)
- Distributed Autonomy/Decentralized Execution (Subsidiarity)
- Sensing/Scanning
- Uncertainty Reduction/Learning
- Active Experimentation / Probing (Optimal Experimental Design)
- Trail-Marking / Externalized Memory (Stigmergy)
- Surprise / Change-Point Detection
- Reactive Response
- Proactive Defense
- Physical/Virtual Barrier
- Self-Monitoring
- Validation of Identity/Intention
- Validation of Effectiveness
- Enclave/Segregation
- Redundancy & Diversity
- Quality Control & Error Correction
- Scheduled Build-and-Dismantle (On-Demand Structure)
floor filled by (27)
- Cryptography
- Electromagnetic field
- Human (Homo sapiens)
- Government
- Internet
- Entropy
- Bitcoin (cryptocurrency)
- Computer
- Algorithm (the practice of step-by-step procedures and the structure they compute)
- Linear algebra (the practice of solving, transforming and taking apart linear systems with vectors and matrices, and the structures it works with)
- Digital signatures and certificates
- Lattice-based cryptography (learning with errors)
- Computer security
- Key pair (public key and private key)
- Integer factorisation (the hard problem under RSA)
- Discrete logarithm (the hard problem under Diffie-Hellman, DSA, elliptic curves)
- Key agreement and key encapsulation
- Protocols: TLS (and SSH, PGP, S/MIME)
- Certificate transparency logs
- Web of trust
- Public-key encryption
- Symmetric-key cryptography
- Random number generator
- Certificate authorities (trust anchors)
- Pretty Good Privacy
- Digital identity
- Prime numbers (the practice of number theory that finds, proves and uses them, and the structure of the primes it works on)
represents (1)
Kinds (11)
- Cryptography
- Digital signatures and certificates
- Post-quantum cryptography
- Key agreement and key encapsulation
- Public-key encryption
- Diffie-Hellman key exchange (key agreement)
- RSA
- Elliptic-curve cryptography
- Finite-field discrete-log systems (Diffie-Hellman, DSA, ElGamal)
- Merkle-Hellman knapsack cryptosystem (broken)
- Merkle's puzzles
wired (1)
Notes published science
- In 1978 the RSA paper reckoned that factoring a 200-digit key would take 3.8 billion years with the best method then known; in 2019 a team factored a 240-digit RSA number in about 1,000 computer-core-years, and a 250-digit one in about 2,700. The mathematics didn't break; the attacks got better, so the keys got longer. (src:rivest-shamir-adleman-1978, src:boudot-2020-rsa240)
- Public-key cryptography was invented twice: in secret at Britain's GCHQ in 1970-1974, kept classified until 1997, and in the open at Stanford and MIT in 1976-1977. Ellis's spark was a World War II Bell Labs voice scrambler in which the receiver, not the sender, adds the noise and later takes it out. (src:wp:public-key-cryptography, src:wp:james-h-ellis)
- Birds do the signature job too: the cuckoo forges eggs, and the host species facing the best cuckoo forgeries have evolved the most recognisable egg-pattern 'signatures', each species in its own way. (src:stoddard-2014-egg-signatures)
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)
- L1: The public channel: bits on links that anyone may overhear or inject into (telephone, radio, the Internet), plus the public directory of keys
- 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
- L3: The hard problem and its trap door: integer factorisation, discrete logarithms in finite fields and on elliptic curves, module lattices with noise
- L4: The schemes: public-key encryption (multiple access), digital signature (broadcast), key agreement and key encapsulation
- L5: The protocols: TLS handshakes, SSH, PGP and S/MIME, combining public-key exchange with symmetric ciphers (hybrid), with forward secrecy
- L6: Trust and standards: certificate authorities and root lists, webs of trust, key servers, certificate transparency logs; standards bodies choosing algorithms and key sizes
- L7: What people get and do with it: private conversation between strangers, signed contracts and software, HTTPS, digital cash
the boardroom (shared floors)
- L4: The schemes at work: key generation, encryption and decryption, encapsulation and decapsulation, signing and verification
- L5: Protocols: handshakes that negotiate algorithms, authenticate and establish keys, then hand the session to symmetric ciphers (hybrid), with forward secrecy
- 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)
- L7: Assurance for people: confidentiality and authenticity of communications and stored data between parties who never met
way in: Cryptanalysis (published attacks and records)
- L1: Published attacks, records and surveys arriving in the literature
- L2: Algorithmic advances: the number field sieve, Schroeppel's method in 1978, timing attacks
- L3: The attack applied to the hard problem itself: factoring or discrete logs of record size
- L4: The attack applied to deployed schemes and keys: shared factors, shared groups
- L5: The attack applied to protocols: downgrade to export-grade groups
way in: Identity claims (requests for certificates)
- L1: A person or organisation claiming that a key belongs to a name
- L2: Registration: the identity checked by a registration or certificate authority, or endorsed by acquaintances (web of trust)
- L3: Automated issuance: free, automated certificate authorities
- L4: The certificate signed: a digital signature binding key to name
- L5: Logged: the certificate submitted to transparency logs, which return a signed promise
way in: Incoming messages: ciphertexts, key shares and signed messages
- L1: Ciphertexts, key shares and signed messages arriving over an insecure channel
- L2: Received and parsed by the protocol endpoint (TLS record and handshake layers)
- 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)
- L1: Laws and regulations on cryptography
- L2: Rules turned into permitted strengths and dates: export grades then; deprecation after 2030 and disallowance after 2035 in NIST's draft now
- L3: Parameter sets kept in deployed software (export-grade 512-bit groups)
- L4: Groups and keys actually configured on servers
- L5: Protocols negotiating them (downgrade possible)
way in: Other parties' public keys and certificates
- L1: Public keys placed in a public file, on key servers, or sent in certificates
- L2: Retrieved: from the directory, a key server, or a certificate chain in a handshake
- L3: Parsed into the hard-problem instance it encodes (modulus and exponent, curve point, lattice key)
way in: Quantum computing progress
- L1: Physical qubits on a planar grid, gate error 0.1%, surface code cycle 1 microsecond (the assumed hardware)
- L2: Error-corrected logical qubits (surface code)
- L3: Shor's period finding on factoring and discrete logs
- L4: Resource estimates against deployed key sizes: RSA-2048 in under a week with under a million noisy qubits
- L5: Threat to recorded sessions: harvest now, decrypt later
way in: Randomness (the entropy keys are drawn from)
- L1: Unpredictable events collected by the device's random number generator; scarce at boot on headless and embedded devices
- L2: Random numbers drawn: odd 100-digit candidates for RSA primes, uniform exponents for Diffie-Hellman
- L3: Primality tested; the hard-problem instance formed (n = p q; Y = alpha^X mod q)
way in: The user's commands and choices
- L1: A person at a screen and keyboard, reading key and lock icons
- L2: The interface's buttons: Encrypt, Sign, Encrypt & Sign, Decrypt/Verify
- L3: Key management exposed to the user: generate a key pair with a pass phrase, publish it, fetch others' keys
- L4: The chosen operation run on the message (sign, encrypt)
way out: Ciphertexts and key shares sent
- L1: The ciphertext on the channel: garbage to an eavesdropper, metadata still visible
- L4: Encryption with the recipient's public key (or encapsulation)
- L5: The protocol establishes or uses a session key
- L7: A person wants to send privately
way out: Migration and revocation (algorithms, sizes, CAs changed)
- L1: New software and configurations deployed on servers and clients
- L5: Protocols changed: static RSA removed, short groups rejected
- L6: Standards and browsers decide what is no longer trusted
way out: Public key published (the door opened ahead of time)
- L1: The key in the public file, for any sender
- L2: The public half of the pair released, the private half kept
- L6: The owner decides where to publish (directory, key server, website, certificate)
way out: Signatures and certificates issued
- L1: The signed object released for anyone to verify
- L4: Signing with the private key
- L6: A CA or publisher decides to vouch for a key or an update
way out: Unintended leakage (timing, metadata)
- L1: Timing differences and message metadata observable on the channel
- L4: Private-key operations whose running time depends on the key