Signatures: What the Signer Computes and the Verifier Checks

Every time your phone installs an update, a browser trusts a website, or an artificial intelligence (AI) agent loads a tool, a quiet check happens first: is this really from who it claims, and has it changed since they sent it? The check is a digital signature, and it is one of the most useful ideas in all of computing. It is also one of the most misunderstood. Many explanations say that signing is 'encrypting with the private key', which is wrong for most modern signatures and misleading even for the one where it sounds plausible. This article builds signatures from the ground up. You will see why every signature starts with a fingerprint of the message, sign and check a message with a tiny RSA key, then sign and check with a tiny elliptic-curve key using the commit-challenge-response shape behind ECDSA and EdDSA. Along the way you will learn exactly what a valid signature proves, what it does not, and how this applies to the code, models and tool descriptions that AI agents depend on.

What a signature is for

A handwritten signature on paper tries to do two jobs: show who agreed to a document, and make it hard to change the document afterwards without anyone noticing. It does both rather badly, because signatures can be copied and pages can be swapped. A digital signature does both jobs well, using mathematics instead of ink.

Here is the promise in plain terms. A signer has a key pair: a private key that only they hold, and a public key that anyone may have. Using the private key, the signer computes a short value from a message. That value is the signature. Anyone with the public key can run a check on the message and the signature. If the check passes, two things are true with overwhelming likelihood: whoever made the signature held that private key, and the message has not changed by even one bit since it was signed.

Those two properties have names. Authenticity means the message really comes from the holder of the private key. Integrity means it has not been altered. A third property often follows: the signer cannot convincingly deny having signed, because only their private key could have produced the signature. That is called non-repudiation, although in practice it depends on the private key having been kept safe.

Notice what is missing from that list: secrecy. A signature does not hide the message. Signed messages are usually sent in plain view, and anyone can read them. Keeping something secret and proving where it came from are different jobs, done by different operations, and confusing the two causes real mistakes.

An old-fashioned picture helps. Think of a wax seal pressed with a signet ring that only one person owns. Everyone in town knows what that ring's pattern looks like, so anyone can check a seal, but only the ring's owner can make one, and a broken seal shows the letter was opened. A digital signature is that seal, except the ring cannot be copied by looking at the pattern, and the seal covers every letter of the message rather than just the flap of the envelope.

Every signature starts with a fingerprint

Before anything is signed, the message is turned into a fingerprint. The tool that does this is called a cryptographic hash function: a recipe that takes data of any size, from a short sentence to a large file, and produces a fixed-size output, such as 256 bits for the widely used SHA-256, the Secure Hash Algorithm with a 256-bit output. Like a human fingerprint, the hash is small, unique in practice to its source, and tells you nothing about what the source looked like.

Three properties make a hash useful here. It is deterministic: the same message always gives the same fingerprint. It is very sensitive: changing a single character, even a comma, produces a completely different fingerprint with no visible relationship to the old one. And it is one-way and collision-resistant: nobody can practically work backwards from a fingerprint to a message, or find two different messages that share the same fingerprint.

Signing the fingerprint instead of the whole message has two big benefits. It is fast, because the expensive public-key arithmetic runs on a small fixed-size value no matter how large the file is. And it is safe, because collision resistance means that a signature on the fingerprint effectively commits to the exact message: to forge a signature for a different message, an attacker would have to find another message with the same fingerprint, which is believed to be infeasible.

This is also why old hash functions are retired so firmly. When researchers found practical ways to create two different documents with the same fingerprint under older hashes such as MD5 and SHA-1, signatures that relied on them could no longer be trusted, even though the public-key part was unchanged. A signature is only as strong as the fingerprint underneath it.

Here is how sensitive that is in practice. Take the sentence 'Transfer 100 to Alice' and its SHA-256 fingerprint. Change it to 'Transfer 900 to Alice' and roughly half of the 256 bits of the fingerprint flip, in a pattern that looks completely random. There is no way to look at the two fingerprints and tell that only one character changed, and no way to adjust the new message so that it lands back on the old fingerprint. That is exactly the behaviour a signature needs underneath it.

Signing with a tiny RSA key

RSA signatures make a good first example because the arithmetic is short. Take a toy RSA key: the public modulus is 55, the public exponent is 3, and the private exponent is 27. These numbers come from the primes 5 and 11, and they are far too small to protect anything, but they let you check every step by hand.

Suppose the fingerprint of the message, squeezed into this tiny range, is 9. To sign, the signer raises the fingerprint to the private exponent and wraps the result around 55. Nine to the power 27, wrapped around 55, comes out as 4. The signature is 4. Only someone who knows the private exponent 27 can produce it.

To verify, anyone takes the signature and raises it to the public exponent, wrapping around 55: 4 cubed is 64, and 64 wrapped around 55 is 9. The verifier separately computes the fingerprint of the message they received. If the two match, 9 and 9, the signature is valid. If an attacker changed the message, its fingerprint would no longer be 9, and the check would fail. If the attacker tried to invent a signature for their changed message without the private exponent, they would have no practical way to find a number that cubes to the right fingerprint.

Real RSA signatures do not sign the bare fingerprint like this. They first wrap it in a carefully designed structure called padding, and the modern choice is the Probabilistic Signature Scheme (PSS), standardised in Request for Comments (RFC) 8017. Padding adds structure and randomness so that tricks which work against the bare, textbook version, such as combining two valid signatures to manufacture a third, no longer work. As with RSA encryption, the bare arithmetic is a teaching tool, not something to deploy.

Why can't an attacker simply work out a signature for their own fingerprint? In this toy, they could: with only 55 possible values they can try every number until one cubes to the fingerprint they want. With a real modulus, hundreds of digits long, there are far too many candidates to try, and finding the right one without the private exponent is believed to be as hard as factoring the modulus into its two primes. The public exponent lets anyone go one way; only the private exponent lets you go back.

Signing is not encrypting with the private key

The RSA example looks like it runs encryption backwards: encryption uses the public exponent, signing uses the private one. That resemblance is where the popular phrase 'a signature is the message encrypted with the private key' comes from. It is worth unlearning, for three reasons.

First, it is only even superficially true for RSA. Elliptic-curve signatures such as ECDSA and EdDSA, which are now the most common kinds, involve no encryption step at all; there is nothing to 'encrypt with the private key'. Second, even for RSA the real operations differ: signing and encryption use different padding, built for different security goals, and the standards warn against using one RSA key for both jobs. Third, the phrase suggests that a signature hides something, when anyone holding the public key can 'decrypt' it, which means nothing is hidden at all.

A better mental model is this: signing is computing a proof that only the private key can compute, about one exact fingerprint, in a form that anyone with the public key can check. Encryption is making data unreadable to everyone except the holder of a key. They answer different questions. Encryption answers 'who can read this?'; a signature answers 'who vouches for this, and is it intact?'.

This matters in practice because the confusion leads to real design errors: reusing an encryption key for signing, assuming a signed message is private, or building a homemade 'signature' by encrypting a message with a symmetric key that both sides share, which proves nothing about which of the two sides wrote it.

Commit, challenge, respond: signing on a curve

Elliptic-curve signatures work differently, and the shape behind them is worth understanding because it shows exactly why one detail matters so much. Recall that on an elliptic curve, a private key is a secret count of steps and the public key is the point you reach after taking that many steps from an agreed base point, called G.

Here is the shape, used by Schnorr signatures and by the Edwards-curve Digital Signature Algorithm (EdDSA). Step one, commit: the signer picks a fresh secret number just for this signature, sometimes called a nonce, a 'number used once', and publishes the point it reaches, called R. Step two, challenge: the signer computes a fingerprint of the message together with R and the public key, and turns it into a number, the challenge. Step three, respond: the signer combines the per-signature secret, the challenge and the private key into one number, the response. The signature is the pair: the commitment R and the response.

Here it is on a toy curve with 19 points and base point G = (5, 1). The signer's private key is 3, so the public key is 3G, the point (10, 6). For one signature the signer picks the fresh secret 5, so the commitment R is 5G, the point (9, 16). Suppose the challenge fingerprint comes out as 4. The response is the fresh secret plus the challenge times the private key, wrapped around the 19-step loop: 5 plus 4 times 3 is 17. The signature is R = (9, 16) and the response 17.

The verifier knows only public things: G, the public key (10, 6), the message, R and 17. They recompute the challenge, 4, from the message, R and the public key. Then they check one equation: walking 17 steps from G must land on the same point as R plus 4 times the public key. Walking 17 steps lands on (6, 14). On the other side, 4 times the public key is 12 steps, and adding R's 5 steps gives 17 steps, which also lands on (6, 14). They match, so the signature is valid. The verifier never learned the private key 3 or the fresh secret 5.

The Elliptic Curve Digital Signature Algorithm (ECDSA), used widely with the P-256 curve, follows a related pattern with a different way of combining the pieces, but the same three ingredients appear: a fresh per-signature secret, a fingerprint of the message, and the private key, combined so that only public values are needed to check the result.

It is worth seeing why that check can only pass for the real signer. Both sides of the check are just step counts from G in disguise: the left side is 17 steps, and the right side is 5 steps plus 4 lots of 3 steps. They only agree if the response really was built from the private key. A forger who does not know the private key can pick any commitment and any response they like, but the challenge depends on the message and the commitment through a hash, so they cannot arrange for the two sides to agree without solving the hard step-counting problem.

Why the per-signature secret matters so much

Look again at the response: fresh secret plus challenge times private key. The verifier sees the response and the challenge. The only things hiding the private key are the fresh secret, which nobody else knows, and the hard problem of counting steps on the curve. If the fresh secret ever leaks, the private key falls out with one subtraction and one division.

Worse, if the same fresh secret is used for two different messages, the attacker does not even need to know it. Two signatures with the same commitment but different challenges give two responses, and the difference between them depends only on the private key. This is not a theoretical worry: reused or predictable per-signature secrets have exposed private keys in real deployed systems, including widely reported cases involving game consoles and cryptocurrency wallets.

The two main signature families answer this risk differently. ECDSA, as originally specified, expects the signer to draw a fresh random secret every time, which puts the burden on a good random number generator. RFC 6979 later defined a deterministic way to produce that secret from the private key and the message, so that weak randomness cannot cause reuse. EdDSA builds deterministic generation into its design from the start: Ed25519, the most widely used form, derives the per-signature secret from the private key and the message, so signing the same message twice gives the same signature and signing different messages never repeats the secret.

Deterministic generation removes one large class of mistakes, but not every risk around signing keys. Implementations can still leak secrets through timing or hardware faults, and none of this helps if the private key itself is stolen. The lesson for a non-specialist is simply to use well-maintained libraries, prefer Ed25519 or deterministic ECDSA where you have the choice, and never write signing code by hand.

What a valid signature does and does not prove

A valid signature proves something narrow and precise: this exact message was signed by whoever held the private key that matches this public key, and it has not changed since. Every word of that sentence matters, and each one leaves something out.

It does not prove who that key belongs to. A signature checked against an attacker's public key is perfectly valid. Tying a public key to a real name or organisation is a separate job, done by a certificate, an electronic document in which a trusted authority signs a statement such as 'this key belongs to example.com', or by an organisation pinning known keys in advance. Verifying the signature but not the identity behind the key is one of the most common real-world failures.

It does not prove the content is safe or true. A signed installer can still contain a vulnerability, and a signed statement can still be false. Signatures record who vouched for something, not whether they were right to.

It does not prove when the signing happened or that the key was not stolen at the time. Keys get compromised, and systems handle that with key expiry, revocation lists and timestamps from separate services. Finally, it does not prove the message was meant for you or is current: an old valid signed message can be replayed later unless the signed content includes context such as a date, a recipient or a unique number.

In practice, verification often happens in a chain. A website's certificate is signed by an intermediate authority, whose certificate is signed by a root authority that your device already trusts. The verifier checks each signature in turn, and also checks names, dates and permitted uses along the way. Every link is the same narrow promise, chained together until it reaches a key the verifier was told to trust in advance.

• Proves: this exact message, unchanged since signing.
• Proves: produced by the holder of the matching private key.
• Does not prove: who owns that key; that needs a certificate or a pinned key.
• Does not prove: that the content is safe, true, current or meant for you.

What this means for practitioners and for AI agents

In day-to-day engineering, signatures are everywhere: in the certificates that let a browser trust a site, in software updates and package managers, in signed commits, in tokens that prove a user signed in, and in the documents that prove a build came from a particular pipeline. The practical choices are which algorithm to use, where the private key lives, and what the verifier checks beyond the mathematics.

AI agents depend on signatures in three places. First, the connections they make: when an agent calls a tool over Transport Layer Security (TLS), the server proves its identity with a signature made during the handshake and a certificate chain that links its key to its name. Second, the things an agent runs or loads: model files, plug-ins, container images and tool descriptions can all be signed, and an agent platform can refuse to load anything whose signature does not check out against an approved key. Third, the agent's own identity: when an agent authenticates with a key pair instead of a password, it signs a challenge to prove it holds its private key.

Each place has the same two failure modes. The first is checking the signature but not the signer: accepting any validly signed tool description, rather than only those signed by keys the organisation trusts, gives attackers an easy path, because anyone can sign their own malicious file. The second is losing the private key: an agent's signing key that ends up in a prompt, a log, a configuration file or the agent's memory turns the strongest signature scheme into a forgery kit. Keys belong in a key store or hardware security module that signs on the agent's behalf and never hands the key out.

For code written with AI assistance, review signature handling with the same eye. Generated code sometimes 'verifies' by checking that a signature field exists, compares fingerprints with a loose string match, accepts whichever algorithm an incoming message names, or skips the step that checks the key belongs to the expected signer. A correct verifier pins the algorithm, checks against an expected key or certificate chain, and fails closed when anything is missing.

Choosing an algorithm today is mostly straightforward. For new systems, Ed25519 is a strong default where it is supported. Where compliance programmes or hardware require a NIST curve, use ECDSA with P-256 and a deterministic or well-seeded per-signature secret. Use RSA with PSS padding and a modulus of at least 3,072 bits when you need compatibility with older systems. And keep an eye on post-quantum signature standards, which are designed to keep signatures trustworthy even against future quantum computers; the habits in this article carry over unchanged.

Glossary

Digital signature

A value computed with a private key that anyone with the public key can check, proving origin and integrity.

Cryptographic hash function

A recipe that turns data of any size into a fixed-size fingerprint that changes completely if the data changes.

Authenticity

Assurance that a message came from the holder of a particular private key.

Integrity

Assurance that a message has not been altered since it was signed.

Padding (PSS)

The Probabilistic Signature Scheme structure that real RSA signatures wrap around a fingerprint before signing.

Nonce

A per-signature secret number that must be used only once.

ECDSA

Elliptic Curve Digital Signature Algorithm, widely used with the P-256 curve.

EdDSA

Edwards-curve Digital Signature Algorithm; Ed25519 is its common form and derives its per-signature secret deterministically.

Certificate

A signed document from a trusted authority that ties a public key to a name.

Further reading

1. FIPS 186-5: Digital Signature Standard (NIST)
2. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 (IETF)
3. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA) (IETF)
4. RFC 6979: Deterministic Usage of DSA and ECDSA (IETF)