The Key Pair

21.0 What this chapter gives you#

1. You will be able to explain, to somebody with no mathematics, why a lock can be made public without making the thing it protects public, and why that single fact changed what identity could be.
2. You will be able to state the asymmetry exactly: which half of a key pair is published, which half is never transmitted, and what each half can and cannot do.
3. You will be able to name what Whitfield Diffie and Martin Hellman actually published in November 1976, what they proposed but did not build, and who had got there first inside a British government building six years earlier.
4. You will be able to generate an RSA key pair, sign a message and verify the signature using numbers small enough to check on paper, and then say which step becomes hard when the numbers are 617 digits long.
5. You will be able to say why a 256-bit elliptic curve key and a 3072-bit RSA key are treated as equally strong, and give the reason in terms of the best known attack on each.
6. You will be able to tell P-256, Curve25519, Ed25519 and Ed448 apart, say which of them signs and which of them only agrees keys, and name the specification that defines each.
7. You will be able to explain why “signing is just encrypting with the private key” is wrong in three separate ways, and give an example of a real product that was broken by believing it.
8. You will be able to say precisely what property of a hash function a signature scheme leans on, and describe two occasions on which a real certificate was forged because that property failed.
9. You will be able to read the NIST comparable-strength table and the transition dates that go with it, and say what is disallowed in 2031 and what is expected to be disallowed in 2035.
10. You will be able to name the two post-quantum signature standards published in August 2024, give their key and signature sizes in bytes, and explain why a signature system faces a different clock from an encryption system.

Every other chapter in this volume has the same shape of problem underneath it. A password is a secret that both sides hold, so the side that checks it can also impersonate you. A one-time code comes from a seed that both sides hold, so the same is true. A fingerprint template sits in a database, and whoever holds the database holds the thing that opens the door. In each case, the party who verifies you is also a party who could become you, and every security control built on top is an attempt to manage that fact rather than remove it.

This chapter is about the one idea that removes it. In 1976 two researchers at Stanford published a paper proposing that a key could come in two halves, that one half could be published in a newspaper, and that publishing it would not weaken the other. If that is true, then verification stops requiring a shared secret. A bank, a website, a border post or a stranger can check that you are the holder of a key without ever holding, storing, or even briefly seeing the thing that makes you the holder. Nothing in this book is a bigger break with what came before.

The consequences run through the whole of the rest of the volume and the whole of the next one. A passkey is a key pair. A certificate is somebody’s statement about a public key. A signed document, a signed software update, a signed identity credential and a signed border-crossing chip are all the same operation with different words around it. If you understand what happens when a private key is applied to a hash and what a verifier learns from checking it, you understand the mechanical core of modern identity, and everything else is packaging, policy and law.

The chapter has two jobs beyond explaining the mechanics. The first is to kill a piece of folklore that appears in almost every introductory account: the claim that a signature is an encryption performed with the private key. It is a comfortable sentence, it is false, and believing it has broken real systems. The second is to be honest about dates. None of these systems is proved secure. Each rests on a computational problem that nobody has publicly solved, and each therefore carries an expiry date that moves as machines and mathematics move. As of August 2026 the relevant dates are being written into standards, and we will read them exactly as they are written. The chapter before this one, “Face and Voice”, dealt with measuring a body. The chapter after it, “Challenge and Response”, deals with making the answer different every time, which is what turns a key pair into a login. Here we do the key pair itself.

The plain version#

The padlock you can leave lying in the street#

Think about an ordinary padlock and its key. There is nothing clever about it: the key opens the lock, the lock is useless without the key, and if you want somebody far away to be able to lock something up for you, you have to get a key to them somehow. That “somehow” has been the whole problem of secret communication for three thousand years. Two people who have never met cannot share a secret without first sharing a secret.

Now imagine a strange kind of padlock. It comes in two pieces that are made together, at the same moment, as a pair. One piece is the lock body. The other is the key. Snapping the lock shut needs only the lock body; you do not need the key to close it. Opening it needs the key, and nothing else will do.

You make ten thousand copies of the lock body and you give them away. You leave a bucket of them on the counter of every post office in the country. You post the design of the lock in the newspaper so that anybody can manufacture their own. You keep exactly one key, in your pocket, and you never let it out of your sight.

Anybody in the world can now send you something that only you can read. They put it in a box, take one of your padlocks off the counter, and snap it shut. The moment it closes, they have locked themselves out too. They cannot reopen it. Nobody who intercepts the box can open it. The postman cannot, the sorting office cannot, a burglar with a thousand of your padlocks cannot, because a padlock does not help you open a padlock. Only the key does, and there is one key, and it is in your pocket.

Notice what has disappeared. You never met the sender. You never agreed anything with them in advance. There was no moment at which a secret had to travel between you and be protected while it travelled. The only thing that travelled was the lock body, and the lock body is not a secret at all. It is deliberately public. That is the whole idea, and the first time somebody wrote it down in the open was 1976.

The lock body has a name in this book: the public key. The key in your pocket has a name too: the private key. They are made together, they belong to each other, and the pair is the smallest unit of modern identity.

Turning the machine round: the mark that only you can make#

So far the machine sends secrets to you. Turn it round and it does something more useful for identity.

Suppose that instead of locking a box, you take the key in your pocket and use it to press a mark into a lump of soft wax on a letter. The mark that comes out depends on the letter and on your key. Anybody holding one of your public padlocks can hold it against the mark and see whether the two fit. If they fit, the letter was marked by somebody holding the key, and there is only one of those.

A stranger who has never met you and holds nothing of yours but a piece of publicly posted metal can now do something remarkable: they can check that a letter came from you and has not been altered on the way, and they can do it without ever holding anything that would let them forge a letter from you. They cannot fake your mark. They can only recognize it.

That is the sentence this chapter exists to defend, so it is worth reading twice. Public key cryptography is the single idea that lets a stranger verify you without ever holding your secret.

Everything else in modern identity is a variation. Your phone holds a key and marks a login for a website; the website holds only the public half and checks the mark. A passport chip holds a key and marks the data on it; a border reader checks the mark against a published public half. A government marks a certificate; a browser checks it. The material changes, the operation does not.

The wax analogy is doing a lot of work here and it is going to be taken away from you in the next section, because it is wrong in an important way. Hold on to it for now.

Sums that are easy one way and horrible the other#

The reason this is possible at all is that arithmetic has a lopsided part, and the lopsidedness is very large.

Take two numbers, 61 and 53. Multiply them. On paper it takes about ten seconds and gives 3,233. Now take somebody who has only been given 3,233 and asked to find the two numbers it was made from. There is no clever move available. They divide by 2, by 3, by 7, by 11, and keep going until something divides cleanly. For a four-digit number that is a minute of tedium.

The gap does not stay a minute. Multiplying gets slightly harder as the numbers grow: two numbers of 300 digits each can be multiplied by a computer in far less than the blink of an eye. Un-multiplying gets catastrophically harder. When the answer is 617 digits long, the best publicly known method, running on thousands of computers for years, has never yet succeeded on a number of that size.

This is the shape of thing the whole subject is built on: an operation that is cheap in one direction and ruinous in the other. Locking is the cheap direction. Unlocking is the ruinous direction, unless you happen to be holding a piece of information that collapses it back to cheap. That piece of information is the private key.

There is a second ingredient. All the arithmetic here happens on a clock. An ordinary clock face has twelve hours, and if it is ten o’clock and you wait five hours it is three o’clock, not fifteen. Adding and multiplying on a clock face is normal arithmetic followed by throwing away everything except the remainder. The clocks in this chapter are large: our small worked example uses a clock with 3,233 positions on it, and a real one has a number of positions with 617 digits. Working on a clock is what stops the numbers running away, and it is also what makes the reverse direction hard, because a result on a clock face does not tell you how many times round you went.

A worked example small enough to check by hand#

Here is a complete, real, working key pair, small enough that you can check every step with a pocket calculator. We will use it for the rest of the chapter.

Pick two prime numbers. A prime is a number with no divisors except itself and one. Take 61 and 53. Multiply them: 61 times 53 is 3,233. That is the size of our clock. It is public.

Now take each prime, subtract one from it, and multiply those together: 60 times 52 is 3,120. This is a helper number. It is not published. Anybody who knows the two primes can compute it in a second; anybody who knows only 3,233 cannot, because finding it is the same problem as finding the primes.

