RSA Key Generation Inefficient

[amkomatz]

Hi everyone. First I'd like to say I love the framework, keep up the good work!

I'm trying to use RSA key generation in this framework. However, for any realistic key size (1024, 2048, 4096) the key generation takes a huge amount of time. For 2048 I measured 519 seconds. This is what I'm doing:

let rsa = RSA(keySize: 2048)

This alone will take 519 seconds, from what I measured. I'm scared to even try 4096, I suspect I'll be waiting a long time.

I'm guessing this is because of how primes are being generated. In RSA.swift line 121, there's even a note:

// Note: Need to find a better way to generate prime numbers

It looks like primes are being generated by just picking a random number and checking if it's prime. I'm hoping we can fix this soon. I'd love to help if anyone has any suggestions. I'm no expert in cryptography or number theory, but I'm positive that there's a better way to generate primes.

[nathanfallet]

That's what I reported a while ago on BigInt's repository: attaswift/BigInt#85

[krzyzanowskim]

Until we figure out a better and safe way to generate prime numbers, this is a known issue. I encourage everyone to input how we can improve it.

[Akazm]

Not a cryptography expert at all, but wouldn't Sieve of Eratosthenes (O(n log log n)) be more efficient here?

This, of course, would require a memory-efficient implementation, but as far as I've seen so far, there are quite a few essays and example implementations available.

[nathanfallet]

@Akazm The Miller–Rabin primality test is okay. The problem is about picking the candidates. I think we can look how big libs like openssl are generating those numbers.

[Akazm]

@Akazm The Miller–Rabin primality test is okay. The problem is about picking the candidates. I think we can look how big libs like openssl are generating those numbers.

Then this might be a good point to start investigations?!

https://github.com/openssl/openssl/blob/master/crypto/bn/bn_prime.c