The Rivest-Shamir-Adleman (RSA) encryption algorithm, first theorized by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, enabled the secure transmission of communications and information across insecure networks and the internet at large.
RSA is a key component in digital signatures, digital certificates, and various online security protocols. Its encryption strength is backed by the hardness of factoring large semiprimes, which uses two large, randomly selected prime numbers to protect your information.
What Is RSA Encryption?
The development of RSA encryption is a story of two labs arriving at the same conclusion at roughly the same time, with both MIT and British Intelligence working toward similar goals, unaware of each other's work.
According to public records, in the late 1960s, the UK's Government Communications Headquarters (GCHQ) tasked a lone cryptographer on its team, James Ellis, with developing a new algorithm that could work for a new concept (at the time) known as "public-key cryptography". Although Ellis was able to develop a theoretical framework for the algorithm, at the time, he was unable to calculate the necessary mathematical equations to make it work. Years later, the program was resumed by another cryptographer, Clifford Cocks. Cocks eventually solved the equations needed, but the work was kept classified as "Top Secret" by the UK government all the way until 1997.
Five years after Cocks solved RSA's equations in private, Rivest, Shamir, and Adleman published the first formal description of RSA in Communications of the Association of Computing Machinery in 1978. Based on a paper titled "New Directions in Cryptography" that had hit the wires two years prior in 1976 from Whitfield Diffie and Martin Hellman, the new RSA algorithm (based on the authors' last names) relied on a simple principle: While it was computationally simple to multiply two large prime numbers together to create a large composite number, factoring those two numbers back down to find the primes that created the number was exceedingly difficult.
The difficulty that both humans and computers faced in solving this problem at the time formed the basis of the RSA encryption method as we know it today. And although the initial implementations of RSA were small in bit depth (you can read more about what bit depth means in our explainer here), as computers grew in power and complexity, so did the prime factorials of RSA alongside it.
Today, the standard bit depths for RSA commonly come in 2,048-bit, 3,072-bit, or 4,096-bit integers.
How Does RSA Encryption Work?
There are three stages involved in RSA's encryption standard: key generation, encryption, and decryption.
1. Key Generation: Two large prime numbers are selected, each of which is distinct from the other. The primes are then multiplied to create a large composite number, known as the "modulus." A public exponent (which is composed of the public key in addition to the modulus) is chosen independently, and the private exponent (private key), which is a modular multiplicative inverse using the public exponent. In essence, this is math speak for a secret system based on two prime numbers: a public locking key that belongs to everyone, and a private key that's calculated to reverse the actions of the public key.
2. Encryption: To transmit an encrypted message, the sender will encrypt the message using the recipient's public key (using both the public exponent and the modulus). This results in a seemingly random message.
3. Decryption: The ciphertext recipient then uses their private key to reverse the encryption process to convert the ciphertext back to plaintext.
Where Is RSA Most Commonly Used?
RSA is most commonly used to encrypt protocols like TLS (see our article about TLS) and SSL, both of which are regularly implemented in secure web browsing over HTTPS, in email communications, and other online messaging applications.
RSA is also used to create secure shell (SSH) to create encrypted tunnels for remote logins and other hardened network services. Digital signatures and digital certificate services also rely on RSA, which is used to verify the authenticity and integrity of digital documents, messages, and devices.
Virtual private networks (VPNs) also use RSA, though more recently, you'll see VPNs using AES-256 in place of RSA due to potential threats that could arise with the advent of quantum computing.
Conclusion
The bottom line on RSA is its total reliance on one mathematical truth: factoring huge numbers is computationally infeasible. You've seen that the core mechanism is modular arithmetic: taking a plaintext message and transforming it using the recipient's public key into an unusable ciphertext.
However, the secret method to its mathematical madness is the private key, derived from two huge secret prime numbers. Without those primes in hand, reversing the encryption is too difficult for even the most powerful supercomputers to solve today.
This asymmetric approach is what makes RSA work in the modern security landscape, providing confidentiality for encrypted messages, but also enabling the framework for digital signatures, VPNs, and secure key exchanges that keep our modern digital world safe from anyone who might be trying to peek in on any communications where they don't belong.