Choose a small number that shares no factor with 3,120. Seventeen will do. That is the public exponent, and it is published.

Now find the number that undoes seventeen on the helper clock: a number which, multiplied by 17, leaves a remainder of 1 when divided by 3,120. That number is 2,753, because 17 times 2,753 is 46,801, and 46,801 is 15 lots of 3,120 with 1 left over. That is the private exponent, and it is never published.

So the public key is the pair of numbers 3,233 and 17. Print it in the newspaper. The private key is 2,753, and it lives in your pocket.

Next we need something to sign. Signing works on numbers, so the letter has to be turned into a number smaller than 3,233 first. We do that with a recipe that squashes any text down to one number. Start at zero. For each letter, multiply what you have by 31, add the letter’s number in the standard computer alphabet, and keep only the remainder after dividing by 3,233. The letters of the name SHIKHAR have the numbers 83, 72, 73, 75, 72, 65 and 82.

letter  value   running sum        remainder
S        83     0 x 31 + 83  =  83        83
H        72     83 x 31 + 72 = 2645     2645
I        73     2645 x 31 + 73 = 82068  1243
K        75     1243 x 31 + 75 = 38608  3045
H        72     3045 x 31 + 72 = 94467   710
A        65     710 x 31 + 65 = 22075   2677
R        82     2677 x 31 + 82 = 83069  2244

The squashed-down number, which we will call the fingerprint, is 2,244.

To sign, raise the fingerprint to the power of the private exponent on the clock. That is 2,244 multiplied by itself 2,753 times, keeping only the remainder after each step. The answer is 2,942. That number is the signature.

To verify, a stranger takes the signature, 2,942, and raises it to the power of the public exponent, 17, on the same clock. The answer comes out as 2,244. They then squash the letter down themselves with the same recipe and get 2,244. The two agree, so the letter was signed by whoever holds 2,753.

sign    2244 ^ 2753  mod 3233  =  2942
verify  2942 ^   17  mod 3233  =  2244
letter  fingerprint of SHIKHAR =  2244   match

Now change one letter. Make it SHIKHAB instead of SHIKHAR, which changes the last number from 82 to 66. Run the same squashing recipe and the fingerprint comes out as 2,228, not 2,244. The signature still unwinds to 2,244. The two no longer agree, and the verifier rejects it. A single letter changed anywhere in a document of any length has the same effect.

That is the entire mechanism. Everything else in this chapter is that mechanism done with bigger numbers, safer packaging and different arithmetic.

What the stranger knows, and what the stranger cannot do#

Stand in the verifier’s shoes for a moment and take an exact inventory.

The verifier holds 3,233 and 17. That is all. With numbers this small, the verifier can work out the private half and start forging letters: split 3,233 into 61 and 53, multiply 60 by 52 to get 3,120, undo the 17, and there is 2,753. It takes a schoolchild a few minutes.

The only thing standing between a verifier and forgery is the difficulty of that factoring step. Nothing else. Not secrecy, since every other number is published. Not a rule, since there is no authority enforcing anything. Just the arithmetic gap between multiplying and un-multiplying.

So the security of the whole arrangement is a bet on how big that gap is. Make the two primes 300 digits each, so that the clock has 617 digits on it, and the same attack still exists in principle and has never been carried out in practice. That is a real distinction and this book will not blur it: the attack is not impossible, it is unaffordable, and the price falls every year.

Why the mark goes on a fingerprint and not on the letter#

Two reasons, and they matter more than they look.

The first is size. The signing operation works on numbers smaller than the clock. Our clock has 3,233 positions, so the biggest thing we can sign directly is a number under 3,233, which is about two letters of text. A real clock is 617 digits wide, which is 256 characters. A contract is longer than that. Squashing the document into one fixed-size number first is what makes signing a document of any length possible at all.

The second is speed. The signing operation is arithmetic on enormous numbers, and enormous-number arithmetic is slow. Squashing a document is fast. Doing the slow operation once on a small squashed value, rather than repeatedly across a long document, is the difference between a system that works and one that does not.

The squashing recipe has to have one specific property, and it is the property everything else hangs from: it must be effectively impossible to find two different documents that squash to the same number. If somebody can find two, then a signature made on one is automatically a valid signature on the other, and they can get you to sign a harmless letter and walk away holding your signature on a different letter entirely. Our little 31-and-remainder recipe fails this test immediately; a real one is designed for years against exactly this attack, and we will see what happens when a real one fails.

The year it was said out loud, and the year it was said in secret#

In November 1976, Whitfield Diffie and Martin Hellman published a paper called “New Directions in Cryptography”. It opens by saying that they stand at the beginning of a revolution in cryptography, and for once that was not an overstatement. They described the two-part key, described what a signature made with the private part would mean, and gave a concrete method by which two people who had never met could agree on a shared secret over a line that everyone could listen to.

They did not, in that paper, give a working method for the padlock itself. They set the problem. A year later three researchers at the Massachusetts Institute of Technology, Ronald Rivest, Adi Shamir and Leonard Adleman, solved it with the multiply-two-primes construction we just worked through by hand, and published in early 1978.

There is a footnote to that history which is not a footnote. Inside the British government’s communications agency at Cheltenham, a man named James Ellis had proposed the same impossible-sounding idea in a classified report in January 1970, six years earlier. In 1973 a young mathematician there named Clifford Cocks worked out a concrete scheme, and it was essentially the multiply-two-primes construction. In 1974 a colleague, Malcolm Williamson, worked out the key-agreement method. None of it was published, none of it was used at scale, and none of it was admitted until December 1997. Ellis had died the month before. The idea was discovered twice, in secret and then in the open, and only the open one changed the world.

Where the plain version stops being true#

The padlock and the wax seal are two different machines#

The plain version told you that signing is the padlock run backwards: lock with the private key, unlock with the public one. Almost every introductory account says this. It is the single most repeated sentence about public key cryptography and it is wrong.

The honest version: encryption and signing are two distinct schemes that happen, in the special case of RSA only, to share an underlying arithmetic operation. They differ in what is fed into that operation, they differ in what security property they are trying to achieve, and outside RSA they do not share anything at all.

Take the third point first, because it settles the matter. The signature scheme in your phone, in your passkey, in your passport chip and in most certificates today is not RSA. It is ECDSA or its Edwards-curve cousin, and those schemes have no encryption operation. There is no “encrypt with the private key” available to describe, not because nobody has implemented it but because the mathematics does not offer one. A description of signing that cannot describe the signature scheme actually in use is not a simplification, it is a different subject.

The other two differences are described exactly in the technical half. The short form is that even in RSA, the thing fed into the operation when signing is padded to a different shape than the thing fed in when encrypting, deliberately, so that a signature can never be mistaken for a decryption or the other way round; and that the goal of an encryption scheme is that an eavesdropper learns nothing, while the goal of a signature scheme is that nobody can produce a new valid pair, which is not the same goal and is not achieved by the same means.

Nothing here is proved. It is only unbroken so far#

The plain version said that un-multiplying a huge number is horrible. It is horrible using every method anybody has published. It is not known to be horrible.

The honest version: there is no proof that factoring is hard. There is no proof that computing discrete logarithms is hard. There is no proof that any of the problems underneath modern public key cryptography require large effort, because proving such a thing would settle questions in computational complexity that have been open since the early 1970s. Every deployed public key system in the world rests on the observation that a large number of clever people have tried for decades and published nothing fast.

That is a much weaker statement than most people carry around, and it has a practical consequence: the numbers move. A key size that was respectable in 1998 is broken today, not because anybody proved anything new about the difficulty of the problem, but because computers got cheaper and the algorithms got better. The largest RSA modulus publicly factored is 829 bits, in February 2020. That is one quarter the size of the 2048-bit keys ordinarily used, which sounds comfortable, but the effort was about 2,700 core-years on ordinary rented computers, and rented computers are not scarce.

So every claim in this chapter of the form “an attacker cannot do X” should be read as “no public method exists by which an attacker could afford to do X, as of August 2026”. The book will keep putting the date in.

The wax analogy hides the fingerprint, and the fingerprint is where systems break#

In the plain version the seal was pressed onto the letter. In every real system the seal is pressed onto the fingerprint, and the security of the whole arrangement is no better than the fingerprinting recipe.

