Read about num-primes | Docs
Read about ramp-primes | Docs
Read about openssl-primes
I apologize if the writing is all over the place as I have been staying up late, coding a lot.
I recently showed off my work on a rust library (ramp-primes) for generation of large composite, prime, and safe prime numbers and received a positive response. However, I had concerns over the library, partly due to it having inline assembly and running on unstable rust (nightly toolchain).
I also wanted to improve on the API and to use a library with a larger amount of downloads, so here came the bright idea to develop a new library: num-primes
The aim of these projects is to develop an alternative to openssl-primes, possibly with faster results.
A Safe Prime can be defined as a prime that follows the following and results in a prime itself:
2q + 1 or (p-1)/2An example of a safe prime would be 5
These primes are useful in cryptography such as in the DH key exchange and usually require a large bit-size for use in cryptography, but these primes are also difficult to generate. They also are useful in some zero-knowledge range proofs.
Even with OpenSSL-primes, it can take around 1-2 minutes to generate a 1024 bit Safe Prime for use in DH.
Before continuing, I recommend you read the README of num-primes available here as it describes all the new features and the differences.
num-primes was meant to be my rust library for generating composite, prime, and safe prime numbers with a simple API and easy to understand syntax, and while using not only pure rust, but also using the stable branch of the rust toolchain.
The num library has over ~6,000,000 downloads compared to RAMP which only had around ~17,000.
From the project, erupted three structs with multiple new methods that extended the functionality. These structs were:
At first, I felt the project turned out great and would be a successor to ramp-primes but I quickly realized I was facing heavy performance issues especially in Safe Prime Generation.
This post will detail out the problems I faced and what I plan on doing in the future.
RAMP and num offer two related but also distinctly different. Both offer bignum integers but ramp is more focused on high performance. As per RAMP:
The
numcrate provides some bignum types that can be used, so why use Ramp? Well, Ramp is specifically focussed on multiple-precision arithmetic, whilenumis a general-purpose numerics library that happens to provide some multiple-precision arithmetic.You should
numif you aren't able to use unstable Rust features or just want a small amount of functionality. Ramp should be used when you need high-performance and extra functionality.
While ramp-primes can easily generate a 512-bit safe prime in around a minute or two, num-primes has issues generating safe primes of around 64 bits. This is a huge difference and goes to show how promising RAMP is performance-wise, although the difference could also be partly due to the code, although mostly identical to each other.
There may be some security concerns surrounding RAMP and the use of unsafe functions when compared to the num library.
The low-level routines (in
ll) are predominantly unsafe functions that work with raw pointers, and some of the routines are implemented using inline assembly to gain access to processor-specific functionality.
I came across a safe prime sieving method from 2003 that may allow a major increase in performance in safe prime generation. I will try to implement this in soon.
Feel free to use num-primes for safe, secure generation/verification of prime numbers but do not expect it to be performant enough for safe prime numbers until it is updated to do so.
RAMP-primes should be considered as an alternative for safe prime generation and I will try to implement more functionality into it, as well as performance boosts.