Digital Signatures — DSA, ECDSA, and EdDSA

Digital signatures provide three guarantees simultaneously: authentication (it came from the claimed sender), integrity (it was not modified), and non-repudiation (the sender cannot deny sending it). These three properties together are what make digital signatures legally binding in most jurisdictions under e-signature laws (ESIGN in the US, eIDAS in the EU).

Every HTTPS certificate is signed by a CA. Every Git commit can be signed. Every software package distributed through pip, apt, or npm is signed. Every code signing certificate for macOS/Windows applications uses digital signatures. The choice of signature scheme — RSA-PSS, ECDSA, Ed25519 — matters for performance, security, and implementation risk.

How Digital Signatures Work

RSA signature: sign by computing s = hash(m)^d mod n (private key operation). Verify by checking hash(m) == s^e mod n (public key operation).

ECDSA: sign by choosing random k, computing r = (k×G).x mod n, s = k⁻¹(hash(m) + r×privkey) mod n. The critical requirement: k must be randomly generated for EACH signature. Reusing k leaks the private key — this is how Sony PlayStation 3's ECDSA implementation was broken in 2010.

from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat, PrivateFormat, NoEncryption
from cryptography.exceptions import InvalidSignature

# Ed25519 — the correct modern signature scheme
# Deterministic (no random k), fast, side-channel resistant

# Key generation
private_key = Ed25519PrivateKey.generate()
public_key  = private_key.public_key()

# Sign
message = b'Deploy to production: v2.3.1'
signature = private_key.sign(message)
print(f'Signature: {signature.hex()[:32]}... ({len(signature)} bytes)')

# Verify
try:
    public_key.verify(signature, message)
    print('Signature valid ✓')
except InvalidSignature:
    print('Signature invalid ✗')

# Tampered message — verification fails
try:
    public_key.verify(signature, b'Deploy to production: v2.3.2')
except InvalidSignature:
    print('Tampered message detected ✗')

Why ECDSA k-Reuse is Catastrophic

The PlayStation 3 was broken in 2010 by fail0verflow and geohot. Sony used ECDSA to sign PS3 software but used a fixed random number k instead of a truly random one per signature. Given two signatures (r1,s1) and (r2,s2) on messages m1, m2 with the same k:

s1 - s2 = k⁻¹(hash(m1) - hash(m2)) mod n

Since r1 = r2 (same k → same r), we can compute k = (hash(m1) - hash(m2)) × (s1 - s2)⁻¹ mod n. Once k is known, the private key follows immediately.

This is why Ed25519 (EdDSA) was designed to be deterministic — k is derived from the private key and message hash rather than from a random source. No random number generator failure can compromise Ed25519 signatures.

Signature Scheme Comparison

| Scheme | Key Size | Sig Size | Speed | Notes | |---|---|---|---|---| | RSA-PSS-2048 | 2048 bit | 256 bytes | Slow | Legacy, widely supported | | RSA-PSS-4096 | 4096 bit | 512 bytes | Very slow | High security margin | | ECDSA P-256 | 256 bit | 64 bytes | Fast | NIST, TLS standard | | Ed25519 | 256 bit | 64 bytes | Very fast | Best choice for new systems | | CRYSTALS-Dilithium | 1312 bytes | 2420 bytes | Fast | Post-quantum standard (NIST 2024) |

For new systems: Ed25519. For TLS/X.509 compatibility: ECDSA P-256. For post-quantum safety: Dilithium.

Frequently Asked Questions