12,625,402 members (37,605 online)
Tip/Trick
alternative version

20.4K views
22 bookmarked
Posted

# Nondeterministic Random Number Generation

, 18 Nov 2014 CPOL
 Rate this:
I keep reading articles on the web about how all random number generators on a computer are "pseudo" random, or "deterministic". Here I present an approach for nondeterministic number generation.

## Introduction

The provided C# WPF .NET solution generates truly random numbers in a nondeterministic manner. These are most useful in cryptography and help protect against side-channel attacks. Although this solution was developed targeting an Intel multi-processor, targeting a machine with a single processor may produce different results.

What is a random number sequence?

For example (as the editor was kind enough to point out):

"314159......." is an example of the output from a deterministic routine for producing random numbers (if indeed, it is using an algorithm for producing digits of the value of pi). Most random number generators are of these types; they use a specific mathematical formula and usually require a "seed" value (quite commonly the system timer is used).

What are the problems with using deterministic routines for producing random values? In cryptography, if the algorithm used is already known, then the random values can be reproduced just by knowing what the initial seed of the generator is. Why is this a problem? Well, it's quite common to use random number generators for generating secret "keys".

So how do we create nondeterministic random values? Quite simply, we have to resort to either non-algorithmic approaches (such as white noise sampling) or producing our own nondeterministic algorithm.

From the Wiki article:

"A concurrent algorithm can perform differently on different runs due to a race condition."

