RSA is a public key cryptography method that lets people send secure messages without first sharing a secret password. Its security comes from a one-way math idea: multiplying two large primes is easy, but factoring their product is extremely hard when the primes are huge. This makes RSA a powerful example of number theory used in real digital communication.
It also shows why modular arithmetic is more than a classroom topic, since it helps protect bank transactions, messages, and software updates.
In RSA, a public key is used to encrypt a message, while a related private key is needed to decrypt it. The keys are built from two prime numbers p and q, their product n = pq, and Euler's totient phi(n) = (p - 1)(q - 1). A public exponent e is chosen so it shares no factors with phi(n), and the private exponent d is chosen so ed = 1 mod phi(n).
Encryption and decryption work because modular exponentiation has a special inverse structure when the key values are chosen correctly.
Key Facts
- RSA starts by choosing two primes p and q, then computing n = pq.
- For two distinct primes, Euler's totient is phi(n) = (p - 1)(q - 1).
- The public key is (n, e), where gcd(e, phi(n)) = 1.
- The private key uses d, where ed = 1 mod phi(n).
- Encryption uses c = m^e mod n, where m is the message number and c is the ciphertext.
- Decryption uses m = c^d mod n, which recovers the original message number.
Vocabulary
- Prime number
- A prime number is a whole number greater than 1 with exactly two positive factors, 1 and itself.
- Modular arithmetic
- Modular arithmetic studies remainders after division, such as 17 mod 5 = 2.
- Euler's totient
- Euler's totient phi(n) counts how many positive integers less than or equal to n are relatively prime to n.
- Public key
- A public key is the pair of numbers shared openly so others can encrypt messages for the key owner.
- Private key
- A private key is the secret number used to decrypt messages that were encrypted with the matching public key.
Common Mistakes to Avoid
- Using p and q that are not prime, which breaks the totient formula phi(n) = (p - 1)(q - 1) and makes the key construction invalid.
- Choosing e without checking gcd(e, phi(n)) = 1, which is wrong because e must have a modular inverse for a private key d to exist.
- Treating mod as ordinary division, which is wrong because a mod n means the remainder after division by n, not the quotient.
- Trying to encrypt a message number m that is greater than or equal to n, which is wrong in basic RSA because message blocks must satisfy 0 <= m < n.
Practice Questions
- 1 Let p = 5 and q = 11. Compute n, phi(n), and decide whether e = 3 is a valid public exponent.
- 2 For RSA with n = 33 and e = 3, encrypt the message m = 4 by computing c = 4^3 mod 33.
- 3 Explain why RSA can make the public key visible to everyone while still keeping the private key secret.