English
Menu

RSA vs Elliptic-Curve vs Post-Quantum Cryptography: Key Sizes, Speed, Quantum Resistance and Migration Compared

All three are public-key cryptography, used to share keys (key exchange or key encapsulation) and for digital signatures. RSA rests on the difficulty of factoring large numbers, and elliptic-curve cryptography on the difficulty of the discrete logarithm problem on elliptic curves; for the same security, elliptic-curve cryptography needs much shorter keys than RSA. Both, however, would be broken by Shor's algorithm once a large fault-tolerant quantum computer exists. Post-quantum cryptography rests on problems such as lattice problems that are believed to be hard even for quantum computers; in August 2024 the US NIST published standards including the key encapsulation mechanism ML-KEM (FIPS 203) and the signature scheme ML-DSA (FIPS 204). Their main drawback is large keys and signatures.

AspectRSAElliptic-curve cryptographyPost-quantum cryptography (ML-KEM, ML-DSA)
Underlying hard problemFactoring large numbersThe discrete logarithm problem on elliptic curvesFor ML-KEM and ML-DSA, lattice problems (such as Module-LWE, recovering a secret from linear equations with small errors added); there is also SLH-DSA (FIPS 205), a signature scheme based only on hash functions
Key size (guideline)In the NIST SP 800-57 table, the guideline for 128-bit security is a 3072-bit n (384 bytes); 2048 bits corresponds to 112-bit securityIn the same table, the guideline for 128-bit security is 256 bits; in X25519 key exchange the public value sent is 32 bytesAn ML-KEM-768 public key (encapsulation key) is 1,184 bytes, far larger than the 32 bytes of X25519
Ciphertext and signature sizeBoth ciphertexts and signatures are as long as n (384 bytes for 3072 bits)An ECDSA (P-256) signature is two 256-bit values, r and s, for 64 bytes (slightly more depending on the encoding)An ML-KEM-768 ciphertext is 1,088 bytes and an ML-DSA-65 signature is 3,309 bytes
SpeedBecause the public exponent can be small (such as 65537), encryption and signature verification are fast; decryption, signing and key generation are heavyKey generation and signing are much faster than RSA at the same security; signature verification is often slower than RSAML-KEM computation is light and is considered no slower than elliptic-curve key exchange; the size of the data sent tends to be the bigger issue than computation
Quantum resistanceNone: Shor's algorithm breaks it on a large fault-tolerant quantum computerNone: Shor's algorithm also solves the discrete logarithm problem, so it is broken like RSABelieved to be hard to solve efficiently even with quantum computers (this has not been proven)
StandardizationInvented in 1977; in practice used with randomized padding such as OAEP for encryption and PSS for signaturesCurves such as P-256, and X25519 and Ed25519 based on Curve25519, are widely usedPublished by NIST in August 2024 as FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA)
Typical uses todayAs of the mid-2020s, mainly certificates and software signing; TLS 1.3 removed key exchange that sends key material encrypted with RSAAs of the mid-2020s, the mainstay of TLS key exchange (ECDHE); also ECDSA and EdDSA signatures, and resource-constrained devices such as smart cards and embedded systemsAs of 2025, hybrid key exchange combined with X25519 (such as X25519MLKEM768) has started to be used in TLS 1.3; migration of signatures is following after key exchange
MigrationA target of the migration to post-quantum cryptography; replacing signatures, such as in certificates and code signing, is the challengeA target of the migration; during the transition it serves as one half of hybrid key exchange with ML-KEM, providing security against classical computersFor now, migration proceeds step by step with hybrid schemes that combine it with conventional cryptography; designs that make algorithms easy to swap later (crypto agility) are emphasized
Implementation cautionsNever use textbook RSA without padding; key generation needs good-quality randomnessReusing or biasing the per-signature random value (nonce) lets attackers recover the private key; received points must also be checked to lie on the correct curveLarge keys and signatures require checking the impact on packet sizes and memory-constrained devices; watch for bugs in new implementations and for side-channel attacks

Figures are typical orders of magnitude and vary by process generation and product.

When to use which

RSA
When compatibility with existing certificates and systems is required. Fast verification suits uses with many verifiers, but a plan for migrating to post-quantum cryptography is needed.
Elliptic-curve cryptography
When new systems today need key exchange and signatures with short keys and small data. It also suits smart cards and embedded devices. Plan a move to hybrid schemes to prepare for quantum computers.
Post-quantum cryptography (ML-KEM, ML-DSA)
When protecting data that must stay secret for a long time. To prepare for "harvest now, decrypt later", where ciphertext recorded today is decrypted in the future, adopt it first for key exchange in a hybrid scheme.

