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

Question

I need to create public and private RSA keys for a client/server application, and I'm using the JSch library to do so. I've been generating 4096-bit keys up until now, as I'd like to have the best security possible. However, this takes 3~5 minutes, whereas generating a 2048-bit key takes something to the tune of 10 seconds. Have an sscce:

import com.jcraft.jsch.JSch;
import com.jcraft.jsch.JSchException;
import com.jcraft.jsch.KeyPair;

public class KeyGenerator {

    public static void main(String[] args) {
        JSch jsch = new JSch();

        System.out.println("Starting...");

        try {
            KeyPair keyPair = KeyPair.genKeyPair(jsch, KeyPair.RSA, 4096);
        }
        catch (JSchException e) {
            e.printStackTrace();
        }

        System.out.println("Done.");
    }
}

Would this huge difference in generation time be expected? I'm not super clear on how RSA keys are generated (hence using a library) but I suppose the time required might be exponential? It just seems...too exponential.

Here's the JSch API (since the library itself and the website it comes from have next to no documentation).

Update: I did some profiling. Here's a chart of the keygen times, starting at 512 bits and going up to 4096, with 30 samples per key size.

And here's a similar chart with the 4096-bit trials excluded (same dataset):

These look pretty similar, which denotes a fairly smooth exponential increase in time. I guess I'm just impatient!

Answer 1

Generating an RSA key requires finding two large, random prime numbers that satisfy certain criteria. Finding such primes is essentially a matter of picking random numbers and then checking if they are prime or not by performing certain tests. The Prime Number Theorem tells us that as prime numbers get bigger, they also get rarer so you have to generate more random numbers in order to find one that's prime. The checking to determine whether the number is prime also takes longer for bigger numbers.

All of the above factors contribute to the increased time it takes to generate larger keys, however this aside, it sounds like this library just isn't particularly fast. Using OpenSSL on a reasonably modern PC I can generate a 2048 bit key in ~1 second and a 4096 bit key in <10 seconds, so your times of 10 secs and 3-5 mins seems excessive. If performance is an issue, I'd suggest trying a different library, with the understanding than any library is going to be slower to generate big keys than smaller ones!

Answer 2

A bit late for an answer, but as the other answers are purely heuristic, here some background about why it takes so much longer:

The slowest part of an RSA key generation is usually the Fermat test, which has to be run for each prime candidate x and consists of checking if 2^{x-1} = 1 modulo x (using 2 can be made faster than using other bases). So how does the time needed for the Fermat tests depend on the bit-length of x?

1. The running time for multiplication is about quadratic in the bit-lengths of the factors, so doubling the length quadruples the time (that's for school multiplication; if you use Karatsuba, then its about tripling the time; for more sophistic multiplication methods the bit-lengths of RSA are too short).

2. The running time for a modular exponentiation is linear in the bit-length of the exponent.

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

So doubling the bit-length gives you a factor of 4 from (1) and twice a factor of 2 from (2) and (3) for the running time of the RSA key generation, so in total the running time for the Fermat tests go up by a factor of 16 (or 12 using Karatsuba).

As there are other parts of the key generation whose running times don't go up so quickly, so a factor of around 10, as indicated in the answer of by Iridium, is reasonable.