Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 37 ยท Cryptographic Applications

RSA from Scratch

Build RSA in plain Python: choose primes, compute keys with Euler's theorem, encrypt and decrypt, sign messages, and speed up decryption with the CRT.

RSA, published by Rivest, Shamir and Adleman in 1977, was the first practical public-key cryptosystem. Anyone can lock a message with your public key; only you can unlock it with your private key. Its security rests on a number-theory asymmetry: multiplying two primes is easy, but recovering them from the product (factoring) is believed to be hard.

You already have every ingredient: modular exponentiation, Euler's theorem, modular inverses from the extended Euclidean algorithm, and Miller-Rabin prime generation. This lesson assembles them into a working toy RSA and explains why it works. The code here is for learning; real systems use vetted libraries and padding.

Key generation

  1. Choose two large distinct primes p and q.
  2. Compute the modulus n = pยทq and ฯ†(n) = (p - 1)(q - 1).
  3. Choose a public exponent e with gcd(e, ฯ†(n)) = 1 (commonly 65537).
  4. Compute the private exponent d = eโปยน mod ฯ†(n).

The public key is (n, e), the private key is (n, d) (and the primes, kept secret or discarded).

Python Generating a small RSA key

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 last line prints 1: that is the defining property of d.

Why decryption works

To encrypt a message number m (with 0 โ‰ค m < n), compute c = m^e mod n. To decrypt, compute c^d mod n. Why does that return m? Because eยทd = 1 + kยทฯ†(n) for some k, so

c^d = m^(ed) = m ยท (m^ฯ†(n))^k โ‰ก m ยท 1^k = m (mod n)

by Euler's theorem, when gcd(m, n) = 1. The identity also holds if p or q divides m, which one checks prime by prime using Fermat's little theorem and the Chinese remainder theorem. Try a tiny example where every number can be verified by hand.

Python The classic small example

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 final line checks all 3233 possible messages, including the ones divisible by 61 or 53, which confirms the theory.

Encrypting text

A message such as "hello" must first become a number below n. A direct way is int.from_bytes. If the text is longer than the modulus, split it into blocks. (Real protocols use RSA only to transport a short symmetric key.)

Python Encrypt and decrypt a short text

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 ciphertext is a roughly 154-digit number, and decryption restores the sentence exactly.

Digital signatures

Reverse the roles: sign a message hash h with the private key, s = h^d mod n, and anyone can verify with the public key by checking s^e mod n == h. Only the owner of d can produce s, and any change in the message changes h.

Python Sign and verify

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 first check prints True and the tampered message prints False. (A production scheme such as RSA-PSS adds randomized padding to the hash before signing.)

Speeding up decryption with the CRT

Decrypting with a 2048-bit d mod a 2048-bit n is slow. Because n = pq, we can compute modulo p and q separately with half-size numbers and recombine with the Chinese remainder theorem: about four times faster.

m_p = c^(d mod (p-1)) mod p, m_q = c^(d mod (q-1)) mod q, h = qโปยน(m_p - m_q) mod p, m = m_q + hยทq.

Python CRT decryption

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 speed-up is why every real RSA private key stores p, q, dp, dq and qinv. (A flaw in this computation, such as a single bit error, can leak the key, so implementations double-check the result.)

flowchart LR
    G["generate p, q"] --> N["n = p*q"]
    N --> E["choose e"]
    E --> D["d = e^-1 mod phi(n)"]
    M["message m"] -->|"m^e mod n"| C["ciphertext c"]
    C -->|"c^d mod n"| M2["message m"]

Key generation, encryption and decryption.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which pair is the public key?

    Anyone may know n and e. The private exponent d (and the primes) must stay secret.
  2. 2. Why does c^d mod n return m?

    m^(ed) = m * (m^phi)^k, which is m modulo n.
  3. 3. For p = 61, q = 53, e = 17, what is phi(n)?

    (61 - 1)(53 - 1) = 60 * 52 = 3120.
  4. 4. What is the benefit of CRT decryption?

    Each half-size exponentiation is about eight times cheaper than a full-size one, so two of them cost about a quarter.

Summary

  • RSA picks primes p, q, publishes n = pq and e, and keeps d = eโปยน mod ฯ†(n).
  • Encryption c = m^e, decryption m = c^d (mod n); correctness comes from Euler's theorem.
  • Signatures use d to sign a hash and e to verify.
  • CRT decryption works modulo p and q separately and is about four times faster.
  • Textbook RSA is unsafe on its own: next, see why padding matters.

Next: RSA Attacks and Padding