Generating a 4096-bit RSA key is much slower than 2048-bit using Jsch

Question

I need to create RSA public and private keys for a client / server application, and I use

Will such a huge difference in generation time be expected? I don’t really understand how RSA keys are generated (hence the use of the library), but I believe that the required time can be exponential? It just seems ... too revealing.

Here (since the library itself and the website from which it comes from do not have documentation).

Update: I did some profiling. Here is a keygen timeline, starting from 512 bits and rising to 4096, with 30 samples per key size.

And here a similar diagram with 4096-bit tests is excluded (the same data set):

They look pretty similar, which means a pretty smooth exponential increase in time. I guess I'm just impatient!

Answer 1

RSA key generation requires finding two large random primes that satisfy certain criteria. The search for such primes mainly depends on the choice of random numbers, and then to check whether they are basic or not by performing certain tests. The number number theorem tells us that as primes get larger, they also become rarer, so you need to generate more random numbers to find one of them. A test to determine if a number is prime and takes longer for large numbers.

All of the above factors increase the time spent on creating large keys, however, aside, it seems that this library is not particularly fast. Using OpenSSL on a fairly modern PC, I can generate a 2048-bit key in ~ 1 second and a 4096-bit key in <10 seconds, so your time in 10 seconds and 3-5 minutes seems excessive. If performance is a problem, I would suggest trying a different library with the understanding that any library will slower to generate large keys than smaller ones!

Answer 2

A bit late for an answer, but since the other answers are purely heuristic, here are some details on why this takes so much longer:

The slowest part of RSA key generation is usually the Fermat test, which must be run for each major candidate x and consists in checking if 2 ^ {x-1} = 1 modulo x [using 2 can be done faster than using other bases]. So how does the time required for Fermat tests depend on the bit length of x?

1) The execution time of multiplication is approximately quadratic in the length of the factor bits, so doubling the length by four times increases the time (which for school multiplication, if you use Karatsuba, this will approximately triple the time, and for more sophisticated methods of multiplying the RSA bit lengths are too short).

2) The execution time of a modular exponentiation is linear along the length of the exponent bit.

3) The probability that a random n-bit number will be prime is 1: log (2 ^ n), where log is the natural logarithm, i.e. it is 1: (n * log (2)).

Thus, doubling the bit length gives you a factor of 4 from 1) and twice in 2 times from 2) and 3) for the generation time of RSA keys, therefore, in general, the operating time for Fermat tests rises 16 times (or 12 use Karatsuba) . Since there are other parts of the key generation whose uptime is not growing so fast, there is a reasonable factor of about 10, as indicated by Iridium.

Answer 3

Generating a key with a length of 4096 bits takes significantly longer than a key with 2048 bits, see reference numbers here .