Digital Signatures

The previous lesson closed with an unverified item: key exchange produces a shared secret but does not say who the other side is. The proof had to come from outside, and the fifth lesson already caught a glimpse of that proof’s direction once — an operation done with the private key is reversed with the public key, and being reversible showed the source.

This lesson takes up that direction in its own form. A digital signature is a value produced with the private key and verified with the public key; verification does not need any secret item. What is measured is not whether the signature works, but exactly what it proves and what it does not prove.

The Signature and a Single-Bit Change

CF20: a signature is produced by the party holding the private key and is verified by anyone using the public key; verification does not need any secret item.

CF21: a signature depends on the entire signed byte sequence; changing a single bit drops verification.

// signature/generate.mjs — a signature is generated and verified, then each bit of the
// signed data is flipped and the number of surviving verifications is counted. A fictional
// measurement network's daily reading batch is signed; key material is not printed.
import { generateKeyPairSync, sign, verify } from "node:crypto";

// CF20: a signature is produced by the party holding the private key and is verified by
//       anyone using the public key; verification does not need any secret item.
// CF21: a signature depends on the entire signed byte sequence; changing a single bit
//       drops verification.

const { publicKey: PUBLIC, privateKey: PRIVATE } = generateKeyPairSync("ed25519");
const BATCH = Buffer.from("BRANCH-03|2026-03-01|reads=4180|total=8813304|recs=1240");
const signature = sign(null, BATCH, PRIVATE);

console.log("signed batch    :", BATCH.length, "bytes,", BATCH.length * 8, "bits");
console.log("signature size  :", signature.length, "bytes");
console.log("unchanged batch :", verify(null, BATCH, PUBLIC, signature) ? "valid" : "invalid");

let survived = 0;
for (let i = 0; i < BATCH.length * 8; i++) {
  const b = Buffer.from(BATCH); b[i >> 3] ^= 1 << (i & 7);
  if (verify(null, b, PUBLIC, signature)) survived++;
}
console.log(`batch bit flipped    : ${BATCH.length * 8} attempts, verification survived: ${survived}`);

let signatureSurvived = 0;
for (let i = 0; i < signature.length * 8; i++) {
  const s = Buffer.from(signature); s[i >> 3] ^= 1 << (i & 7);
  if (verify(null, BATCH, PUBLIC, s)) signatureSurvived++;
}
console.log(`signature bit flipped: ${signature.length * 8} attempts, verification survived: ${signatureSurvived}`);

const { publicKey: OTHER_PUBLIC } = generateKeyPairSync("ed25519");
console.log("verification with a different public key:",
  verify(null, BATCH, OTHER_PUBLIC, signature) ? "valid" : "invalid");

signed batch    : 55 bytes, 440 bits
signature size  : 64 bytes
unchanged batch : valid
batch bit flipped    : 440 attempts, verification survived: 0
signature bit flipped: 512 attempts, verification survived: 0
verification with a different public key: invalid

Verification did not survive a single one of nine hundred fifty-two attempts. Whether any of the 440 bits of the batch or any of the 512 bits of the signature is flipped, the result is the same: invalid. This is the signature-side counterpart of the avalanche effect measured in the second lesson — a signature binds the data as a whole, and no part of it is handled separately.

The last line is a separate item. A signature is verified with the public key that is the counterpart of the private key it was produced with; verifying with a different public key returns invalid. The verifying party holding the correct public key is a separate link in this chain, and it is exactly the item left open at the end of this lesson.

Signature size is also a decision. The 64 bytes here, compared with the 256-byte output from the fifth lesson, is a quarter of it; if the fictional network produces 12,400 signatures a day, the difference is a 2.3 MiB load per day. A signature’s size does not determine its security — it determines its transport cost.

The Signature Is Produced Over a Digest

The batch was 55 bytes, but what gets signed is not directly that 55 bytes. Signature schemes first run the data through a hash function and perform the asymmetric operation on the digest. The reason is the size limit measured in the fifth lesson: the asymmetric operation takes a fixed, small input, while the data to be signed can be any length. A fixed-length digest ties these two requirements together.

The direct consequence is that the signature’s security depends on the hash function’s collision resistance. This is why the second lesson’s table lists the “digest signed between branches” row under the collision column. If two different batches that produce the same digest can be found, a signature produced for one also fits the other; while signing one batch, the signing party ends up signing another batch it never saw.

The number follows from this. When collision resistance drops, the count of signatures that become disputed is the same as the count from the signing key leaking — 2,190 in the fictional network. But the reason differs: in one case the key has fallen into someone else’s hands, in the other the key was never touched and a different link in the chain broke. This is why the chain’s items are counted separately; a signature’s security is the security of its weakest link.

