RSA is a widely used encryption method that allows two parties to communicate securely without ever needing to share a secret password ahead of time. Invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman (whose initials give it its name), RSA was one of the first practical systems to use a pair of mathematically linked keys: one public, one private. Its security rests on the fact that multiplying two huge prime numbers together is easy, but working backward to figure out which two primes were used is extraordinarily hard. Decades later, RSA still underpins much of the internet’s security infrastructure, though its long-term future is complicated by the rise of quantum computing.
The Two-Key Idea
Before RSA, if you wanted to send someone an encrypted message, both of you needed access to the same secret key. That is called symmetric encryption, and the logistical headache is obvious: how do you safely deliver the key in the first place? RSA solved this by introducing a pair of keys. The public key can be shared openly with anyone. The private key stays secret with its owner. A message encrypted with the public key can only be decrypted with the matching private key, and vice versa. This means you can post your public key on a website, and anyone in the world can use it to send you a message that only you can read.
The same two-key structure also enables digital signatures. If you encrypt a piece of data with your private key, anyone holding your public key can verify that the data came from you and hasn’t been tampered with. This is how your browser confirms that a website really belongs to the organization that claims to own it, and how software updates prove they came from a legitimate developer rather than a malicious third party.
How RSA Works in Plain Terms
The setup starts with two very large prime numbers, chosen at random. These primes are multiplied together to produce an even larger number, often called the modulus. The modulus, combined with a related number, forms the public key. The private key is derived from the original two primes using a mathematical relationship rooted in what’s known as the Euler totient function, a concept introduced by the mathematician Leonhard Euler centuries before RSA existed.1Journal of Physics: Conference Series. A Study of the Use of Euler Totient Function in RSA Cryptosystem and the Future of RSA Cryptosystem What matters for the reader is that this relationship makes encryption and decryption mirror images of each other: one key locks, the other unlocks, and neither can do the other’s job.
The core mathematical operation in RSA is modular exponentiation, which is a fancy way of saying “raise a number to a very large power, then take the remainder after dividing by the modulus.”2Journal of Circuits, Systems and Computers. SOFTWARE/HARDWARE CO-DESIGN OF MODULAR EXPONENTIATION FOR EFFICIENT RSA CRYPTOSYSTEM When you encrypt a message, you perform this operation using the public key. When the recipient decrypts it, they perform a similar operation using the private key. The math guarantees that the original message pops back out at the end. You don’t need to understand the arithmetic to use RSA, and most people never see it directly. Your web browser, email client, or VPN handles it behind the scenes in milliseconds.
Why It’s Hard to Break
The entire security of RSA hangs on one assumption: that factoring the product of two very large primes back into those original primes is computationally impractical. When the primes are small, this is trivial. If someone tells you the product is 15, you can quickly figure out the primes are 3 and 5. But RSA doesn’t use small primes. A standard RSA key today uses a modulus that is 2048 bits long, which translates to a number with roughly 617 digits. The best-known algorithms for factoring numbers this large on conventional computers would take longer than the age of the universe to finish, even on the fastest supercomputers available.
The gap between multiplication and factoring is a one-way street that cryptographers depend on. Multiplying two 1024-bit primes together takes a fraction of a second. Reversing that multiplication to recover the primes remains beyond the reach of all known classical computing resources at current key sizes. This asymmetry is what gives RSA its strength. If someone ever discovers a fast factoring algorithm that runs on conventional hardware, or if computing power grows dramatically in unexpected ways, RSA would collapse. So far, no such breakthrough has appeared in over four decades of intense mathematical research.
Key Sizes and What They Mean
RSA key size refers to the length of the modulus in bits. Over the years, recommended minimum key sizes have grown steadily as computers have become faster. In the 1990s, 512-bit keys were common. By the 2000s, 1024-bit keys became the standard. Today, 2048 bits is considered the minimum for serious security, and many organizations use 3072-bit or 4096-bit keys for long-term protection.
A longer key makes factoring harder, but it also makes encryption and decryption slower. RSA is already relatively slow compared to symmetric encryption methods, which is why RSA is rarely used to encrypt large amounts of data directly. Instead, it typically serves as a way to securely exchange a symmetric key at the start of a communication session. Your browser, for example, might use RSA (or a similar public-key system) during the initial handshake with a website, then switch to a faster symmetric cipher for the actual data transfer. This hybrid approach gives you the convenience of public-key cryptography without the performance cost of using it for everything.
Known Attacks and Weaknesses
RSA’s mathematical foundation has been studied relentlessly since its publication, and while no one has broken it outright, researchers have identified several conditions under which implementations can be vulnerable.
One well-known class of attack targets implementations that use a small private exponent to speed up decryption. The Wiener attack, first described in the 1990s, showed that if the private key is too short relative to the modulus, an attacker can recover it efficiently. Later researchers extended and refined this approach, reducing the computational cost of the search needed to push the attack further.3PubMed Central. On the improvement of Wiener attack on RSA with small private exponent The practical takeaway is straightforward: don’t cut corners on key generation to save processing time. Using a full-size private exponent avoids this entire category of attack.
Another vulnerability comes not from the math itself but from how RSA is implemented in hardware. Many real-world systems speed up RSA decryption using a technique based on the Chinese Remainder Theorem. This optimization works by splitting the computation into smaller pieces. But if an attacker can induce a hardware fault during one of those sub-computations, they can sometimes recover the private key from the faulty output. This is called a fault injection attack, and it has been demonstrated against real cryptographic libraries. Research has shown that even libraries designed with protections against such attacks can still be vulnerable to newly discovered fault locations, and in one case, the protection mechanism itself created a new path to extracting the private key.4Microprocessors and Microsystems. Exhaustive single bit fault analysis. A use case against Mbedtls and OpenSSL’s protection on ARM and Intel CPU
These attacks require physical access to the device or very specific conditions, so they are not something the average internet user needs to worry about. They matter more for embedded devices, smart cards, and hardware security modules where an attacker might be able to physically tamper with the equipment.
When the Random Numbers Aren’t Random Enough
Perhaps the most common real-world failures of RSA have nothing to do with clever mathematics and everything to do with sloppy implementation. RSA’s security depends on the two starting primes being truly random and unpredictable. If the random number generator used to pick those primes is flawed, the resulting keys can be weak, sometimes catastrophically so.
This has happened repeatedly in practice. Researchers analyzing large sets of RSA public keys collected from the internet have found that a small but meaningful fraction share a prime factor with another key. When two different keys happen to share one of their two primes, an attacker can compute the common factor and immediately derive both private keys. Weak random number generation in embedded devices, such as routers, firewalls, and internet-connected appliances, has been identified as the primary cause of these failures.5arXiv. When RSA Fails: Exploiting Prime Selection Vulnerabilities in Public Key Cryptography These devices often boot up without enough environmental randomness to seed their random number generators properly, and they generate their RSA keys too early in the process.
The lesson here is that RSA’s mathematical elegance only protects you if the software and hardware generating the keys do their jobs correctly. A mathematically perfect algorithm implemented with a bad random number generator is not secure. Mitigation strategies include collecting randomness from multiple sources, validating that generated primes are truly independent, and waiting until enough entropy has accumulated before generating cryptographic keys.
The Quantum Computing Threat
The most serious long-term challenge to RSA comes from quantum computing. In 1994, mathematician Peter Shor devised an algorithm that, if run on a sufficiently powerful quantum computer, could factor large numbers exponentially faster than any known classical method. The Shor algorithm could defeat RSA by finding the prime factors of the modulus relatively quickly, a task that would take years or more on even the fastest conventional supercomputers.6Quantum Computing: From Alice to Bob. RSA Encryption and the Shor Factoring Algorithm
The key word here is “sufficiently large.” Current quantum computers are nowhere near the scale required to run Shor’s algorithm against a 2048-bit RSA key. The most optimistic estimates suggest that breaking RSA-2048 would require a quantum computer with millions of stable, error-corrected qubits, a milestone that could be a decade away or more. But cryptographic systems are designed to protect data for years or decades into the future, and some nation-states are known to be harvesting encrypted communications today with the intent of decrypting them once quantum computers mature. This “harvest now, decrypt later” strategy means the threat is already real for information that needs to stay secret for many years.
In response, the U.S. National Institute of Standards and Technology (NIST) has been running a multi-year effort to standardize post-quantum cryptographic algorithms, ones designed to resist both classical and quantum attacks. CRYSTALS-Kyber, standardized by NIST in 2022, represents one of the leading replacements for RSA and similar public-key systems, though widespread adoption still faces significant challenges.7arXiv. Performance and Storage Analysis of CRYSTALS Kyber as a Post Quantum Replacement for RSA and ECC These new algorithms rely on mathematical problems that are believed to be hard for both classical and quantum computers, such as problems involving lattices, which are high-dimensional geometric structures with no known efficient quantum shortcut.
RSA Compared to Elliptic Curve Cryptography
RSA isn’t the only public-key system in use today, and for many applications it isn’t even the preferred one anymore. Elliptic curve cryptography (ECC) provides comparable security with much shorter keys. A 256-bit ECC key offers roughly the same protection as a 3072-bit RSA key, which translates to significant savings in storage, bandwidth, and processing power. This makes ECC especially attractive for mobile devices, embedded systems, and any context where computing resources are limited.
ECC’s security rests on a different mathematical problem, one involving points on an elliptic curve rather than the factoring of large numbers. Both problems are believed to be hard for classical computers, and both fall to Shor’s algorithm on a quantum computer, so the quantum threat applies equally. The practical difference is efficiency: ECC does the same job with less overhead, which is why most modern implementations of TLS (the protocol securing web traffic) have shifted toward ECC for key exchange and digital signatures.
RSA remains dominant in some contexts, particularly where long-established infrastructure and backward compatibility matter. Many certificate authorities still issue RSA certificates, and some legacy systems only support RSA. But for new deployments without compatibility constraints, ECC has largely taken over the role RSA once filled.
Where You Encounter RSA Without Knowing It
Even if you never think about encryption, RSA is working in the background of your daily digital life. When you visit a website with “https” in the address bar, your browser is verifying a digital certificate that may be signed with RSA. When you send an encrypted email using PGP or S/MIME, RSA is often part of the key exchange. When you connect to a remote server using SSH, RSA key pairs are one of the standard authentication methods. When your operating system installs an update, it may check an RSA signature to confirm the update hasn’t been tampered with.
Credit card payment terminals, VPN connections, secure messaging apps, government identity documents with embedded chips: RSA or its close relatives appear in all of these. The algorithm’s longevity is partly a testament to its mathematical soundness and partly a reflection of how deeply embedded it has become in global infrastructure. Replacing it isn’t just a matter of switching to a new algorithm. It means updating hardware, firmware, protocols, and standards across billions of devices and countless software systems.
Common Misconceptions About RSA
One persistent misunderstanding is that RSA directly encrypts your emails, files, or web traffic. In practice, RSA almost always works as a key-exchange mechanism. The actual bulk encryption of your data is handled by a faster symmetric algorithm. RSA’s job is to get both parties securely holding the same symmetric key, after which it steps aside.
Another misconception is that “RSA has been broken” every time a new attack paper appears. Academic cryptanalysis papers routinely describe attacks on reduced or weakened versions of RSA, such as implementations with unusually short keys or poorly chosen parameters. These results are valuable because they map the boundaries of where RSA remains safe and where it doesn’t, but they rarely threaten properly configured RSA as used in real systems. The difference between breaking RSA-512 (which researchers accomplished years ago) and breaking RSA-2048 (which nobody has come close to) is not incremental. It is a gulf so vast that a doubling of computing power barely dents it.
A third common confusion involves the relationship between RSA and quantum computing. People sometimes assume that quantum computers have already broken RSA or will do so imminently. The reality is more measured. Quantum computers capable of running Shor’s algorithm at the scale needed to threaten RSA-2048 do not yet exist. The concern is forward-looking, which is why the transition to post-quantum cryptography is being planned now rather than after the threat materializes. Cryptographic migrations take years or decades to complete across global infrastructure, so starting early is prudent even if the timeline for a practical quantum attack remains uncertain.
The Transition to Post-Quantum Cryptography
The shift away from RSA won’t happen overnight, and RSA won’t vanish the day a quantum computer becomes powerful enough to threaten it. What is happening now is a gradual, carefully managed transition. Government agencies in the United States and Europe have begun issuing guidance for organizations to inventory where they use RSA and related algorithms, assess which data would be vulnerable in a post-quantum world, and begin testing replacements.
The replacement algorithms standardized by NIST are based on mathematical problems that quantum computers aren’t expected to solve efficiently. These include lattice-based schemes, code-based schemes, and hash-based signatures. Each comes with trade-offs: some have larger key sizes than RSA, some are faster, some require more bandwidth. The practical challenge is fitting these new algorithms into existing protocols and hardware that were designed around the characteristics of RSA and ECC.
For most individuals, this transition will be invisible. Browser vendors, operating system developers, and cloud providers will update their implementations, and the new algorithms will work behind the scenes just as RSA does today. For organizations managing their own cryptographic infrastructure, the transition involves more deliberate planning but follows a well-trodden path: standards bodies publish specifications, software libraries add support, and systems gradually migrate. The biggest risk isn’t the quantum computer itself but the inertia of legacy systems that resist updates. History suggests that some corner of the internet will still be running RSA long after its useful security life has ended, just as some systems today still support encryption methods that were deprecated years ago.