Digital Signatures

Introduction

A digital signature is a mathematical scheme that provides proof that a digital message or document was created by a known sender (authentication), that the sender cannot deny having signed it (non-repudiation), and that the message has not been altered in transit (integrity). Digital signatures are the electronic equivalent of handwritten signatures and wax seals, but they are far more difficult to forge.

Unlike a simple checksum or MAC (Message Authentication Code), digital signatures use asymmetric cryptography: the signer uses their private key to create the signature, and anyone can use the signer's public key to verify it. This asymmetry is what enables non-repudiation -- only the holder of the private key could have produced the signature.

Digital signatures are foundational to modern internet security. They secure TLS/HTTPS certificate verification, software distribution, email authentication, cryptocurrency transactions, electronic contracts, and government document systems worldwide.

"A digital signature is the most important cryptographic primitive. Without it, you cannot build authentication, non-repudiation, or trust -- the three pillars of secure communication." -- Whitfield Diffie, co-inventor of public key cryptography

How Digital Signatures Work

The Signing Process

Creating a digital signature involves two steps:

1. Hash the message: The signer computes a cryptographic hash (e.g., SHA-256) of the message, producing a fixed-size digest. This ensures that the signature covers the entire message regardless of its length, and that even a single bit change produces a completely different hash.
2. Encrypt the hash with the private key: The signer applies the signature algorithm to the hash using their private key, producing the signature value. The specific mathematics depend on the algorithm (RSA, ECDSA, or Ed25519).

// Digital signature creationmessage = "Transfer $1000 to Account 12345"hash = SHA256(message)// hash = "a1b2c3d4e5f6..."signature = Sign(hash, signer_private_key)// signature = "3045022100..."// Send: message + signature + signer's certificate

The Verification Process

Any recipient with the signer's public key can verify the signature:

1. Hash the received message: The verifier independently computes the SHA-256 hash of the message they received.
2. Decrypt the signature with the public key: The verifier applies the verification algorithm to the signature using the signer's public key, recovering the hash value the signer computed.
3. Compare: If the two hash values match, the signature is valid -- the message is authentic and unaltered. If they differ, either the message was tampered with or the signature was not created by the claimed signer.

// Digital signature verificationreceived_message = "Transfer $1000 to Account 12345"received_signature = "3045022100..."signer_public_key = GetPublicKeyFromCertificate(cert)computed_hash = SHA256(received_message)is_valid = Verify(received_signature, computed_hash, signer_public_key)if is_valid: print("Signature is valid - message is authentic")else: print("INVALID - message may be tampered or forged")

Security Properties

A secure digital signature scheme provides three fundamental guarantees:

Non-repudiation is the property that distinguishes digital signatures from MACs (Message Authentication Codes). With a MAC, both the sender and receiver share the same secret key, so either party could have generated the MAC. With a digital signature, only the private key holder can sign, making the signature attributable to a specific individual. This property is essential for legal contracts, financial transactions, and regulatory compliance.

Signature Algorithms

RSA Signatures

RSA signatures were described in the original 1977 paper by Rivest, Shamir, and Adleman. The mathematics are the inverse of RSA encryption: the signer "encrypts" the hash with the private key, and the verifier "decrypts" with the public key.

Signing:s = h^d mod n (where h is the hash, d is the private exponent, n is the modulus)

Verification:h' = s^e mod n (where e is the public exponent; verify h' equals h)

Raw "textbook RSA" signatures are insecure. In practice, a padding scheme is essential:

• PKCS#1 v1.5: The original padding scheme, still widely used. It is deterministic (same message always produces the same signature). The Bleichenbacher attack (1998) showed vulnerabilities in the encryption variant, leading to caution about its signature use.
• PSS (Probabilistic Signature Scheme): Introduced by Bellare and Rogaway in 1996, PSS adds randomness to the signature process. It has a provable security reduction to the RSA problem and is recommended by NIST and other standards bodies. PSS is the required padding for new implementations.

DSA and ECDSA

