Cryptographic Foundations
- Chapter 14: Cryptographic Foundations
Chapter 14: Cryptographic Foundations
“The universe believes in encryption. It is easier to encrypt information than it is to decrypt it.”
Julian Assange, Cypherpunks: Freedom and the Future of the Internet (2012)^1^
Introduction
The goal of this chapter is conceptual understanding, not a full cryptography course. Readers need to understand what cryptographic tools accomplish and why they work, not how to implement them. Implementation requires specialized expertise; using implementations requires understanding their properties. Readers who want to go deeper should consult David Wong, Real-World Cryptography (Manning, 2021) for an accessible applied introduction, Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed. (CRC Press, 2020) for rigorous formal treatment, Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2022, available free online) for the proof-systems side, and Ross Anderson, Security Engineering, 3rd ed. (Wiley, 2020) for how cryptography interacts with everything around it.^2^ The foundational papers of the discipline, its political and ethical framing, and its longer historical narrative are collected in a separate further-reading note at the end of the chapter.^3^
Cryptography solves coordination problems through mathematics, not institutions. Where traditional systems require trusting intermediaries, cryptographic systems require trusting only computational hardness assumptions. This shift from institutional to mathematical trust is the foundation for privacy-preserving technology.
Three jobs must stay separate from the beginning. One tool hides content, another proves who authorized a message, and a third lets strangers verify integrity without trusting the same intermediary. The chapter moves through those jobs in that order, then asks what mathematics can and cannot replace.
14.1 Symmetric and Asymmetric Cryptography
Symmetric Cryptography
Symmetric cryptography is the oldest form of the first job: hiding content. One key encrypts; the same key decrypts. If only Alice and Bob possess the key, only they can read the message.
The speed of symmetric algorithms makes them the workhorse of content protection. Modern ciphers (AES, ChaCha20) encrypt data at gigabytes per second.^4^ But speed alone does not solve the trust problem.
How do Alice and Bob establish a shared secret without meeting in person? If they communicate the key over an insecure channel, an eavesdropper intercepts it. If they need a secure channel to exchange the key, they already have secure communication and do not need the key. This is the key distribution problem, and for millennia it confined cryptography to parties who could physically exchange secrets: diplomats with couriers, military with secure channels, spies with dead drops. Mass adoption of encryption required breaking that confinement.
Asymmetric Cryptography
Asymmetric (public-key) cryptography, discovered in the 1970s, broke the key-distribution bottleneck.^5^ Instead of one shared key, each party generates a mathematically related key pair: a public key they can share openly and a private key they keep secret.
The mathematical relationship between the two keys is non-reversible: computing the public key from the private key is simple, but computing the private key from the public key is computationally infeasible. No prior relationship is required. Alice can send Bob an encrypted message having never communicated with him before, using only his publicly available public key. The trust requirement shifts from “do I have a secure channel to this person?” to “is this public key authentic?” That second question is solvable without institutions.
This resolves the confidentiality side of key distribution. Alice publishes her public key; others encrypt messages to her; only she can decrypt them. No secure channel is needed, and no intermediary. Authenticity of the public key remains a separate problem, addressed below.
The Hybrid Reality
Symmetric cryptography hides content efficiently when parties already share a secret. Asymmetric cryptography eliminates the need for that prior secret. Neither alone suffices.
In practice, systems use both. Asymmetric cryptography establishes a session key; symmetric cryptography encrypts the actual data. The hybrid approach means every encrypted connection on the internet rests on the same foundation: mathematical trust replacing institutional trust at the key-exchange layer, then raw speed protecting the content itself.
The Algorithms
Several foundational algorithms enable asymmetric cryptography. Diffie-Hellman key exchange, published in 1976, allows two parties to establish a shared secret over a public channel.^6^ Neither party reveals their private key, but both derive the same shared secret through mathematical operations on public values. Diffie-Hellman solves key exchange but not encryption directly; the shared secret it produces typically becomes the key for symmetric encryption.
RSA, published in 1978, provides both encryption and digital signatures using the difficulty of factoring large prime numbers.^7^ Security depends on factorization remaining computationally infeasible for sufficiently large numbers. RSA can encrypt messages directly (up to a size limit) and create signatures. Its disadvantage is key size: secure RSA requires keys of 2048 bits or more, making it slower and more resource-intensive than alternatives.
Elliptic Curve Cryptography (ECC), introduced in the mid-1980s, achieves equivalent security with smaller keys using different mathematical structures.^8^ A 256-bit elliptic curve key provides security comparable to a 3072-bit RSA key. The smaller keys make ECC faster and more suitable for constrained devices. Bitcoin uses the secp256k1 elliptic curve for its signatures.^9^ Most modern systems prefer ECC over RSA for new implementations.
In practice, these algorithms serve complementary roles. Diffie-Hellman (or its elliptic curve variant ECDH) establishes shared secrets; RSA or elliptic curve signatures authenticate parties; and the resulting shared secrets key symmetric ciphers like AES for bulk encryption.
The Role of Randomness
Cryptographic security depends on unpredictability. Keys must be randomly generated; if an attacker can guess or predict a key, the strongest algorithm provides no protection.
Entropy measures unpredictability. A 256-bit key has 256 bits of entropy only if each bit is equally likely to be 0 or 1, independent of all other bits. If key generation has bias or patterns, effective entropy falls below what the bit length suggests, leaving the key weaker than it appears.
Randomness in cryptography must be cryptographically secure: not just “random looking” but unpredictable to any adversary. A pseudorandom number generator (PRNG) is an algorithm that uses a small initial value called a seed to produce a long sequence of numbers that appear random but are deterministic. PRNGs that produce statistically random output may still be predictable if an attacker knows the internal state or seed value. Cryptographically secure pseudorandom number generators (CSPRNGs) are designed so that even observing their output does not reveal future values.
Sources of entropy include hardware random number generators that sample physical phenomena (thermal noise, radioactive decay, electronic noise) and system events (keystroke timing, mouse movements, network packet arrival times). Since any single source might be compromised or insufficient, secure systems concatenate multiple independent entropy sources. An attacker who can predict one source still cannot predict the combined output if other sources remain unpredictable. Operating systems maintain entropy pools that accumulate randomness from all available sources and feed CSPRNGs that applications use for key generation.
When randomness fails, cryptography fails completely. The algorithms may be sound, but predictable keys are guessable keys.
14.2 Hash Functions and Digital Signatures
One-Way Functions
A cryptographic hash function takes input of any size and produces a fixed-size output (the “hash” or “digest”). SHA-256, widely used in Bitcoin and elsewhere, produces a 256-bit output regardless of input size.^10^
Hash functions exhibit several properties that together make them useful. The same input always produces the same output. Given the output, finding any input that produces it is computationally infeasible, and finding two different inputs that produce the same output is also computationally infeasible. They also exhibit the avalanche effect: small changes in input produce dramatically different outputs.
Hash functions enable efficient integrity verification. Instead of comparing entire files, compare their hashes. Matching hashes indicate matching files with overwhelming probability; differing hashes show the files differ.
Digital Signatures
Digital signatures use asymmetric cryptography to provide authentication and integrity.^11^ Unlike encryption (where anyone with the public key encrypts and only the private key holder decrypts), signatures work in the opposite direction: only the private key holder can create a signature, but anyone with the public key can verify it.
The signing process begins by computing the hash of the document, creating a fixed-size digest of the content. The signer then applies the signature algorithm using their private key and the hash, producing a signature value that accompanies the document.
Verification reverses this process. The verifier independently hashes the document, then applies the verification algorithm using the public key, the signature, and the recomputed hash. The algorithm outputs valid or invalid.
The mathematics varies by scheme. RSA signatures involve modular exponentiation; ECDSA,^15^ the scheme used in Bitcoin, involves elliptic curve point multiplication and modular arithmetic; and Schnorr signatures^16^ use a different construction with useful algebraic properties. What they share is the core asymmetry: creating a valid signature requires the private key; verifying requires only the public key.
Signatures prove three things. Authentication: only someone with the private key could have created the signature, so if you trust the public key belongs to Alice, the signature proves Alice signed. Integrity: any modification to the document after signing invalidates the signature because the recomputed hash will not match. Non-repudiation: Alice cannot credibly deny having signed if the signature validates against her public key.
Trustless Verification
What does it mean to verify without trusting the verifier? Anyone with the public key can independently confirm a signature, so no authority needs to be asked and no intermediary can falsely claim the verification happened. The mathematics is self-enforcing.
“Trustless” has a narrow meaning here: the verification process itself requires no trust because anyone can perform it. The question of whether the public key belongs to its purported owner remains, but that is a different problem addressed below.
14.3 Trust: Mathematical vs. Institutional
Traditional Trust Models
Before cryptography, trust required institutions. Reputation allowed parties to build track records over time, though new entrants faced high barriers. Legal enforcement punished breach of agreements, but effectiveness depended on jurisdiction and resources. Trusted third parties served as intermediaries who vouched for unknown parties, concentrating trust in those intermediaries. Physical security through vaults or guards, along with sealed documents, provided tangible protection.
Each model has failure modes: reputation can be manufactured, enforcement requires access to legal systems, intermediaries can be corrupted or coerced, and physical security can be breached.
Digital systems inherited this pattern without changing it. To send email, share a file, or join a chatroom, you trusted a server administrator to keep your messages confidential and to enforce who could access them. Access control was a server-side policy, implemented as a database row or a permission flag or a configuration setting, running on infrastructure you did not control and could not inspect. If the administrator was honest, competent, and uncoerced, the system worked as advertised. If the administrator was malicious, subpoenaed, or breached, access policies were irrelevant and the data was exposed. The institutional trust problem had been translated into a system administration problem, and the trust requirement was no smaller for the translation.
Mathematical Trust
Cryptographic trust rests on computational hardness assumptions. The factorization assumption holds that factoring the product of two large primes is computationally infeasible. The discrete logarithm assumption holds that computing discrete logarithms in certain groups is computationally infeasible. Hash function assumptions hold that finding collisions or preimages for properly designed hash functions is computationally infeasible. These assumptions have been studied for decades by mathematicians and cryptographers worldwide. Unlike institutional trust, they do not vary with personnel changes, political pressures, or economic incentives. Mathematics does not accept bribes.
End-to-end encryption changes where access rules are enforced. Instead of a server deciding who may read a message, the cryptography decides: only holders of the correct keys can decrypt, and no configuration change on the server can override that fact. Access control moves from a policy in the infrastructure to a property of the data itself. The administrator who was once the guarantor becomes irrelevant to the guarantee. Infrastructure continues to route and store the ciphertext, but it does so without being able to read it, and the trust the user must extend collapses from trust in people and institutions to trust in mathematics and in the key management practiced at the endpoints.
Why Mathematics Is More Reliable
Why should anyone trust a mathematical proof over a human institution? Because mathematical trust has properties institutional trust structurally lacks. The same proof verifies the same way everywhere; a valid signature in one country is valid in all countries. The algorithms are public; anyone can verify the mathematics; security does not depend on secrecy of method. Verification requires no third party. Alice can verify Bob’s signature without asking anyone’s permission or trusting any intermediary. And computational verification scales with hardware, while human verification does not.
Limits of Mathematical Trust
Mathematical trust is not unlimited. Mathematics cannot tell you whether a public key belongs to whom it claims; that requires external verification: meeting in person, a web of trust, certificate authorities, or some other out-of-band confirmation. The mathematics may be sound while the implementation is flawed, and software bugs can undermine theoretically perfect cryptography. Computational assumptions themselves could fail if P=NP or if quantum computers mature sufficiently. Users can also be tricked into revealing keys or trusting the wrong public keys, and they may rely on compromised software.
Mathematical trust replaces some trust requirements but not all, shifting reliance away from institutions and toward assumptions tested in code and mathematics. The shift is valuable but not absolute.
14.4 Limitations and Vulnerabilities
Implementation Bugs vs. Cryptographic Breaks
Cryptographic algorithms are rarely broken mathematically; what fails is implementation.
Buffer overflows allow attackers to overwrite memory and extract keys, while timing attacks measure how long operations take to reveal information about keys from the timing alone. Random number failures compromise security because cryptography requires unpredictable randomness. Protocol errors occur when individual algorithms are secure but their combination is not. Most real-world cryptographic failures are implementation failures. The mathematics can hold while the code fails.
Side-Channel Attacks
Side-channel attacks extract information from physical implementation, not from mathematical weakness. Power analysis measures power consumption during cryptographic operations to reveal key bits, and electromagnetic emanations from computing equipment can leak information via radio signals. Cache timing attacks observe cache behavior to reveal memory access patterns correlated with keys. Acoustic attacks analyze sound produced by computers to leak cryptographic information. These attacks require physical proximity or sophisticated equipment but demonstrate that cryptographic security depends on more than algorithm strength.
The Human Element
Humans are the weakest link. Social engineering that convinces people to reveal keys or install malware bypasses cryptography entirely. Encryption protected by weak passwords provides weak protection. Key management presents persistent challenges: lost keys mean lost data, and compromised keys mean compromised data. Systems that are hard to use correctly are used incorrectly, and users disable security features that interfere with tasks.
Physical coercion, the “$5 wrench attack” examined in Chapter 5, remains outside cryptography’s domain.^12^ Cryptography protects data, not people.
The Quantum Horizon
Quantum computers threaten current public-key cryptography. Shor’s algorithm, running on a sufficiently powerful quantum computer, could break RSA and elliptic curve cryptography by efficiently solving the mathematical problems they rely on.^13^ The threat is not hypothetical in the academic sense, because the algorithms are published and their operation is well understood. The threat is hypothetical in the hardware sense, because the machines that would execute them at the required scale do not yet exist. Estimates of the year by which such a machine might appear vary across national-security agencies and industrial research programs, with the mainstream published range falling between 2030 and 2040. The defender’s planning horizon must be calibrated to the earliest credible date, not the median.
Status varies by cryptographic type. Asymmetric cryptography, including RSA and ECC, is vulnerable to quantum attack through Shor’s algorithm. Symmetric cryptography is less affected; Grover’s algorithm^17^ provides only quadratic speedup, so doubling key lengths (for example, using AES-256 instead of AES-128) maintains security. Hash functions are similarly less affected, with quantum computers providing modest speedup that does not break them. Asymmetric primitives must be migrated; symmetric primitives need parameter adjustments but not architectural replacement.
The more pressing near-term threat is not live attack but “harvest now, decrypt later.” An adversary who captures encrypted traffic today and retains it until quantum decryption becomes available can read that traffic when the machine arrives. The defender’s exposure therefore depends on the longevity of the secret, not on the current state of quantum hardware. Traffic that must remain confidential for a decade or more should be assumed to be exposed to future quantum decryption even when captured today.
The Standards Arrive
NIST finalized three core standards in August 2024, ML-KEM for key exchange, ML-DSA for signatures, and SLH-DSA as a conservative hash-based backup, and added a code-based HQC backup in March 2025.^14^ The standardization process took eight years of public cryptanalysis.
The transition from standardization to deployment has moved faster than any previous cryptographic transition. Signal deployed PQXDH (a hybrid combining X25519 and Kyber) in September 2023 before the NIST standard was finalized. Apple shipped iMessage PQ3 in iOS 17.4 and macOS 14.4 in February 2024. Google enabled hybrid Kyber-based key exchange by default in Chrome 124 in April 2024 and migrated to the standardized X25519MLKEM768 later that year. Cloudflare reported by mid-2025 that more than thirty percent of Transport Layer Security handshakes at its edge used hybrid post-quantum key exchange. The deployment pattern is consistent: mix the new primitive with a proven classical primitive so a break in either one does not compromise the session, and migrate the entire internet before the threat materializes.
Governments have published migration timelines on the same premise. The U.S. National Security Agency’s CNSA 2.0 suite requires ML-KEM and ML-DSA for National Security Systems by 2033, with earlier adoption permitted where possible. The U.K. National Cyber Security Centre recommends post-quantum migration for high-value systems by 2035. Both timelines assume a cryptanalytically relevant quantum computer could appear before 2035, and both use 2033 to 2035 as the deadline by which migration must be complete, not as the expected appearance date. The principle is standard in security engineering: the migration budget is the gap between the deadline and the threat, and the deadline must precede the threat by a margin that accounts for implementation lag.
The Quantum Horizon and the Axiom of Resistance
The Axiom of Resistance holds that a system’s security is measured by the cost required to compromise it. Post-quantum cryptography is an engineering response to a predictable change in that cost. Mathematical problems that were hard for classical computers become tractable for quantum computers; the cost of breaking them collapses. The axiom does not require that cost be infinite. It requires that the defender’s cost of maintenance remain below the adversary’s cost of compromise, and the post-quantum transition is what keeps that inequality in place across the hardware transition.
The hash-based construction illustrated by FIPS 205 depends only on the properties of hash functions, which are well understood and less affected by quantum computing. The primitive is conservative in exactly the sense the axiom calls for: when the assumption set is smaller, the failure surface is smaller. The lattice-based ML-KEM and ML-DSA standards rely on assumptions that are more recent and less studied than the assumptions underlying RSA. This is the cost of the transition. The defender accepts a less-tested assumption in exchange for quantum resistance, and the standards community’s response has been to publish multiple independent algorithm families so that an unexpected attack on one family does not break the entire transition.
The harvest-now-decrypt-later threat model also forces a calibration of what qualifies as a long-lived secret. Conversations that were assumed ephemeral because they were encrypted in transit are long-lived if the ciphertext is captured. The defender who encrypted a message in 2024 under pre-quantum primitives must assume that the message will be readable at the point in the future when the machine arrives. This is why Signal and Apple and Chrome deployed their hybrid constructions before the threat materialized. The clock on past traffic cannot be rewound, but the clock on future traffic is still running.
The transition is a major infrastructure project. It is also technically feasible, and the deployments cited above demonstrate the feasibility at internet scale. Whether the defender completes the transition before the adversary benefits from captured pre-transition traffic is the variable that determines whether the harvest-now-decrypt-later threat lands.
What Cryptography Cannot Solve
Cryptography cannot solve endpoint security; if the device is compromised, cryptography on that device is meaningless. It cannot hide metadata; encryption hides content but not the fact of communication, and who talks to whom remains visible, along with timing and frequency, without additional protection (see Chapter 17). Physical coercion can still compel key disclosure. Cryptography also cannot solve social problems or make people trustworthy, only make certain betrayals detectable. Nor can it establish key authenticity, because mathematics cannot tell you if the public key belongs to its purported owner.
Cryptography is a tool. It solves specific problems. Expecting it to solve problems beyond its scope leads to false confidence.
Chapter Summary
Cryptography shifts trust from institutions to mathematics. Where traditional systems require trusting intermediaries, cryptographic systems require trusting only computational hardness assumptions, the same body of assumptions tested by decades of failed attacks. Symmetric cryptography hides content efficiently when keys are shared; asymmetric cryptography eliminates the need for a prior shared secret by giving each party a key pair whose private half cannot be derived from the public half. Hybrid systems use both: asymmetric for key agreement, symmetric for bulk encryption. Hash functions produce fixed-size fingerprints that enable integrity verification, and digital signatures combine hashing with asymmetric cryptography to provide authentication, integrity, and non-repudiation. Anyone with the public key can verify a signature independently; no authority need confirm, and no intermediary can falsify the result.
Mathematical trust replaces some trust requirements but not all. Key authenticity still requires external verification, meeting in person, a web of trust, certificate authorities, or some out-of-band channel, because mathematics cannot tell whether a public key belongs to whom it claims. Implementations can be flawed even when algorithms are sound, and most real-world cryptographic failures originate in code: bad parameters, weak randomness, poor key handling, side channels. Side-channel attacks extract information from physical observables (power consumption, timing, electromagnetic emanations) while the underlying mathematics holds. Humans remain the weakest link: social engineering bypasses the mathematics entirely, and physical coercion compels disclosure regardless of key strength. Cryptography protects data, not people.
The quantum horizon has moved from research to production. NIST finalized the core lattice and hash-based signature standards (ML-KEM, ML-DSA, SLH-DSA) in August 2024 and selected HQC as a code-based backup KEM in March 2025. Signal’s PQXDH protocol, Apple iMessage PQ3, Chrome’s hybrid key exchange, and Cloudflare’s edge all ship post-quantum cryptography in deployed consumer systems. The transition is a major infrastructure project that must complete before cryptanalytically relevant quantum computers arrive, because harvest-now-decrypt-later makes today’s ciphertext an asset for tomorrow’s decryption. Cryptography solves confidentiality, authentication, and integrity; it does not solve endpoint compromise, metadata exposure, physical coercion, or key authenticity, and the rest of the book addresses what cryptography alone cannot.
Endnotes
^1^ Julian Assange, with Jacob Appelbaum, Andy Müller-Maguhn, and Jérémie Zimmermann, Cypherpunks: Freedom and the Future of the Internet (New York: OR Books, 2012). The quoted passage, from the opening of Assange’s introduction, states the structural claim this chapter develops: that the asymmetry between the cost of encrypting information and the cost of decrypting it is a law of the universe, not a policy choice; strong cryptography therefore constrains state power architecturally, at the level of physics and computation, where law cannot reach. For the earlier cypherpunk-movement statement of the same goal in manifesto form, see Eric Hughes, “A Cypherpunk’s Manifesto” (1993), https://www.activism.net/cypherpunk/manifesto.html.
^2^ For open-source implementations readers can inspect and use, GnuPG (gnupg.org) remains the dominant OpenPGP implementation; age (age-encryption.org, Filippo Valsorda) is a modern minimal file-encryption tool with strong defaults; Signal (signal.org) is the reference deployment of the Signal Protocol; OpenMLS (openmls.tech) is the primary open MLS implementation. For reading lists beyond the core texts above, the Cryptography Engineering mailing list (blog.cryptographyengineering.com, Matthew Green) and Bruce Schneier’s Cryptogram newsletter remain current and accessible.
^3^ Further reading on cryptography as a discipline and its political history. For the foundational twentieth-century papers: Claude E. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal 28, no. 4 (1949): 656–715, https://www.iacr.org/museum/shannon/shannon45.pdf, established cryptography as a mathematical discipline and articulated the “enemy knows the system” principle (Kerckhoffs’s principle, originally stated in Auguste Kerckhoffs, “La cryptographie militaire,” Journal des sciences militaires 9 [January–February 1883]: 5–38); Whitfield Diffie and Martin Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory IT-22, no. 6 (1976): 644–654, invented public-key cryptography; Ronald Rivest, Adi Shamir, and Leonard Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM 21, no. 2 (1978): 120–126, gave the first practical public-key scheme; David Chaum, “Security Without Identification: Transaction Systems to Make Big Brother Obsolete,” Communications of the ACM 28, no. 10 (1985): 1030–1044, extended the discipline to privacy-preserving transactions. For the political and ethical frame, Phillip Rogaway, “The Moral Character of Cryptographic Work,” IACR Distinguished Lecture (2015), http://web.cs.ucdavis.edu/~rogaway/papers/moral-fn.pdf, argues that cryptographic design is an act of political engineering; Julian Assange, with Jacob Appelbaum, Andy Müller-Maguhn, and Jérémie Zimmermann, Cypherpunks: Freedom and the Future of the Internet (OR Books, 2012), collects the cypherpunk-political reading of the same discipline; Jon Callas’s oft-quoted formulation that “cryptography is the ultimate form of non-violent direct action” captures the same position from a practitioner who helped ship PGP, iMessage, and Silent Circle. For history and narrative, David Kahn, The Codebreakers: The Story of Secret Writing, rev. ed. (Scribner, 1996; original 1967), is the definitive long-form history of cryptography through the mid-twentieth century; Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (Anchor, 2000), covers similar ground accessibly. Steven Levy, Crypto: How the Code Rebels Beat the Government, Saving Privacy in the Digital Age (Viking, 2001), is the narrative history of public-key cryptography and the cypherpunk movement through PGP and the Clipper Chip fight.
^4^ AES is specified in NIST FIPS 197, Advanced Encryption Standard (AES) (2001), https://csrc.nist.gov/pubs/fips/197/final. ChaCha20 is specified in RFC 8439, ChaCha20 and Poly1305 for IETF Protocols (2018), https://www.rfc-editor.org/rfc/rfc8439.
^5^ Whitfield Diffie and Martin E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory 22, no. 6 (1976): 644-654.
^6^ Diffie and Hellman, “New Directions in Cryptography.”
^7^ Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM 21, no. 2 (1978): 120-126.
^8^ Victor S. Miller, “Use of Elliptic Curves in Cryptography,” Advances in Cryptology: CRYPTO ’85 (1985): 417-426; Neal Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation 48, no. 177 (1987): 203-209.
^9^ The secp256k1 curve parameters are defined in Standards for Efficient Cryptography Group, SEC 2: Recommended Elliptic Curve Domain Parameters, version 2.0 (2010), https://www.secg.org/sec2-v2.pdf. The reference open-source implementation used by Bitcoin Core is libsecp256k1, https://github.com/bitcoin-core/secp256k1.
^10^ National Institute of Standards and Technology, Secure Hash Standard (SHS), FIPS PUB 180-4 (Gaithersburg, MD: NIST, 2015).
^11^ For digital signature foundations, see Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest, “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks,” SIAM Journal on Computing 17, no. 2 (1988): 281-308.
^12^ The “$5 wrench attack” refers to the observation that physical coercion is often easier than cryptanalysis. See XKCD comic 538, “Security.”
^13^ Peter W. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proceedings 35th Annual Symposium on Foundations of Computer Science (1994): 124-134.
^14^ NIST finalized the core post-quantum standards in August 2024 (ML-KEM, ML-DSA, SLH-DSA) and added HQC as a code-based backup KEM in March 2025; Signal’s PQXDH (Sept 2023), Apple’s iMessage PQ3 (Feb 2024), Google Chrome’s X25519MLKEM768 (Nov 2024), and Cloudflare’s edge (30%+ PQ TLS by mid-2025) are the largest deployed hybrid implementations; NSA CNSA 2.0 and UK NCSC target 2033–2035 for high-value migration. NIST Post-Quantum Cryptography Standardization project, https://csrc.nist.gov/projects/post-quantum-cryptography. Finalized standards: FIPS 203 (ML-KEM), https://csrc.nist.gov/pubs/fips/203/final; FIPS 204 (ML-DSA), https://csrc.nist.gov/pubs/fips/204/final; FIPS 205 (SLH-DSA), https://csrc.nist.gov/pubs/fips/205/final. HQC selection: NIST IR 8547 (March 2025), https://csrc.nist.gov/pubs/ir/8547/ipd. Signal PQXDH specification at https://signal.org/docs/specifications/pqxdh/. Apple iMessage PQ3 documentation at https://security.apple.com/blog/imessage-pq3/. Google Chrome post-quantum TLS announcement at https://blog.chromium.org/2024/05/advancing-our-amazing-bet-on-asymmetric.html and X25519MLKEM768 rollout at https://security.googleblog.com/. Cloudflare post-quantum TLS telemetry at https://blog.cloudflare.com/pq-2024/. U.S. National Security Agency CNSA 2.0 suite, https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF. U.K. National Cyber Security Centre post-quantum migration guidance at https://www.ncsc.gov.uk/guidance/pqc-migration-timeline.
^15^ Don Johnson, Alfred Menezes, and Scott Vanstone, “The Elliptic Curve Digital Signature Algorithm (ECDSA),” International Journal of Information Security 1, no. 1 (2001): 36-63. ECDSA is the signature scheme used in Bitcoin, Ethereum, and many TLS implementations; it applies elliptic curve point multiplication to produce signatures that are smaller and faster than RSA signatures at equivalent security levels. The original standard is ANSI X9.62 (1998); NIST’s version is FIPS 186-5 (2023), https://csrc.nist.gov/pubs/fips/186-5/final.
^16^ Claus-Peter Schnorr, “Efficient Signature Generation by Smart Cards,” Journal of Cryptology 4, no. 3 (1991): 161-174. Schnorr signatures have a linear algebraic structure that RSA and ECDSA lack: multiple signatures can be aggregated into a single signature whose size is independent of the number of signers (MuSig, MuSig2), and the scheme admits provably secure constructions in the random oracle model. Bitcoin added native Schnorr signatures via BIP 340 (activated in the Taproot upgrade, November 2021), https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki.
^17^ Lov K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996): 212-219. Grover’s algorithm provides a quadratic speedup for unstructured search problems: a quantum computer can search an N-item database in O(√N) steps, compared to O(N) classically. Applied to symmetric cryptography, this halves the effective key length: AES-128 under Grover’s attack has roughly the security of 64-bit classical search. The standard response is to double key lengths (AES-256 in place of AES-128), which restores the original security margin. Unlike Shor’s algorithm, which breaks RSA and ECC asymptotically, Grover’s attack leaves symmetric and hash-based primitives intact; it requires larger parameters but not architectural replacement.
<- Previous: The Crypto Wars |
-> Next: Zero-Knowledge Proofs |The Praxeology of Privacy – third edition. New chapters publish daily at 1600 UTC.
More from The Praxeology of Privacy
Write a comment