RSA key generation comparatively slow

[beamer159]

I need to frequently generate RSA keys in bulk. I am using the following Rust code to generate a key:

let rsa_key = rsa::RsaPrivateKey::new(&mut rand::thread_rng(), 2048).unwrap();

Running this code in release mode to generate 100 RSA keys takes about 18 seconds on my machine. In comparison, I used the following code in C (OpenSSL) and C# (CNG) to generate the same-size RSA key.

C - OpenSSL

RSA *rsa_key = RSA_new();
BIGNUM *e = BN_new();
BN_set_word(e, RSA_F4);
RSA_generate_key_ex(rsa_key, 2048, e, NULL);

C# - CNG

var rsaKey = new RSACng(2048).Key;

To generate 100 keys, the C code takes about 6.7 seconds and the C# code takes about 5.5 seconds. I was surprised that the Rust key generation took about 3x more time than both C and C#.

[aloucks]

I ran into this a while back as well. The bottleneck appears to be in the prime number generation:

RSA/src/algorithms.rs

Line 99 in 7395997

*prime = rng.gen_prime(todo / (nprimes - i));

EDIT: After benchmarking this some more, it actually looks like the number of primes used to generate the key is the influencing factor. I increased the number of primes from 2 to 3 (based on the table 1 in the PDF linked below) and saw the time it took to generate 100 keys dropped from about 16 seconds to 7 seconds.

RSA/src/key.rs

Line 279 in 7395997

generate_multi_prime_key(rng, 2, bit_size)

https://cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf

[dignifiedquire]

The main reason asfaik is that the underlying operations are nowhere nearly as optimized as the code in OpenSSL and whatever library C# is calling into.

@aloucks that will generate a different RSA key setup though, and most applications today assume using 2 primes and not more asfaik.

[jellevos]

In https://github.com/jellevos/scicrypt/blob/master/scicrypt-numbertheory/src/lib.rs I have implemented an algorithm that is almost exactly the same as OpenSSL's. Depending on the machine and parameters it is slightly faster or slightly slower than OpenSSL. I am happy to give it a try to reimplement it in this crate (the algorithm is not complicated). Of course, if the bottleneck is the underlying arithmetic, then it might not make a large difference.

[tarcieri]

@jellevos would definitely be curious what the performance is if you did port it over

[r10s]

ftr: older issue with similar topic: #29

[darconeous]

Once dignifiedquire/num-bigint#48 lands, prime generation should be a little faster.

[dignifiedquire]

@darconeous next_prime is not actually used for prime generation in this crate, so that won't help unfortunately.

[darconeous]

do'h!

[richarddd]

@jellevos can you open a PR?

[tarcieri]

#394 switches to using crypto-primes which should be a fairly mature implementation of prime number generation and primality testing.

I'm not sure if it improves performance as I haven't benchmarked it, but regardless whatever performance problems remain are in crypto-bigint itself.

[dignifiedquire]

FYI using latest crypto-bigint@0.7.0-rc.1 these are the current performance numbers on my M4

test bench_rsa_1024_gen_key             ... bench:   5,671,345.85 ns/iter (+/- 3,268,350.33)
test bench_rsa_2048_gen_key             ... bench:  63,307,870.90 ns/iter (+/- 62,277,206.68)
test bench_rsa_2048_pkcsv1_decrypt      ... bench:     839,999.95 ns/iter (+/- 30,592.95)
test bench_rsa_2048_pkcsv1_sign_blinded ... bench:   1,237,025.00 ns/iter (+/- 45,101.41)