Public key cryptography and digital signatures

For most of the history of cryptography, two parties could only communicate secretly if they already shared a secret. That circularity is the key distribution problem, and it put a hard ceiling on how many parties could transact securely: a network of n participants who each need a shared key with every other needs n(n−1)/2 keys. For 1,000 participants that is 499,500 keys, each of which has to be delivered by some channel already trusted.

Public key cryptography broke the circle. It lets you publish something that allows anyone to verify your statements or send you a secret, while you keep something else that allows only you to produce those statements or read those secrets. On a blockchain this is the entire authorisation model. There are no accounts held by a bank, no passwords, no reset. Control of a private key is ownership, in the only sense the protocol understands.

Trapdoor functions, and why elliptic curves won

The construction relies on a function that is easy to compute and hard to invert, unless you hold a piece of side information. RSA, published by Rivest, Shamir and Adleman in 1978, uses multiplication of large primes: multiplying two 1,536-bit primes is instant, factoring the 3,072-bit product is not.

Elliptic curve cryptography, proposed independently by Neal Koblitz and Victor Miller in the mid-1980s, uses a different hard problem. Points on a suitable curve form a group with an addition operation. Given a fixed base point G and an integer k, computing the point k·G is fast, using repeated doubling. Recovering k from the point k·G is the elliptic curve discrete logarithm problem, and the best known general algorithms take roughly the square root of the group size.

That square root is why elliptic curves displaced RSA in this domain. To reach a comparable security level, NIST's guidance treats a 256-bit elliptic curve key as roughly equivalent to a 3,072-bit RSA key. Twelve times smaller keys and much smaller signatures matter enormously when every signature is stored forever by every node on the network.

Bitcoin and Ethereum both use the curve secp256k1. A private key is a 256-bit integer below the curve's group order, which is a number just under 2^256, approximately 1.158 × 10^77. The public key is the curve point obtained by multiplying the base point by that integer. There is no cleverness in generating a key: you take 256 bits from a good random source and check the value is in range. The security of every franc of value you hold rests on that random source having been genuinely unpredictable.

Signing, and what a signature actually asserts

A digital signature scheme has three operations: generate a key pair, sign a message with the private key, verify a signature against the message and the public key.

In practice you never sign the message itself. You hash it first, then sign the digest. This is efficient, and it is also why the previous lesson matters here: if an attacker can find two messages with the same hash, a signature over one is automatically a valid signature over the other. Signature security inherits hash security.

ECDSA, the scheme Bitcoin launched with and which Ethereum still uses for externally owned accounts, produces a signature as a pair of 256-bit integers (r, s), 64 bytes in total. It has one notorious sharp edge: each signature requires a fresh random nonce, and if that nonce is ever reused across two different messages under the same key, the private key can be recovered from the two signatures by simple algebra. This is not theoretical. Sony's PlayStation 3 code-signing key was extracted in 2010 after researchers found the same nonce in multiple signatures, a result presented publicly at the Chaos Communication Congress. In 2013 a flaw in Android's random number generator produced repeated nonces in mobile Bitcoin wallets and funds were drained from affected addresses. The standard defence, specified in RFC 6979, is to derive the nonce deterministically from the private key and the message hash, so it is unique per message without depending on the device's entropy at signing time.

Schnorr signatures, adopted by Bitcoin in the Taproot upgrade activated in November 2021, avoid some of ECDSA's awkwardness and add a property ECDSA lacks: linearity. Two Schnorr public keys can be added to give a key whose valid signature is the sum of the two parties' partial signatures. This means an n-of-n multi-party arrangement can appear on-chain as an ordinary single-key spend, which is smaller, cheaper, and reveals nothing about the arrangement.

Be precise about what a valid signature asserts. It says: whoever produced this had the private key corresponding to this public key, and the message has not been altered since. It does not say who that person is, that they intended the economic consequence, that they were not coerced, or that the key had not been stolen the week before. Every dispute about a "hacked" wallet is a dispute about that gap, and the protocol has no view on it.

From key to address

Addresses are derived from public keys by hashing, which serves two purposes: it shortens them, and it keeps the public key itself hidden until the moment of spending.

Bitcoin applies SHA-256 then RIPEMD-160 to the public key, producing a 160-bit value that is then encoded with a checksum. Ethereum takes the Keccak-256 hash of the 64-byte uncompressed public key and keeps the last 20 bytes. In both cases the on-chain address is a hash, and the public key becomes visible only when you sign a transaction spending from it.

That has a practical consequence for address reuse. An address that has never sent funds exposes only a hash; an address that has spent has published its public key. Under current cryptography this makes little difference, since the discrete log problem is intractable either way. It matters for the quantum question below.

