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

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.

RSA’s operational security is entirely determined by key size. A 512-bit RSA key was broken in 1999; 768-bit in 2009; 1024-bit is considered insecure and deprecated; 2048-bit is the current minimum considered safe against classical attacks, and 3072-bit or 4096-bit is recommended for new keys with long lifetime requirements. The dominant padding schemes are OAEP (Optimal Asymmetric Encryption Padding) for encryption and PSS (Probabilistic Signature Scheme) for signatures — both specified in PKCS#1 v2.2 (RFC 8017). The older PKCS#1 v1.5 padding remains in wide deployment for historical reasons but carries known vulnerabilities (Bleichenbacher’s 1998 padding oracle attack against RSA encryption, and related attacks against TLS 1.2 RSA key exchange that necessitated the RFC 7568 deprecation of those cipher suites). RSA private key operations are computationally expensive: a 2048-bit RSA signature requires roughly 1000× more CPU than an equivalent ECDSA operation at the same security level, which is why ECC-based algorithms have largely displaced RSA for new deployments in TLS and SSH.

RSA is the primary target of PQC migration. Shor’s algorithm running on a CRQC solves integer factorisation in polynomial time, meaning all RSA keys — at any size — become trivially breakable. NIST IR 8547 designates RSA for deprecation in new systems after 2030 and full disallowance after 2035. The HNDL (Harvest Now, Decrypt Later) threat is particularly acute for RSA key encapsulation: TLS sessions using RSA key exchange recorded today can be retroactively decrypted once a CRQC exists. TLS 1.3 mitigated part of this by removing RSA key exchange entirely (all TLS 1.3 sessions use ephemeral Diffie-Hellman, providing forward secrecy), but RSA signatures on X.509 certificates remain in the chain of every HTTPS connection. The replacement for RSA key encapsulation is ML-KEM; the replacement for RSA signatures is ML-DSA (primary) or SLH-DSA (hash-based conservative alternative). HSMs protecting RSA signing keys must be re-keyed with ML-DSA keys and re-certified under the new algorithm before the deprecation deadlines.

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.

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.

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).