Discrete Math · Undergraduate
RSA Encryption: Public Keys from Modular Arithmetic
Quick answer
RSA lets anyone encrypt a message with a public key while only the owner of the private key can decrypt it. Choose primes p and q, let n = pq and φ = (p − 1)(q − 1), pick e with gcd(e, φ) = 1, and find d with ed ≡ 1 (mod φ) using the extended Euclidean algorithm. A message m is encrypted as c = mᵉ mod n and recovered as cᵈ mod n. Euler's theorem makes decryption undo encryption, and finding d from n and e requires factoring n, which is impractical for numbers hundreds of digits long.
What you'll learn
- Build an RSA public and private key from two primes
- Encrypt and decrypt with fast modular exponentiation
- Explain why decryption works using Euler's theorem
- Explain why security depends on the difficulty of factoring
A lock anyone can close
In ordinary codes, the key that locks a message also unlocks it. RSA splits them: a public key that anyone can use to encrypt, and a private key that only its owner can use to decrypt. The steps use only modular arithmetic.
- Choose two primes and . Let and .
- Choose with .
- Find with , using the extended Euclidean algorithm.
- Publish . Keep , and secret.
To send a number , compute . To read it, compute .
Why decryption undoes encryption
Euler’s theorem says that if , then , where counts the numbers below sharing no factor with it; for , that count is . Since , write . Then
Raising to the power and then multiplies the exponent by , and every full in the exponent collapses to . An eavesdropper knows and but needs to find , and needs and . Real keys use primes with hundreds of digits, and no known method factors their product in any practical time.
Worked examples
Common mistakes
Practice problems
-
For and , find and .
Answer
,
Full solution
and .
-
For and , find .
Answer
Full solution
.
-
With , is a valid choice?
Answer
No
Full solution
, so has no inverse mod .
-
Encrypt with the public key .
Answer
Full solution
.
-
Encrypt with the public key .
Answer
Full solution
.
-
Decrypt with and .
Answer
Full solution
Exercise 4 shows encrypts to , and decryption reverses encryption.
-
Why does publishing not reveal and for real keys?
Answer
Factoring a product of two very large primes takes far too long with any known method.
Full solution
Multiplying is fast and the Euclidean algorithm is fast, but no fast factoring method is known for numbers hundreds of digits long.
-
A student builds the key in Example 1 with , the inverse of modulo . What goes wrong?
Answer
Decryption fails; must be the inverse modulo , which is .
Full solution
Euler’s theorem needs . With , the ciphertext decrypts to instead of .
Frequently asked questions
What are the public and private keys in RSA?
The public key is the pair (n, e), shared with everyone. The private key is d, kept secret. Together they satisfy ed ≡ 1 (mod φ(n)).
How is a message encrypted and decrypted?
Encrypt a number m < n as c = mᵉ mod n. Decrypt by computing cᵈ mod n, which gives back m.
Why does decryption give back the message?
ed = 1 + kφ(n) for some k, and Euler's theorem says m^φ(n) ≡ 1 (mod n) when gcd(m, n) = 1. So m^(ed) = m · (m^φ(n))ᵏ ≡ m.
Why is RSA secure?
Computing d needs φ(n) = (p − 1)(q − 1), which needs the factors p and q. Multiplying primes is fast, but factoring a product of two large primes is far too slow with known methods.
How are large powers computed quickly?
By repeated squaring: compute m, m², m⁴, m⁸, … mod n, and multiply the ones matching the binary digits of the exponent.