RSA from Primitives | Python Implementation

A from-scratch Python implementation of RSA. Every algorithm is hand-implemented (Fast Modular Exponentiation, Euclidean Algorithm, Extended Euclidean Algorithm, brute-force factorization) rather than calling out to a cryptography library. The notebook covers key generation, encryption, decryption, and a working brute-force attack that recovers the private key by factoring the modulus.

Why I Built This

There is a meaningful difference between knowing what rsa.encrypt() does at the API level and understanding why each line of the implementation has to be the way it is. Building from primitives was the way I closed that gap.

The brute-force attack code in the same notebook makes the point explicit. RSA is not secure because it hides the math. It is secure because factoring large semi-primes is computationally infeasible against current hardware. The attack works against the small moduli I use as examples and stops working at production key sizes for exactly the reason RSA is supposed to be safe.

What It Does

The notebook walks through the complete RSA pipeline:

• Key generation: choose two primes (p, q), derive the modulus n = p*q, find a public exponent e coprime to φ(n), and derive the private exponent d via the Extended Euclidean Algorithm
• Encryption: c = m^e mod n, computed via Fast Modular Exponentiation
• Decryption: m = c^d mod n, the same primitive
• Cryptanalysis: brute-force factorize n to recover (p, q), then derive d and decrypt any captured ciphertext encrypted under the corresponding public key
• Interactive CLI: a menu-driven program that wraps the implementation in a usable command-line tool

Honest Assessment

The repo includes a security analysis section that names at least five reasons this implementation should not be used for anything beyond learning:

1. Insecure random source. Python’s random module (Mersenne Twister) is predictable; production code uses secrets.
2. No padding scheme. Textbook RSA leaks structural information; real RSA uses OAEP.
3. Character-by-character encoding. Each character is encrypted independently, which exposes the message to frequency analysis. Production cryptography uses hybrid encryption (symmetric cipher for the data, RSA for the key exchange).
4. No defense against side-channel attacks. Timing and power-analysis attacks are not considered.
5. Key sizes are too small. The primes used as examples are factorable in seconds. Industry standard is 2048-bit n minimum, with NIST recommending 3072 or higher for systems intended to remain secure past 2030.

The gap between this implementation and production RSA is exactly the point. The math is the easy part. Real cryptographic engineering is everything that surrounds the math: entropy, padding, side channels, key management, hybrid construction. Building this implementation was the way I started understanding what that gap actually contains.

Course Context

This project was originally completed for an applied computer science course at the University of Colorado Boulder. The mathematical structure, algorithms, and overall project shape were specified by the course. The implementation, the security analysis, the brute-force attack code, the interactive CLI, and the documentation in the repository are my own work.