Diffie-Hellman Random Number Generation
(Regarding the Chilkat Diffie-Hellman Component/Library)
If it is possible, we´d like to know what algorithm is used to generate random numbers because one of our clients is very strict with security and they demand us this information.
The most difficult problem in implementing a good random number generator is in generating a good seed value for a starting point. Chilkat uses Microsoft’s CryptGenRandom function (detailed below) to generate a seed. When Chilkat is eventually ported to Linux/Unix, we’ll need to search for an equally good solution on that platform. Chilkat uses the R250 pseudo-random number generator algorithm (PRNG) as described here:
First described in 1981, R250 is a relatively old random number generator,
but it’s still one of the best. It was invented/discovered by
Kirkpatrick and Stoll, in the article
A Very Fast Shift-Register Sequence Random Number Generator,
J. Computational Physics, vol 40, pp. 517-526..
If you’re interested in how it works, you can read more here or here (PDF).
R250 is what’s known as a generalized feedback shift register, or GFSR.
GFSRs are determined by two parameters, a length and an offset.
R250 is actually GFSR(250,103), indicating a length of 250 and an
offset of 103. R250 has a period of almost 2^250.
This is a description of Microsoft’s CryptGenRandom function as described at http://msdn.microsoft.com/en-us/library/aa379942(VS.85).aspx
The data produced by this function is cryptographically random. It is far more random than the data generated by the typical random number generator such as the one shipped with your C compiler.
This function is often used to generate random initialization vectors and salt values.
Software random number generators work in fundamentally the same way. They start with a random number, known as the seed, and then use an algorithm to generate a pseudo-random sequence of bits based on it. The most difficult part of this process is to get a seed that is truly random. This is usually based on user input latency, or the jitter from one or more hardware components.
With Microsoft CSPs, CryptGenRandom uses the same random number generator used by other security components. This allows numerous processes to contribute to a system-wide seed. CryptoAPI stores an intermediate random seed with every user. To form the seed for the random number generator, a calling application supplies bits it might have—for instance, mouse or keyboard timing input—that are then combined with both the stored seed and various system data and user data such as the process ID and thread ID, the system clock, the system time, the system counter, memory status, free disk clusters, the hashed user environment block. This result is used to seed the pseudorandom number generator (PRNG). In Windows Vista with Service Pack 1 (SP1) and later, an implementation of the AES counter-mode based PRNG specified in NIST Special Publication 800-90 is used. In Windows Vista, Windows Storage Server 2003, and Windows XP, the PRNG specified in Federal Information Processing Standard (FIPS) 186-2 is used. If an application has access to a good random source, it can fill the pbBuffer buffer with some random data before calling CryptGenRandom. The CSP then uses this data to further randomize its internal seed. It is acceptable to omit the step of initializing the pbBuffer buffer before calling CryptGenRandom.