Skip to content
Back to search results

RSA Cryptosystem

Introduced by
Ronald Rivest
Year
1978
Type
asymmetric encryption algorithm
Family
Public-key cryptography
Font size

What does it do?

RSA is a foundational public-key cryptosystem developed by Rivest, Shamir, and Adleman in 1978.

It enables secure encryption and digital signatures by using a pair of mathematically linked keys: a public key for encryption and a private key for decryption. RSA's security relies on the computational difficulty of factoring large composite numbers into their prime factors.

The intuition behind the method

RSA works on a simple mathematical principle: it is easy to multiply two large prime numbers together, but extremely difficult to reverse the process by factoring their product. Each user generates two keys from the product of two large primes. The public key is shared openly and used to encrypt messages, while the private key is kept secret and used to decrypt them. The security comes from the fact that without knowing the prime factors, an attacker cannot practically derive the private key from the public key.

History

RSA was published in 1978 and became one of the first practical public-key cryptosystems. It fundamentally changed cryptography by enabling secure communication without pre-shared secret keys. The algorithm was patented in the United States until 2000, after which it entered the public domain. RSA has been continuously analyzed and refined over nearly five decades, with modern variants incorporating padding schemes and larger key sizes to counter evolving attacks.

When to use it

RSA is appropriate for encrypting small amounts of data, establishing secure channels, and creating digital signatures. It is commonly used in TLS/SSL protocols, email encryption (PGP), and certificate authorities. RSA requires careful padding schemes (OAEP for encryption, PSS for signatures) to be secure. Modern implementations should use key sizes of at least 2048 bits for reasonable security against current computational power.

Limitations and considerations

  • Computationally expensive compared to symmetric encryption; typically used for key exchange rather than bulk data encryption
  • Key size must be large (2048 bits or more) for adequate security, making encryption and decryption slower than symmetric alternatives
  • Vulnerable to quantum computers if they become practical, necessitating post-quantum alternatives

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Widely standardized and supported across platforms and libraries
  • Enables both encryption and digital signature generation with the same key pair
  • Mathematically elegant foundation based on the factoring problem
  • Backward compatible with decades of existing infrastructure

Applications

  • HTTPS and TLS/SSL protocols for securing web communication and e-commerce
  • Pretty Good Privacy (PGP) and S/MIME for encrypting email messages
  • Digital certificates and public key infrastructure (PKI) for authenticating identities online
  • Blockchain systems and cryptocurrency for transaction signing and verification
  • Smart card authentication and government ID card encryption
  • Hardware security modules (HSMs) for enterprise key management

How it works

How it works

1

Select two large distinct prime numbers p and q, compute their product n = p × q, compute Euler's totient φ(n) = (p-1)(q-1), choose e with 1 < e < φ(n) coprime to φ(n), compute d such that e × d ≡ 1 (mod φ(n)). The public key is (e, n) and the private key is (d, n).

2

To encrypt a message m, compute the ciphertext c = m^e mod n, where e and n are the recipient's public key.

3

To decrypt a ciphertext c, compute the plaintext m = c^d mod n, where d and n are the private key.

4

Digital signatures are created by encrypting a hash of the message with the private key, and verified by decrypting with the public key to confirm the hash matches.

Common pitfalls

  • Using RSA without proper padding schemes (OAEP or PSS) can expose the algorithm to various attacks
  • Reusing the same RSA key for both encryption and signature operations increases attack surface; dedicated key pairs are preferred
  • Incorrect prime generation or weak randomness in key generation can compromise security entirely

Frequently asked questions

Why is RSA slow compared to symmetric encryption like AES?

RSA involves modular exponentiation with very large numbers (2048 bits or larger), which requires orders of magnitude more computation than the efficient byte-level operations of AES. In practice, RSA is used to encrypt a small key that then encrypts the bulk data with AES.

What happens if someone factors my public key modulus n?

If an attacker factors n into its prime factors p and q, they can compute φ(n) and then derive your private key d from your public exponent e. This is why using sufficiently large primes and key sizes is critical.

Can RSA signatures be forged without the private key?

Not with properly padded signatures (PSS). However, unpadded or improperly padded RSA signatures are vulnerable to various mathematical attacks. Always use standard padding schemes.

Is RSA still secure in 2026?

RSA with 2048-bit keys is still considered secure against classical computers, though 4096-bit keys are recommended for long-term security. However, RSA will be vulnerable to quantum computers if they are built at scale, so post-quantum cryptography research is actively underway.

How do I choose appropriate primes p and q?

Use a cryptographically secure random number generator to generate large numbers, then test each for primality using algorithms like the Miller-Rabin test. Modern libraries handle this automatically.

Related methods

Sources

  1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.

    Open DOI reference
    Copied.
  2. Koblitz, N. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.

    ISBN: 978-0387966618
    Copied.