The honest version: a signature is a statement about a hash value, not about a document. The verifier recomputes the hash and compares. If an attacker can find two documents with the same hash, then any signature on the first is, mathematically and legally, a valid signature on the second, and no amount of key size helps. This is not a theoretical worry. It has happened twice in ways that mattered: a working forged certification authority certificate was built in December 2008 from an MD5 collision, and a piece of state-grade malware in 2012 forged a Microsoft code-signing certificate the same way. Both times the key was fine. The fingerprint was not.

The private key is a file, and files go where files go#

The plain version put the key in your pocket, which invites you to think of it as a possession like a house key.

The honest version: a private key is a number stored somewhere, and “somewhere” is usually a file on a disk, a row in a database, an environment variable in a container, or an entry in a cloud secrets manager. It can be copied perfectly, silently and instantly, and a copy is indistinguishable from the original. There is no equivalent of noticing that your keys are missing.

There is a good answer to this, which is to generate the key inside a chip that has no operation for exporting it, so that the number never exists outside the hardware. That is what a smartcard, a security key, a phone’s secure enclave and a hardware security module all are. It changes the property from “you must keep the file safe” to “you must keep the chip”, which is a far better property and is the reason passkeys are built the way they are. Chapter 23 handles that in full.

Some schemes need a fresh random number for every signature, and reuse is fatal#

The plain version made signing look deterministic: same key, same message, same signature. For our RSA example that is exactly true.

The honest version: the elliptic curve signature scheme in the widest use, ECDSA, requires a fresh secret random number for each signature, and if the same random number is ever used for two different messages, anybody who sees both signatures can compute the private key with school algebra. This is not a subtle failure mode; it is a total one. Sony shipped the PlayStation 3 with a fixed value in that position, and in December 2010 a group of researchers extracted the console’s master signing key and demonstrated it publicly. A study presented in August 2012 scanned the whole internet and found the private keys of 1.03 per cent of the SSH hosts it saw, from the same class of mistake.

The plain version’s picture of a key sitting quietly in your pocket does not prepare you for the fact that a signature scheme can hand over that key because a random number generator was not seeded properly at boot.

Bigger numbers are not stronger numbers, across families#

The plain version encourages a natural belief: 3,072 must be much stronger than 256.

The honest version: key sizes are only comparable inside one family. A 3072-bit RSA key and a 256-bit elliptic curve key are officially treated as providing the same strength, 128 bits, because the best known attack on each has a different shape. Against RSA the attacker uses a method whose cost grows in a way that lets very large keys still be attacked with realistic resources; against a well-chosen elliptic curve the best known attack is essentially exhaustive, costing roughly the square root of the number of points on the curve. Twelve times more key material buys RSA the same protection that the curve gets for free. Comparing the two numbers directly is like comparing a temperature in Celsius with one in Fahrenheit and concluding that the larger reading is hotter.

The expiry date is written down, and it is not the same date for everybody#

The plain version left the impression of a permanent solution.

The honest version: a sufficiently large quantum computer would break RSA and every elliptic curve scheme completely, not by making them slower to attack but by removing the difficulty entirely, using an algorithm published by Peter Shor in 1994. No such machine exists, and no credible person claims one is close. What is being argued about is when, and the argument has been settled for planning purposes by publishing dates rather than by winning it.

There is a further wrinkle that matters specifically for identity, and it is usually stated backwards. For encryption, the threat is retroactive: an adversary can record encrypted traffic today and decrypt it in twenty years, so anything with a twenty-year secrecy requirement is already at risk. For signatures, the threat is not retroactive in the same way. A signature verified today by a key that becomes breakable in 2040 was still genuine in 2026, provided you can show when it was made. What is at risk is anything that must remain verifiable far into the future, and anything with a very long-lived key, which in practice means the root keys of certificate authorities, document-signing keys and the keys burned into hardware at manufacture.

A key pair proves control of a key, and nothing else at all#

This is the most important limit and it is the one the padlock analogy hides completely.

The honest version: verifying a signature tells you that whoever produced it had the private key that matches this public key. It tells you nothing about who that is. It does not tell you their name, their nationality, whether they are a person, whether they consented, or whether the key was stolen last Tuesday. All of that has to be added on top by something else: a registration process that ties a name to a key, a certificate in which somebody vouches for that tie, a revocation system that lets the tie be cut, and a legal framework that says what any of it means. Volume III is entirely about that layer, starting with chapter 25.

A key pair is a very sharp tool for one job. It answers “is this the same party as before, and did they authorize this exact content”. It does not answer “who is this”, and every failure of identity systems in the second half of this book happens where somebody assumed it did.

The technical version#

The vocabulary, stated exactly#

A one-way function is a function that is cheap to evaluate and, on the evidence available, expensive to invert. A trapdoor one-way function is a one-way function with an extra piece of information, the trapdoor, whose possession makes inversion cheap again. Public key cryptography is the engineering of trapdoor one-way functions: the public key describes the forward direction, the private key is the trapdoor.

A digital signature scheme is three algorithms, not one. KeyGen produces a key pair. Sign takes a private key and a message and produces a signature. Verify takes a public key, a message and a signature and returns accept or reject. The security goal is stated formally as existential unforgeability under adaptive chosen-message attack, usually written EUF-CMA: an adversary who may ask the legitimate signer for signatures on any messages of their choosing must still be unable to produce any new valid message-signature pair, including a meaningless one. That last clause matters. It is not enough that the attacker cannot forge a signature on a message they choose; they must not be able to produce any new valid pair at all.

NIST divides the classical public key algorithms into three families, and the abbreviations appear throughout its documents. IFC is integer factorization cryptography, which in practice means RSA. FFC is finite field cryptography, which means Diffie-Hellman key agreement and the old DSA signature scheme working with exponents modulo a large prime. ECC is elliptic curve cryptography, which means ECDSA, EdDSA and elliptic curve Diffie-Hellman. These names are used in NIST Special Publication 800-57 Part 1 Revision 5 of May 2020, and if you know them the tables in that document become readable.

Security strength, expressed in bits, is the shorthand everything else hangs off. An algorithm with a key of a given size is said to provide s bits of security if the best known attack on it costs about 2 to the power s operations. It is a comparison against an idealized symmetric cipher, it is an estimate rather than a measurement, and it changes when somebody publishes a better attack. It is not the length of the key.

What Diffie and Hellman actually published in 1976#

“New Directions in Cryptography” appeared in the IEEE Transactions on Information Theory, volume IT-22, number 6, November 1976, pages 644 to 654. Its first sentence is “We stand today on the brink of a revolution in cryptography.”

The paper did four things. It defined the idea of a public key cryptosystem, in which the enciphering key can be made public without compromising the deciphering key. It defined the idea of a one-way authentication, that is a digital signature, and observed that a public key system with the right structure would provide one. It gave a concrete, working method for two parties to agree on a shared secret over a channel that an eavesdropper can read in full. And it discussed one-way functions for login password storage, which is the subject of chapter 14 in this book.

What it did not do is give a working public key cryptosystem or a working signature scheme. Those were posed as open problems. The concrete contribution was the key agreement, and it is worth writing out because the arithmetic is the same shape as everything that follows.

Two parties agree in public on a prime and a base. Take the prime 23 and the base 5. One party picks a secret number, 6, and publishes 5 to the power 6 modulo 23, which is 8. The other picks a secret number, 15, and publishes 5 to the power 15 modulo 23, which is 19. Each raises the number they received to their own secret: the first computes 19 to the power 6 modulo 23, the second computes 8 to the power 15 modulo 23, and both get 2. An eavesdropper who saw 23, 5, 8 and 19 must find an exponent from a power, which is the discrete logarithm problem.

public   p = 23    g = 5
Alice    secret a = 6    sends g^a mod p = 8
Bob      secret b = 15   sends g^b mod p = 19
Alice    19^6  mod 23 = 2
Bob       8^15 mod 23 = 2      shared secret = 2

The result is a shared secret and nothing more. Unauthenticated Diffie-Hellman gives both parties a key and gives neither of them any assurance about who is at the other end, so an attacker sitting in the middle can run the exchange twice, once with each side, and read everything. The fix for that is a signature over the exchange, which is why key agreement and signatures always travel together, and why this chapter is about the second one.

