Digital signatures (Ed25519)

Deep dive

How it works

In: sign: 32-byte seed and message; verify: 32-byte public key, message, 64-byte signature · Out: 64-byte signature, or accept/reject · State: none; the caller stores the seed · Cost: sign 15.0 µs, verify 40.1 µs (ed25519-dalek README, Intel 10700K)

Keys: seed s (32 random bytes) → SHA-512(s) = (a, prefix); a is clamped into a scalar; public key A = a·B (B the base point).

Sign message M:

1. r = SHA-512(prefix || M) mod L (deterministic nonce).
2. R = r·B.
3. k = SHA-512(R || A || M) mod L.
4. S = (r + k·a) mod L. Signature = R || S (64 bytes).

Verify: check S < L, decode R and A, then accept if S·B = R + k·A (the cofactored form multiplies both sides by 8).

Because A is hashed into k, a signature commits to the public key; this also means the signer must use the matching A, or the private key leaks.

Code

Rust, ed25519-dalek = { version = "2", features = ["rand_core"] }, rand = "0.8".

use ed25519_dalek::{Signature, Signer, SigningKey, VerifyingKey, SIGNATURE_LENGTH};
use rand::rngs::OsRng;

/// Domain separation: prefix every signed payload with what it is,
/// so a signature for one purpose can't be replayed as another.
const CONTEXT: &[u8] = b"myapp/webhook/v1\0";

fn framed(payload: &[u8]) -> Vec<u8> {
    let mut m = Vec::with_capacity(CONTEXT.len() + payload.len());
    m.extend_from_slice(CONTEXT);
    m.extend_from_slice(payload);
    m
}

pub fn keygen() -> (SigningKey, VerifyingKey) {
    let sk = SigningKey::generate(&mut OsRng);
    let vk = sk.verifying_key(); // derived, never supplied separately
    (sk, vk)
}

pub fn sign(sk: &SigningKey, payload: &[u8]) -> [u8; SIGNATURE_LENGTH] {
    sk.sign(&framed(payload)).to_bytes()
}

pub fn verify(vk: &VerifyingKey, payload: &[u8], sig: &[u8]) -> bool {
    let Ok(sig) = Signature::from_slice(sig) else { return false };
    // verify_strict rejects small-order keys and non-canonical encodings,
    // so all honest verifiers agree on validity
    vk.verify_strict(&framed(payload), &sig).is_ok()
}

fn main() {
    let (sk, vk) = keygen();
    let sig = sign(&sk, b"{\"event\":\"paid\"}");
    assert!(verify(&vk, b"{\"event\":\"paid\"}", &sig));
    assert!(!verify(&vk, b"{\"event\":\"refund\"}", &sig));
    // persist: sk.to_bytes() (32 B, secret), vk.to_bytes() (32 B, public)
}

Complexity and constants

• Sign: one fixed-base scalar multiplication, order of 10-20 µs. Verify: double-scalar multiplication, order of 30-60 µs. Batch verify of 64+ signatures: roughly 2x throughput per signature.
• Sizes vs. alternatives: ECDSA P-256 64 B sig / 33-65 B key; RSA-3072 384 B sig, verify fast but sign order of 1 ms; ML-DSA-65 3309 B sig, 1952 B key.
• Hashing the message dominates for inputs beyond a few KiB (SHA-512 at order of 1 GB/s); for big files sign a hash of the file.

Efficiency

• Cost: ed25519-dalek README (Intel 10700K): sign 15.0 µs, verify 40.1 µs, 64-signature batch 1.21 ms. Bound: compute (scalar multiplications); for big payloads, hashing.
• Levers:
  • Batch verification (batch feature, verify_batch) — about 19 µs each at batch 64, roughly 2x (dalek README) — many independent signatures; re-check individually if the batch fails.
  • AVX2 backend, -C target_cpu=native — verify 40.1 → 26.0 µs (dalek README) — x86-64.
  • Keep decoded VerifyingKey values — skips public-key decompression per request — repeated keys.
  • Sign a digest of large data — hashing, not the curve, dominates beyond a few KiB — files and streams.
• Naive → standard → state of the art:
  • Naive · RSA-3072 sign order of 1 ms, re-parse key each request
  • Standard · Ed25519 single verify, order of 30-60 µs
  • State of the art · batched, SIMD Ed25519 verify (about 134,000 cycles per signature at batch 64 in the original paper's software); HMAC when verifier = signer (order of 10-100x faster)

Implementation notes

• Store the 32-byte seed, not an "expanded" key; wrap it with a KMS or keep it in an HSM/secret manager (see secrets management).
• Key IDs: put a kid (e.g., first 8 bytes of SHA-256 of the public key) next to signatures so you can rotate keys and verify old ones.
• Signing large data: Ed25519 hashes the message twice, so the whole message must be available; for streams, sign BLAKE3/SHA-512 of the content (Ed25519ph exists but is rarely supported).
• Constant time: dalek and libsodium are constant time; don't write your own field arithmetic.
• In JWTs the algorithm name is EdDSA; pin it on the verifier.

Pitfalls

• APIs that take the private and public key separately: signing with a mismatched public key leaks the private key (dalek 1.x had this; 2.x fixed it with SigningKey).
• Verification differs between libraries (cofactored vs cofactorless, canonical S): in consensus systems, all nodes must use the same rules. Use verify_strict or ZIP-215 rules consistently.
• Signing without context: a signature over raw JSON for one endpoint is valid for another.
• Signature does not mean secrecy, and does not stop replay: add timestamps or nonces in the signed payload.
• Comparing serialized JSON: sign the exact bytes you send, and verify before parsing.

Variants and alternatives

In production

• Ledgers: Solana transactions (docs).
• Internet infrastructure: DNSSEC algorithm 15 (RFC 8080), Tor onion services v3, TLS 1.3 certificates (supported, less common than ECDSA).
• Remote access, messaging and releases: OpenSSH (ssh-ed25519), Signal (XEdDSA), minisign/signify (OpenBSD releases), Sigstore.

Implementations

Sources

• Bernstein, Duif, Lange, Schwabe, Yang, High-speed high-security signatures, Journal of Cryptographic Engineering, 2012. paper · site
• Josefsson, Liusvaara, RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA), 2017. RFC
• Chalkias, Garillot, Nikolaenko, Taming the many EdDSAs, SSR 2020. paper · eprint
• NIST, FIPS 186-5: Digital Signature Standard, 2023. spec; FIPS 204: Module-Lattice-Based Digital Signature Standard, 2024. spec