Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 37 · Applications: Codes and Cryptography

RSA from Scratch

Understand why RSA works using the unit group of Z_n and Euler's theorem, then build a toy RSA with the extended Euclidean algorithm in Python.

RSA is a public-key cryptosystem: anyone can encrypt a message with your public key, but only you can decrypt it with your private key. Its security rests on a one-way street of arithmetic that you can now explain with the groups and rings from this track. In this lesson you build a toy RSA from scratch.

This lesson is for learning. The numbers are tiny and the scheme is "textbook RSA", which is not secure in practice (no padding, deterministic). Real systems use keys of 2,048 bits or more with padding schemes and well-tested libraries. Never roll your own cryptography.

The group behind RSA

Let n = p q for two distinct primes. The units of ℤₙ form a group ℤₙ× of order

Text
φ(n) = (p - 1)(q - 1)

By Lagrange's theorem, the order of any element divides the order of the group, so for every a coprime to n:

Text
a^φ(n) ≡ 1  (mod n)        (Euler's theorem)

Now choose an exponent e coprime to φ(n) (the public exponent) and find d with

Text
e · d ≡ 1  (mod φ(n))        (the private exponent)

Then e d = 1 + k φ(n) for some integer k, and for m coprime to n:

Text
(m^e)^d = m^(1 + kφ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m  (mod n)

So raising to the power e is a permutation of ℤₙ× and raising to the power d undoes it. (The identity also holds for m not coprime to n, by the Chinese remainder theorem.)

The recipe

Step Action
1 Pick two large primes p, q and set n = p q.
2 Compute φ(n) = (p - 1)(q - 1).
3 Pick e with gcd(e, φ(n)) = 1 (often 65537).
4 Compute d = e⁻¹ mod φ(n) with the extended Euclidean algorithm.
5 Public key: (n, e). Private key: d.
6 Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n.

Security: given n and e, finding d requires φ(n), which requires factoring n. No efficient classical algorithm for factoring large n is known.

Extended Euclid and modular inverse

Bézout's identity says gcd(a, b) = a x + b y for integers x, y. The extended Euclidean algorithm finds them. When gcd(e, φ) = 1 it gives e x + φ y = 1, so x is the inverse of e modulo φ. Here is the whole toy system:

Python Toy RSA with the extended Euclidean algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the check covers all n messages, including ones sharing a factor with n. The identity holds for every m, not only for units.

Turning text into numbers

Messages are text, but RSA works on numbers smaller than n. In real use, you convert bytes to an integer and apply padding. For a toy, we encode each character separately with n = 3233 (larger than any code point we use). This demonstrates the mechanism only.

Let's also attack our own toy key: trial division factors a 12-bit n instantly, which is why real keys use primes of 1,000 bits or more.

Python Encrypt a word, then break the toy key by factoring

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The attack succeeds because trial division needs only about √n steps. For a 2,048-bit modulus, √n has about 1,024 bits. Better algorithms than trial division exist, but none is fast enough to break well-chosen large keys.

Where the algebra shows up

  • Group theory: ℤₙ× has order φ(n); Lagrange's theorem gives Euler's theorem.
  • Ring theory: ℤₙ ≅ ℤₚ × ℤ_q (Chinese remainder theorem) lets real implementations decrypt about four times faster by working mod p and mod q separately.
  • Number theory: primality tests (such as Miller-Rabin) generate the large primes.

The next lesson uses a different group, a cyclic group of prime order, for key exchange: Diffie-Hellman and discrete logarithms.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is phi(n) for n = p q with distinct primes p and q?

    The units of Z_n correspond to pairs of units mod p and mod q, giving (p - 1)(q - 1).
  2. 2. Which condition must the public exponent e satisfy?

    Only then does e have an inverse d modulo phi(n).
  3. 3. Which theorem explains why (m^e)^d = m for m coprime to n?

    m^phi(n) = 1 in the unit group, and e d = 1 + k phi(n).
  4. 4. Why does the toy key above offer no real security?

    Factoring n reveals phi(n), from which anyone can compute d.

Summary

  • RSA works in the unit group ℤₙ× of order φ(n) = (p - 1)(q - 1).
  • Euler's theorem (from Lagrange's theorem) gives m^(e d) ≡ m when e d ≡ 1 (mod φ(n)).
  • The extended Euclidean algorithm computes the private exponent d.
  • Security rests on the difficulty of factoring n; toy sizes are trivial to break.
  • Textbook RSA needs padding and large keys in real use.

Next: Diffie-Hellman and Discrete Logarithms