← all systems · see it in The System
Cryptography
Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior (src:wp:cryptography). Until modern times it meant encryption: converting readable plaintext into unintelligible ciphertext that only holders of the key can turn back; since the 1970s it also covers integrity, authentication, signatures and secure computation. Walked here as the practice (codemakers and codebreakers, their machines and procedures, from antiquity to now) together with the mathematical structure it rests on (finite arithmetic, hard problems, one-way and trap-door functions).
Properties published scienceour proposal
Sourced fields, and our own readings.
| born at | circa 1900 BC (non-standard hieroglyphs in an Old Kingdom Egyptian tomb, the earliest known case) |
| born precision | century; earliest known case, not a sharp birth |
| boundary | Inside: the techniques for keeping messages secret and genuine (codes, ciphers, keys, protocols, signatures), the people and machines that make and run them (cryptographers, cipher clerks, code talkers, cipher machines, cryptographic software), the codebreakers who attack them (cryptanalysis, the other half of cryptology), and the mathematics they rest on. Outside: the messages' content and senders, the channels that carry them (couriers, radio, the Internet), the computers and networks they protect, and the states, armies, firms and people who use them. Hiding that a message exists at all (steganography) is a sibling practice, not counted inside: Shannon set concealment systems apart as 'primarily a psychological problem' (src:shannon-1949). |
| nested level | A practice carried by people (rung 11) and, since the 1940s, by machines and computers (rung 12); a part of information and computer security (src:diffie-hellman-1976); built on writing and language and on number theory, algebra and complexity theory. Runs on human L7 output and on computers. |
| scale | social |
Measures (22) published science
| characteristic clock: Enigma key change | 1 day (settings generally changed daily) |
| characteristic clock: attackers' computing doubling time (Moore's law as used for key sizing) | 18 months |
| unicity distance, simple substitution on English | about 30 letters |
| factoring time for a 200-digit n, as estimated in 1978 | 3.8 x 10^9 years (Schroeppel's method, one microsecond per operation) |
| cost to factor RSA-240 (795 bits) | about 1000 core-years |
| cost to factor RSA-250, of which linear algebra | about 2700 (250 for the linear algebra step) core-years |
| DES key search by Deep Crack | 56 hours |
| minimum symmetric key length for 20 years (1996) | 90 bits |
| extra key length to stay ahead of Moore's law | about 14 bits |
| AES key and block sizes | keys 128, 192, 256; block 128 bits |
| GC&CS decrypts at peak | about 4,000 messages per day |
| Navajo code talkers at Iwo Jima, first two days | over 800 (six code talkers), no errors messages |
| TLS hosts whose RSA private keys were computed (2012 scan) | 64,000 (0.50%) hosts |
| popular HTTPS sites initially vulnerable to Heartbleed | 24-55 % |
| TLS certificates sharing keys from insufficient entropy | 0.75 % |
| Heartbleed: share of still-vulnerable sites that replaced certificates within a month | 10 (of those, 14% kept the same private key) |
| PGP 5.0 users who signed and encrypted correctly within 90 minutes | one third (of 12) participants |
| QKD repeaterless key-rate limit (PLOB) at high loss | about 1.44 x eta secret bits per channel use (eta = channel transmissivity) |
| standard fibre loss used for QKD rate plots | 0.2 dB per km |
| Copiale cipher size | 105 pages, about 75,000 handwritten characters pages / characters |
| drongo rejection of near-perfect cuckoo forgeries (comparison case, biology) | 93.7 % of cuckoo eggs predicted rejected |
| post-quantum migration target (US federal) | 2035 year |
Open contentions (6) open contention
Where sources or readings disagree. Both stay on the map.
- C-736 When a system first throws away its excess energy and later learns to store it for reuse, is that one process that grew or two separate ones?
booked: The map keeps both readings side by side and rules neither. A few examples fit the 'one process that grew' reading, but it hasn't been tested.
the other reading: - C-1099 How much did breaking the Enigma code shorten World War II?
booked: The map lists three views side by side: it changed the outcome, it shortened the war by about two years, or it was largely incidental.
the other reading: - C-1118 In cybersecurity, do attackers have the advantage?
booked: The map keeps both: attack is easier because defenders must cover everything, and attackers have no inherent advantage because one block can break their chain.
the other reading: defender (cipher) advantage; attacker advantage through everything around the cipher - 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: the assumptions hold classically (decades of failed attacks; 'certified' by trying to break it); an efficient classical algorithm exists (P vs NP open; 'one of the great open questions in complexity theory'); a large quantum computer breaks factoring and discrete logs (Shor) while lattice problems stay hard (Regev's reduction) - 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: GCHQ first ('GCHQ has released documents claiming they had developed public key cryptography before the publication of Diffie and Hellman's paper'); the open invention counts as the invention because it was published and used - C-1338 Who invented the first multi-alphabet cipher?
booked: The map credits Alberti, around 1467, and keeps the hint that Al-Kindi knew it centuries earlier alongside.
the other reading: 'some indication that it was already known to Al-Kindi' (c. AD 800)
Partners and parts published science
Built from / builds (14)
- Cryptographic hash function
- Public-key cryptography
- Cryptanalysis (the attack side of the practice)
- Cipher
- Key
- Cipher machines and devices
- Cryptographic protocols
- Computer security
- Information security
- Hash designers and cryptanalysts competing over a hash's security margin
- Codemakers against codebreakers for the secrecy of messages
- The Crypto Wars: states against industry and researchers over strong encryption
- Interception against communications security (top-level)
- Interception against encryption and countersurveillance
Sits inside / holds (4)
- Human society (from local community up to societies)
- Computer security
- Cryptographic hash function
- Public-key cryptography
Trades with (valence) (30)
- Quantum mechanics via sys:electromagnetic-field · Cryptography mixed
- Entropy via sys:mental-representation · Cryptography mixed
- Mathematics (the field: the practice and the structures it studies) via sys:sensory-environment · Cryptography gain
- Human (Homo sapiens) via sys:written-record · Cryptography mixed
- Language (human language) via sys:written-record · Cryptography mixed
- Writing (the practice of marking language on a surface, and the script plus rules it works with) via sys:written-record · Cryptography gain
- Government via sys:written-record · Cryptography mixed
- Internet via sys:electromagnetic-field · Cryptography mixed
- Bitcoin (cryptocurrency) via sys:written-record · Cryptography gain
- Computer via sys:electromagnetic-field · Cryptography gain
- Algorithm (the practice of step-by-step procedures and the structure they compute) via sys:written-record · Cryptography gain
- Linear algebra (the practice of solving, transforming and taking apart linear systems with vectors and matrices, and the structures it works with) via sys:mental-representation · Cryptography mixed
- World wars (the two world wars of the 20th century: World War I, 1914-1918, and World War II, 1939-1945) via sys:electromagnetic-field · Cryptography gain
- Quantum computing via sys:electromagnetic-field · Cryptography loss
- Cryptographic hash function via sys:written-record · Cryptography gain
- Public-key cryptography via sys:written-record · Cryptography gain
- Computer security via sys:electromagnetic-field · Cryptography gain
- Signals intelligence via sys:cryptography · Cryptography mixed
- Malware via sys:written-record · Cryptography even
- Authentication via sys:written-record · Cryptography gain
- Intrusion detection system via sys:electromagnetic-field · Cryptography even
- Information security via sys:written-record · Cryptography gain
- Firewall (computing) via sys:written-record · Cryptography gain
- Chaos and nonlinear dynamics (the practice, and the chaotic behaviour it studies) via sys:computer · Cryptography mixed
- Computer network via sys:written-record · Cryptography gain
- Privacy via sys:internet · Cryptography gain
- Surveillance via sys:internet · Cryptography gain
- Computer science (the field: the practice and the computation it studies) via sys:sensory-environment · Cryptography gain
- Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them via sys:sensory-environment · 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 · Cryptography gain
expressed by (21)
- Generation/Synthesis
- Recombination/Composition
- Templating / Standardization
- Quality Improvement/Refinement
- Encapsulation & Modularity (Abstraction)
- Amplification/Scale-Up (Manufacture & Distribution)
- Sensing/Scanning
- Mapping/Modeling
- Uncertainty Reduction/Learning
- Active Experimentation / Probing (Optimal Experimental Design)
- Trail-Marking / Externalized Memory (Stigmergy)
- Social Learning / Public Information Use
- Overcome Barrier
- Subversion & Co-optation
- Prepositioning & Latency
- Reactive Response
- Proactive Defense
- Physical/Virtual Barrier
- Validation of Identity/Intention
- Validation of Effectiveness
- Quality Control & Error Correction
floor filled by (34)
- Entropy
- Electromagnetic field
- Human (Homo sapiens)
- Language (human language)
- Writing (the practice of marking language on a surface, and the script plus rules it works with)
- Government
- Internet
- Bitcoin (cryptocurrency)
- Computer
- Algorithm (the practice of step-by-step procedures and the structure they compute)
- Bletchley Park
- Information theory
- Courier
- Intercept station
- Computational complexity
- Signals intelligence
- Public-key cryptography
- Cryptanalysis (the attack side of the practice)
- Cipher
- Key
- Cryptographic protocols
- Block cipher
- Rotor machine (Enigma, Lorenz)
- Frequency analysis
- Computer security
- Integer factorisation (the hard problem under RSA)
- Random number generator
- One-way function
- Cryptographic hash function
- Malware
- Information security
- Chaos and nonlinear dynamics (the practice, and the chaotic behaviour it studies)
- Computer network
- Privacy
represents (1)
Kinds (9)
- Computer security
- Computer science (the field: the practice and the computation it studies)
- Quantum key distribution
- Public-key cryptography
- Symmetric-key cryptography
- Classical ciphers (transposition and substitution)
- Post-quantum cryptography
- Codes (codebooks)
- Symmetric-key cryptography
Notes published science
- The same inventions keep turning up twice at once: the rotor machine 'was invented simultaneously by four separate people, all amateurs', and British intelligence had public-key encryption and key exchange in 1973-74, kept secret until 1997, before Diffie, Hellman and RSA published them in the open (src:diffie-hellman-1976, src:wp:history-of-cryptography).
- Birds run the same signature-versus-forgery race: African cuckoos copy fork-tailed drongo eggs almost perfectly, yet because every drongo female lays her own distinct egg 'signature', 93.7% of cuckoo eggs are predicted to be rejected; if all drongo eggs looked alike, a cuckoo egg would generally be accepted (src:lund-2023-cuckoo).
- In 1978 the RSA inventors estimated that factoring a 200-digit number would take about 3.8 billion years; in 2019-2020 a team factored the 250-digit RSA-250 in roughly 2,700 core-years, and 250 of those core-years were spent on one big linear algebra step (src:rsa-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)
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.
cryptography as cryptographers describe it: the open channel up to the purposes secret writing serves (reader's view)
- L1: The open channel: courier, telegraph, telephone, radio, network; anyone may intercept and record what passes
- L2: The message as symbols: plaintext letters, words or bits and the ciphertext that replaces them
- L3: The key and its randomness: a secret shared only by the communicants, drawn at random
- L4: The cipher: substitution and transposition, rotor machines, block and stream ciphers (DES, AES), Feistel networks
- L5: Protocols and key management: key delivery (courier, public directory), modes of operation, signatures, hybrid schemes, standards
- L6: What 'secure' means: Kerckhoffs's rule, perfect secrecy, computational security, the indistinguishability notions; resting on unproven hardness
- L7: Purposes: secrecy for spies, commanders and diplomats; then integrity, authentication, signatures and secure computation; private and signed electronic mail, payments
the boardroom (shared floors)
- L4: The cipher at work: encryption and decryption, by hand, machine or program
- L4: The attack: cryptanalysis proper
- L5: Protocols, modes and key management: the session the cipher runs in
- L5: The codebreaking operation at scale (Bletchley Park's huts and machines; research groups with core-years)
- L6: The security goal: what 'secure' means and the assumptions it rests on
- L6: Intelligence: what the decrypts mean (Ultra); in open research, a published break
- L7: The purposes: secrecy, integrity, authentication, signatures; for states, armies, firms and people
- L7: Motive and use: command decisions, state interest, the open science of breaking
the codebreaker's side (cryptanalysis): intercepted traffic up to the decisions it informs (secondary stack)
- L1: Enemy traffic on the air or the wire, enciphered (Enigma, Lorenz)
- L2: Interception and collection: intercept stations, captured material, Internet-wide scans
- L3: Statistics and cribs: letter frequencies, probable words, indices; known plaintext
- L4: The attack: frequency analysis, permutation theory, bombes and Colossus, factoring algorithms, side channels
- L5: The cryptanalytic operation: huts, shifts and machines at industrial scale
- L6: Intelligence: decrypts turned into a product (Ultra), with its secrecy guarded
- L7: Use: commanders' and states' decisions
the mathematical structure it rests on: numbers and operations up to reductions (secondary stack)
- L1: Finite symbol sets and numbers: alphabets, integers modulo n, finite fields such as GF(2^8) and GF(q)
- L2: Operations: permutations, modular exponentiation, invertible matrices, polynomial arithmetic modulo m(x)
- L3: Hard problems: factoring, discrete logarithms, lattice problems (learning with errors)
- L4: One-way and trap-door functions
- L5: Reductions: breaking a scheme shown at least as hard as a named problem
way in: Captured or betrayed cipher material
- L1: Cipher materials obtained by a spy, including daily keys
- L2: Used with traffic to solve the unknown rotor wiring
- L3: Reconstructed machines and techniques handed on
way in: Ciphertext arriving for the legitimate receiver
- L1: Cryptogram on the open channel
- L2: Received blocks; transmission errors spread by some modes
- L3: The receiver's key, shared only with intended recipients
way in: Intercepted traffic
- L1: Enemy traffic intercepted and recorded
- L2: Collected at volume
- L3: Letter statistics read through the cipher
way in: Keys arriving from correspondents (courier, public directory)
- L1: Keys sent in advance by courier or registered mail, or published
- L2: The correspondent's enciphering key read from a public directory
- L3: The protected public file as the port
- L4: Encipher in the receiver's public key; decipher with one's own secret key
way in: Known and probable plaintext (cribs)
- L1: Corresponding plaintext and ciphertext in the analyst's hands
- L2: Indexed: preambles, persons, ships, jargon
- L3: The crib laid against the ciphertext, using the machine's own rule that no letter encrypts to itself
way in: Mathematical results (hard problems, one-way functions)
- L1: Problems worked on for centuries (factoring since Fermat and Legendre)
- L2: Hardness assumptions chosen as foundations
- L3: One-way and trap-door functions as the designer's port
way in: Messages to protect (plaintext)
- L1: Messages people write, to be kept private and signed
- L2: Encoded into the cipher's alphabet: letters for classical ciphers, any binary data for computer ciphers
- L3: Plaintext blocks at the cipher's input
way in: Physical leakage (timing)
- L1: Time taken by private-key operations
- L2: Measured, even by passive eavesdropping on a protocol
- L3: Timing measurements exploited to recover the whole key
way in: Public keys gathered at Internet scale
- L1: Public keys and certificates offered by Internet hosts
- L2: Repeated keys found
- L3: Shared factors computed, giving private keys
way in: Published breaks and records
- L1: Breaks and records published (RSA-240 and a 795-bit discrete logarithm, 2019-2020)
- L2: Cost measured in core-years
- L3: Compared against key lengths under Moore's law
- L4: Designs re-evaluated and adapted
way in: Randomness and keys
- L1: Physical randomness at the device (events, noise); scarce on first boot of embedded devices
- L2: The operating system's random number generator
- L3: The key, chosen uniformly at random
way in: Spoken codes over telephone and radio (code talkers)
- L1: Voice on military telephone and radio nets
- L2: Agreed words standing for letters, in the speaker's own language
- L3: The trained code talker on each end
way in: The user's and cryptographer's thought (keys remembered, procedures followed)
- L1: The key held in memory, without written notes
- L2: Working the system without mental strain or a long list of rules
- L3: Understanding what to do at the interface (encrypt, sign, publish and fetch keys) and avoiding dangerous errors
way out: Breaks published in the open
- L1: Published for all, including the designers
- L6: A break or record written up
way out: Ciphertext sent
- L1: The cryptogram goes out where anyone may record it
- L4: The cipher enciphers
- L5: The mode chains or counts the blocks
way out: Ciphertext stored for later decryption
- L2: Ciphertext held
- L7: Collect now, decrypt when quantum technology matures
way out: Intelligence disseminated
- L1: Commanders act on it
- L6: Decrypts summarised under cover names
way out: Patches and replaced keys deployed
- L1: Patches installed on servers
- L5: Patched software and new certificates chosen
way out: Plaintext delivered to the reader
- L1: The recovered message in front of the intended reader (Human sight)
- L4: Decryption reverses the cipher
way out: Public key placed in a directory
- L1: The entry in the public directory, waiting to be used
- L5: Key pair made; the enciphering half published
way out: Signed messages and contracts
- L1: The signed document checked by anyone with the public key
- L5: Signature computed with the private key
way out: Standards and migration targets
- L1: Algorithms deprecated and disallowed on dates in products
- L5: Standards issued (AES 2001; ML-KEM in FIPS 203)
- L7: A national target for migrating away from quantum-vulnerable public keys