Two pieces of history sit either side of the paper. Ralph Merkle had submitted a paper describing a related idea, now called Merkle’s puzzles, in 1975; it appeared in Communications of the ACM volume 21, number 4, April 1978, pages 294 to 299, after the Diffie-Hellman paper it predated. And inside the British government’s communications organization at Cheltenham, James Ellis had written a classified report titled “The Possibility of Secure Non-Secret Digital Encryption” in January 1970, Clifford Cocks had found the factoring-based scheme in 1973, and Malcolm Williamson had found the key agreement in 1974. That work was declassified in December 1997, and Cocks described it publicly in a talk on 18 December 1997.

RSA, exactly#

Rivest, Shamir and Adleman published “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” in Communications of the ACM volume 21, number 2, February 1978, pages 120 to 126. The paper was received on 4 April 1977 and revised on 1 September 1977, which is why the scheme is dated 1977 in some accounts and 1978 in others. Their own worked example in the paper uses the primes 47 and 59, giving a modulus of 2,773.

Key generation, as specified today in RFC 8017 and referenced by FIPS 186-5 of 3 February 2023, runs as follows.

1. Generate two distinct large primes p and q of about half the intended modulus size each, tested for primality to a stated error bound.
2. Compute the modulus n as p times q. The bit length of n is the key size: a 2048-bit RSA key has a 2048-bit n, which is 256 bytes, which is 617 decimal digits.
3. Compute the order, either as Euler’s totient, that is p minus 1 times q minus 1, or as the least common multiple of those two quantities, which is what RFC 8017 uses and which yields a smaller private exponent.
4. Choose a public exponent e coprime to that order. Essentially every key in the world uses 65537, which is 2 to the power 16 plus 1: it is prime, it has only two bits set so exponentiation is fast, and it is large enough to avoid the small-exponent attacks that plagued the value 3.
5. Compute d as the multiplicative inverse of e modulo the order.

The public key is the pair n and e. The private key is d, but a real private key file also stores p, q and three derived values, so that signing can be done with the Chinese remainder theorem in two half-size exponentiations rather than one full-size one, which is roughly four times faster. Those values are named dP, dQ and qInv in RFC 8017. Their presence is why an RSA private key file is more than twice the size of the public key, and their presence is also a hazard: a single computational fault during a CRT signing operation leaks the factorization of n, a result published by Dan Boneh, Richard DeMillo and Richard Lipton in 1997, which is why hardware signers verify their own signatures before releasing them.

Signing is s equals the encoded message raised to the power d modulo n. Verification is the encoded message recovered as s raised to the power e modulo n, followed by a check of the encoding. Our worked example from the plain half, in exact terms:

p = 61  q = 53          n = 3233   (11 bits)
phi = 60 * 52 = 3120    e = 17     d = 2753
because 17 * 2753 = 46801 = 15 * 3120 + 1

H(m)   = 2244           (toy hash of "SHIKHAR")
sign   s = 2244^2753 mod 3233 = 2942
verify     2942^17   mod 3233 = 2244  -> equals H(m)
tamper H("SHIKHAB") = 2228           -> reject

Everything about that example is real except the size and the hash. A production key replaces 3,233 with a 617-digit number and replaces the toy hash with SHA-256, and the padding step described next is not optional.

The padding is the algorithm, not a detail#

A bare RSA operation on a raw hash is insecure and has been known to be since the beginning. What is actually signed is an encoded message, and RFC 8017, which is PKCS number 1 version 2.2, published in November 2016, defines two encodings.

The older is EMSA-PKCS1-v1_5. The encoded message is exactly as long as the modulus and is laid out as a zero byte, then the byte 0x01, then a run of 0xFF bytes long enough to fill the space, then a zero byte, then a DER structure containing an identifier for the hash function and the hash itself. Here is the actual encoded block recovered from a real 2048-bit RSA signature over a 38-byte message, produced with OpenSSL 3.0.13 in August 2026 and unwrapped with the public key:

00 01 ff ff ff ff ff ff ff ff ff ff ff ff ff ff
   ... 202 bytes of ff in total ...
ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 00
30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05
00 04 20
bb 96 d0 88 32 91 cc ef a8 8f b7 df 8f cd 97 e3
c6 23 54 4b a4 6f d4 43 b7 58 2e c7 cb 0b 43 7a

The nineteen bytes beginning 30 31 30 0d are the DER encoding that says “what follows is a SHA-256 digest”; they are identical in every PKCS number 1 version 1.5 signature that uses SHA-256, which is why implementers often hard-code them. The last thirty-two bytes are the SHA-256 hash of the message. The arithmetic is 256 bytes wide, the hash is 32 bytes, and the other 224 bytes exist purely to make the number the right size and the right shape.

The newer encoding is RSASSA-PSS, the probabilistic signature scheme. It mixes the hash with a random salt, expands it with a mask generation function, and produces a different encoded message every time even for the same key and the same message. RFC 8017 states plainly that RSASSA-PSS is required in new applications and that RSASSA-PKCS1-v1_5 is included only for compatibility with existing applications. Most of the web ignores this: RS256, the COSE and JOSE name for PKCS number 1 version 1.5 with SHA-256, remains far more common than PS256, its PSS equivalent. That is a convention, not a standard, and it is one the standards have been trying to end for a decade.

Why “signing is encrypting with the private key” is wrong#

Three separate reasons, in increasing order of severity.

The first is that the shapes differ on purpose. Compare the signature encoding above with the encryption encoding in the same document. For encryption, EME-PKCS1-v1_5 produces a zero byte, then the byte 0x02, then a run of random nonzero bytes, then a zero byte, then the message. For signing, EMSA-PKCS1-v1_5 produces a zero byte, then the byte 0x01, then a run of 0xFF bytes, then a zero byte, then the DER-wrapped hash. The second byte differs, 0x01 against 0x02, and the filler differs, fixed against random. That separation is deliberate: it means a decryption result can never be mistaken for a signature and a signature can never be mistaken for a decryption, even though both are exponentiations modulo the same n. Any description that says the two operations are the same has thrown away the byte that keeps them apart.

The second is that the security goals differ. An encryption scheme aims at indistinguishability: an adversary must learn nothing about the plaintext. A signature scheme aims at unforgeability: an adversary must be unable to produce a new valid pair. Neither goal implies the other, and a construction can meet one while failing the other. RSA-PSS has a security proof as a signature scheme that has nothing to do with any encryption property.

The third and decisive reason is that most modern signature schemes have no encryption operation at all. ECDSA, EdDSA, the old DSA, and both post-quantum signature standards published in 2024 are signature-only constructions. There is no private key operation that could be called encryption because there is no plaintext-in, ciphertext-out map defined in the scheme. When a WebAuthn authenticator signs with ES256, or an SSH client signs with an Ed25519 key, nothing is being encrypted anywhere in the operation. If your mental model of signing is “encrypt with the private key”, it explains none of the signatures your systems actually produce.

The cost of believing the folklore is concrete. If you think verification means “decrypt the signature and see if the hash is in there”, you write a verifier that searches the recovered block for the hash rather than reconstructing the expected block byte for byte and comparing. Daniel Bleichenbacher demonstrated at the CRYPTO conference rump session in August 2006 that such a verifier accepts forged signatures for keys with public exponent 3, with no knowledge of the private key at all, because the attacker can construct a perfect cube whose top bytes look like valid padding and whose lower bytes are junk the lazy verifier never inspects. The bug kept coming back: a 2019 study presented at Black Hat USA, “A Decade After Bleichenbacher '06, RSA Signature Forgery Still Works”, found current implementations still failing, and the same flaw was found in the widely used python-rsa library in 2016. The correct rule is that a PKCS number 1 version 1.5 verifier must rebuild the entire expected encoded block from the message and compare all 256 bytes.

Hash-then-sign, and the weight the hash is carrying#

Every deployed signature scheme signs a hash, not a message. The pattern is called hash-then-sign and it has a precise security requirement attached.

The requirement is collision resistance: it must be infeasible to find any two distinct messages m1 and m2 with the same hash. It is not enough for the hash to be one-way. The reason is the definition of forgery given earlier. The attacker is allowed to choose the messages they ask you to sign. If they can construct a pair that collides, they bring you the innocent one, obtain your signature on its hash, and then attach that same signature to the guilty one. The verifier hashes the guilty document, gets the same value, checks it against the signature, and accepts. Nothing in the signature scheme has been broken. The key is untouched.

attacker finds  m1, m2   with  H(m1) = H(m2)
you sign        m1       ->  s = Sign(sk, H(m1))
attacker ships  m2, s
verifier        H(m2) = H(m1)  ->  accept

the signature is genuine, the document is not