The second rule that follows is key separation. Using the same key pair for both encryption and signing halves the item count but ties two breaks to a single root: the signing key leaking also opens all the traffic encrypted with that pair. In the fictional network, using separate pairs means two key items per participant — 14 items for 7 participants — and what that buys is that one break does not bring down the other use.

What the Signature Proves and Does Not Prove

CF22: a signature proves that the signing party held the private key; it does not prove who that key belongs to, when it was used, or whether it was stolen at that moment.

// signature/item.mjs — the items a signature proves and does not prove, the split between
// integrity and non-repudiation, and the items that drop if the signing key leaks (model).
// Fictional regional measurement network figures are used.

// CF22: a signature proves that the signing party held the private key; it does not prove
//       who that key belongs to, when it was used, or whether it was stolen at that
//       moment.

const printRow = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));
const ITEMS = [
  ["the data has not changed since it was signed", "yes"],
  ["the signing party held the private key", "yes"],
  ["who that private key belongs to", "no"],
  ["when the signature was produced", "no"],
  ["whether the signer saw and accepted the content", "no"],
  ["whether the key was stolen at that moment", "no"],
];
const A = [-49, 13];
printRow(A, "item", "proven");
for (const [name, p] of ITEMS) printRow(A, name, p);
const proven = ITEMS.filter(([, p]) => p === "yes").length;
console.log(`${ITEMS.length} items, ${proven} proven, ${ITEMS.length - proven} not proven`);

const PARTICIPANTS = 7;                              // fictional: center + 6 branches
console.log(`\nif the same batch were signed two ways (${PARTICIPANTS} participants):`);
const B = [-22, 12, 12, 16];
printRow(B, "method", "verifying", "sender", "third party");
printRow(B, "", "party", "candidate", "proof");
printRow(B, "keyed hash", 2, 2, "no");
printRow(B, "digital signature", PARTICIPANTS, 1, "yes");

const BRANCHES = 6, DAYS = 365;
console.log(`\nif the signing key leaks (${BRANCHES} branches, 1 batch per day):`);
const C = [-26, 14, 14];
printRow(C, "item", "per branch", "network-wide");
printRow(C, "disputed past signatures", DAYS, BRANCHES * DAYS);
printRow(C, "new key pair", 1, BRANCHES);
printRow(C, "public key to distribute", 1, BRANCHES);
printRow(C, "batches to re-sign", DAYS, BRANCHES * DAYS);

item                                                    proven
the data has not changed since it was signed               yes
the signing party held the private key                     yes
who that private key belongs to                             no
when the signature was produced                             no
whether the signer saw and accepted the content             no
whether the key was stolen at that moment                   no
6 items, 2 proven, 4 not proven

if the same batch were signed two ways (7 participants):
method                   verifying      sender     third party
                             party   candidate           proof
keyed hash                       2           2              no
digital signature                7           1             yes

if the signing key leaks (6 branches, 1 batch per day):
item                          per branch  network-wide
disputed past signatures             365          2190
new key pair                           1             6
public key to distribute               1             6
batches to re-sign                   365          2190

Two of six items are proven, four are not. This ratio is not the signature’s weakness; it is the definition of its scope — each of the four unproven items calls for its own mechanism. For time, an independent timestamp is needed; for whether the key was stolen, a revocation scheme; for the key’s owner, an identity document — all three lie outside this topic, and all three bring their own trust root.

The second item a signature produces — that the signing party held the private key — is not an identity. Who the key belongs to is not written inside the signature. Nor is when it was signed; a timestamp can be added to a signature, but the signing party is the one who puts that timestamp there too, so the timestamp is the signer’s own claim. Whether the key was stolen at the moment of signing does not show up in the signature in any form: a signature produced with a stolen key is a valid signature.

Integrity and Non-Repudiation

The second table ties this lesson’s conceptual distinction to a number. The keyed hash measured in the fourth lesson also provided integrity — if the body changed, the tag did not hold. The difference lies beyond integrity.

Integrity shows that the data has not changed, and both mechanisms do that. Non-repudiation, though, is the signer not being able to say “I did not produce this,” and that requires the sender candidate to narrow down to one.

With a keyed hash, both sides know the key; the number of parties who can verify is two, and the sender candidate count is also two. Because the recipient could have produced the same tag itself, it cannot prove anything to a third party. With a digital signature, the secret item sits with a single side: the number of parties who can verify is seven — everyone who has the public key — and the sender candidate count is one. Proof can be presented to a third party.

