Design of the PRNG used in the RAND library

It should be noted that this PRNG is intended to be used to generate 'random' keys for various ciphers including generation of DH and RSA keys.

It should also be noted that I have just created a system that I am happy with. It may be overkill but that does not worry me. I have not spent that much time on this algorithm so if there are glaring errors, please let me know. Speed has not been a consideration in the design of these routines.

First up I will state the things I believe I need for a good PRNG.

• A good hashing algorithm to mix things up and to convert the PRNG 'state' to random numbers.
• An initial source of random 'state'.
• The state should be very large. If the PRNG is being used to generate 4096 bit RSA keys, 2 2048 bit random strings are required (at a minimum). If your RNG state only has 128 bits, you are obviously limiting the search space to 128 bits, not 2048. I'm probably getting a little carried away on this last point but it does indicate that it may not be a bad idea to keep quite a lot of PRNG state. It should be easier to break a cipher than guess the PRNG seed data.
• Any PRNG seed data should influence all subsequent random numbers generated. This implies that any random seed data entered will have an influence on all subsequent random numbers generated.
• When using data to seed the PRNG state, the data used should not be extractable from the PRNG state. I believe this should be a requirement because one possible source of 'secret' semi random data would be a private key or a password. This data must not be disclosed by either subsequent random numbers or a 'core' dump left by a program crash.
• Given the same initial 'state', 2 systems should deviate in their RNG state (and hence the random numbers generated) over time if at all possible.
• Given the random number output stream, it should not be possible to determine the PRNG state or the next random number.

The algorithm is as follows.

There is a global state made up of a 1023 byte buffer (the 'state'), a working message digest ('md') and a counter ('count').

Whenever seed data is added, it is inserted into the 'state' as follows.

The input is chopped up into units of 16 bytes (or less for the last block). Each of these blocks is run through the MD5 message digest. The data passed to the MD5 digest is the current 'md', the same number of bytes from the 'state' (the location determined by in incremented looping index) as the current 'block' and the new key data 'block'. The result of this is kept in 'md' and also xored into the 'state' at the same locations that were used as input into the MD5. I believe this system addresses points 1 (MD5), 3 (the 'state'), 4 (via the 'md'), 5 (by the use of MD5 and xor).

When bytes are extracted from the PRNG, the following process is used. For each group of 8 bytes (or less), we do the following,

Input into MD5, the top 8 bytes from 'md', the byte that are to be overwritten by the random bytes and bytes from the 'state' (incrementing looping index). From this digest output (which is kept in 'md'), the top (upto) 8 bytes are returned to the caller and the bottom (upto) 8 bytes are xored into the 'state'. Finally, after we have finished 'generation' random bytes for the called, 'count' (which is incremented) and 'md' are fed into MD5 and the results are kept in 'md'. I believe the above addressed points 1 (use of MD5), 6 (by hashing into the 'state' the 'old' data from the caller that is about to be overwritten) and 7 (by not using the 8 bytes given to the caller to update the 'state', but they are used to update 'md').

So of the points raised, only 2 is not addressed, but sources of random data will always be a problem.