Educational cryptography case study

RSA Factoring Roadmap: From Trial Division to Quadratic Sieve

A cryptography course project exploring how RSA can be broken when the modulus is small enough to factor, using Python, number theory, and iterative algorithm testing.

This project started with a public RSA key and the question: can we recover the private key by factoring the modulus? Our group tested multiple factoring strategies, learned from failed attempts, and eventually used Quadratic Sieve ideas to recover the factors and decrypt the message.

Project tags

PythonCryptographyNumber TheoryRSAQuadratic SieveAlgorithmsResearch-style Project

This is a toy RSA / educational cryptography project, not a real-world RSA hacking demo.

Public exponent

e = 5

Modulus size

70 digits / 233 bits

First factor found

947

Hard remainder

67 digits / 223 bits

QS smoothness bound

1,257,807

Factor base size

48,763 primes

Prerequisite 01

How RSA Works

The one idea needed before following the roadmap: RSA separates a public encryption key from a private decryption key.

An RSA public key is defined by (e, n). The modulus n is a large composite number, usually formed as n = p x q. Encryption transforms a numerical message m into ciphertext c.

c = m^e mod n

To decrypt, we need the private exponent d, where d = e^-1 mod phi(n). Factoring n reveals p and q, making phi(n) = (p - 1)(q - 1) easy to compute. From there, we can recover d and decrypt with m = c^d mod n.

01 / Public key

(e, n)

The modulus n is the product of two primes, p and q. The exponent e is public.

02 / Encrypt

c = m^e mod n

A plaintext number m is raised to e modulo n to produce the ciphertext c.

03 / Recover the key

d = e^-1 mod phi(n)

The private exponent d is the modular inverse of e, but computing it requires phi(n).

04 / Decrypt

m = c^d mod n

Applying the private exponent reverses the encryption and recovers the plaintext number.

The project's central insight: knowing the public key is not enough to compute phi(n) efficiently, but successfully factoring this educational toy modulus makes the private key recoverable.

Prerequisite 02

Why RSA Decryption Works

Before understanding RSA decryption, we need one important idea from modular arithmetic: the modular inverse. Encryption raises the message m to the public exponent e:

c ≡ m^e (mod n)

01 / Choose the inverse

The private exponent d is chosen so that:

ed ≡ 1 (mod φ(n))

This means d is the modular inverse of e modulo.
Equivalently, for some integer k:

ed = 1 + kφ(n)

02 / Apply the private exponent

During decryption, we raise the ciphertext to d. Substituting the encryption equation gives:

c^d ≡ (m^e)^d ≡ m^ed (mod n)

m^ed = m^1+kφ(n) = m · (m^φ(n))^k

03 / Use Euler's theorem

When m and nare relatively prime, Euler's theorem tells us:

m^φ(n) ≡ 1 (mod n)

The repeated factor therefore collapses to 1 under modulo n.

04 / Recover the message

m · (m^φ(n))^k ≡ m · 1^k ≡ m (mod n)

Therefore, decrypting c with the private exponent d returns the original message m.

In simple terms: RSA works because the encryption exponent e and decryption exponent d are chosen to undo each other under modular arithmetic.

Stage 01

The Problem

Problem

RSA security relies on the difficulty of factoring large composite numbers.

Given a public key, the goal was to factor n, compute phi(n), recover the private key d, and decrypt the message.

Public Key

Factor n

Compute phi(n)

Recover d

Decrypt

Our task was to decrypt an RSA encrypted message using only the public key and ciphertext below.

Public key (e, n)

(5, 8721717648951034180751989933592484457226804450832605710315649207114191)

Encrypted message / ciphertext c

2016279054524078341299256251568889523037078816031686455795312148201129

The modulus is a 70 digit, 233 bit number n, and the encrypting exponent e = 5.

Attack route chosen

We focused on factoring n because recovering the factors makes phi(n) computable, which then makes the private exponent d recoverable.

Routes not pursued

We considered low-exponent and implementation attacks, but Coppersmith-style methods required extra assumptions, and timing/side-channel attacks required access to a real implementation.

Stage 02

Early Attempts

Tried

Before moving to a stronger method, our group tested several classic factoring strategies and treated each result as a clue.

Stage 03

From Direct Factoring to Sieving

Breakthrough

After simpler factoring methods failed, the project moved toward the Quadratic Sieve, which reframes factoring as finding enough smooth relations and solving a linear algebra problem over GF(2).

Smooth Relations

Factor Base

Matrix over GF(2)

Null Space

GCD

Factors

Smooth number

A number is y-smooth when all of its prime factors are at most y. QS searches for many smooth values because their exponent patterns can be combined into squares.