This is the most under-appreciated dependency in applied cryptography, and it has produced two of its most instructive failures.

On 30 December 2008, at the 25th Chaos Communication Congress, Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger presented “MD5 considered harmful today”, in which they obtained a legitimate certificate from a commercial certification authority that still signed with MD5, and used a chosen-prefix collision computed on a cluster of PlayStation 3 consoles to turn it into a working certification authority certificate that could issue certificates for any website in the world. The authority’s key was never touched.

In June 2012 the same weakness was used in the wild. The Flame malware carried a certificate that chained to Microsoft, obtained by a chosen-prefix MD5 collision against a certificate issued by Microsoft’s Terminal Server Licensing Service, and used it to sign components so that they appeared to be genuine Microsoft code. Microsoft published an emergency advisory and revoked the affected authorities, and its Security Research Centre published a technical account under the title “Flame malware collision attack explained” in June 2012. The collision work in Flame was, in the assessment of the researchers who analysed it, better than anything then in the public literature.

SHA-1 went the same way, slower. On 23 February 2017 researchers at CWI Amsterdam and Google, Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov, published the first SHA-1 collision under the name SHAttered, at a cost they gave as roughly nine quintillion SHA-1 computations, about 6,500 CPU-years and 110 GPU-years. On 15 December 2022 NIST announced that it would transition away from SHA-1 for applying cryptographic protection in all applications by 31 December 2030.

The practical rule follows directly. Sign with SHA-256 or better. Treat a system that still verifies MD5 or SHA-1 signatures as a system with no signatures, because the strength of a hash-then-sign scheme is the minimum of the key strength and the collision resistance of the hash, not the maximum.

Elliptic curves, and why the keys can be so much smaller#

An elliptic curve over a prime field is the set of points satisfying an equation of the form y squared equals x cubed plus a times x plus b, with all arithmetic done modulo a prime p, plus one extra point called the point at infinity. What makes it useful is that the points form a group: there is a rule for adding two points to get a third point on the same curve. Geometrically, the rule is to draw the line through the two points, find the third place it meets the curve, and reflect that in the horizontal axis. Algebraically, it is a handful of multiplications and one modular inversion.

Take the curve given by y squared equals x cubed plus 2x plus 2 modulo 17, with the starting point G at coordinates (5, 1). Adding G to itself repeatedly walks through the whole group and comes back to the start after 19 steps:

 1G (5,1)    2G (6,3)    3G (10,6)   4G (3,1)
 5G (9,16)   6G (16,13)  7G (0,6)    8G (13,7)
 9G (7,6)   10G (7,11)  11G (13,10) 12G (0,11)
13G (16,4)  14G (9,1)   15G (3,16)  16G (10,11)
17G (6,14)  18G (5,16)  19G = point at infinity

Scalar multiplication, writing kG for G added to itself k times, is the one-way function. Computing 7G from G is fast even when k has 256 bits, because doubling and adding gets there in a few hundred steps. Recovering k from G and 7G is the elliptic curve discrete logarithm problem, and this is where the size advantage comes from.

Against RSA, the attacker has the number field sieve, an algorithm whose running time is sub-exponential in the size of the modulus. Sub-exponential means the cost grows more slowly than doubling the key would suggest, so RSA keys have to grow disproportionately to stay ahead. Against a properly chosen elliptic curve, no such algorithm is known. The index-calculus techniques that make the number field sieve work depend on being able to factor group elements into small pieces, and a general elliptic curve group offers nothing to factor. The best known attack is therefore generic: Pollard’s rho method, whose cost is about the square root of the number of points on the curve. A curve with about 2 to the power 256 points gives about 2 to the power 128 work, and that is the whole explanation for the rule of thumb that an elliptic curve key needs twice as many bits as the security strength it provides.

The public record shows the gap plainly. These are the largest publicly completed computations of each kind:

The RSA-250 factorization by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thome and Paul Zimmermann took roughly 2,700 core-years, quoted against Intel Xeon Gold 6130 processors at 2.1 GHz. The 112-bit elliptic curve record, on the curve named secp112r1, was set in July 2009 by Joppe Bos, Marcelo Kaihara, Thorsten Kleinjung, Arjen Lenstra and Peter Montgomery using a cluster of more than 200 PlayStation 3 consoles for about six months. The binary-curve record of December 2016, by Daniel Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe and Ralf Zimmermann, used between 64 and 576 field-programmable gate arrays for six months. Nobody has published a break of anything close to a 256-bit curve, and the distance from 117 bits to 256 bits is not a matter of buying more machines.

ECDSA, and the one number that destroys it#

The Elliptic Curve Digital Signature Algorithm is specified in FIPS 186-5 section 6. Its domain parameters are the prime p, the curve coefficients a and b, a base point G, the order n of G, and the cofactor h. A private key d is an integer from 1 to n minus 1. The public key Q is dG.

To sign a message, compute the hash and take its leftmost bits as an integer e. Choose a per-signature secret k at random from 1 to n minus 1. Compute the point kG and take its x coordinate modulo n as r. Compute s as the inverse of k modulo n, multiplied by the quantity e plus r times d, modulo n. The signature is the pair r and s.

To verify, compute w as the inverse of s modulo n, then u1 as e times w and u2 as r times w, both modulo n. Compute the point u1 G plus u2 Q, take its x coordinate modulo n, and accept if it equals r.

On the toy curve above, with n equal to 19, a private key of 7 and therefore a public key at (0, 6):

private d = 7        public Q = 7G = (0,6)
hash e = 11          nonce k = 5

kG = 5G = (9,16)     r = 9
s  = 5^-1 (11 + 9*7) mod 19 = 4 * 74 mod 19 = 11
signature = (9, 11)

verify: w = 11^-1 mod 19 = 7
        u1 = 11*7 mod 19 = 1   u2 = 9*7 mod 19 = 6
        1G + 6Q = (9,16)       x mod 19 = 9 = r   accept

Now the failure. The value k must be secret, unpredictable and never reused. If the same k is used for two different messages under the same key, the two signatures share the same r, and the private key falls out immediately. With the same key and the same k of 5, signing a second hash of 4 gives s equal to 2:

sig 1: e1 = 11   r = 9   s1 = 11
sig 2: e2 =  4   r = 9   s2 =  2

k = (e1 - e2) / (s1 - s2) mod 19 = 7/9 mod 19 = 5
d = (s1*k - e1) / r      mod 19 = (55-11)/9   = 7

That is not a toy weakness scaled down. It is the exact arithmetic that recovered Sony’s PlayStation 3 master signing key, which the group fail0verflow demonstrated at the 27th Chaos Communication Congress in December 2010, in a talk whose subtitle was “PS3 Epic Fail”. Sony’s implementation used a constant where a random number belonged. The same class of failure was found at internet scale in the study “Mining Your Ps and Qs” by Nadia Heninger, Zakir Durumeric, Eric Wustrow and J. Alex Halderman, presented at USENIX Security in August 2012: they computed the private keys of 0.50 per cent of the TLS hosts and 0.03 per cent of the SSH hosts they scanned from shared RSA prime factors, and the DSA private keys of 1.03 per cent of SSH hosts from repeated signature randomness, almost all of it on embedded devices generating keys at first boot before any entropy was available.

There are two fixes and both are in use. RFC 6979, published in August 2013, derives k deterministically from the private key and the message hash using HMAC, so that no randomness is needed at signing time at all; FIPS 186-5 approves this as deterministic ECDSA in section 6.3.2. EdDSA, described next, builds the same idea into the scheme so that it cannot be got wrong.

One more ECDSA property is worth knowing because it surprises people: signatures are malleable. If the pair r and s verifies, so does the pair r and n minus s, because the x coordinate does not distinguish a point from its reflection. Two distinct byte strings are therefore both valid signatures on the same message by the same key. Systems that use a signature’s bytes as a unique identifier, as early Bitcoin did, have to add a rule requiring the smaller of the two values.

P-256, Curve25519, Ed25519, Ed448: which is which#

Four names cause more confusion than the rest of this subject put together, mostly because people use one of them for three different things.

P-256 is a NIST curve in short Weierstrass form over a 256-bit prime. It also answers to secp256r1 in the SEC standards and to prime256v1 in OpenSSL, and all three names denote the same curve. It first appeared in FIPS 186-2 in 2000, and its current definition for United States federal use is in NIST Special Publication 800-186 of 3 February 2023. It is used with ECDSA. It is the curve behind the COSE algorithm ES256, which is the algorithm a WebAuthn authenticator can be relied on to support, and behind a large share of the certificates on the public web.

