Why KeyPairGenerator.genKeyPair() so slow

Question

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();

Answer 1

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 - does not always contain a native optimized methods for all functionality. Note that Oracle JDK / OpenJDK has made several changes when this answer was posted and does allow intrinsics for several BigInteger methods, starting at JDK 8, including Montgomery multiplication. 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 implementation.

RSA key generation depends mainly on finding two large primes that are about half the key size in size. 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; the process is not deterministic. A very large number is picked (in this case about 4096 / 2 = 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:

1. obtain a native implementation of a Java Provider that is known to be fast, e.g. using native code or specialized hardware such as a HSM;
2. switch to another algorithm for which key pair generation is fast, such as Elliptic Curve Cryptography;
3. 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. Normally you only use static key pairs that do not need to be generated very often (edit: except for key establishment that provides forward security, but for that you'd normally use (Elliptic Curve) Diffie-Hellman, not RSA).