The Digital Signature Algorithm (DSA) was proposed by NIST in 1991 and standardized in FIPS 186. Unlike RSA, DSA can only be used for signatures, not encryption. It is based on the discrete logarithm problem.

ECDSA (Elliptic Curve Digital Signature Algorithm) is the elliptic curve variant of DSA. It provides equivalent security with much smaller key and signature sizes. ECDSA is used in TLS certificates, Bitcoin transactions, and many other protocols.

A critical requirement for both DSA and ECDSA is that the random nonce k used during signing must be truly random and secret. If k is ever reused with the same private key, or if it is predictable, the private key can be recovered. This is not a theoretical concern -- in 2010, the PlayStation 3's ECDSA implementation used a fixed value of k, allowing attackers to extract Sony's private signing key and sign arbitrary software.

// ECDSA signing (simplified)// k MUST be cryptographically random and unique per signaturek = random_integer(1, n-1)(x1, y1) = k * G // scalar multiplication on the curver = x1 mod ns = k^(-1) * (hash + r * private_key) mod nsignature = (r, s)

Ed25519 and EdDSA

Ed25519 is a modern digital signature algorithm designed by Daniel J. Bernstein and colleagues in 2011. It is an instance of the EdDSA (Edwards-curve Digital Signature Algorithm) scheme using the Curve25519 elliptic curve in twisted Edwards form.

Ed25519 was designed to address the practical pitfalls of ECDSA:

• Deterministic signatures: The nonce is derived from the message and private key using a hash function, eliminating the catastrophic risk of nonce reuse
• Fast constant-time implementation: The algorithm was co-designed with its implementation, making it resistant to side-channel attacks by construction
• Small signatures: 64 bytes (512 bits), compared to variable-length RSA signatures
• Small keys: 32-byte public keys, 64-byte private keys
• No patents: Completely free to use

Ed25519 is now the recommended signature algorithm for SSH (since OpenSSH 6.5), is supported in TLS 1.3, and is used by Signal, WireGuard, and many modern cryptographic systems.

"Ed25519 was designed to prevent the kinds of implementation mistakes that have repeatedly led to real-world private key compromises in DSA and ECDSA." -- Daniel J. Bernstein, designer of Ed25519

Algorithm Comparison

For new systems, Ed25519 is generally the recommended choice due to its speed, small size, deterministic operation, and resistance to implementation errors. RSA remains important for backward compatibility and in systems that require the separation of signing and verification performance (RSA verification is very fast). ECDSA remains dominant in existing PKI infrastructure and cryptocurrency.

Certificate Chains and Trust

In practice, verifying a digital signature requires knowing that the public key genuinely belongs to the claimed signer. This is solved by digital certificates and certificate chains.

A digital certificate (X.509) binds a public key to an identity. The certificate itself is signed by a Certificate Authority (CA) using the CA's private key. The CA's certificate is in turn signed by a higher-level CA, forming a chain that terminates at a root CA whose certificate is pre-installed in operating systems and browsers.

// Certificate chain verificationServer Certificate: "example.com" signed by Intermediate CAIntermediate CA: "Let's Encrypt R3" signed by Root CARoot CA: "ISRG Root X1" pre-trusted in OS/browserVerification process:1. Verify server cert signature using Intermediate CA's public key2. Verify Intermediate CA cert signature using Root CA's public key3. Root CA is already trusted (in the trust store)4. All signatures valid => server certificate is trusted

If any signature in the chain fails verification, or if any certificate has been revoked (checked via CRL or OCSP), the entire chain is rejected. For a comprehensive treatment of this infrastructure, see Public Key Infrastructure.

Code Signing

Code signing uses digital signatures to verify the authenticity and integrity of software. When a developer signs an executable, library, or package, end users and operating systems can verify that the code has not been tampered with and comes from a known publisher.

