Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 40 ยท Public-Key Cryptography

RSA from Scratch

Build RSA in plain Python: generate primes and keys, encrypt and decrypt, speed up decryption with the CRT, and watch a small modulus fall to a factoring attack.

RSA, named after Rivest, Shamir and Adleman (1977), is the most famous public-key algorithm. It is also one of the shortest to implement: key generation, encryption and decryption together take about twenty lines of Python, because you already own all the ingredients. Modular exponentiation does the encrypting, the extended Euclidean algorithm finds the private exponent, Miller-Rabin supplies the primes, and Euler's theorem explains why it all works.

In this lesson you will build textbook RSA: the bare mathematical core. Textbook RSA is never safe to use directly, and the next lesson shows exactly why. Understanding the core first makes the attacks and the fixes obvious.

The algorithm

Key generation

  1. Choose two large random primes p and q.
  2. Compute the modulus n = p * q.
  3. Compute phi = (p - 1) * (q - 1), the number of integers below n that are coprime to it.
  4. Choose a public exponent e that is coprime to phi. The value 65537 (2**16 + 1) is the near-universal choice: it is prime, and it has only two 1-bits, so encryption needs few multiplications.
  5. Compute the private exponent d = e^-1 mod phi.

The public key is (n, e). The private key is d (together with p and q, which you keep for speed).

Encryption and decryption

  • Encrypt a number m with 0 <= m < n: c = m^e mod n.
  • Decrypt: m = c^d mod n.

Why it works: because e * d = 1 + k * phi for some integer k, Euler's theorem gives m^(e*d) = m * (m^phi)^k = m (mod n) whenever m is coprime to n. (It also holds for the rare other m, by the Chinese Remainder Theorem.)

Why it is hard to break: anyone can see n and e. To compute d they need phi, and to compute phi they appear to need p and q, which means factoring n. That is the trapdoor from the big-idea lesson.

flowchart TD
    P["Pick primes p and q"] --> N["n = p * q"]
    P --> F["phi = (p-1)(q-1)"]
    F --> D["d = e^-1 mod phi"]
    E["e = 65537"] --> D
    N --> PUB["Public key (n, e)"]
    E --> PUB
    D --> PRIV["Private key d, p, q"]

Everything public derives from n and e; the private exponent needs phi, which needs the factors.

Building RSA in Python

The program below generates a 512-bit key (two 256-bit primes). 512 bits is far too small for real use (anything under 2048 is unsafe today), but it keeps the demos quick. It uses a seeded random.Random so every run prints the same numbers; a real key generator must draw randomness from the operating system's CSPRNG (see randomness).

Messages are turned into numbers with int.from_bytes. A 512-bit modulus holds at most 63 bytes of text, and the number must stay below n.

Python Generate an RSA key pair, encrypt and decrypt

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.

Try changing the seed to see a different key, or the message to anything up to 63 bytes. A longer message produces a number larger than n, and RSA would silently reduce it modulo n, producing a wrong decryption; real schemes split the work as in the hybrid scheme from the earlier lesson.

Speeding up decryption with the CRT

Decryption uses the huge exponent d, which makes it the expensive operation. The owner of the key knows p and q, so they can use the Chinese Remainder Theorem (CRT, from the number theory lesson): do two exponentiations modulo the half-sized primes and combine the results.

  1. Precompute dp = d mod (p - 1), dq = d mod (q - 1) and qinv = q^-1 mod p.
  2. Compute mp = c^dp mod p and mq = c^dq mod q.
  3. Combine: h = qinv * (mp - mq) mod p, then m = mq + h * q.

Each exponentiation works with numbers half as long and exponents half as long, so each costs about an eighth of the full one; two of them take roughly a quarter of the time. Real libraries nearly always decrypt and sign this way, though it needs care: a single computation error in a CRT signature can leak the factorization of n (the Bellcore attack), so implementations verify the result before releasing it.

Python CRT decryption gives the same answer, faster

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.

Breaking a small key by factoring

The only protection RSA has is the difficulty of factoring n. When n is small, an attacker does exactly what the public-key lesson predicted: factor it, recompute phi, compute d, and decrypt anything. The attack below breaks a 40-bit modulus by trial division, and a 64-bit one with Pollard's rho, a clever method that finds a factor p in about sqrt(p) steps instead of p steps.

Python Factoring small RSA moduli

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 64-bit modulus fell almost instantly, after roughly the square root of a 32-bit prime in steps. Record-setting factoring efforts use much stronger algorithms (the number field sieve) on far more hardware, and have reached 829-bit moduli. That is why guidance asks for at least 2048 bits today, and 3072 bits for new long-lived systems.

Choosing the key and the exponent

  • Size. 2048 bits minimum, 3072 for longer protection. Each doubling of the modulus makes decryption about 8 times slower, which is another reason elliptic curves are popular.
  • Exponent. Use 65537. A tiny exponent such as 3 is faster but opens attacks, shown in the next lesson.
  • Primes. Choose them from a CSPRNG, make them similar in length but not close together, and never reuse a prime across keys.
  • Use a library. Production code should never contain a hand-written RSA. Libraries handle padding, constant-time arithmetic, key validation and fault protection.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the RSA modulus n?

    n = p * q. It is public. Security rests on the difficulty of recovering p and q from n.
  2. 2. Which key does a sender use to encrypt a message to Bob with RSA?

    Encryption is c = m^e mod n with Bob's public values. Only Bob's d, which needs the factors of n, inverts it.
  3. 3. How is the private exponent d related to e?

    e * d = 1 modulo phi, which is what makes decryption undo encryption through Euler's theorem.
  4. 4. Why does CRT decryption run faster?

    Two exponentiations with half-length numbers and exponents cost about a quarter of one full-size exponentiation.
  5. 5. Why can a 40-bit RSA modulus be broken on a laptop in a fraction of a second?

    Knowing p and q gives phi and then d = e^-1 mod phi. Factoring a number that small takes at most a million trial divisions.

Summary

  • RSA key generation: choose primes p and q, set n = p*q, pick e = 65537, and compute d = e^-1 mod (p-1)(q-1).
  • Encrypt with c = m^e mod n; decrypt with m = c^d mod n. Euler's theorem makes this a round trip.
  • Security is the difficulty of factoring n; small moduli fall instantly to trial division or Pollard's rho.
  • The CRT lets the key owner decrypt and sign about four times faster using p and q.
  • What you built is textbook RSA: deterministic and malleable. Real systems always add padding.

Next: RSA Padding and Common Pitfalls, where textbook RSA gets attacked and OAEP and PSS come to the rescue.