The word “can” is conditional, and that condition sits in the first table. Non-repudiation holds only if it is accepted that the private key truly sits with just that one party. If the key sits in a file and several people can reach that file, even a mathematically flawless signature does not refute the “I did not do it” defense. This is why non-repudiation is not a cryptographic property but an operational one, supported by cryptography.

The Chain’s Six Items

The number of items that must be true at the same time to draw a conclusion from a signature’s verification is six, and five are technical, one is operational.

The first is the signing party’s private key staying secret. The second is the collision resistance of the hash function the signature is produced over. The third is the verifying party holding the correct public key. The fourth is the scheme’s parameters being chosen correctly.

The fifth item is the quietest one: the signed byte sequence and the verified byte sequence being byte-for-byte identical. A signature is produced over a byte sequence, not over a meaning. In the fictional network, a branch turns its daily batch into a text line and signs it; if the center parses that line, rewrites it in its own format, and then tries to verify, verification drops — even if the data has not changed. The reverse case is worse: if verification is done on the raw incoming bytes but the business logic runs on a re-parsed copy, what was signed and what is operated on diverge. This is why the byte sequence a signature verifies and the data that gets used must come from the same source.

The sixth item depends on the scheme choice. Some signature schemes require a fresh random value for every signature, and reusing that value exposes the private key; this is the signature-side counterpart of the fourth lesson’s nonce condition. The scheme used in this lesson produces the signature deterministically and removes the item. One of the six items can be reduced away to five by the choice of scheme — the cheapest way to cut an item count is making an item unnecessary rather than managing it.

If the Root Breaks

The third table fills in the course’s third column for this mechanism. If the signing key leaks, how many items fall? The item that falls directly is every past batch signed with that key: 365 signatures per branch, 2,190 across the whole fictional network become disputed. “Disputed” does not mean invalid — the signatures still verify, but the sender candidate is no longer one, and the non-repudiation property drops retroactively.

The renewal cost is counted in two separate items. Generating a new key pair and distributing the public key is six items — cheap, because the distributed item is not secret. Rescuing the past, though, is 2,190 items: re-signing every batch with the new key. The second number goes unpaid in most setups, and the past is left disputed.

One way to narrow the disputed past is to have a party independent of the signer record when a signature was produced. In that case, signatures from before the leak date stay outside the dispute, and only part of the 2,190 items falls. The cost is an extra call to an outside party for every signature, and that party itself becoming a new trust root. The item count does not shrink — it moves.

This takes a different shape compared to the renewal costs in earlier lessons. When a symmetric key leaked, renewal required carrying a secret item; the item carried for a signing key is public. On the other hand, renewing a symmetric key does not make the past disputed — renewing a signing key does.

Summary

• A signature is produced with the private key, verified with the public key, and verification does not require any secret item.
• A signature depends on the entire signed data: when the bits of the 440-bit batch and the 512-bit signature are flipped one at a time, verification does not survive a single one of 952 attempts.
• A signature proves two of six items; who the key belongs to, when it was used, whether the content was seen and accepted, and whether the key was stolen at that moment are not proven.
• Both mechanisms provide integrity; non-repudiation requires the sender candidate to narrow to one — the candidate count is 2 for a keyed hash and 1 for a digital signature.
• Non-repudiation is conditional: it rests on the assumption that the private key truly sits with a single party, and that assumption is an operational item.
• If the signing key leaks, 2,190 past signatures become disputed; renewal is 6 public item distributions, while rescuing the past is 2,190 re-signing items.

Next Step

This topic built a chain across seven lessons. How many items a reversal depends on was counted, collision resistance was measured, the attempt-cost curve was drawn, key distribution’s arithmetic was written out, roles were separated, a shared secret was produced over an insecure channel, and a signature proved integrity. Every link in the chain named its own root.

The roots, in order, were these: encoding had no root; encryption’s root was the key staying secret; hashing’s root was a collision not being found; password storage’s root was the password not being in the candidate list; the symmetric scheme’s root was the shared key existing only on two sides; the asymmetric scheme’s root was the private key sitting with a single side; key exchange’s root was the secret exponents never being sent; and the signature’s root was the signing key staying with its owner. None of the eight roots is the algorithm itself — each one is about where an item sits.

But one line stayed open in the last output block: the signature returned invalid when verified with a different public key — meaning verification rests on holding the correct public key. That public key reached the verifying party over an open channel. The question asked in the fifth lesson goes unanswered here too: nothing proves who the public key that verifies the signature belongs to. A verifier that mistakes the wrong public key for the right one treats every signature produced with that key’s counterpart as valid, and sees no error while doing so. The next topic, Public Key Infrastructure, ties this single item into a chain: the document that says a public key belongs to an identity, the party that signs that document, and the root sitting at the very top of the chain.