I recently finished a project I've been working on: primitive-rsa, a from-scratch implementation of RSA in C17.
I initially started this project after the original RSA paper.
I was quite amazed since I only recently started learning about cryptography how much simple RSA encryption actually is (atleast on paper).
So I thought maybe I should try implementing it.
But ended up thinking I should do it from scratch means implementing in C (It was my first time building a project in C) and not relying on libraries (no GMP).
So I tasked myself with implementing an arbritary precision library or simply bigint library in C which atleast provides all the necessary arithmatic operations required by RSA.
Than I finally realised why people say it's pain to handle memory.
Literaly whenever I call a function like basic add(a,b) i need to check return result for allocation failure and if allocation fails I needed to free all the holding resource carefully.
It may sound simple but when implementing an complex algorithm like FFT where we have so many operations in single function.
Each functions call becomes a pain to write.
Although it was quite headache to always think about allocation failures, memory leaks, or can this be optimized with SIMD or will this integer overflow. Will it fit in 64 bit etc.
I learnt a lot, different cleanup patterns in C. Different algorithms like FFT / NTT, Chinese remainder theorem is used. Finite spaces like how montgomery reduction is used to avoid division operation and much more.
I ended up implementing several components myself:
A custom arbitrary-precision integer library.
Schoolbook and FFT/NTT multiplication.
Knuth's Algorithm D for division.
Montgomery reduction for modular exponentiation.
Miller–Rabin primality testing.
Extended Euclidean Algorithm.
RSA key generation, encryption and decryption.
I also tried to explore implementation efficiency rather than relying on existing BigInt or cryptography libraries.
This was primarily a learning project, and it's not intended for production use.
It was a great exercise in C, number theory, algorithms and understanding how cryptographic systems work under the hood.
I'd love to hear feedback, particularly on the BigInt implementation, algorithm choices, and project architecture. I'm still learning, so constructive criticism is very welcome!
AI usage: mostly for docs and demonstration code (in main.c) and for snippets like logging and some testing codes.
GitHub: https://github.com/akramdevstuffs/primitive-rsa