RSA encryption explained: RSA is a public-key cryptosystem with two mathematically linked keys. A recipient publishes a public key so others can encrypt a message for them. The recipient keeps the matching private key secret and uses it to decrypt that message.
Ron Rivest, Adi Shamir, and Leonard Adleman publicly described RSA in 1977. RSA can provide public-key encryption and digital signatures. The equations below explain its core arithmetic; deployed encryption uses a defined scheme such as RSAES-OAEP.
The two-key message flow
RSA is asymmetric encryption, also called public-key cryptography. Unlike a shared-key system, it lets someone encrypt for a recipient without the two parties first sharing the recipient’s private key.
- The recipient creates an RSA key pair.
- They distribute the public key.
- A sender uses that public key to turn readable plaintext into ciphertext.
- The recipient uses the secret private key to recover the plaintext.
The math that creates the keys
RSA begins with two secret prime numbers, p and q. A prime has no positive divisors other than 1 and itself. Their product is n = p × q, the public modulus.
The key-generation process calculates φ(n) = (p − 1)(q − 1). It chooses a public exponent, e, that is coprime to φ(n), meaning the two values share no factor other than 1. It then finds a private exponent, d, such that e × d ≡ 1 mod φ(n).
“Mod” means the remainder after division. For example, 13 mod 5 is 3. In the relationship above, dividing e × d by φ(n) leaves a remainder of 1.
- Public key: (n, e)
- Private key: (n, d)
- M: a numerical representation of the plaintext
- C: the ciphertext
The textbook operations use modular exponentiation: raise a number to a power, then retain the remainder after division by n.
- Encryption: C = M^e mod n
- Decryption: M = C^d mod n
A deliberately tiny example
This demonstrates the arithmetic, not a secure setup.
- Inputs: p = 3 and q = 11
- Modulus: n = 3 × 11 = 33
- Totient: φ(n) = (3 − 1)(11 − 1) = 20
- Choose: e = 3 and d = 7, because 3 × 7 = 21 and 21 mod 20 = 1
The public key is (33, 3), and the private key is (33, 7). For M = 4, encryption gives C = 4^3 mod 33 = 64 mod 33 = 31. Decryption gives 31^7 mod 33 = 4, returning the original numerical message.
Why the public key does not disclose the private key
The public modulus n is the product of the secret primes p and q. Multiplication is easy; factoring a sufficiently large public product back into its two prime factors is difficult. Knowing p and q permits calculation of φ(n), which permits calculation of d from the relationship between e and d.
This is a security intuition, not a proof that breaking every form of RSA is exactly equivalent to factoring n. That equivalence remains an open question.
Encryption and signatures are separate jobs
- Confidentiality: encrypt with the recipient’s public key; the matching private key decrypts.
- Authenticity and integrity: a signer uses a private key to create a digital signature, and others use the corresponding public key to verify it.
A signature can be verified with the public key; it does not make the signed data secret.
Why RSA usually encrypts a short secret
RSA public-key encryption is used for very short messages, almost always a single-use symmetric key in a hybrid cryptosystem. RSA protects that small key rather than directly encrypting bulk data.
The bare equations describe RSA’s arithmetic. RSAES-OAEP is an example of an RSA public-key-encryption scheme.
Frequently asked questions
What is the difference between RSA encryption and an RSA digital signature?
RSA encryption provides confidentiality: a sender encrypts with the recipient’s public key, and the recipient decrypts with the matching private key. An RSA digital signature is created with a private key and verified with the corresponding public key; it does not make the signed data secret.
Why is RSA normally combined with symmetric encryption?
RSA public-key encryption is used for very short messages, almost always a single-use symmetric key in a hybrid cryptosystem, rather than directly encrypting bulk data.
Why does knowing an RSA public key not reveal the private key?
The public modulus n is made from two secret primes. Deriving the private exponent depends on information obtained from those primes, and factoring a sufficiently large public product into them is difficult. RSA’s security is related to factoring difficulty, though whether breaking RSA is equivalent to factoring is an open question.
Why are the textbook RSA equations not the whole encryption scheme?
C = M^e mod n and M = C^d mod n describe RSA’s core arithmetic. RSAES-OAEP is an example of an RSA public-key-encryption scheme.
Sources
- RSA cryptosystem - Wikipedia — en.wikipedia.org
- RSA Algorithm in Cryptography - GeeksforGeeks — www.geeksforgeeks.org
- [PDF] The RSA Cryptosystem - MIT Mathematics — math.mit.edu
- What is RSA? How does an RSA work? - Encryption Consulting — www.encryptionconsulting.com
