Cryptic Stash

Disclaimer: This library is created for fun and educational purposes and should not be used in any real software project. A well-tested library such as OpenSSL should be used instead to ensure optimal security.

I've always wanted to create a library of my own, but I’ve struggled to come up with unique ideas for one that solves a real-world problem. While a cryptography library isn’t unique, and is actually strongly discouraged for most developers to write. However I still decided to pursue this project because I believe the best way to learn something is by doing it yourself, even if it means reinventing the wheel. And I have also come to realization that a project can be very interesting even if it serves practically no purpose in real life, other than making me happy!

Implementing this library from scratch has been an excellent learning experience. Learning cryptography involves much more than just studying and reading the algorithms standardized by NIST. To truly understand an algorithm and why it was chosen as a standard, we need to understand the underlying math that makes one algorithm more secure than others. The math involved is what makes this field so fascinating to me.

I hope to eventually turn this project into a basic, functional TLS stack, and it could also serve as a good target for me to practice cryptanalysis as I begin learning that.

Basic Math Functions

To truly appreciate the math behind cryptography, I decided to start with the basics: arithmetic operations like addition, subtraction, multiplication, and division. These are fundamental operations that we learned in elementary school, and they come so naturally to us that we often perform them without thinking—or, more likely, with a calculator! While these operations sound simple, implementing them in software has proven to be far from easy. Basic operations with 32-bit or 64-bit integers can be handled by C without much trouble, but modern cryptography requires computations with huge integers that are far larger than 64 bits. There is no primitive data type for these large integers, so I had to create a custom structure to hold them, representing each large integer as an array of digits, with each digit being 32 bits long.

In my implementation, I made it so that the integers can grow in size dynamically. However, this is not an ideal approach, as it often requires memory reallocation based on input, which can sometimes include sensitive data like private keys. This introduces timing variance during runtime, creating a side-channel vulnerability that could compromise secret data. A better approach would be to use fixed-size integers depending on the algorithm.

Since each integer is essentially an array of digits, I had to revisit the manual addition and subtraction algorithms we learned in elementary school, where calculations are done digit by digit with carry, and recreate these in code. Aside from the algorithm itself, there are other challenges, such as overflow. Since each digit is 32 bits, when the result of an addition exceeds 32 bits, a new digit must be created and added to the array. This issue happens frequently with multiplication, so careful handling was required.

Of all these basic operations, division was the hardest to implement. After some research, I quickly realized why division is generally avoided in cryptographic use: there aren’t many good division algorithms that run in constant time. However, for the sake of completeness, I decided to implement division anyway, even if it won’t be used much. The algorithm I have now is… well, not great, but it can return both the quotient and the remainder, so it works as a modulo operation too. That said, I’ll need a better modulo algorithm in the future, as it’s used extensively in modern public-key algorithms.

As of now, I believe my big integer library includes all the basic arithmetic and number theory algorithms (even though they are not fully optimized) for cryptographic use. Below is the source code.

There are probably plenty of bugs (non-security-related) in this code, as I have only implemented basic test cases for each function. Please open an issue on my repo if you spot any! As for security-related bugs, I think it will be fun to exploit them later when I start learning cryptanalysis.

I am also looking into more optimized big integer algorithms for modulo operations, such as Montgomery Multiplication, Barrett Reduction, etc.

I will update this post regularly with other topics, such as encryption/decryption algorithms, hash algorithms, and more.