FAQ

Why does elliptic-curve cryptography need shorter keys than RSA?

Because the best known attacks differ in cost. Factoring has methods much faster than brute force, so RSA keys must be quite long. For the elliptic-curve discrete logarithm problem, even the best known attacks take work on the order of half the key length in bits, so the key only needs to be about twice the security level. In the NIST SP 800-57 table, the guideline for 128-bit security is 3072 bits for RSA versus 256 bits for elliptic-curve cryptography.

Why migrate now when quantum computers do not exist yet?

Because ciphertext intercepted and stored today could be decrypted by future quantum computers (harvest now, decrypt later). On top of that, replacing cryptography takes many years across software, devices and certificate infrastructure. That is why migration is starting with key exchange, which carries data that must stay secret for a long time.

Will quantum computers also break symmetric ciphers such as AES?

They are not targets of Shor's algorithm. Under the simple guideline that Grover's algorithm gives a quadratic speedup in key search, the security level in bits is halved, which can be handled by choosing AES-256 where long-term security is needed. What must be replaced is mainly public-key cryptography such as RSA and elliptic-curve cryptography.

What is a hybrid scheme?

A scheme that uses conventional cryptography and post-quantum cryptography at the same time and combines the results. In key exchange, the shared secrets from X25519 and ML-KEM both go into key derivation, so the resulting key stays protected as long as either one is secure. Post-quantum schemes are new, and implementation errors or new attacks cannot yet be fully ruled out, so the hybrid approach serves as insurance during the transition.

Check your understanding

In the table of NIST SP 800-57, which of the following is the combination of RSA key length (the number of bits of n) and elliptic-curve key length given as the guideline for security comparable to a 128-bit symmetric-key cipher (AES-128)?

  1. AAbout 128 bits for RSA and about 128 bits for elliptic-curve cryptography
  2. BAbout 2048 bits for RSA and about 128 bits for elliptic-curve cryptography
  3. CAbout 3072 bits for RSA and about 256 bits for elliptic-curve cryptography
Show answer and explanation

Answer: C. About 3072 bits for RSA and about 256 bits for elliptic-curve cryptography

Public-key cryptography needs longer keys than symmetric-key cryptography to achieve the same security. In the table of NIST SP 800-57 Part 1, the guideline for 128-bit security is 3072 bits for RSA and 256 to 383 bits for elliptic-curve cryptography. For elliptic-curve cryptography the best known attacks take effort of about half the key length in bits, so a key of about twice the number of security bits suffices, giving the same security with a much shorter key than RSA. 2048-bit RSA is the guideline for 112-bit security.

Which of the following correctly pairs the post-quantum cryptography standards published by the US NIST in August 2024 with their types?

  1. AFIPS 203 ML-KEM is a lattice-based signature scheme, FIPS 204 ML-DSA a hash-based key encapsulation mechanism, and FIPS 205 SLH-DSA a symmetric-key cipher
  2. BFIPS 203 ML-KEM, FIPS 204 ML-DSA and FIPS 205 SLH-DSA are all signature schemes with short keys based on problems on elliptic curves
  3. CFIPS 203 ML-KEM is a lattice-based key encapsulation mechanism, FIPS 204 ML-DSA a lattice-based signature scheme, and FIPS 205 SLH-DSA a hash-based signature scheme
Show answer and explanation

Answer: C. FIPS 203 ML-KEM is a lattice-based key encapsulation mechanism, FIPS 204 ML-DSA a lattice-based signature scheme, and FIPS 205 SLH-DSA a hash-based signature scheme

On August 13, 2024, NIST published three FIPS as the first post-quantum cryptography standards. FIPS 203 ML-KEM (originally named CRYSTALS-Kyber) is a key encapsulation mechanism for sharing keys, and FIPS 204 ML-DSA (CRYSTALS-Dilithium) and FIPS 205 SLH-DSA (SPHINCS+) are digital signature schemes. ML-KEM and ML-DSA rest on the difficulty of lattice problems, such as the Module-LWE problem of recovering a secret from a system of linear equations with small errors added. SLH-DSA rests only on the security of hash functions, so its signatures are large and slow, but it is a safeguard in case a weakness is found in lattice problems.

Which of the following correctly describes the idea of hybrid key exchange, used during the migration to post-quantum cryptography, that combines X25519 (Diffie–Hellman key exchange using an elliptic curve) with ML-KEM?

  1. ABoth shared secrets obtained from the two schemes are fed into key derivation, so the resulting key is secure as long as either one is secure
  2. BOf the two schemes, only the shared secret of whichever finishes first in the handshake is used and the other is discarded
  3. CML-KEM is not used until quantum computers become a reality, and both are prepared so that the switch happens automatically when they do
