RSA is a public key encryption method that uses number theory to send secure messages. This cheat sheet walks through the ingredients, key generation, encryption, and decryption steps. Students need it because RSA combines primes, exponents, remainders, and inverse operations in one procedure.
A clear reference helps keep the order of steps organized.
The main formulas are n = p q, phi(n) = (p - 1)(q - 1), c = m^e mod n, and m = c^d mod n. The public key is (n, e), while the private key is d. The encryption exponent e must be relatively prime to phi(n), and d must satisfy e d mod phi(n) = 1.
Small classroom examples use small primes, but real RSA uses very large primes for security.
Key Facts
- Choose two distinct primes p and q, then compute n = p q.
- For RSA with two primes, Euler's totient is phi(n) = (p - 1)(q - 1).
- Choose an encryption exponent e so that gcd(e, phi(n)) = 1.
- Find the private exponent d so that e d mod phi(n) = 1.
- The public key is (n, e), and it can be shared with anyone.
- The private key is d, and it must be kept secret.
- Encrypt a message number m using c = m^e mod n, where 0 <= m < n.
- Decrypt the ciphertext c using m = c^d mod n.
Vocabulary
- Prime number
- A whole number greater than 1 whose only positive factors are 1 and itself.
- Modulus
- The number n in a remainder calculation, such as a mod n.
- Euler's totient
- The number phi(n) counts how many positive integers less than n are relatively prime to n.
- Relatively prime
- Two integers are relatively prime when their greatest common divisor is 1.
- Modular inverse
- The modular inverse of e modulo phi(n) is a number d such that e d mod phi(n) = 1.
- Ciphertext
- Ciphertext is the encrypted form of a message after applying the RSA encryption rule.
Common Mistakes to Avoid
- Using p and q that are not prime is wrong because the totient formula phi(n) = (p - 1)(q - 1) only works for distinct primes in this RSA setup.
- Choosing e that shares a factor with phi(n) is wrong because e will not have a modular inverse, so d cannot be found.
- Treating d as the same as 1/e is wrong because d is a modular inverse, not an ordinary decimal or fraction.
- Forgetting to reduce powers modulo n is wrong because RSA calculations require remainders after exponentiation, not the full huge power.
- Trying to encrypt a message number m with m >= n is wrong because RSA message blocks must satisfy 0 <= m < n.
Practice Questions
- 1 Let p = 5 and q = 11. Find n and phi(n).
- 2 For p = 5, q = 11, and e = 3, find d such that e d mod phi(n) = 1.
- 3 Using n = 55 and e = 3, encrypt the message m = 7 by computing c = 7^3 mod 55.
- 4 Explain why sharing the public key (n, e) does not directly reveal the private exponent d when p and q are very large.
Understanding RSA Algorithm Walkthrough
RSA is built on an uneven mathematical task. Multiplying two primes is quick, even when the primes are huge. Recovering those two primes from their product is much harder.
The public modulus is safe only while its prime factors remain unknown. If an attacker factors the modulus, they can calculate the hidden number needed to undo the encryption.
This is why real systems use primes hundreds of digits long and generate them with carefully tested software. Small values are useful for learning, but they provide no real protection because a person can factor them by trial.
Modular arithmetic keeps the calculations manageable. A modular result is the remainder left after division by the modulus. During encryption, a message number is raised to a large power, yet the full enormous power never needs to be written down.
The efficient method is repeated squaring. Square a number, reduce it to its remainder, then square that remainder again. Select the needed powers based on the exponent and multiply their remainders, reducing after every multiplication.
This method is fast even for very large exponents. Students should reduce at each stage. Carrying giant unreduced numbers often causes arithmetic mistakes and hides the pattern.
The reason decryption returns the original message comes from Euler's theorem. For a number with no common factor with the modulus, raising it to the totient power leaves a remainder of one. The private exponent is chosen so that multiplying the public exponent by the private exponent gives one plus some whole number of totient cycles.
Encrypting then decrypting therefore applies an exponent that acts like one extra step after complete cycles. The message returns to its starting remainder.
A full proof for every possible message uses the Chinese remainder theorem, which checks the result separately for each secret prime. This is a useful reminder that RSA relies on precise conditions, not a numerical trick.
In real life, RSA does not usually encrypt a long file or a whole chat directly. It commonly protects a short random secret, then a faster symmetric cipher encrypts the actual data. Secure websites use related ideas during connection setup.
RSA can support digital signatures too. In that case, the private exponent is applied to a protected summary of a document, and the public key checks it. Real RSA always uses padding schemes.
Plain textbook RSA is predictable, so the same message produces the same ciphertext and can leak information. When learning a walkthrough, keep message encoding separate from the mathematics. Check that the message number lies below the modulus, verify that the chosen exponents are valid, and use the extended Euclidean algorithm carefully when finding the modular inverse.