S I T E   M A P

It is possible that there is a problem with the primality testing under some compilers (notably Visual C++ 5.0). This page gives a background on what is expected, and what I've observed.

RSA key generation

When building an N-bit key, one has to compute two primes of length N/2 bits. For a large number X, the number of primes less than X is about X/ln(X); so the probability of a number near X being prime is roughly 1/ln(X). Thus the probability of an N/2 bit number being prime is thus approximately 1/ln(2**N/2), or roughly 2.8/N. We know that even numbers can't be prime and don't generate them, so that the probability of an odd number being prime is roughly 6/N.

To find two primes of this length will take on average, therefore, about N/6 trials - about 200 for a 1024 bit key, about 3-400 for a 2048 bit key.

This applies to the simple scan (try every odd number starting from a random base) and jump scan which starts with a given odd number and steps by some even number greater than two.

Sophie Germain primes are primes P such that 2P+1 is also a prime; CTClib's Sophie Germain prime generation method for RSA keypairs produces a key pair whose primes are of the form 2P+1 for some smaller prime. This yields some theoretical benefits for the resistance of the keys to analysis. However, such primes are comparatively sparse.

We observe that P has to be of the form 6K-1 for some K, as is 2P+1; meaning that we sample from a population from which we have discarded multiples of 3 as well as multiples of 2, and so have a probability of about 8/N of being prime.

So we want to generate an N/2 bit prime X, so that Y = (X-1)/2 is also prime - Y is thus an N/2 - 1 bit value. Assuming no correlation, between them, then the probability that X and Y are both prime is approximately 70/N^2, so generating a keypair will take on average approximately N^2/70 attempts - about 15,000 tries for a 1024 bit keypair, about 50,000 tries for a 2048 bit keypair. This can take a substantial time.

Timings

Using a debug build under Borland C++Builder3, simple-scan RSA keypairs have taken the expected number of trials, and, on a 200MHz MMX processor a few tens of seconds for 1024 and 2048 bit keys. For a 1024-bit Sophie-germain pair, tests have run between 10,000 and 25,000 attempts and a few tens of minutes : a 2048-bit Sophie Germain keypair is probably an overnight job (four times as many trials, and large numbers of twice the size, and hence slower to manipulate).

Some speed-up of primality testing is possible, to reduce the number of large integer operations performed in the initial checking against small prime factors though it would take some significant reworking of the code.

---

S I T E   M A P