Click here to Skip to main content
Click here to Skip to main content

Nondeterministic Random Number Generation

, 18 Nov 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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;
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.

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)

Share

About the Author

Cryptonite

United States United States
No Biography provided

Comments and Discussions

 
GeneralAwesome! my vote of 5 PinmemberJustCodeForFun26-Nov-14 12:53 
GeneralRe: Awesome! my vote of 5 PinmemberCryptonite27-Nov-14 9:53 
SuggestionToo slow for no gain PinmemberArchAngel12319-Nov-14 11:03 
GeneralRe: Too slow for no gain PinmemberCryptonite19-Nov-14 11:09 
QuestionIs GUID generation nondeterministic? Pinmemberfredatcodeproject19-Nov-14 6:20 
AnswerRe: Is GUID generation nondeterministic? PinmemberArchAngel12319-Nov-14 11:00 
AnswerRe: Is GUID generation nondeterministic? PinmemberCryptonite19-Nov-14 11:02 
GeneralRe: Is GUID generation nondeterministic? PinmemberArchAngel12319-Nov-14 11:11 
GeneralRe: Is GUID generation nondeterministic? Pinmemberfredatcodeproject20-Nov-14 1:55 
GeneralRe: Is GUID generation nondeterministic? Pinmemberfredatcodeproject20-Nov-14 1:54 
AnswerRe: Is GUID generation nondeterministic? PinmemberCryptonite19-Nov-14 14:29 
GeneralRe: Is GUID generation nondeterministic? Pinmemberfredatcodeproject20-Nov-14 1:52 
GeneralNot so fast Pinmembernategoose19-Aug-14 10:14 
GeneralRe: Not so fast PinmemberCryptonite19-Aug-14 14:03 
QuestionJust wander... PinmemberFiwel19-Aug-14 10:10 
SuggestionWhat's important is the distribution of the random number generated PinmemberMember 999737119-Aug-14 8:46 
GeneralRe: What's important is the distribution of the random number generated PinmemberCryptonite19-Aug-14 9:20 
QuestionSnippet indent PinmemberNelek19-Aug-14 6:03 
AnswerRe: Snippet indent PinmemberCryptonite19-Aug-14 8:06 
GeneralRe: Snippet indent PinmemberNelek19-Aug-14 23:34 
QuestionWhat about a Javascript implementation using web workers? PinmemberJohnEEvansIII18-Aug-14 12:19 
AnswerRe: What about a Javascript implementation using web workers? PinmemberCryptonite18-Aug-14 12:56 
AnswerRe: What about a Javascript implementation using web workers? PinmemberCryptonite18-Aug-14 18:20 
QuestionHow random are the results? PinmemberJohn Brett17-Aug-14 21:31 
AnswerRe: How random are the results? PinmemberCryptonite18-Aug-14 10:48 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141216.1 | Last Updated 18 Nov 2014
Article Copyright 2014 by Cryptonite
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid