Digital signatures

Understand what a digital signature proves (and what it does not), how sign/verify works with a key pair, and why signatures are the backbone of authenticated authority in agent systems.

Track

Fundamentals

Module

2 · Applied cryptography for agents

Prerequisites

Hash functions · Basic modular arithmetic

A digital signature answers two questions at once about a message: who authored it, and whether it was changed since. The signer holds a secret (the private key); anyone with the matching public key can verify. Unlike a shared-secret MAC, verification needs no secret, so a signature can be checked by third parties who were never trusted with any key material — which is exactly what multi-agent and cross-organization authorization needs.

A signature scheme is three algorithms: key generation produces a (public key, private key) pair; signing takes the private key and a message and outputs a signature; verification takes the public key, the message and the signature and outputs accept or reject. Security rests on asymmetry: deriving the private key from the public key, or forging a signature without it, must be computationally infeasible.

Key pair

A private key kept secret and a public key shared freely; mathematically linked but the private key cannot be recovered from the public one.

EUF-CMA

The standard security goal: existential unforgeability under chosen-message attack — an adversary who can get signatures on messages of their choosing still cannot forge a signature on a new message.

Modern agent systems favour EdDSA over the Edwards curve Ed25519 (RFC 8032). At a high level, over an elliptic-curve group of prime order with base point B:

Ed25519 (schematic)
KeyGen:  private scalar a  ->  public key A = a·B
Sign(a, M):
  r = H(prefix, M)            # deterministic nonce from a hash
  R = r·B
  s = r + H(R, A, M)·a   (mod L)
  signature = (R, s)
Verify(A, M, (R, s)):
  accept  iff  s·B  ==  R + H(R, A, M)·A

Two properties matter in practice. The nonce r is derived deterministically from the key and message, so Ed25519 does not need a secure random number at signing time — removing the catastrophic “reused nonce leaks the key” failure that plagues naive ECDSA. And the whole message M is signed, not a separate pre-hash chosen by the caller, which removes an ambiguity attackers can exploit.

1. 1Generate a key pair; publish the public key, protect the private key (ideally in a KMS/HSM so it never leaves).
2. 2To authorize an action, canonicalize the message to exact bytes (sorted keys, fixed encoding) so signer and verifier agree byte-for-byte.
3. 3Sign the canonical bytes with the private key, producing a signature.
4. 4Transmit (message, signature, key-id) — never the private key.
5. 5The verifier re-canonicalizes the message, fetches the public key by key-id from a trusted store (never from the message), and checks the signature.

synthetic — a signed authority event
event = { "action": "transfer", "scope": "vault:A", "exp": 1699999999 }
msg    = canonical(event)                 # deterministic bytes
sig    = Ed25519_sign(privateKey, msg)    # private key stays in KMS
# sent on the wire: { event, sig, kid }
# verifier:
ok = Ed25519_verify(publicKey[kid], canonical(event), sig)

Note the discipline: the verifier selects the key by kid from its own trust store, re-derives the canonical bytes, and treats a valid signature only as proof of authorship — business checks (is this scope allowed? is it expired?) are separate and come after.

Signatures are how an agent system binds authority to identity. A control plane signs its intent so an executor can verify it authored the order; an agent signs its messages so a peer can confirm the sender; audit records are chained and signed so “who authorized this, and when?” stays answerable and unforgeable. Because verification is public, a worker can hold only public keys — it can verify an order but can never mint one, a clean separation of the ability to authorize from the ability to execute.

Signatures are also the base layer for delegation (Module 3) and for zero-knowledge attestations of delegation (Modules 4–5): a delegation is a signed statement that one key grants a narrowed capability to another.

• ▸A signature with no nonce/expiry can be replayed; bind a per-use nonce, an audience and a purpose (see replay prevention).
• ▸ECDSA signatures are malleable (an (r, s) has a valid sibling) and a reused or biased nonce leaks the private key; Ed25519 avoids both but legacy systems may not.
• ▸Missing domain separation lets a signature valid in one context be replayed in another — always bind the contract/chain/context.
• ▸Key custody is the real attack surface: a leaked private key forges everything. Keep keys in a KMS; signing is a call, never an export.
• ▸Above all: a valid signature authenticates bytes, not judgement. It never proves the authorized action was correct or safe.

Expected direction: Examples: replay the signed message if it has no nonce/expiry; use it in a different context/chain if there is no domain separation; rely on the fact that a valid signature says nothing about whether the authorized action is semantically correct or safe.

Does a valid digital signature prove the signed statement is true or safe?

No — only that these exact bytes were produced by the private key and not altered. Correctness and safety are separate properties.

Why can an executor hold only public keys and still be useful?

Because verification needs only the public key; it can verify a signed order but cannot mint one, separating authorization from execution.

What problem does Ed25519’s deterministic nonce solve compared with naive ECDSA?

It removes the need for a secure random nonce at signing time, eliminating the “reused/biased nonce leaks the private key” failure.