Key generation is super slow

[Snowiiii]

Hello, I' coming from RustCrypto/RSA#144 and RustCrypto/RSA#454 and wanted to ask why the generation is currently so slow especially in debug mode (even 10ms in release), Currently it looks like most of the overhead comes from cargo:index.crates.io-1949cf8c6b5b557f:crypto-primes-0.7.0-pre.8:src/hazmat/miller_rabin.rs::test_base_two but other things are also causing the slowdown, Here is an screenshot from samply

Would be great if this can be fixed because this is literally the only thing which prevents my Server from startup within 0ms

[fjarri]

why the generation is currently so slow especially in debug mode (even 10ms in release)

Well, primality test is a computationally expensive process. Debug mode is expected to be slow - there are additional checks, less optimization, less inlining. A more productive question to ask is - slow compared to what? crypto-primes has comparison benchmarks with GMP and OpenSSL, and shows comparable performance (especially considering that OpenSSL does most of the work in specialized assembly). In fact, for the sizes of primes that result in generation times about 10ms, OpenSSL is actually slower than crypto-primes.

Currently it looks like most of the overhead comes from cargo:index.crates.io-1949cf8c6b5b557f:crypto-primes-0.7.0-pre.8:src/hazmat/miller_rabin.rs::test_base_two

Yes, that is entirely expected. That's Miller-Rabin test base 2, the main workhorse sieving out the most candidates.

Would be great if this can be fixed because this is literally the only thing which prevents my Server from startup within 0ms

As I said above, this cannot be "fixed" since finding a random prime is essentially hard. It won't be instantaneous even if you switch to OpenSSL (although it may be faster, so depending on your requirements you may consider that). But depending on your current approach, some ways to speed things up are:

• Using fixed-size integers (Uint) instead of BoxedUint,
• Making sure you're not looking for safe primes where regular primes are enough,
• Using the multicore functionality of crypto-primes,
• Caching pre-generated primes (if security requirements allow that)

There may be some room for improvement in the rsa crate, but that's beyond the scope of this repo.

[tarcieri]

Reports here suggest the performance seems OK: RustCrypto/RSA#144 (comment)