Project 3: RSA Cryptosystem from Scratch

Build a minimal RSA system that generates keys, encrypts, and decrypts messages.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 1-2 weeks
Main Language Python
Alternative Languages C++, Rust
Knowledge Area Number theory
Tools CLI
Main Book “Introduction to the Theory of Numbers” by Hardy & Wright

What you’ll build: A toy RSA implementation that demonstrates key generation, encryption, and decryption.

Why it teaches math: RSA is pure number theory in action: primes, modular arithmetic, and inverses.

Core challenges you’ll face:

  • Generating prime numbers reliably
  • Implementing modular exponentiation
  • Computing modular inverses

Real World Outcome

You will generate a keypair and successfully encrypt and decrypt a short message.

Example Output:

$ python rsa.py --gen-keys
Public key: (e=65537, n=...)
Private key: (d=...)

$ python rsa.py --encrypt "HELLO"
Ciphertext: 123456789...

$ python rsa.py --decrypt 123456789...
Plaintext: HELLO

Verification steps:

  • Encrypt and decrypt multiple test messages
  • Verify that decryption fails with the wrong key

The Core Question You’re Answering

“How can simple arithmetic properties make encryption possible?”

RSA is a direct application of modular math.

Concepts You Must Understand First

Stop and research these before coding:

  1. Prime numbers
    • Why are primes essential for RSA?
    • Book Reference: “Introduction to the Theory of Numbers” by Hardy & Wright, Ch. 1
  2. Euler’s totient
    • What is phi(n) and why does it matter?
    • Book Reference: “A Course in Number Theory and Cryptography” by Neal Koblitz, Ch. 4
  3. Modular inverses
    • How do you compute d such that e*d ≡ 1 mod phi(n)?
    • Book Reference: “A Course in Number Theory and Cryptography” by Neal Koblitz, Ch. 2

Questions to Guide Your Design

  1. Key generation
    • How large will your primes be for the demo?
    • How will you test primality?
  2. Message encoding
    • How will you map text to numbers and back?
    • What block size fits within n?

Thinking Exercise

Modular Inverse

Find the modular inverse of 3 modulo 11. Verify the result.

Questions while working:

  • Why does an inverse exist here?
  • What happens if the numbers are not coprime?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “Why does RSA rely on primes?”
  2. “What is Euler’s totient function?”
  3. “How does modular exponentiation work efficiently?”
  4. “Why is RSA hard to break?”
  5. “Why is your toy RSA not secure in practice?”

Hints in Layers

Hint 1: Starting Point Start with small primes so you can verify by hand.

Hint 2: Next Level Implement fast modular exponentiation for performance.

Hint 3: Technical Details Use the extended Euclidean algorithm to compute inverses.

Hint 4: Tools/Debugging Test each step with known small examples from textbooks.

Books That Will Help

Topic Book Chapter
Prime basics “Introduction to the Theory of Numbers” by Hardy & Wright Ch. 1
Totient function “A Course in Number Theory and Cryptography” by Neal Koblitz Ch. 4
Modular inverse “A Course in Number Theory and Cryptography” by Neal Koblitz Ch. 2

Implementation Hints

  • Keep keys small for demonstration and testing.
  • Separate key generation, encryption, and decryption steps.
  • Validate with known plaintext-ciphertext pairs.

Learning Milestones

  1. First milestone: You can generate small RSA keys.
  2. Second milestone: You can encrypt and decrypt correctly.
  3. Final milestone: You can explain why RSA works mathematically.