This is a project for the Distributed Systems 2023 course at the University of Oulu.
The goal of this project is RSA codebreaking for reasonably sized input. Given a RSA number N, we'd like to find its factors such that we could break a code that is encoded using it. We do this by creating a system which runs a distributed version of the Quadratic Sieve method for factoring large primes.
There is a Makefile in this directory. You need Docker v20.10.6 or greater in order to run it. make up should build and run the project. If you wish to make changes and restart you can run make recompose. To stop, you can run make down. You can also change the number of workers by updating the --scale parameter in the Makefile.
There is a simple frontend for this application in the /front/index.html file. This can be opened in your browser. You can generate new example input here: https://bigprimes.org/RSA-challenge. You can also verify that the primes we found are correct here 🤠. Alternatively, the API can be accessed directly at 0.0.0.0:5000/api/factorize/.
This project has some observability options. You can see some metrics on the processes at 0.0.0.0:8889 where a Flower app is running. You should also be able to see docker compose rainbow logs from your make up command for all the containers.
In this diagram you can see the main flow of the application. Our user input comes from a simple HTML frontend. It makes an HTTP request to our main node which is responsible for coordinating the work associated with factoring the integer provided. The main node queues up work in our RabbitMQ worker queue which is a Celery task queue. The workers are each Celery worker nodes which pull tasks off of the queue and place the result in a Redis database. The main node then collects these results and does some further calculations with the aggregated results. The result is then returned in the same original HTTP request.
A bit of explanation on the distributed nature of this problem. The Quadratic Sieve algorithm lends itself well to parallelization and we attempt to take advantage of this in this system by distributing the independent work across multiple nodes. The idea being that this could potentially scale and result in faster performance. We distribute the work in two different places where there is often a bottleneck and also where there is clearly independent work.
In both the factor base discovery and the B-smooth searching, we dole out the parallel work to our workers so that it may be completed concurrently.
- We used Docker and docker compose for our container and orchestration layer. These tools are familiar and well suited to this sort of standalone toy project.
- We used Celery for our distributed task queue. This is because it's scalable and quick to set up a main node with a worker queue. Our workflow is quite simple so mostly we wanted something that would be straightforward to implement.
- We used Redis as our backend for the task result queue. Redis is highly scalable and fast database which really should have no performance bottlenecks at our scale.
- We used RabbitMQ as our MQTT message broker since MQTT is the supported protocol in Celery and Rabbit is a well-known broker for this protocol.
- We used Flask for our HTTP API since it is a standard and simple way to create HTTP servers in Python.
You can do your own benchmarking by running make benchmark. This uses Locust which must be installed. We have a user test built in which runs a few 60-bit, 80-bit and one 120-bit primes. You can add your own tests if you'd like. The results from running these on my Macbook Pro 2020 1.4 GHz Quad-Core Intel Core i5 are stored in some CSV files in this repo. Each file was generated using a different number of worker nodes. You can run the graph_results.py script if you want to see these yourself.
- The Quadratic Sieve code is almost all originally written in this repo: https://github.com/NachiketUN/Quadratic-Sieve-Algorithm
- A lot of inspiration for the overall structure of the project and using Celery with Docker came from this repo: https://github.com/tanchinhiong/decoupled-celery-example
Some other stuff I read that was good inspiration / interesting: