# How does RSACryptoServiceProvider generate keys

The documentation for the constructor for RSACryptoServiceProvider states

"If no default key is found, a new key is created. This constructor creates an Exchange key pair suitable to encrypt session keys so that they can be safely stored and exchanged with other users. The generated key corresponds to a key generated using the AT_KEYEXCHANGE value used in the unmanaged Microsoft Cryptographic API (CAPI)."

This leaves some questions;

• How is this key generated, I think RSA keys require a large prime, but I don't think .net keeps a large list of primes available. Nor does the constructor spend the time to find new primes.
• When is a default key available?
• How secure are the keys generated by this constructor?

RSACryptoServiceProvider, like most system classes in .NET, is a thin wrapper around the older Win32 implementation (an API which was meant to be used with C or C++ -- or even Pascal, if we really dig deep). See CryptAcquireContext(). In .NET terminology, this is called "unmanaged code".

Generating a RSA key pair involves producing new random prime numbers. Knowledge of these primes is the private key, so we strongly hope that the Microsoft implementation does not simply uses a fixed list of pre-generated primes ! Conceptually, this generation is simple: produce sequences of random bits of the right size, and repeat until you find one that is prime.

In more details, if you want a 2048-bit RSA key, you will need two 1024-bit primes whose product is a 2048-bit integer. This goes that way:

1. Generate a sequence of 1024 random bits, such that the first two bits and the last one are equal to 1; the 1021 other bits are obtained from a strong random source (in Win32, this is CryptGenRandom() -- `RNGCryptoServiceProvider` is the .NET wrapper).

2. Interpret the 1024 bits as a big integer p. Since we set the first two bits to 1, and there are 1024 bits, then the integer is greater than 3×21022 and less than 4×21022; since the last bit is also 1, the integer is odd.

3. Verify that p-1 is not a multiple of the chosen RSA public exponent. Traditional exponent is 65537. There is a probability 1/65537 that p-1 is a multiple of 65537; if that is again, go back to step 1 to generate another candidate.

4. Test the integer p for primality. There are several methods for that; usually, Miller-Rabin primality test is used. If p is not found to be prime, go back to step 1 to generate another prime. For a 1024-bit p that we took care to make odd, you can expect to test an average of about 500 candidates before finding a prime.

5. Once you have generated a random prime p, do that again to get another one, which we will call q.

6. The modulus will be n = pq. The public exponent is the chosen e (65537 in the example above). The private exponent d and the other RSA private key components are computed algebraically from p, q and e. Thanks to the way p and q were generated (two top bits equal to 1), it is guaranteed that n will have size 2048 bits, not 2047.

The whole API is barely usable. The concept of the "default key" is aberrant; you cannot decently rely on it in any protocol, since you do not control neither its storage nor its life cycle. Also, that default key will have length 1024 bits, which is a bit too short for today's technology. If you want to obtain and use a RSA key, you should ask for its generation explicitly, and certainly not register it as a "default" that any other application may use or possible modify, export, publish or whatever.

It is also badly underspecified. CryptAcquireContext() accepts multiple options that impacts how the key, if any, is generated and stored; the documentation for RSACryptoServiceProvider does not tell which options are used. If you want to know what really happens under the hood, you have to delve into the source code.

The bottom-line is that the RSACryptoServiceProvider constructor will generate new primes, for a 1024-bit RSA modulus (hence 512-bit primes), but it will try to keep around a "default key" so that it will do that only once even if you call it repeatedly. Note that producing a new 1024-bit RSA key takes only a fraction of a second with a modern PC.

• When looking for a single prime number, could it be faster to start at an initial random guess, then increment +1 until a prime is found? Would "randomness" be lost with that +1 search? (This instead of having another random guess every time, which involves more processing to generate more pseudorandom bytes) – Todd May 3 at 14:19