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.

  1. Choose two primes pp and qq. Let n=pqn = pq and φ=(p−1)(q−1)\varphi = (p - 1)(q - 1).
  2. Choose ee with gcd⁡(e,φ)=1\gcd(e, \varphi) = 1.
  3. Find dd with ed≡1(modφ)ed \equiv 1 \pmod{\varphi}, using the extended Euclidean algorithm.
  4. Publish (n,e)(n, e). Keep dd, pp and qq secret.

To send a number m<nm < n, compute c=me mod nc = m^e \bmod n. To read it, compute cd mod nc^d \bmod n.

Why decryption undoes encryption

Euler’s theorem says that if gcd⁡(m,n)=1\gcd(m, n) = 1, then mφ≡1(modn)m^{\varphi} \equiv 1 \pmod{n}, where φ\varphi counts the numbers below nn sharing no factor with it; for n=pqn = pq, that count is (p−1)(q−1)(p - 1)(q - 1). Since ed≡1(modφ)ed \equiv 1 \pmod{\varphi}, write ed=1+kφed = 1 + k\varphi. Then

cd=med=m⋅(mφ)k≡m⋅1k=m(modn)c^d = m^{ed} = m \cdot \left(m^{\varphi}\right)^k \equiv m \cdot 1^k = m \pmod{n}

Raising to the power ee and then dd multiplies the exponent by 1+kφ1 + k\varphi, and every full φ\varphi in the exponent collapses to 11. An eavesdropper knows nn and ee but needs φ\varphi to find dd, and φ\varphi needs pp and qq. 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

  1. For p=7p = 7 and q=13q = 13, find nn and φ\varphi.

    Answer

    n=91n = 91, φ=72\varphi = 72

    Full solution

    7⋅13=917 \cdot 13 = 91 and 6⋅12=726 \cdot 12 = 72.

  2. For φ=72\varphi = 72 and e=5e = 5, find dd.

    Answer

    2929

    Full solution

    5⋅29=145=2⋅72+15 \cdot 29 = 145 = 2 \cdot 72 + 1.

  3. With φ=40\varphi = 40, is e=4e = 4 a valid choice?

    Answer

    No

    Full solution

    gcd⁡(4,40)=4\gcd(4, 40) = 4, so 44 has no inverse mod 4040.

  4. Encrypt m=2m = 2 with the public key (55,3)(55, 3).

    Answer

    88

    Full solution

    23=8<552^3 = 8 < 55.

  5. Encrypt m=9m = 9 with the public key (55,3)(55, 3).

    Answer

    1414

    Full solution

    93=729=13⋅55+149^3 = 729 = 13 \cdot 55 + 14.

  6. Decrypt c=8c = 8 with n=55n = 55 and d=27d = 27.

    Answer

    22

    Full solution

    Exercise 4 shows 22 encrypts to 88, and decryption reverses encryption.

  7. Why does publishing n=pqn = pq not reveal pp and qq 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.

  8. A student builds the key in Example 1 with d=37d = 37, the inverse of 33 modulo 5555. What goes wrong?

    Answer

    Decryption fails; dd must be the inverse modulo φ=40\varphi = 40, which is 2727.

    Full solution

    Euler’s theorem needs ed≡1(modφ)ed \equiv 1 \pmod{\varphi}. With d=37d = 37, the ciphertext 1717 decrypts to 5252 instead of 88.

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.

What to learn next