Pseudo-random generation able to regenerate backwards

Question

Using the accepted answer from this question, I made a random number generator which can regenerate previous numbers in order.

Ideone version

byte[] Encrypt(byte[] ClearData, byte[] Key)
{
   MemoryStream ms = new MemoryStream();

    Rijndael alg = Rijndael.Create();
    alg.KeySize = 128;
    alg.BlockSize = 128;
    alg.Mode = CipherMode.ECB;

    alg.Key = Key;

    CryptoStream cs = new CryptoStream(ms, alg.CreateEncryptor(), CryptoStreamMode.Write);

    cs.Write(ClearData, 0, ClearData.Length);

    cs.Close();

    byte[] encryptedData = ms.ToArray();

    return encryptedData;
}

int RandomValue(int Max)
{
    byte[] FirstHalf = BitConverter.GetBytes(Key);
    byte[] SecondHalf = BitConverter.GetBytes(Key);

    byte[] KeyBytes = new Byte[FirstHalf.Length + SecondHalf.Length];
    FirstHalf.CopyTo(KeyBytes, 0);
    SecondHalf.CopyTo(KeyBytes, FirstHalf.Length);

    byte[] RandValue = Encrypt(new byte[0], KeyBytes);

    int Rand = Math.Abs(BitConverter.ToInt32(RandValue, 0));

    return Rand % Max;
}

int NextValue(int Max)
{
    ++Key;
    return RandomValue(Max);

}

int PreviousValue(int Max)
{
    --Key;
    return RandomValue(Max);

}

static void Main()
{
    byte[] buffer = new byte[sizeof(Int64)];
    Rand.NextBytes(buffer);
    Key = BitConverter.ToInt64(buffer, 0);

    for(int i = 0 ; i < 4 ; ++i)
    {
        Console.WriteLine(NextValue(10));
    }

    Console.WriteLine();

    for(int i = 0 ; i < 4 ; ++i)
    {
        Console.WriteLine(PreviousValue(10));
    }
}

Sample output:

Value 0: 8
Value 1: 1
Value 2: 0
Value 3: 8

Value 2: 0
Value 1: 1
Value 0: 8
Value -1: 7

The desired output from the asker of the stackoverflow question could be obtained by incrementing Key after getting a random value in the NextValue function but for my use this output is more appropriate.

It won't generate backwards properly if the Max changes. It doesn't need to be able to do this especially since Max in unlikely to change between calls, but seeing as how the whole purpose of this is to generate forward and backwards accurately, it seems like something should change.

I'm using Encrypt blindly since I don't understand how it works or even what the ClearData is used for.

What can be changed to improve it and make it more understandable?

Answer 1

I'm using Encrypt blindly since I don't understand how it works or even what the ClearData is used for.

This PRNG uses an arbitrary encryption algorithm to generate pseudo-random numbers. The trick is just that the encryption algo will return the same crypto text whenever the same plain text is encrypted with the same key.

Because the routine used is usually employed for encryption, it operates on two parameters: the plain text and the key/password.

In your case, there's no need to encrypt a particular plain text, but since the encryption function needs it as input, some arbitrary, but constant, "plain text" is given to it via the "ClearData" array.

Because the Rijndael algorithm chosen here is a block cipher, it will always output a whole block of crypto text, even if, as in this case, the input plain text has zero length: Encrypt(new byte[0], KeyBytes);.

Your program then takes the first 32 bits of the block of crypto text (BitConverter.ToInt32(RandValue, 0)) as the random value. This value should depend (pseudo-)randomly on the key, so that key+1 will yield a completely different value than key with high probability; this way, there's no simple correlation between subsequent values of the RNG, which makes the output look like real random data.

Another approach I once tried was using a simpler stream cipher (RC4) whose calculations can actually be completely reversed so that one may go back and forth through the sequence of output numbers as desired by either using the (normal) forward or the reverse operations.

Answer 2

Dispose of IDisposable objects with the using statement. For example, objects of type Rijndael, MemoryStream, and CryptoStream. Follow C#'s capitalization conventions, in particular camelCase for parameters (and though not specified in the link, for local variables).

Answer 3

In your code, you're changing the key and re-initializing the block cipher for each random number. It will, generally, be much more efficient to initialize the cipher only once, with a fixed key, and increment / decrement the encrypted data block instead.

This is, in fact, a standard method for creating a seekable pseudorandom bitstream using a block cipher like AES / Rijndael. It's known as counter (CTR) mode, and is commonly used to implement a stream cipher (which needs a keyed pseudorandom bitstream) based on a block cipher.

In fact, it's likely that your crypto library already implements CTR mode, but the API it exposes for it may or may not suit your needs. If not, it's perfectly fine to implement it yourself by using ECB mode (which basically gives you direct access to the raw block cipher) and incrementing the data blocks yourself.