Every time you visit a website with HTTPS, send a secure email, or verify a software update, you are using RSA. It is one of the most important cryptographic algorithms ever invented, and it has been protecting internet communications for over 40 years.
Let's break down how RSA works, the math behind it, and why it is secure.
The Big Idea: Public Key Cryptography
Before RSA, all cryptography was symmetric. If you wanted to send an encrypted message to someone, you both needed the same key. The challenge was: how do you share the key securely? If you could share a key securely, you could just share the message securely.
Public key cryptography (also called asymmetric cryptography) solved this problem. Instead of one key, you have two: a public key and a private key. The public key can be freely shared with anyone. The private key is kept secret.
Here is the magic: a message encrypted with the public key can only be decrypted with the private key. So you can publish your public key, anyone can use it to encrypt a message, and only you (with the private key) can read it.
RSA was the first practical implementation of this idea, introduced by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977. (The name RSA comes from their initials.)
The Math: Prime Factorization
RSA's security is based on a simple mathematical fact: it is easy to multiply two large prime numbers, but it is extremely hard to factor the product back into the original primes.
If I tell you that 7 times 11 is 77, you can easily verify it. But if I tell you that the number 77 is the product of two primes and ask you to find them, you have to try dividing by each prime until you find one that works. For small numbers, this is easy. For numbers with hundreds of digits, it is practically impossible with classical computers.
This asymmetry, easy to multiply but hard to factor, is the foundation of RSA.
Key Generation
Generating an RSA key pair involves these steps:
**1. Choose two large prime numbers (p and q).** For a 2048-bit key, each prime is about 1024 bits long. These primes are generated randomly and tested for primality.
**2. Compute n = p * q.** This is the modulus, and it is part of both the public and private keys. The security of RSA depends on the difficulty of factoring n back into p and q. For a 2048-bit key, n is a 2048-bit number (about 617 decimal digits).
**3. Compute the totient: φ(n) = (p-1)(q-1).** This is Euler's totient function, which counts the numbers from 1 to n that are coprime to n.
**4. Choose a public exponent (e).** This is typically 65537 (a prime number that is efficient for computation). The public key is (n, e).
**5. Compute the private exponent (d).** This is the modular multiplicative inverse of e modulo φ(n). In other words, d is the number such that (e * d) mod φ(n) = 1. The private key is (n, d).
The public key (n, e) can be shared with anyone. The private key (n, d) must be kept secret. The primes p and q are usually stored with the private key for efficiency but are not strictly part of it.
Encryption
To encrypt a message m using the public key (n, e):
ciphertext = m^e mod n
This is modular exponentiation: raise the message to the power of e, then take the remainder when divided by n. The result is the ciphertext.
In practice, the message is first encoded as a number and padded (using OAEP or PKCS1 padding) before encryption. We cover padding in our RSA padding guide.
Decryption
To decrypt the ciphertext c using the private key (n, d):
message = c^d mod n
This reverses the encryption: raise the ciphertext to the power of d, then take the remainder when divided by n. The result is the original message.
The math works because of a property of modular arithmetic: (m^e)^d mod n = m. In other words, encrypting and then decrypting gives you back the original message.
Why It Is Secure
The security of RSA rests on the assumption that factoring large numbers is hard. If an attacker could factor n (the modulus in the public key) into its prime factors p and q, they could compute φ(n) and then derive the private exponent d. The key would be broken.
For a 2048-bit key, n is a 617-digit number. Factoring a number this large is beyond the capability of any known classical algorithm. The fastest known factoring algorithm (the General Number Field Sieve) would take billions of years on current hardware to factor a 2048-bit number.
This is why RSA key size matters. A 1024-bit key (768-bit in practice, since RSA-768 was factored in 2009) is no longer considered secure. A 2048-bit key is secure for the foreseeable future. See our RSA 2048 vs 4096 guide for details.
Signing (The Reverse Operation)
RSA can also be used for digital signatures, which is the reverse of encryption. Instead of encrypting with the public key, you sign with the private key. Anyone with the public key can verify the signature.
Signing: signature = hash(message)^d mod n Verifying: hash(message) == signature^e mod n
This proves that the signature was created by the private key holder (because only they have d) and that the message has not been tampered with (because the hash must match). We cover the difference between signing and encryption in our RSA signing vs encryption guide.
The Practical Limitations
RSA has two important limitations that shape how it is used in practice:
**1. Message size limit.** RSA can only encrypt messages smaller than the modulus n. For a 2048-bit key with OAEP padding, the maximum is about 245 bytes. This is far too small for most real-world messages.
**2. Performance.** RSA operations are computationally expensive. Encrypting or decrypting a single message takes milliseconds, compared to microseconds for symmetric algorithms like AES.
The solution to both problems is hybrid encryption: use RSA to encrypt a symmetric AES key, then use AES to encrypt the actual data. This combines RSA's key distribution advantage with AES's speed and unlimited message size. We cover this in our hybrid encryption guide.
The Bottom Line
RSA is the foundation of internet security. Every HTTPS connection, every signed software update, every encrypted email uses RSA or a similar public key algorithm. The math is elegant: the difficulty of factoring large numbers creates a one-way function that is easy to compute but hard to reverse.
For most developers, you will not implement RSA yourself. You will use libraries that handle the math correctly. But understanding how it works helps you make better decisions about key sizes, padding, and when to use RSA versus other algorithms.
Try RSA encryption yourself with our RSA Encrypt/Decrypt tool, and read our guide on RSA 2048 vs 4096 key sizes to choose the right key size for your needs.