Curve25519 is a Montgomery-form curve over the prime 2 to the power 255 minus 19, designed by Daniel Bernstein and published at the Public Key Cryptography conference in 2006. Its coefficient is 486662 and its cofactor is 8. It is a key agreement curve. The function built on it is called X25519 and is defined in RFC 7748 of January 2016. It does not sign anything.

Ed25519 is a signature scheme. It uses EdDSA on edwards25519, a curve birationally equivalent to Curve25519, meaning the same mathematical object in different coordinates. It was published as “High-speed high-security signatures” by Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang at CHES in 2011, and standardized in RFC 8032 of January 2017. A public key is 32 bytes and a signature is 64 bytes.

Ed448 is the same idea at a higher strength, over the prime 2 to the power 448 minus 2 to the power 224 minus 1, with a 57-byte public key and a 114-byte signature. Its key agreement counterpart is X448. RFC 7748 puts Curve25519 at roughly the 128-bit security level and Curve448 at roughly the 224-bit level.

EdDSA differs from ECDSA in three ways that all remove a foot-gun. The per-signature secret is derived deterministically from the private key and the message by hashing, so there is no random number generator to fail. The scheme is defined with a specific hash, SHA-512 for Ed25519, so there is no negotiation of hash strength. And the encoding is fixed-length and unambiguous, so there is no DER parsing in the verification path. The pure variant hashes the message twice, once inside the nonce derivation and once inside the challenge, which means a signer must have the whole message before it can begin; RFC 8032 defines prehashed variants, Ed25519ph and Ed448ph, for streaming cases, and FIPS 186-5 approves that as HashEdDSA in section 7.8.

FIPS 186-5, published on 3 February 2023, is the document that changed the landscape for federal use. It approves RSA by reference to RFC 8017, specifies ECDSA in section 6 including the deterministic variant, and specifies EdDSA in section 7 with the edwards25519 and edwards448 curves. It also removes DSA: the standard states that DSA is no longer specified in it and may only be used to verify previously generated signatures.

There is a genuine expert disagreement about the NIST prime curves, and it should be stated in one line rather than avoided. The coefficients of P-256 were produced by hashing an unexplained seed value supplied by the National Security Agency, so nobody outside can demonstrate that the seed was not searched for a curve with a hidden weakness; one camp holds that since no weakness has ever been shown in more than twenty-five years, the curve is fine and the ubiquitous hardware support settles it, while the other holds that a parameter nobody can justify has no place in a system whose whole value is public verifiability, and prefers the rigid, fully explained parameters of Curve25519. Both camps deploy both curves in practice, because interoperability decides.

For identity work the practical positions as of August 2026 are these. Certificates on the public web are overwhelmingly RSA-2048 and P-256. WebAuthn and passkey authenticators must support ES256 on P-256 and may support EdDSA; chapter 23 covers the ceremony in detail. OpenSSH has supported Ed25519 host and user keys and Curve25519 key exchange since version 6.5 of 30 January 2014, and Ed25519 is now the ordinary default. TLS 1.3 key exchange is usually X25519. Machine-readable travel documents and national identity cards commonly use P-256 or the Brainpool curves.

Key sizes and equivalent security strengths, with the dates attached#

NIST Special Publication 800-57 Part 1 Revision 5, published in May 2020, gives the comparison table that everything else refers to. This is table 2 from section 5.6.1.1, where L is the size of the prime field, N is the size of the subgroup, and f is the size of the elliptic curve key:

Two readings of that table are worth having. The first is the one everybody quotes: RSA-3072 and a 256-bit curve are both 128-bit strength, so the curve does the same job with one twelfth of the key material. The second is less often noticed: to reach 256-bit strength, RSA needs a 15360-bit modulus, which is nearly two kilobytes of key and a signing operation so slow that essentially nobody does it. Above 128 bits of strength, RSA stops being practical, and this is why the high end of the classical world is entirely elliptic.

The same document, in table 4 of section 5.6.3, attaches dates. For applying cryptographic protection to data:

Processing data that was already protected at those strengths is marked legacy use rather than disallowed, which is the standard’s way of saying that you may still verify an old signature after you may no longer make a new one. Read together with table 2, this is the sentence that matters for planning: RSA-2048 and P-256 both sit at 112 bits and 128 bits respectively, so RSA-2048 signing becomes disallowed for United States federal use in 2031, while P-256 does not.

A separate draft moves the whole picture. NIST Internal Report 8547, “Transition to Post-Quantum Cryptography Standards”, was released as an initial public draft on 12 November 2024, with comments closing on 10 January 2025, and as of August 2026 it has not been finalized. Its tables propose that RSA and ECDSA at 112 bits of strength be deprecated after 2030 and disallowed after 2035, and that RSA and ECDSA at 128 bits of strength and above be disallowed after 2035 outright. If that draft is adopted as written, every classical signature algorithm in this chapter has a published end date of 2035 for United States federal use.

Performance is the other axis, and it does not go the way people expect. These are measurements taken on 18 August 2026 on a single core of an Intel Xeon processor at 2.10 GHz using OpenSSL 3.0.13. They are an implementation detail of one machine, not a property of the algorithms, but the ratios between them hold broadly:

RSA verifies about eighteen times faster than it signs, because verification is an exponentiation by 65537 while signing is an exponentiation by a 2048-bit secret. Elliptic curve schemes are the other way round, signing about three times faster than they verify. That asymmetry drives real design decisions: certificate chains, which are signed once and verified billions of times, historically favoured RSA, while authenticators in a phone, which sign constantly on a small battery, favour elliptic curves.

Sizes on the wire, measured from real keys and signatures generated with OpenSSL on the same day. The first three are the DER-encoded SubjectPublicKeyInfo structure as it would appear inside a certificate, so they include the algorithm identifier as well as the key:

The ECDSA signature size varies because it is a DER SEQUENCE of two INTEGERs whose lengths depend on whether the leading bit is set; the raw pair is always 64 bytes, and the sample measured here encoded to 71.

Post-quantum signatures: what exists and what does not#

Peter Shor published an algorithm in 1994 that factors integers and computes discrete logarithms in polynomial time on a quantum computer. It applies to RSA, to finite-field Diffie-Hellman and DSA, and to every elliptic curve scheme in this chapter, and it does not merely weaken them; it removes the hard problem. There is no key size that escapes it, because doubling an elliptic curve key doubles the classical attack cost by squaring but leaves Shor’s algorithm facing a linearly larger problem.

The machine does not exist. What exists is a falling estimate of what it would take. Craig Gidney and Martin Ekera estimated in 2019 that factoring a 2048-bit RSA modulus would need about 20 million noisy qubits running for eight hours; Gidney published a revised estimate on 21 May 2025 putting it under one million noisy qubits running for under a week. That is a twentyfold reduction in the hardware requirement in six years, achieved entirely by better algorithms and error-correction techniques rather than by better hardware, and it is the reason standards bodies stopped waiting.

On 13 August 2024 NIST published three post-quantum standards. Two of them are signature schemes.

FIPS 204, the Module-Lattice-Based Digital Signature Standard, specifies ML-DSA, derived from the CRYSTALS-Dilithium submission. It has three parameter sets:

Their private keys are 2,560, 4,032 and 4,896 bytes respectively, and they claim NIST security categories 2, 3 and 5. The standard also defines HashML-DSA, a pre-hash variant for signing large messages, and recommends that a given key pair be used for one variant or the other but not both.

FIPS 205, the Stateless Hash-Based Digital Signature Standard, specifies SLH-DSA, derived from SPHINCS+. Its security rests only on the properties of a hash function, which makes it the conservative choice: if lattice problems turn out to be easier than believed, SLH-DSA is unaffected. The price is size and speed. There are twelve parameter sets, six security and hash choices each in a SHA2 and a SHAKE flavour:

The s and f suffixes mean small and fast: the s variants produce smaller signatures and sign more slowly, the f variants the reverse. A 7,856-byte signature is about thirty times the size of an RSA-2048 signature and about one hundred and twenty times the size of an Ed25519 signature, which is why SLH-DSA is proposed for firmware and root-of-trust signing, where a signature is made rarely and lives for decades, rather than for a login.

Three things are worth stating plainly about the current position, all as of August 2026.