Here, I present a class which does just that:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace randTesting
{
/// <summary>
/// Random byte generator
/// </summary>
public class RandomBytes
{
static volatile int v = 0;
/// <summary>
/// Creates the requested number of random bytes
/// </summary>
/// <param name="count"></param>
/// <returns></returns>
public static List<byte> GenerateBytes(int count)
{
List<byte> resbytes = new List<byte>();

//get the number of processors on this os
var pcount = Environment.ProcessorCount == 1 ? 2 : Environment.ProcessorCount;

//initialize our bit value
v = 1;

for (int i = 0; i < pcount; i++)
{
thd.Start();
}

//wait on them to start up

string bts = "";

while (count > 0)
{
int res = 0;
if (v == 1) res = 1;
bts += res;
if (bts.Length == 8)
{
int val = 0;
for (int x = 0; x < 8; x++)
{
val += (int)(Math.Pow((double)2, (double)x) * int.Parse(bts.Substring(x, 1)));
}
bts = "";

count--;
}
}

{
try
{
thd.Abort();
}
catch { }
});

return resbytes;
}

static void mashup()
{
while (true)
{
v *= -1;
}
}
}
} ```

## Background

I've often wondered about the ability of a computer to generate truly random values. One approach that came to mind was to cause the processors to constantly "fight" over the same shared memory until paused and read. This is known as creating a "race condition". If sufficient amount of time is allowed to pass, the value in the shared memory location should be unknown, or random, since only the OS controls how much time is allotted to each processor.

## Using the Code

The RandomBytes.cs file contains method "`GenerateBytes`" which returns the specified number of random bytes requested.

`var bytes = RandomBytes.GenerateBytes(20);`

Here's an example of 100 random bytes generated using this call:

```220,252,230,230,105,62,1,101,143,95,78,243,215,3,95,45,66,33,160,29
114,147,147,39,12,68,249,95,59,225,86,237,95,190,91,79,160,214,169,105
29,218,77,54,12,246,244,101,204,158,95,169,249,104,41,128,251,33,79,20
124,247,207,53,216,129,222,74,161,214,247,94,179,229,103,22,184,213,14,132
43,15,130,147,207,27,77,47,196,111,143,94,197,177,67,65,81,202,126,157
51,176,166,171,137,111,227,171,151,206,150,218,23,37,74,37,20,95,204,226```

## Points of Interest

1. The pause (of 5 milliseconds) while looping and sampling the variable (`v`) might need to be adjusted depending on the speed of the target machine.
2. This processor: Intel Core I7, 2201 Mhz, 4 Cores
3. Used to seed deterministic (or pseudo random number generators)
4. Aperiodic
5. Poor Efficiency

A lot of people seem confused by all of the different random number generators available - and with good reason, too. Most RNGs (and apparently, some GUID generators) work by seeding themselves (a.k.a. conditioning) with a nondeterministic number generator and then are used to produce deterministic values (for a more efficient and perfect distribution). For the nondeterministic part, most use the mashing of a high speed timer and/or X and Y movements of the mouse. Some even use hashing of screen captures.

Also, I get a lot of questions about what Microsoft does. So, as for Microsoft's cryptographic random number generator:

Notice that the algorithm (or DETERMINISTIC) part isn't even published. However, the timer mashing (or NONDETERMINISTIC) part is clearly hinted at.

Thank you everybody for your comments and for helping me build a better article.

## Share

 United States
No Biography provided

## You may also be interested in...

 First Prev Next
 Sleep itself is non-deterministic? sbarnes9-Dec-15 18:05 sbarnes 9-Dec-15 18:05
 Re: Sleep itself is non-deterministic? Cryptonite10-Dec-15 8:51 Cryptonite 10-Dec-15 8:51
 Awesome! my vote of 5 JustCodeForFun26-Nov-14 12:53 JustCodeForFun 26-Nov-14 12:53
 Re: Awesome! my vote of 5 Cryptonite27-Nov-14 9:53 Cryptonite 27-Nov-14 9:53
 Too slow for no gain ArchAngel12319-Nov-14 11:03 ArchAngel123 19-Nov-14 11:03
 Re: Too slow for no gain Cryptonite19-Nov-14 11:09 Cryptonite 19-Nov-14 11:09
 Is GUID generation nondeterministic? fredatcodeproject19-Nov-14 6:20 fredatcodeproject 19-Nov-14 6:20
 Re: Is GUID generation nondeterministic? ArchAngel12319-Nov-14 11:00 ArchAngel123 19-Nov-14 11:00
 Re: Is GUID generation nondeterministic? Cryptonite19-Nov-14 11:02 Cryptonite 19-Nov-14 11:02
 Re: Is GUID generation nondeterministic? ArchAngel12319-Nov-14 11:11 ArchAngel123 19-Nov-14 11:11
 Re: Is GUID generation nondeterministic? fredatcodeproject20-Nov-14 1:55 fredatcodeproject 20-Nov-14 1:55
 Re: Is GUID generation nondeterministic? fredatcodeproject20-Nov-14 1:54 fredatcodeproject 20-Nov-14 1:54
 Re: Is GUID generation nondeterministic? Cryptonite19-Nov-14 14:29 Cryptonite 19-Nov-14 14:29
 Re: Is GUID generation nondeterministic? fredatcodeproject20-Nov-14 1:52 fredatcodeproject 20-Nov-14 1:52
 Not so fast nategoose19-Aug-14 10:14 nategoose 19-Aug-14 10:14
 Re: Not so fast Cryptonite19-Aug-14 14:03 Cryptonite 19-Aug-14 14:03
 Just wander... Fiwel19-Aug-14 10:10 Fiwel 19-Aug-14 10:10
 What's important is the distribution of the random number generated Member 999737119-Aug-14 8:46 Member 9997371 19-Aug-14 8:46
 Re: What's important is the distribution of the random number generated Cryptonite19-Aug-14 9:20 Cryptonite 19-Aug-14 9:20
 Snippet indent Nelek19-Aug-14 6:03 Nelek 19-Aug-14 6:03
 Re: Snippet indent Cryptonite19-Aug-14 8:06 Cryptonite 19-Aug-14 8:06
 Re: Snippet indent Nelek19-Aug-14 23:34 Nelek 19-Aug-14 23:34
 What about a Javascript implementation using web workers? JohnEEvansIII18-Aug-14 12:19 JohnEEvansIII 18-Aug-14 12:19
 Re: What about a Javascript implementation using web workers? Cryptonite18-Aug-14 12:56 Cryptonite 18-Aug-14 12:56
 Re: What about a Javascript implementation using web workers? Cryptonite18-Aug-14 18:20 Cryptonite 18-Aug-14 18:20
 How random are the results? John Brett17-Aug-14 21:31 John Brett 17-Aug-14 21:31
 Re: How random are the results? Cryptonite18-Aug-14 10:48 Cryptonite 18-Aug-14 10:48
 Last Visit: 31-Dec-99 19:00     Last Update: 5-Dec-16 3:22 Refresh 1