Show answer and explanation

Answer: A. Both shared secrets obtained from the two schemes are fed into key derivation, so the resulting key is secure as long as either one is secure

ML-KEM is a new scheme, and the possibility of implementation errors or new attacks being found cannot yet be fully ruled out. X25519, on the other hand, is weak against quantum computers but has a long track record of security against classical computers. In hybrid key exchange both shared secrets are concatenated and fed into a key derivation function, so an attacker must break both to obtain the key, and communications recorded today are also protected against decryption by future quantum computers. As of 2025, this combination (such as X25519MLKEM768) has started to be used in TLS 1.3.

  1. Once large fault-tolerant quantum computers are built, which ciphers are expected to have their security seriously undermined by Shor's algorithm?
  2. Which is the most appropriate reason to hurry the migration to post-quantum cryptography even before large quantum computers exist?
  3. Which of the following correctly describes a problem with using textbook RSA (computing c = m^e mod n directly from the plaintext m) without padding in real communication?

Practice Applied Cryptography questions

Key terms explained

RSA cryptosystem
A public-key cryptosystem devised in 1977 by Rivest, Shamir and Adleman. The public key is the product n of two large primes p and q together with a public exponent e, and the private key is the d that satisfies e × d ≡ 1 (mod (p − 1)(q − 1)). Encryption is c = m^e mod n and decryption m = c^d mod n. Its security rests on the difficulty of factoring n, and it can be used for both encryption and signatures. In practice it is combined with randomized padding such as OAEP or PSS.
Elliptic-curve cryptography
A family of public-key cryptosystems that use arithmetic on points of an elliptic curve over a finite field. Their security rests on the difficulty of recovering the secret integer k from the point kG, the curve point G multiplied by k (the elliptic-curve discrete logarithm problem). For the same security they need much shorter keys than RSA: a 256-bit key is the guideline for about the same security as 3072-bit RSA (128-bit security). They are used for key exchange (ECDH and ECDHE) and signatures (ECDSA and EdDSA), with curves such as P-256 and Curve25519 in wide use. Because Shor's algorithm breaks them, they are among the schemes to be replaced by post-quantum cryptography.
Post-quantum cryptography
Cryptography that bases its security on mathematical problems believed to be hard to solve efficiently even for quantum computers, such as lattice problems and hash functions. It runs on conventional computers and is used to replace RSA and elliptic-curve cryptography, which Shor's algorithm can break.
ML-KEM
A lattice-based key encapsulation mechanism (KEM) standardized by the US NIST in August 2024 as FIPS 203. The name stands for Module-Lattice-Based Key-Encapsulation Mechanism, and it is based on CRYSTALS-Kyber. Its security rests on the difficulty of the Module-LWE problem, recovering a secret from a system of linear equations with small errors added, which is believed to be hard even for quantum computers. There are three parameter sets: ML-KEM-512, ML-KEM-768 and ML-KEM-1024. It is used in protocols such as TLS to replace, or be combined with, ECDHE key exchange.
Shor's algorithm
A quantum algorithm that solves factoring of large integers and the discrete logarithm problem in polynomial time by finding periods with the quantum Fourier transform. It was published by Peter Shor in 1994. It can break RSA and elliptic-curve cryptography, but running it requires a large fault-tolerant quantum computer.
Diffie–Hellman key exchange
A method by which two parties create a shared secret using only a public channel, published by Diffie and Hellman in 1976. A prime p and a generator g are public; A and B choose secret values a and b, send each other g^a mod p and g^b mod p, and each raises the other's value to their own secret, both obtaining the same g^(ab) mod p. Its security rests on the difficulty of the discrete logarithm problem. The version on an elliptic curve is ECDH, and versions using throwaway values for each connection are DHE and ECDHE, which provide forward secrecy. It does not authenticate the other party, so it is combined with signatures and certificates to prevent man-in-the-middle attacks.
Crypto agility
The ability to switch to another scheme without major redesign of a system when a cryptographic algorithm or key length becomes insecure. It is increased by keeping an inventory of which cryptography is used where, making algorithms selectable through configuration or protocol negotiation, and including algorithm identifiers in data formats. It has been emphasized in migrations away from MD5, SHA-1 and short RSA keys, and in the migration to post-quantum cryptography.
Public-key cryptography
A cryptographic method that uses a matched pair of different keys for encryption and decryption: a public key and a private key. The public key may be known to anyone, while only its owner holds the private key. It makes key distribution easy but is computationally heavy, so it is combined with symmetric-key cryptography for encrypting the data itself. RSA and elliptic-curve cryptography are typical examples.

Related comparisons