First, the third signature standard is still missing. FIPS 206, which will specify FN-DSA based on the Falcon submission and which offers much smaller signatures than ML-DSA, has not been published, and NIST’s own publication database lists no FIPS 206 in either draft or final form. NIST submitted a draft for approval on 28 August 2025, and public statements point at publication in late 2026 or 2027. Anything you read that describes FN-DSA as a standard is describing something that does not yet exist.

Second, there are two older hash-based signature standards that are stateful and are already approved: LMS and XMSS, specified for United States federal use in NIST Special Publication 800-208. They are excellent for firmware signing and dangerous everywhere else, because signing twice with the same state destroys their security, and keeping state correctly across backups and restores is a problem most systems fail.

Third, the ecosystem work is real but young. The COSE and JOSE registrations for ML-DSA were published as RFC 9964 in May 2026, giving the algorithm identifiers -48, -49 and -50 for ML-DSA-44, ML-DSA-65 and ML-DSA-87, alongside the long-established -7 for ES256, -8 for EdDSA, -37 for PS256 and -257 for RS256. The National Security Agency’s Commercial National Security Algorithm Suite 2.0, announced on 7 September 2022, names the post-quantum algorithms as the future requirement for United States national security systems.

The clock for signatures is different from the clock for encryption, and confusing the two produces bad decisions. Encrypted traffic captured today can be decrypted later, so a twenty-year secret sent today is already exposed to a machine built in 2040. A signature is not retroactively forgeable in the same way: an attacker with a quantum computer in 2040 cannot go back and make you have signed something in 2026. What they can do is forge new signatures under any long-lived key that is still trusted, which means the urgent cases in identity are exactly the long-lived ones: certification authority root keys with twenty-year validity, document-signing keys for passports whose chips will be read for a decade, and manufacturer keys burned into hardware at the factory. Login signatures made by a passkey are the least urgent thing in the estate.

One signature, end to end, with real bytes#