Private keys are almost never handled directly. BIP-32 hierarchical deterministic wallets derive a whole tree of keys from one seed, and BIP-39 encodes that seed as a word list whose length encodes how much entropy sits behind it, together with a short checksum that catches most transcription errors. The wallet lesson later in this course works that encoding through with its arithmetic; the point here is that every address in the tree descends from the single random number described above, so the tree is exactly as strong as that number was unpredictable.

Splitting the key: multisig and threshold schemes

Single-key custody has a single point of failure in both directions: lose the key and the funds are gone, leak the key and the funds are gone. Two families of construction split that risk.

Multisignature does not split the key at all. It leaves several ordinary key pairs intact and writes the spending condition into the script, for example "two of these three public keys must sign", so the chain itself checks each signature separately against each named public key.

Threshold signatures and multi-party computation split the key mathematically instead. Using secret sharing, the private key is divided into shares such that any sufficient subset can jointly compute one ordinary signature, while any smaller subset learns nothing about the key — and crucially the whole key is never reconstructed on any single machine, at any moment. The chain sees a normal single-signature transaction and cannot tell the difference. The operational trade-off between the two, and which failure modes each one actually protects against, is the subject of the wallet lesson.

Quantum computing, stated accurately

Shor's algorithm, if run on a sufficiently large fault-tolerant quantum computer, solves both integer factorisation and the elliptic curve discrete logarithm efficiently. That would break RSA and ECDSA outright: a public key would yield its private key. Machines of the required scale do not exist, and the engineering gap between current devices and that requirement remains very large, but the threat is structural rather than speculative.

Grover's algorithm is the other half of the story and is much weaker. It gives a quadratic speed-up on unstructured search, effectively halving the security level of hash functions and symmetric ciphers. SHA-256 would offer roughly 128-bit preimage security instead of 256-bit, which is uncomfortable but not fatal. This asymmetry is why the exposure sits with signatures rather than with the hash chain.

NIST published its first post-quantum standards in August 2024, including ML-KEM for key encapsulation and ML-DSA for digital signatures, both based on structured lattice problems, alongside the hash-based signature scheme SLH-DSA. Migrating a live blockchain to such a scheme is a governance problem as much as a cryptographic one, because coins sitting in addresses whose owners never move them cannot be migrated by anyone.

The Swiss angle: proving you control the key you claim to

Swiss anti-money-laundering supervision produced an unusually direct application of message signing. FINMA's guidance on payments on the blockchain, issued in 2019, took the position that when a supervised institution sends assets to an external wallet, it must establish that the wallet belongs to the customer, since the technology provides no equivalent of the counterparty information carried by a bank transfer.

The practical result is that Swiss-supervised exchanges and banks ask a customer withdrawing to self-custody to demonstrate control of the destination address, typically by signing an agreed message with the private key and submitting the signature, or by a small verified transfer from that address. This is public key cryptography being used exactly as designed and for a purpose Satoshi did not have in mind: not to authorise a payment, but to link an address to an identified person in a supervisor's file.

It is worth seeing the asymmetry that makes it work. Signing a message costs nothing and reveals nothing about the key. Producing the same signature without the key is infeasible. That is the whole trick, and it also explains the limitation regulators have to live with: the signature proves control at the moment of signing, and control can change hands the following day.

What to take away

• A private key is simply a random 256-bit number below the curve order, so the quality of the random source used at generation is the true root of security for everything derived from it.
• ECDSA's requirement for a unique unpredictable nonce has caused real key recovery incidents on the PlayStation 3 and in Android wallets; RFC 6979 deterministic nonces remove the dependency on device entropy.
• Elliptic curve keys are roughly twelve times shorter than RSA keys of comparable strength, which is why chains that store every signature permanently adopted them.
• A valid signature proves control of a key over a specific message, and nothing about identity, intent or whether the key was stolen.
• Quantum computing threatens signature schemes far more than hash functions, because Shor's algorithm breaks discrete logarithms outright while Grover's only halves hash security.

Sources

• Whitfield Diffie and Martin Hellman, "New Directions in Cryptography" (1976).
• Ronald Rivest, Adi Shamir and Leonard Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (1978).
• Neal Koblitz (1987) and Victor Miller (1985) on elliptic curve cryptosystems.
• Thomas Pornin, RFC 6979, "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)".
• Bitcoin Improvement Proposals BIP-32 (hierarchical deterministic wallets), BIP-39 (mnemonic seed phrases) and BIP-340 (Schnorr signatures for secp256k1).
• National Institute of Standards and Technology, FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA), published August 2024; NIST SP 800-57 on comparable key strengths.
• FINMA Guidance 02/2019, "Payments on the blockchain".
• Peter Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" (1994).