Why KeyPairGenerator.genKeyPair() so slow

I have some Java code and when I run function KeyPairGenerator.genKayPair() it's work 40 seconds or more. How change this situation? If I run

openssl req -x509 -nodes -days 365 -newkey rsa:4096 -keyout server.key -out cert.pem

it's work 3 seconds. The slow code:

KeyPairGenerator gen = KeyPairGenerator.getInstance("RSA");
SecureRandom random = new SecureRandom();
gen.initialize(4096, random);        
keyPair = gen.generateKeyPair();        
PublicKey pubk = keyPair.getPublic();
PrivateKey prvk = keyPair.getPrivate();

First of all, although Java is certainly fast with regards to business logic, optimized C code (with assembly where it counts) will blow it out of the water when it comes to cryptography. Java will use BigInteger to perform these calculations, and BigInteger - as far as I know - does not contain a native optimized Montgomery multiplier. Scripting languages generally are much worse than Java unless they call native code.

Java also needs time to optimize byte code. That means it runs faster if it is called multiple times. So you need to at least call one key gen before to see what happens if such a method is called multiple times in your application. In this case the runtime may be so high that it is already able to optimize - that depends on the VM.

RSA key generation depends mainly on finding two large primes. Finding large primes is a very CPU intensive process. It also depends on the random number generator to create starting points. So the actual random number generator implementation used makes a lot of difference - especially if the random number generator can block if not enough entropy is available. So play around with the random number generators available until you find one that is fast and secure enough.

Finding a prime of a certain length is a process that doesn't have a designated runtime. A very large number is picked (in this case about 2048 bits in size) and start testing if the subsequent numbers are prime. This is what hammers your CPU. So you need to calculate the average runtime of generating prime - in case you are generating a lot of them - or you will have to live with the uncertainty about the time it takes.

This is all a bit moot though. In general you don't need oodles of RSA keys - you generate one to three per user. So this only becomes a problem when 1) you have a lot of users 2) you have a protocol that requires a lot of key pairs or 3) you need very large RSA keys.

If you want to have a faster way of generating key pairs you can do a few things:

obtain a native implementation of a Java Provider that does this for you;
switch to another algorithm for which key pair generation is fast, such as Elliptic Curve Cryptography;
generate the keys using openssl and just import/use them in your Java application;

Usually though you would need to fix the protocol instead of the key pair generator.