↓ Skip to main content
Le Site de François
  1. Index/

ECDSA (Elliptic Curve Digital Signature Algorithm)

Cryptography Signatures Pki Tls Ecc Pqc

ECDSA (Elliptic Curve Digital Signature Algorithm) is the elliptic curve analogue of DSA, standardised in FIPS 186 and the IETF, that produces digital signatures using a private key and verifies them with the corresponding public key. It is the most widely deployed signature algorithm in X.509 certificates (P-256 with SHA-256 is the default for certificate authorities issuing TLS certificates), in code signing (Authenticode, macOS, Linux package signing), in TLS 1.3 certificate authentication, in SSH host keys and user keys (though Ed25519 is increasingly preferred), and in blockchain and cryptocurrency systems. An ECDSA signature over a message m with private key d on curve with base point G produces a pair (r, s), where r is the x-coordinate of an ephemeral public key k × G and s encodes the relationship between the message hash, r, the private key d, and the nonce k. Verification requires only the public key Q = d × G and is fast; signing requires the private key and a nonce.

ECDSA’s most important operational characteristic — and its most dangerous — is its per-signature nonce requirement. Each signature requires a freshly generated, cryptographically random, secret, and unique scalar k. If k is ever reused across two signatures with the same private key (even accidentally, due to a broken random number generator), the private key can be algebraically recovered from the two signatures alone — no other information is needed. This vulnerability has been exploited in practice: the PlayStation 3 used a constant k in ECDSA, allowing its signing key to be extracted; similar attacks have recovered Bitcoin private keys from wallets using weak entropy. The safe solution is RFC 6979 deterministic ECDSA, which derives k deterministically from the message hash and private key using HMAC-DRBG, eliminating the random number dependency and making signatures reproducible without sacrificing security. Alternatively, EdDSA (Ed25519, Ed448) solves this problem architecturally by using a hash-based nonce derived from the private key and message — making it impossible to accidentally reuse a nonce — which is why EdDSA is generally preferred over ECDSA for new deployments where the curve choices overlap. ECDSA signatures are compact: a P-256 ECDSA signature is 64 bytes (two 32-byte integers encoded as DER adds overhead to 70–72 bytes), compared to 256 bytes for a 2048-bit RSA signature.

ECDSA’s quantum vulnerability is identical to ECC’s generally: Shor’s algorithm recovers the private key from the public key, making every ECDSA key — at any curve size — breakable by a CRQC. NIST IR 8547 designates ECDSA for deprecation in new systems after 2030. The HNDL threat applies specifically to ECDSA signatures on long-lived artifacts: code signing certificates with multi-year validity, CA certificates with decade-long lifetimes, and firmware update signatures that must remain verifiable on deployed hardware years from now. A signed firmware image whose signature was produced with a P-256 ECDSA key today will be forgeable — and therefore unsafely upgradeable — once a CRQC can recover that signing key. The replacement is ML-DSA for new signatures, with ECDSA retained only during the hybrid transition period where both an ECDSA and an ML-DSA signature are produced and both verified. cert-manager and Vault’s PKI engine are the primary automation paths for migrating X.509 certificate issuance from ECDSA P-256 to ML-DSA across a Kubernetes or enterprise infrastructure.

Related

ECC (Elliptic Curve Cryptography)

Cryptography Pki Tls Signatures Key-Exchange Pqc
Elliptic Curve Cryptography (ECC) is a family of public-key cryptographic algorithms built on the mathematics of elliptic curves over finite fields. Its security rests on the Elliptic Curve Discrete Logarithm Problem (ECDLP): given a public point Q = k × G on a curve (where G is a fixed base point and k is the private key scalar), recovering k from Q and G is computationally infeasible on classical computers. The practical advantage over RSA is dramatic key size efficiency: a 256-bit ECC key provides roughly the same classical security as a 3072-bit RSA key, because the best known classical algorithms for ECDLP (Pollard’s rho) are exponential whereas the best RSA algorithms (GNFS) are sub-exponential. This size difference has compounding benefits — smaller keys mean faster operations, smaller certificates, smaller TLS handshake messages, and lower power consumption on constrained devices. ECC is now the dominant choice for all new asymmetric cryptography deployments: TLS 1.3 mandates ECDHE for key exchange, and ECDSA or EdDSA for authentication; SSH defaults to Ed25519; code signing infrastructure increasingly uses ECDSA P-256 or Ed25519.

ML-DSA (Module-Lattice-Based Digital Signature Algorithm)

Cryptography Pqc Signatures Pki Tls Nist Lattice
ML-DSA (Module-Lattice-Based Digital Signature Algorithm), standardised as NIST FIPS 204 in August 2024, is the primary post-quantum replacement for digital signatures. It replaces ECDSA, EdDSA, and RSA PSS/PKCS#1 signatures in X.509 certificates, code signing, TLS client and server authentication, SSH, JWT signing, and any other context where a party proves possession of a private key by producing a signature that others verify with the public key. ML-DSA is derived from CRYSTALS-Dilithium, the submission that won NIST’s lattice-based signature selection, and its security rests on the Module Learning With Errors (MLWE) and Module Short Integer Solution (MSIS) problems — the same mathematical family as ML-KEM, which is significant because both algorithms can share implementation code and hardware acceleration for the underlying polynomial arithmetic (NTT, number-theoretic transform).

RSA (Rivest–Shamir–Adleman)

Cryptography Pki Tls Signatures Key-Exchange Pqc
RSA (Rivest–Shamir–Adleman), published in 1977, was the first widely adopted public-key cryptosystem and for decades the most deployed asymmetric algorithm in existence. Its security rests on the integer factorisation problem: given a public modulus n = p × q (the product of two large primes), recovering p and q is computationally infeasible on classical computers for sufficiently large n. The public key is the pair (n, e) and the private key is (n, d), where e and d are related by the modular arithmetic of Euler’s totient function. RSA enables two operations: encryption (the sender uses the public key to encrypt a message that only the private key holder can decrypt) and signing (the private key holder produces a signature that anyone with the public key can verify). In practice, RSA encryption is used almost exclusively for key encapsulation — encrypting a randomly generated symmetric key — rather than encrypting arbitrary data directly, both because RSA is slow and because direct RSA encryption of large messages requires padding schemes that are historically error-prone.