1.61: Performance issue with RSA key generation

[bs-rscs]

Due to the changes to random prime number generation introduced in 1.61 (or, more specifically, in commit 5e45db6), RSA key generation is much slower than it was in 1.60, by up to almost factor 10 (after what I've seen so far).

I couldn't exactly figure out why this drop in performance happens, but the switch from using JVM's BigInteger prime number generation to the self-made one in core/src/main/java/org/bouncycastle/util/BigIntegers.java is likely to be the cause. I suspect that the method chosen is not as efficient as the BigInteger one, and having two cascaded while-loops (RSAKeyPairGenerator.chooseRandomPrime() calling BigIntegers.createRandomPrime() ) for finding a prime number also likely introduces a fair amount of overhead. But I don't fully know my way around all that code, so I keep wondering, why was this change made? Is there a cryptography/security-related reason? Could it be reverted or at least optimized for RSA key generation (that uses additional constraints while searching for primes)?

Minimum test setup for this:

	public static void main(String[] args) throws Exception {
		Security.insertProviderAt(new BouncyCastleProvider(), 1);

		SecureRandom random = SecureRandom.getInstance("SHA1PRNG", "SUN");
		random.setSeed(random.generateSeed(64));

		KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC");

		long totalMillis = 0L;
		for (int i = 0; i < 10; i++) {
			Instant start = Instant.now();
			generator.initialize(4096, random);
			generator.generateKeyPair();
			Instant end = Instant.now();
			totalMillis += ChronoUnit.MILLIS.between(start, end);
		}

		System.out.println("Generation time: " + totalMillis + " msec => avg. time " + (totalMillis / 10L) + " msec");
	}

With 1.60, this yields on my machine:

Generation time: 38214 msec => avg. time 3821 msec

With 1.61, this yields on my machine:

Generation time: 290862 msec => avg. time 29086 msec

[bs-rscs]

PS: This is a Windows machine. On Linux, the impact seems to be smaller (but it exists there, too).

[bcgit]

Interesting... yes it looks isProbablePrime() doesn't do any of the internal speedups that the default BigInteger constructor does. I've pushed a new beta which should improve things somewhat. You can find it at https://www.bouncycastle.org/betas 162b11 or later.

Let me know how it goes.

[bs-rscs]

Thanks so far, the changes definitely make a difference. It is still slower, by about factor 1.7 compared to 1.60. Of course, a little more speed would be nice, but this is definitely much more acceptable. Now we will consider upgrading (which we didn't do yet because of this issue).

With 162b11:

Generation time: 57407 msec => avg. time 5740 msec

vs. 1.60:

Generation time: 34186 msec => avg. time 3418 msec

and 1.61 for reference:

Generation time: 192203 msec => avg. time 19220 msec

[bcgit]

Treating this one as closed for now. If one of us has a bright idea for speeding things up further we'll certainly try it.