Factor base

The selected list of small primes used to test and represent smooth relations. In our run, the base included -1 and 48,762 positive primes.

Relation

A pair built from a candidate x and x^2 - n. When x^2 - n factors completely over the factor base, that row becomes useful linear algebra data.

GF(2) null space

Exponent vectors are reduced mod 2. A dependency whose sum is the zero vector means the selected relations multiply into a perfect square.

Stage 04

Quadratic Sieve Pipeline

Pipeline

The final approach became a staged process: generate relations, translate them into parity vectors, find dependencies, and recover factors.

Choose a smoothness bound

Build a factor base

Generate sieve intervals

Collect smooth relations

Convert relations into exponent vectors

Build a matrix over GF(2)

Find null space dependencies

Recover non-trivial factors with GCD

Compute the RSA private key

Decrypt the plaintext

Stage 05

Engineering Notes

Built

The project was as much about implementation tradeoffs as number theory: runtime, intervals, relation collection, and matrix operations all mattered.

Implemented core logic in Python
Used integer arithmetic and custom / library square root handling
Estimated a smoothness bound near 1,257,807 and built a factor base with 48,763 entries
Ran sieving over 5 million number intervals and observed roughly 10-15 relations per interval
Manually parallelized relation collection across different computers / terminals and merged 70,000+ relations
Used Meataxe matrix operations over GF(2) for null space computation
Learned that algorithm choice and implementation details matter a lot for runtime

From the group repository

Selected implementation excerpts

Recovering the numerical plaintext

rsa.py

Once the prime factors were known, this helper computed phi(n), found the modular inverse of e, and applied modular exponentiation.

def rsa_decrypt(cypher, d, n):
    return pow(cypher, d, n)

def special_function(factors_of_modulus, exponent, cypher):
    totient = mul([x - 1 for x in factors_of_modulus])
    private_exponent = extended_euclidean(totient, exponent)
    modulus = mul(factors_of_modulus)
    return rsa_decrypt(cypher, private_exponent, modulus)

Turning a relation into a GF(2) row

QS.py

Each smooth relation became a parity vector: every division by a factor-base prime toggled that prime’s exponent bit.

def new_representation(factorBase, relation, composite):
    number = pow(relation, 2, composite)
    binary_list = [False] * len(factorBase)

    if number < 0:
        binary_list[0] = True
        number = abs(number)

    for index in range(1, len(binary_list)):
        prime = factorBase[index]
        while number % prime == 0:
            binary_list[index] = not binary_list[index]
            number //= prime

    return binary_list

Finding dependencies with Meataxe

QS.py

The relation matrix was exported over GF(2), converted to Meataxe format, and passed through its null-space operation.

def meataxe_linear_dependance(factorBase, composite, relations):
    matrix = build_matrix(factorBase, relations, composite)
    export_matrixTXT(matrix, "meataxe/matrix1.txt")

    subprocess.run(["zcv", "meataxe/matrix1.txt", TEMP_MATRIX_FILE])
    subprocess.run(["znu", TEMP_MATRIX_FILE, TEMP_MATRIX_FILE_NULL])
    subprocess.run(["zpr", TEMP_MATRIX_FILE_NULL, "meataxe/matrix2.txt"])

    null_space = read_matrix_from_file("meataxe/matrix2.txt")
    return n_zero_vector_combination(null_space, relations)

Excerpts are lightly renamed and formatted for presentation. The underlying algorithmic steps come from the Spring 2024 group repository.

Stage 06

Final Reveal

Solved

Once the factors were recovered, we computed the private key and decrypted the educational toy RSA message.

toy-rsa-decrypt.py

> factoring modulus...

> collecting relations...

> building matrix over GF(2)...

> recovering factors...

> decrypting message...

Final decrypted message

"IT IS BY STANDING ON THE SHOULDERS OF GIANTS"

n = 947 * 2257187839841721982510344526578229 * 4080227156941526084162391407957057

phi(n) was computed from the recovered prime factorization.

The private exponent d was found as the modular inverse of e = 5 modulo phi(n).

The numeric plaintext was decoded into letters using a 1-26 mapping with ambiguity checks.

Stage 07

Reflection

Learned

The strongest lesson was how mathematical theory, algorithm design, implementation details, and runtime constraints connect in practice.

This project helped me understand how mathematical theory, algorithm design, implementation details, and runtime constraints connect in practice. It also showed me that solving technical problems often means trying several approaches, learning from failed assumptions, and gradually moving toward a more scalable method.

Learning focus

Problem solving through mathematical modeling, algorithm selection, Python implementation, and careful runtime observation.