The importance of code signing was dramatically illustrated by the SolarWinds attack (2020), where attackers compromised the build process to inject malicious code into a legitimately signed software update. The malicious update was signed with SolarWinds' valid code-signing certificate, so it passed all verification checks. This demonstrated that code signing guarantees authenticity of the signing entity, not the absence of malicious code -- if the signing process itself is compromised, the signature provides false assurance.

Attacks and Vulnerabilities

Digital signature schemes can be attacked at multiple levels:

Key Recovery from Nonce Reuse (ECDSA/DSA): If the random nonce k is reused across two different signatures with the same private key, an attacker can solve a simple system of equations to recover the private key. This affected the PS3 (2010), some Bitcoin wallets, and numerous other implementations.

Hash Collision Attacks: If an attacker can find two messages with the same hash (a collision), a signature on one message is valid for the other. The SHA-1 collision demonstrated by Google's SHAttered project (2017) showed that this is practical for SHA-1, which is why SHA-256 or SHA-3 should be used with all signature schemes.

Bleichenbacher's Attack on RSA PKCS#1 v1.5: Daniel Bleichenbacher demonstrated in 1998 that RSA PKCS#1 v1.5 encryption padding is vulnerable to an adaptive chosen-ciphertext attack. Variants of this attack (ROBOT, 2017) continue to affect implementations. RSA-PSS was designed to prevent this class of attacks.

Fault Injection: Inducing computational errors during signing (via voltage glitching, laser pulses, or electromagnetic interference) can cause the signature algorithm to leak private key material. RSA-CRT implementations are particularly vulnerable: a single faulty signature reveals the private key. Countermeasures include signature verification before output and redundant computation.

Quantum Threats: Shor's algorithm can break RSA, DSA, and ECDSA on a sufficiently large quantum computer. NIST has standardized post-quantum signature algorithms (ML-DSA/CRYSTALS-Dilithium, SLH-DSA/SPHINCS+) as replacements. The transition is expected to take many years.

Real-World Applications

Digital signatures are ubiquitous in modern computing:

• TLS/HTTPS: Every TLS handshake involves the server proving its identity by signing a challenge with its private key. The client verifies the signature using the certificate's public key.
• Email (S/MIME, PGP): Signed emails prove the sender's identity and that the email content has not been modified. S/MIME uses X.509 certificates; PGP uses a web of trust model.
• Cryptocurrency: Every Bitcoin or Ethereum transaction is digitally signed with the sender's private key. The signature proves ownership of the funds without revealing the private key.
• Document Signing: PDF documents can include digital signatures conforming to the PAdES standard. Many countries accept digitally signed documents as legally binding under regulations like the EU's eIDAS.
• Secure Boot: UEFI Secure Boot verifies that each piece of boot software (firmware, bootloader, OS kernel) is signed by a trusted authority before executing it, preventing bootkits and rootkits.
• Git Commits: Developers can sign Git commits and tags with GPG or SSH keys to prove authorship and prevent tampering with repository history.

For related cryptographic topics, see Hash Functions (used to create the digest that is signed), RSA (the mathematics behind RSA signatures), and Public Key Infrastructure (the trust framework for verifying certificates).

References

• Rivest, R., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." Communications of the ACM, 21(2), 120-126.
• NIST (2013). FIPS 186-4: Digital Signature Standard (DSS).
• Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B.-Y. (2012). "High-speed high-security signatures." Journal of Cryptographic Engineering, 2(2), 77-89.
• Josefsson, S., & Liusvaara, I. (2017). RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA).
• Bellare, M., & Rogaway, P. (1996). "The Exact Security of Digital Signatures -- How to Sign with RSA and Rabin." EUROCRYPT '96, Springer.
• Bleichenbacher, D. (1998). "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS#1." CRYPTO '98, Springer.
• Stevens, M., et al. (2017). "The First Collision for Full SHA-1." CRYPTO 2017, Springer.
• Shor, P. (1994). "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." IEEE FOCS, 124-134.
• NIST (2024). FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA).
• European Parliament (2014). Regulation (EU) No 910/2014 (eIDAS) on electronic identification and trust services.