Here is the whole operation as it happens, with nothing hidden.

        signer                          verifier
   +-------------+                 +--------------+
   | private key |                 |  public key  |
   +-------------+                 +--------------+
          |                                |
      message m ------------ m ----------> |
          |                                |
     h = H(m)                         h' = H(m)
          |                                |
   s = Sign(priv, h) ------- s ----------> |
                                           |
                                  Verify(pub, h', s)
                                           |
                                    accept or reject

The commands below were run on 18 August 2026 with OpenSSL 3.0.13. The message is a 38-byte instruction, deliberately banal, because the interesting part is what happens when one character changes:

openssl genpkey -algorithm EC \
    -pkeyopt ec_paramgen_curve:P-256 -out p256.key
openssl pkey -in p256.key -pubout -out p256.pub
printf 'transfer 250000 INR to account 91 4402' > msg.txt
openssl dgst -sha256 -sign p256.key -out sig msg.txt
openssl dgst -sha256 -verify p256.pub -signature sig msg.txt

The last command prints “Verified OK”. The SHA-256 hash of that message begins bb96d088. Change the final digit of the account number from 2 to 3 and the hash begins 8d42339f, a completely unrelated value, and the same verification command prints “Verification failure”. The signature file itself decodes as two integers:

SEQUENCE (69 bytes)
  INTEGER r  710e41470cf3839b8363750d0d3ba0d2
             95bef6c63f9f45f50c3cbacba2187131
  INTEGER s  e3dca9aedb6993f0969fda1df072e703
             8d24f11c763318ede9f48a3cc18a00a0

That is the whole of what travels: two 32-byte numbers, wrapped in eleven bytes of structure. The verifier already had the public key. Nothing secret moved in either direction at any point, and the verifier is now able to prove to a third party that the holder of that key authorized those exact 38 bytes, which is the property the rest of this book is built on.

One last practical point, because it decides whether any of the above is worth anything. The private key in that example is a file called p256.key sitting in a directory, readable by any process running as the same user. In a real identity system the key should be generated inside hardware that has no operation for exporting it: a Trusted Platform Module, a phone’s secure element, a smartcard, a FIDO security key or a hardware security module. The public key comes out, the signature comes out, the private key never does. That single architectural decision, and not the choice of curve, is what separates a credential that can be stolen remotely from one that cannot. Chapter 23 shows what it looks like when it is done properly.

21.98 Common wrong ideas#

Wrong: Signing is just encrypting with the private key. Right: They are different schemes with different inputs and different goals; even in RSA, where both are exponentiations modulo the same n, the encoding for signing under RFC 8017 begins with the bytes 00 01 followed by 0xFF filler while the encoding for encryption begins 00 02 followed by random nonzero filler, and outside RSA the question does not arise because ECDSA, EdDSA, ML-DSA and SLH-DSA have no encryption operation at all.

Wrong: The public key encrypts and the private key decrypts, so verification is decryption. Right: Verification is a recomputation and a comparison, not a recovery; a correct PKCS number 1 version 1.5 verifier rebuilds the entire 256-byte encoded block from the message and compares every byte, and the verifiers that instead searched the recovered block for a hash are exactly the ones Daniel Bleichenbacher forged signatures against in August 2006 and that were still being found broken in a Black Hat USA study in 2019.

Wrong: A 3072-bit RSA key is much stronger than a 256-bit elliptic curve key. Right: NIST Special Publication 800-57 Part 1 Revision 5 table 2 places both at 128 bits of security strength, because the number field sieve gives a sub-exponential attack on RSA while the best known attack on a well-chosen curve is generic and costs about the square root of the group order, so key sizes are only comparable within one family.

Wrong: RSA-2048 is fine and always will be. Right: It provides 112 bits of strength, table 4 of the same publication makes 112-bit strength unacceptable for applying protection from 2031, and the draft NIST Internal Report 8547 of 12 November 2024 proposes deprecating it after 2030 and disallowing it after 2035, so a key issued today with a ten-year life already outlives its approval.

Wrong: The hash before signing is only there to make signing faster. Right: It is load-bearing security, because a signature is a statement about a hash value, and anyone who can find two documents with the same hash converts your signature on the innocent one into a valid signature on the other, which is exactly how a rogue certification authority certificate was built from MD5 on 30 December 2008 and how the Flame malware forged Microsoft code signing in June 2012.

Wrong: My signing is safe because my key is long enough. Right: Key length protects against the mathematics and nothing else, and real keys are lost to the surrounding engineering: ECDSA leaks the whole private key if the per-signature secret repeats, which is how Sony’s PlayStation 3 master key was recovered in December 2010, and the 2012 study “Mining Your Ps and Qs” computed the private keys of 0.50 per cent of the TLS hosts on the internet from weak key generation entropy.

Wrong: A valid signature tells me who signed. Right: It tells you that the holder of one specific private key authorized those exact bytes, and nothing whatever about the name, nationality, consent or continued control of the holder; binding a key to a person requires registration, certification and revocation machinery, which is the subject of Volume III from chapter 25 onward.

Wrong: Curve25519 and Ed25519 are two names for the same thing. Right: Curve25519 is a Montgomery curve used only for key agreement through the X25519 function of RFC 7748, while Ed25519 is a signature scheme using EdDSA on edwards25519, a birationally equivalent curve in Edwards form, defined in RFC 8032 and approved for federal use in FIPS 186-5 section 7.

Wrong: A quantum computer will retroactively forge my old signatures, so signatures are the urgent case. Right: The retroactive threat belongs to encryption, where captured traffic can be decrypted later, whereas a quantum adversary cannot make you have signed something in the past; the urgent signature cases are the long-lived keys still trusted in 2035, meaning certification authority roots, document-signing keys and keys burned into hardware.

Wrong: Post-quantum signing is standardized, so I can pick Falcon. Right: FIPS 204 for ML-DSA and FIPS 205 for SLH-DSA were published on 13 August 2024 and are the only finished post-quantum signature standards, while FIPS 206 for FN-DSA, the Falcon-based scheme, appears nowhere in the NIST publication database in draft or final form as of August 2026, with a draft submitted for approval on 28 August 2025 and publication expected no earlier than late 2026.

21.99 Chapter summary in 20 lines#

1. A key pair is two matched numbers generated together, of which one is published without harm and the other is never transmitted, and that asymmetry is what lets a stranger verify you without holding your secret.
2. The public half describes a function that is cheap to run forwards, and the private half is the trapdoor that makes running it backwards cheap for exactly one person.
3. Diffie and Hellman published “New Directions in Cryptography” in the IEEE Transactions on Information Theory volume IT-22 number 6 in November 1976, defining public key cryptosystems and digital signatures and giving a working key agreement but not a working signature scheme.
4. James Ellis proposed the same idea in a classified GCHQ report in January 1970, Clifford Cocks found the factoring construction in 1973 and Malcolm Williamson the key agreement in 1974, and none of it was admitted until December 1997.
5. Rivest, Shamir and Adleman supplied the missing construction in a paper received on 4 April 1977 and published in Communications of the ACM volume 21 number 2 in February 1978.
6. RSA key generation multiplies two primes to make the modulus, chooses a public exponent that is almost always 65537, and derives the private exponent as its inverse modulo the order of the group.
7. With the primes 61 and 53 the modulus is 3,233, the public exponent 17 gives the private exponent 2,753, and a message hashing to 2,244 signs to 2,942 and verifies back to 2,244 while a one-letter change gives 2,228 and is rejected.
8. What is actually signed is never the raw hash but an encoded block, and RFC 8017 requires RSASSA-PSS for new applications while permitting RSASSA-PKCS1-v1_5 only for compatibility.
9. Signing is not encrypting with the private key, because the encodings differ deliberately, the security goals differ, and most modern signature schemes have no encryption operation to speak of.
10. Every deployed scheme signs a hash, and the collision resistance of that hash is load-bearing, since a colliding pair turns a genuine signature on one document into a genuine signature on another.
11. The MD5 rogue certification authority of 30 December 2008 and the Flame malware of June 2012 both forged trusted certificates without touching a private key, and the first SHA-1 collision was published on 23 February 2017.
12. An elliptic curve key can be far shorter than an RSA key because no index-calculus attack is known against a general curve group, leaving only generic attacks that cost about the square root of the group order.
13. The largest RSA modulus publicly factored is 829 bits, on 28 February 2020 at a cost of roughly 2,700 core-years, while the largest prime-field elliptic curve discrete logarithm solved is 112 bits, in July 2009.
14. ECDSA needs a fresh secret per-signature value, and reusing it exposes the private key by simple algebra, which is how the PlayStation 3 master key fell in December 2010 and why RFC 6979 and EdDSA derive that value deterministically instead.
15. P-256 is a NIST Weierstrass curve used with ECDSA, Curve25519 is a Montgomery curve used only for X25519 key agreement, Ed25519 is a signature scheme on the equivalent Edwards curve, and Ed448 is the higher-strength version of the last.
16. FIPS 186-5 of 3 February 2023 approves RSA, ECDSA including its deterministic variant and EdDSA on edwards25519 and edwards448, and states that DSA may now only be used to verify old signatures.
17. Table 2 of NIST Special Publication 800-57 Part 1 Revision 5 equates 2048-bit RSA with a 224-to-255-bit curve at 112 bits of strength and 3072-bit RSA with a 256-to-383-bit curve at 128 bits.
18. Table 4 of the same publication makes 112 bits of strength unacceptable for applying protection from 2031 onwards, and the draft NIST Internal Report 8547 proposes disallowing all classical public key strengths after 2035.
19. FIPS 204 and FIPS 205, both published on 13 August 2024, specify ML-DSA with public keys of 1,312 to 2,592 bytes and signatures of 2,420 to 4,627 bytes, and SLH-DSA with 32-byte public keys and signatures from 7,856 bytes upwards.
20. A verified signature proves control of a private key over specific bytes and proves nothing about identity, which is why the next volume exists and why the chapter after this one turns a key pair into a login by making the answer different every time.

Chapter sources: Whitfield Diffie and Martin E. Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, volume IT-22, number 6, November 1976, pages 644 to 654; Ralph C. Merkle, “Secure Communications Over Insecure Channels”, Communications of the ACM, volume 21, number 4, April 1978, pages 294 to 299, submitted in 1975; Ronald L. Rivest, Adi Shamir and Leonard M. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, volume 21, number 2, February 1978, pages 120 to 126, received 4 April 1977 and revised 1 September 1977, with its own worked example on the primes 47 and 59; James H. Ellis, “The Possibility of Secure Non-Secret Digital Encryption”, CESG Research Report 3006, January 1970, together with Clifford Cocks’s 1973 note and Malcolm Williamson’s 1974 result, declassified in December 1997 and described by Cocks in a public talk on 18 December 1997; Daniel J. Bernstein, “Curve25519: new Diffie-Hellman speed records”, Public Key Cryptography 2006, and Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang, “High-speed high-security signatures”, CHES 2011; Peter W. Shor’s 1994 factoring algorithm; Dan Boneh, Richard DeMillo and Richard Lipton on fault attacks against CRT-RSA, 1997. Standards: FIPS 186-5, “Digital Signature Standard”, 3 February 2023, sections 6, 6.3.2, 7 and 7.8, superseding FIPS 186-4 of 19 July 2013; FIPS 203, 204 and 205, all approved 13 August 2024, with the ML-DSA parameter table giving 1,312, 1,952 and 2,592-byte public keys and 2,420, 3,309 and 4,627-byte signatures at security categories 2, 3 and 5, and the SLH-DSA table giving 32, 48 and 64-byte public keys and signatures of 7,856, 17,088, 16,224, 35,664, 29,792 and 49,856 bytes; the absence of any FIPS 206 in the NIST publication database as of 18 August 2026, against a draft submitted for approval on 28 August 2025; NIST Special Publication 800-57 Part 1 Revision 5, May 2020, table 2 in section 5.6.1.1 and table 4 in section 5.6.3; NIST Special Publication 800-186, 3 February 2023; NIST Special Publication 800-208 on stateful hash-based signatures; NIST Internal Report 8547, “Transition to Post-Quantum Cryptography Standards”, initial public draft of 12 November 2024 with comments closed 10 January 2025 and still unfinalized as of August 2026; NIST’s SHA-1 transition announcement of 15 December 2022 setting 31 December 2030; RFC 8017, “PKCS number 1 version 2.2”, November 2016; RFC 7748, “Elliptic Curves for Security”, January 2016; RFC 8032, “Edwards-Curve Digital Signature Algorithm”, January 2017; RFC 6979 on deterministic ECDSA, August 2013; RFC 9964, “ML-DSA for JOSE and COSE”, May 2026, with the IANA COSE algorithm registry values -7, -8, -37, -257, -48, -49 and -50; the National Security Agency’s Commercial National Security Algorithm Suite 2.0 announcement of 7 September 2022. Attacks and measurements: Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger, “MD5 considered harmful today”, 25th Chaos Communication Congress, 30 December 2008; Microsoft Security Response Center, “Flame malware collision attack explained”, June 2012; Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov, the SHAttered SHA-1 collision of 23 February 2017 at about 6,500 CPU-years and 110 GPU-years; Daniel Bleichenbacher’s low-exponent signature forgery presented at the CRYPTO 2006 rump session, with Ulrich Kuhn’s variants and the Black Hat USA 2019 study “A Decade After Bleichenbacher '06, RSA Signature Forgery Still Works”; fail0verflow, “Console Hacking 2010: PS3 Epic Fail”, 27th Chaos Communication Congress, December 2010; Nadia Heninger, Zakir Durumeric, Eric Wustrow and J. Alex Halderman, “Mining Your Ps and Qs”, USENIX Security, August 2012, reporting 5.57 per cent of TLS hosts and 9.60 per cent of SSH hosts sharing keys and private keys recovered for 0.50 per cent of TLS and 1.03 per cent of SSH DSA hosts; CVE-2008-0166, published 13 May 2008, on the Debian OpenSSL entropy defect; Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thome and Paul Zimmermann on RSA-240 of 2 December 2019 and RSA-250 of 28 February 2020; Joppe Bos, Marcelo Kaihara, Thorsten Kleinjung, Arjen Lenstra and Peter Montgomery on the 112-bit prime-field ECDLP of July 2009; the binary-curve record of 2 December 2016 by Bernstein, Engels, Lange, Niederhagen, Paar, Schwabe and Zimmermann; Craig Gidney and Martin Ekera, 2019, and Craig Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits”, 21 May 2025; OpenSSH 6.5 release notes of 30 January 2014. All key generation, signing, verification, byte layouts and speed figures reported in this chapter were produced with OpenSSL 3.0.13 on a single core of an Intel Xeon processor at 2.10 GHz on 18 August 2026.