RSA is a public-key cryptosystem in which a public key encrypts or verifies and a matching private key decrypts or signs, with security resting on the difficulty of factoring the product of two large primes. Named after Rivest, Shamir and Adleman, who published it in 1977, it was the first practical scheme to support both encryption and digital signatures with the same key pair.
In cryptography and cybersecurity today, RSA is used mainly for certificate signatures, code signing and legacy key transport. Its role in establishing session keys has largely passed to elliptic curve key exchange, but RSA remains one of the most widely deployed asymmetric algorithms in public key infrastructure.
How the RSA algorithm works
Key generation picks two large random primes, p and q, and multiplies them to form the modulus n. The size of n in bits is the key size. A public exponent e, almost always 65537, is chosen, and the private exponent d is computed as the inverse of e modulo the least common multiple of p minus 1 and q minus 1.
Encryption raises a message representative m to the power e modulo n; decryption raises the result to the power d modulo n and recovers m. Signing reverses the roles: the signer applies d to a hash of the message, and anyone with the public key applies e to check it. Knowing d is equivalent to being able to factor n, which is why factoring is the core hardness assumption.
| Value | Public or private | Purpose |
|---|---|---|
| Modulus n | Public | Product of p and q, defines key size |
| Exponent e | Public | Encryption and verification, usually 65537 |
| Exponent d | Private | Decryption and signing |
| Primes p and q | Private | Allow fast computation via the Chinese remainder theorem |
| CRT parameters | Private | Precomputed values that speed private operations about fourfold |
Key sizes and security levels
RSA security grows slowly with key length because the best known attack, the general number field sieve, runs in sub-exponential time. Doubling the key size therefore adds far less than double the security, and private-key operations slow down roughly with the cube of the key length.
| Modulus size | Approximate security | Current status |
|---|---|---|
| 1024 bits | About 80 bits | Deprecated, considered breakable by well-funded attackers |
| 2048 bits | About 112 bits | Minimum accepted for new keys |
| 3072 bits | About 128 bits | Recommended for protection beyond 2030 |
| 4096 bits | About 140 to 150 bits | Used for long-lived roots and signing keys |
| 7680 bits | About 192 bits | Rarely used because of performance cost |
The largest RSA modulus publicly factored with classical computers is 829 bits (RSA-250), achieved in 2020. A sufficiently large fault-tolerant quantum computer running Shor’s algorithm would break RSA at any practical size, which drives the migration toward post-quantum signature and key establishment schemes standardized by NIST in 2024.
Padding schemes and why raw RSA is unsafe
Textbook RSA without padding is insecure: it is deterministic, malleable and leaks information for small messages. Real systems wrap the message in a padding scheme defined in PKCS #1, and the choice of scheme matters as much as the key size.
| Scheme | Used for | Security assessment |
|---|---|---|
| PKCS #1 v1.5 encryption | Legacy key transport | Vulnerable to padding oracle attacks such as Bleichenbacher |
| RSA-OAEP | Encryption | Provably secure under standard assumptions, preferred |
| PKCS #1 v1.5 signature | Certificates and signatures | Still widely used, no practical break when verified strictly |
| RSA-PSS | Signatures | Randomized with a security proof, required in TLS 1.3 handshakes |
The Bleichenbacher attack of 1998 and its later variants, including ROBOT in 2017, showed that a server revealing whether decrypted padding was valid lets an attacker decrypt traffic. This is one reason TLS 1.3 removed RSA key transport entirely.
RSA compared with other public-key algorithms
RSA competes mainly with elliptic curve cryptography, which reaches the same security with much shorter keys. In key exchange, ephemeral elliptic curve Diffie-Hellman provides forward secrecy, which static RSA key transport cannot.
| Property | RSA-3072 | ECDSA P-256 or Ed25519 |
|---|---|---|
| Public key size | 384 bytes | 32 to 64 bytes |
| Signature size | 384 bytes | 64 bytes |
| Signing speed | Slow | Fast |
| Verification speed | Very fast | Moderate |
| Forward secrecy in key exchange | Not with key transport | Yes with ephemeral ECDH |
RSA keeps one practical advantage: verification is very fast because e is small. That makes it attractive where signatures are verified many times, such as firmware images and certificate chains checked by millions of clients.
Implementation pitfalls
- Weak randomness in key generation produces moduli that share a prime; scans of internet hosts have found many such keys, factored with a simple GCD.
- Timing and power side channels can leak d unless implementations use constant-time arithmetic and blinding.
- Fault attacks on CRT signing can reveal a prime from one faulty signature, so signatures should be verified before release.
- Small public exponents such as e = 3 combined with poor padding allow message recovery.
- Encrypting bulk data directly is wrong; RSA should protect or sign a key or hash, with AES handling the data.
The safest course is to use a vetted cryptographic library and its high-level interfaces rather than assembling RSA operations manually, and to store private keys in a hardware security module where the risk justifies it.
The short version
RSA works like a mailbox with a slot and a locked door. Anyone can drop a letter through the slot using the public key, but only the owner of the private key can open the door and read it.
It also works in reverse as a seal. The owner stamps a document with the private key, and anyone can check the stamp with the public key. The whole system is safe only because splitting a huge number into its prime factors is practically impossible with today’s computers.
Where it makes a difference
A company that ships firmware for industrial sensors signs every update with a 4096-bit RSA key held in a hardware security module. Each sensor stores the public key in read-only memory and verifies the RSA-PSS signature before installing anything. Verification takes only a few milliseconds even on a modest microcontroller, which suits devices with limited processing power.
When an attacker compromises the download server and replaces an update with a modified image, every sensor rejects it because the signature does not match. The tampered firmware never runs, and the company only needs to restore the server, not recall thousands of devices. The team is also planning a dual-signature scheme that adds a post-quantum signature beside RSA for devices expected to stay in service beyond 2035.