Click here to Skip to main content
15,867,704 members
Articles / Programming Languages / C#
Tip/Trick

Nondeterministic Random Number Generation

Rate me:
Please Sign up or sign in to vote.
4.90/5 (16 votes)
18 Nov 2014CPOL3 min read 57.6K   458   22   27
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:

C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

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>();
            List<Thread> threadList = new List<Thread>();

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

            //initialize our bit value
            v = 1;

            //create a few threads
            for (int i = 0; i < pcount; i++)
            {
                var ts = new ThreadStart(mashup);
                var thd = new Thread(ts);
                thd.Start();
                threadList.Add(thd);
            }

            //wait on them to start up
            while (threadList.Any(a => a.ThreadState != ThreadState.Running));

            string bts = "";

            while (count > 0)
            {
                System.Threading.Thread.Sleep(5);
                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 = "";

                    //add the byte value
                    resbytes.Add((byte)val);
                    count--;
                }
            }

            //thread cleanup
            threadList.ForEach(thd =>
                {
                    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.

C#
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:

http://en.wikipedia.org/wiki/CryptGenRandom[^]

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.

Some References

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionSleep itself is non-deterministic? Pin
sbarnes9-Dec-15 17:05
sbarnes9-Dec-15 17:05 
Great article. I wonder if the statement
System.Threading.Thread.Sleep(5);
itself imparts some determinism or non-determinism. If there are a few threads we wait for but can affect the Sleep value a bit by their current activity, would that be adding to or detracting from the non-determinism.

AnswerRe: Sleep itself is non-deterministic? Pin
Cryptonite10-Dec-15 7:51
Cryptonite10-Dec-15 7:51 
GeneralAwesome! my vote of 5 Pin
JustCodeForFun26-Nov-14 11:53
JustCodeForFun26-Nov-14 11:53 
GeneralRe: Awesome! my vote of 5 Pin
Cryptonite27-Nov-14 8:53
Cryptonite27-Nov-14 8:53 
SuggestionToo slow for no gain Pin
ArchAngel12319-Nov-14 10:03
ArchAngel12319-Nov-14 10:03 
GeneralRe: Too slow for no gain Pin
Cryptonite19-Nov-14 10:09
Cryptonite19-Nov-14 10:09 
QuestionIs GUID generation nondeterministic? Pin
fredatcodeproject19-Nov-14 5:20
professionalfredatcodeproject19-Nov-14 5:20 
AnswerRe: Is GUID generation nondeterministic? Pin
ArchAngel12319-Nov-14 10:00
ArchAngel12319-Nov-14 10:00 
AnswerRe: Is GUID generation nondeterministic? Pin
Cryptonite19-Nov-14 10:02
Cryptonite19-Nov-14 10:02 
GeneralRe: Is GUID generation nondeterministic? Pin
ArchAngel12319-Nov-14 10:11
ArchAngel12319-Nov-14 10:11 
GeneralRe: Is GUID generation nondeterministic? Pin
fredatcodeproject20-Nov-14 0:55
professionalfredatcodeproject20-Nov-14 0:55 
GeneralRe: Is GUID generation nondeterministic? Pin
fredatcodeproject20-Nov-14 0:54
professionalfredatcodeproject20-Nov-14 0:54 
AnswerRe: Is GUID generation nondeterministic? Pin
Cryptonite19-Nov-14 13:29
Cryptonite19-Nov-14 13:29 
GeneralRe: Is GUID generation nondeterministic? Pin
fredatcodeproject20-Nov-14 0:52
professionalfredatcodeproject20-Nov-14 0:52 
GeneralNot so fast Pin
nategoose19-Aug-14 9:14
nategoose19-Aug-14 9:14 
GeneralRe: Not so fast Pin
Cryptonite19-Aug-14 13:03
Cryptonite19-Aug-14 13:03 
QuestionJust wander... Pin
Fiwel19-Aug-14 9:10
Fiwel19-Aug-14 9:10 
SuggestionWhat's important is the distribution of the random number generated Pin
Member 999737119-Aug-14 7:46
Member 999737119-Aug-14 7:46 
GeneralRe: What's important is the distribution of the random number generated Pin
Cryptonite19-Aug-14 8:20
Cryptonite19-Aug-14 8:20 
QuestionSnippet indent Pin
Nelek19-Aug-14 5:03
protectorNelek19-Aug-14 5:03 
AnswerRe: Snippet indent Pin
Cryptonite19-Aug-14 7:06
Cryptonite19-Aug-14 7:06 
GeneralRe: Snippet indent Pin
Nelek19-Aug-14 22:34
protectorNelek19-Aug-14 22:34 
QuestionWhat about a Javascript implementation using web workers? Pin
JohnEEvansIII18-Aug-14 11:19
JohnEEvansIII18-Aug-14 11:19 
AnswerRe: What about a Javascript implementation using web workers? Pin
Cryptonite18-Aug-14 11:56
Cryptonite18-Aug-14 11:56 
AnswerRe: What about a Javascript implementation using web workers? Pin
Cryptonite18-Aug-14 17:20
Cryptonite18-Aug-14 17:20 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.