Digital Signatures Explained: RSA, ECDSA, and EdDSA

Digital signatures are the cryptographic mechanism that proves a message or document genuinely came from a specific key holder and has not been altered. They provide authenticity, integrity, and non-repudiation, meaning the signer cannot plausibly deny having signed. Digital signatures secure software updates, TLS certificates, legal documents, cryptocurrency transactions, and more. This article explains how the three dominant signature schemes work: RSA, ECDSA, and EdDSA.

How Digital Signatures Work in Principle

A digital signature uses a public-key (asymmetric) key pair. The relationship is the reverse of encryption:

• The signer uses their private key to produce a signature over a message.
• Anyone can use the corresponding public key to verify that signature.

Because only the private key can create a valid signature, a successful verification proves the message came from the key owner. And because the signature is bound to the exact message content, any change invalidates it.

In practice, signatures are not computed over the whole message directly. The message is first reduced with a cryptographic hash such as SHA-256, and the signature is computed over the fixed-size digest. This hash-then-sign approach is efficient and lets signatures cover data of any size.

Signatures Versus MACs

A signature is often confused with a MAC like HMAC. The critical difference is the key model:

• A MAC uses one shared secret key, so anyone who can verify can also forge. It cannot provide non-repudiation.
• A digital signature uses a private/public key pair, so verification requires only the public key. The signer alone can create signatures, enabling non-repudiation.

This makes signatures suitable for public verification and third-party trust, which is why they underpin certificates and code signing.

RSA Signatures

RSA can be used for signing as well as encryption. Conceptually the signer applies the private key to the message hash and verifiers apply the public key to check it. Two padding schemes exist:

• RSA-PSS (Probabilistic Signature Scheme) is the modern, recommended padding. It incorporates randomness and has a strong security proof.
• PKCS#1 v1.5 is an older deterministic padding still widely deployed for compatibility, though PSS is preferred for new designs.

RSA signatures are large (matching the key size, for example 2048 or 3072 bits) and verification is fast because the public exponent is small. This makes RSA attractive where signatures are verified far more often than they are created, such as certificate validation.

ECDSA: Elliptic Curve Signatures

ECDSA (Elliptic Curve Digital Signature Algorithm) brings signatures to elliptic curve cryptography, offering much smaller signatures and keys than RSA for equivalent security. A 256-bit curve produces roughly 64-byte signatures at 128-bit security.

ECDSA signing uses a per-signature random value called a nonce (k):

1. Hash the message to a value e.
2. Generate a random secret nonce k and compute a curve point; its x-coordinate gives the value r.
3. Compute s from k, r, e, and the private key.
4. The signature is the pair (r, s).

The nonce is a notorious source of catastrophic failure. If k is ever reused across two signatures, or is even slightly predictable, the private key can be recovered with straightforward algebra. Real-world breaches have exploited exactly this. The defense is deterministic nonce generation as specified in RFC 6979, which derives k from the private key and message hash so it is unique and unpredictable without relying on a random number generator at signing time.

EdDSA and Ed25519

EdDSA (Edwards-curve Digital Signature Algorithm), most commonly instantiated as Ed25519, is a modern scheme designed to eliminate ECDSA's sharp edges. It is based on twisted Edwards curves and the Schnorr signature construction. Its advantages include:

• Deterministic by design: the nonce is derived from the private key and message via hashing, so there is no reliance on a random number generator and no nonce-reuse risk.
• Fast and simple: signing and verification are efficient, and the algorithm avoids many error-prone implementation choices.
• Constant-time friendly: the design encourages implementations that resist timing side channels.
• Small: Ed25519 public keys are 32 bytes and signatures are 64 bytes.

These properties make Ed25519 a strong default for new systems, and it is widely supported in SSH, TLS, and signing tools.

# Verifying a signature (conceptual flow)
digest    = SHA-256(message)
is_valid  = verify(public_key, digest, signature)
# is_valid is true only if the holder of the matching
# private key signed exactly this message

Security Considerations

Signatures are only as trustworthy as the surrounding practices:

• Protect the private key. Anyone who obtains it can forge signatures. Hardware security modules and secure enclaves help.
• Bind the public key to an identity. A signature proves a key signed, not who owns the key. That binding comes from a public key infrastructure using certificates.
• Use strong hashing. A collision in the hash function can let one signature apply to a different message, which is why deprecated hashes like MD5 and SHA-1 are unsafe for signatures.
• Prefer misuse-resistant schemes. EdDSA or RSA-PSS reduce the chance of implementation mistakes compared to legacy options.
• Like RSA and ECC, these schemes are vulnerable to future quantum computers, motivating post-quantum signature research.

Key Takeaways

• Digital signatures use a private key to sign and a public key to verify, providing authenticity, integrity, and non-repudiation.
• Signatures use a hash-then-sign approach and differ from MACs by using asymmetric keys, enabling public verification.
• RSA signatures are large but verify quickly; use RSA-PSS padding rather than legacy PKCS#1 v1.5 for new systems.
• ECDSA is compact but critically depends on a unique, unpredictable nonce; reuse or bias leaks the private key, so use deterministic nonces (RFC 6979).
• EdDSA/Ed25519 is deterministic, fast, and misuse-resistant, making it an excellent default for modern applications.