What is RSA encryption?

RSA is a public-key (asymmetric) cryptosystem that uses a mathematically linked key pair: a public key to encrypt or verify and a private key to decrypt or sign. Its security relies on the difficulty of factoring the product of two large prime numbers, and it underpins TLS, secure email, and digital signatures.

How does RSA encryption work?

RSA creates a modulus by multiplying two large random primes and derives a public exponent and a matching private exponent from it. Anyone can encrypt with the public key, but only the holder of the private key can reverse the operation, because computing the private key would require factoring the modulus.

RSA is considered secure when used with adequately large keys, typically 2048 bits or more, and correct padding such as OAEP. It becomes insecure with small keys, textbook unpadded RSA, or poor random number generation, and large-scale quantum computers would eventually break it using Shor's algorithm.

What key size should I use for RSA?

A 2048-bit key is the common minimum for general use, while 3072- or 4096-bit keys are recommended for stronger long-term security. Larger keys are exponentially harder to factor but slow down operations, which is why many systems now favor elliptic-curve cryptography for equivalent strength with smaller keys.

RSA vs ECC: which is better?

ECC provides the same security as RSA with much smaller keys, so a 256-bit ECC key roughly matches a 3072-bit RSA key, making ECC faster and more efficient for constrained devices. RSA remains widely used for compatibility, but newer systems increasingly prefer ECC for key exchange and signatures.

Why is RSA used for key exchange instead of encrypting data directly?

RSA is slow and can only encrypt small amounts of data no larger than its key, so it is impractical for bulk encryption. Instead it encrypts or negotiates a small symmetric key, such as an AES key, which then efficiently encrypts the actual message.

⚿ Cryptography

RSA Encryption Explained: How Public-Key Cryptography Works

RSA encryption is one of the first and most influential public-key cryptosystems, named after its inventors Rivest, Shamir, and Adleman. Unlike symmetric ciphers where both parties share one secret key, RSA uses a key pair: a public key that anyone can use to encrypt or verify, and a private key that only the owner holds. This asymmetry underpins secure key exchange, digital signatures, and certificate-based trust across the internet. Understanding how RSA works clarifies the foundations of modern public-key cryptography.

The Hard Problem Behind RSA

RSA's security rests on the integer factorization problem: given a large number that is the product of two big prime numbers, it is computationally infeasible to recover those primes. Multiplying two primes is easy; factoring their product back into primes is believed to be hard for classical computers when the numbers are large enough. RSA turns this asymmetry into a usable cryptosystem.

Because factoring gets easier as hardware improves and algorithms advance, RSA key sizes have grown over time. A 2048-bit modulus is a common baseline, with 3072-bit or 4096-bit keys used where stronger long-term security is required.

How RSA Key Generation Works

Generating an RSA key pair follows a precise sequence:

Choose two large, distinct random prime numbers, p and q.
Compute the modulus n = p × q. The bit length of n is the RSA key size.
Compute Euler's totient φ(n) = (p − 1)(q − 1), or the Carmichael function λ(n).
Choose a public exponent e that is coprime to φ(n). The value 65537 is almost universally used because it is prime and its binary form makes exponentiation fast.
Compute the private exponent d as the modular multiplicative inverse of e modulo φ(n), so that e × d ≡ 1 (mod φ(n)).

The public key is the pair (n, e). The private key is d (kept secret, often stored alongside p and q for faster computation). The primes p and q must be discarded or protected, because anyone who learns them can derive d.

Encryption and Decryption Mechanics

RSA operates on numbers, so a message is first encoded as an integer m less than n. The core operations are modular exponentiations:

Encryption: ciphertext c = m^e mod n
Decryption: plaintext m = c^d mod n

Decryption recovers the original message because of Euler's theorem, which guarantees that raising m to the power e·d modulo n returns m. In practice, implementations speed up decryption using the Chinese Remainder Theorem (CRT) with p and q, which is significantly faster than a single exponentiation modulo n.

# Textbook RSA (INSECURE without padding - illustration only)
n = p * q
c = pow(m, e, n)      # encrypt
m = pow(c, d, n)      # decrypt

Why Textbook RSA Is Unsafe

The bare mathematical operations above, sometimes called textbook RSA, must never be used directly. Raw RSA is deterministic (the same plaintext always encrypts to the same ciphertext), which leaks information, and it is vulnerable to a range of algebraic and chosen-ciphertext attacks. Secure RSA always uses randomized padding:

RSA-OAEP (Optimal Asymmetric Encryption Padding) is the standard for encryption. It adds randomness and structure so that identical plaintexts produce different ciphertexts and chosen-ciphertext attacks are thwarted.
RSA-PSS (Probabilistic Signature Scheme) is the recommended padding for signatures.

The older PKCS#1 v1.5 padding is still encountered but has been the source of many practical attacks and should be avoided in new designs.

How RSA Is Used in Practice

RSA is comparatively slow and can only encrypt data smaller than the modulus, so it is rarely used to encrypt bulk data directly. Instead it is used for:

Key encapsulation: encrypting a randomly generated symmetric key (for example, an AES key) which then encrypts the actual message. This hybrid approach combines RSA's key-distribution advantage with the speed of symmetric ciphers.
Digital signatures: signing a hash of a document with the private key so anyone can verify authenticity with the public key. See digital signatures for how RSA compares with ECDSA and EdDSA.
Certificates: RSA keys are widely embedded in X.509 certificates that authenticate servers in TLS.

RSA Compared With Elliptic Curves

RSA is secure but its keys are large. To match the security of a 256-bit elliptic curve key, RSA needs roughly a 3072-bit key. This size gap means elliptic-curve algorithms are increasingly preferred for new deployments because they offer equivalent security with smaller keys, faster operations, and lower bandwidth. RSA remains extremely common, however, due to its maturity and broad compatibility.

It is also worth noting that both RSA and elliptic-curve systems are vulnerable to sufficiently large quantum computers running Shor's algorithm, which motivates ongoing research into post-quantum cryptography.

Key Takeaways

RSA is an asymmetric cryptosystem whose security depends on the difficulty of factoring the product of two large primes.
Key generation produces a public key (n, e) and a private key d, with 65537 the standard public exponent and 2048 bits a common minimum modulus size.
Encryption and decryption are modular exponentiations, but raw textbook RSA is insecure and must use randomized padding like OAEP for encryption and PSS for signatures.
RSA is typically used for key encapsulation and signatures rather than bulk data, pairing with symmetric ciphers in hybrid schemes.
Elliptic-curve cryptography achieves equivalent security with much smaller keys, and both RSA and ECC face future risk from quantum computing.

rsapublic-keyasymmetric-encryptioncryptographykey-exchange