What Makes a Good PRNG/TRNG Algorithm?

[adammartin13]

So I was making a random number generator in C++ and I decided to do something like this:
 

#include <iostream>
#include <chrono> // for timer operations
#include <cmath> // for pow()

using namespace std;


class Timer
{
private:
    using clock_t = chrono::high_resolution_clock;
    using second_t = chrono::duration<double, ratio<1> >;

    chrono::time_point<clock_t> m_beg;

public:
    Timer() : m_beg(clock_t::now())
    {
    }

    double elapsed() const
    {
        return chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
    }
};


int main()
{
    Timer t;

    int time_seed = t.elapsed() * pow(10, 7); // Time in hundredths of nanoseconds
    time_seed = time_seed % 10; // Number is based off nanosecond value

    cout << time_seed << endl;

    return 0;
}

Big thanks to Alex at https://www.learncpp.com/cpp-tutorial/8-16-timing-your-code/ for the timer. Effectively this program can output a double value representative of the timestamp at which it was called. The timer starts when the program begins and the value outputted is how long it took to get there. Running this on a laptop with Visual Studio 2019 I can go far as e-7 digits back (the equivalent of 100's of nanoseconds or 1/10,000,000 of a second). The "randomness" is derived from two factors: the speed of the computer and the human element at which the user performs an action (in this case, running the program). Now this performs much better when there is a more extensive action or calculation done prior, such as performing a Fibonacci sequence or something of the like, but my point being that you could feasibly create a TRNG algorithm using a mix of a timer and some human interaction with the program.

So I tried a few things; I compared the TRNG algorithm above with the rand() PRNG function found in the <cstdlib> library and built a calculator to determine bias. There are three tests between the two, all of which seek to create a thousand "random" numbers: one test will generate a thousand numbers between 0-9, the second test will take those one thousand numbers and convert them to a binary value 0 or 1, and the third test will convert a thousand numbers into binary and then XOR those values. Each of these tests will measure, and output, a bias value that's determined by the sum of each individual integers absolute value difference between it's outputted count vs expected count (if the number 9 is outputted 97 times when it's supposed to be outputted 100 times then the bias is 3). Here is what I made:
 

#include <iostream>
#include <chrono> // for timer operations
#include <cstdlib> // rand() function
#include <cstdarg> // bias calculators
#include <cmath> // pow() function
using namespace std;



class Timer
{
private:
    using clock_t = chrono::high_resolution_clock;
    using second_t = chrono::duration<double, ratio<1> >;

    chrono::time_point<clock_t> m_beg;

public:
    Timer() : m_beg(clock_t::now())
    {
    }

    double elapsed() const
    {
        return chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
    }
};

int bias_calc(int num_value, ...)
{
    int bias_sum(0);

    va_list num_values;
    va_start(num_values, num_value);

    for (int it(0); it < num_value; it++)
    {
        bias_sum += abs(100 - va_arg(num_values, int));
    }

    va_end(num_values);

    return bias_sum;
}

int binary_bias_calc(int num_value, ...)
{
    int bias_sum(0);

    va_list num_values;
    va_start(num_values, num_value);

    for (int it(0); it < num_value; it++)
    {
        bias_sum += abs(500 - va_arg(num_values, int));
    }

    va_end(num_values);

    return bias_sum;
}

int main()
{
    Timer t;

    int num1(0), num2(0), num3(0), num4(0), num5(0), num6(0), num7(0), num8(0), num9(0), num0(0);

    for (int it(0); it < 1001; it++) // 1000 iterations
    {
        int num_cache = rand() % 10; // random number 0-9

        if (num_cache == 0)
            ++num0;
        else if (num_cache == 1)
            ++num1;
        else if (num_cache == 2)
            ++num2;
        else if (num_cache == 3)
            ++num3;
        else if (num_cache == 4)
            ++num4;
        else if (num_cache == 5)
            ++num5;
        else if (num_cache == 6)
            ++num6;
        else if (num_cache == 7)
            ++num7;
        else if (num_cache == 8)
            ++num8;
        else if (num_cache == 9)
            ++num9;
    }

    int num1_time(0), num2_time(0), num3_time(0), num4_time(0), num5_time(0), num6_time(0), num7_time(0), num8_time(0), num9_time(0), num0_time(0);

    for (int it(0); it < 1001; it++)
    {
        int time_seed = t.elapsed() * pow(10, 7); // Time in hundredths of nanoseconds
        time_seed = time_seed % 10;
        
        int num_cache = time_seed; // Numbers are based directly off nanosecond value

        if (num_cache == 0)
            ++num0_time;
        else if (num_cache == 1)
            ++num1_time;
        else if (num_cache == 2)
            ++num2_time;
        else if (num_cache == 3)
            ++num3_time;
        else if (num_cache == 4)
            ++num4_time;
        else if (num_cache == 5)
            ++num5_time;
        else if (num_cache == 6)
            ++num6_time;
        else if (num_cache == 7)
            ++num7_time;
        else if (num_cache == 8)
            ++num8_time;
        else if (num_cache == 9)
            ++num9_time;
    }

    int bin_num0(0), bin_num1(0);

    for (int it(0); it < 1001; it++) // 1000 iterations
    {
        int num_cache = rand() % 10; // random number 0-9

        if (num_cache % 2 == 0)
            ++bin_num0;
        else if (num_cache % 2 == 1)
            ++bin_num1;
    }

    int bin_num0_time(0), bin_num1_time(0);

    for (int it(0); it < 1001; it++) // 1000 iterations
    {
        int time_seed = t.elapsed() * pow(10, 7); // Time in hundredths of nanoseconds
        time_seed = time_seed % 10;

        int num_cache = time_seed; // Numbers are based directly off nanosecond value

        if (num_cache % 2 == 0)
            ++bin_num0_time;
        else if (num_cache % 2 == 1)
            ++bin_num1_time;
    }

    int xor_bin_num0(0), xor_bin_num1(0);

    for (int it(0); it < 1001; it++)
    {
        int num_cache = rand() % 10; // random number 0-9
        num_cache = num_cache % 2; // Converts to its last binary digit
        int num_cache_2 = rand() % 10;
        num_cache_2 = num_cache_2 % 2;
        int bin_check = num_cache + num_cache_2; // Four outcomes: 00 01 10 11

        if (bin_check == 0)
            ++xor_bin_num0; // 00
        else if (bin_check == 2)
            ++xor_bin_num0; // 11
        else if (bin_check == 1)
            ++xor_bin_num1; // 01 10
    }

    int xor_bin_num0_time(0), xor_bin_num1_time(0);

    for (int it(0); it < 1001; it++)
    {
        int time_seed = t.elapsed() * pow(10, 7);
        time_seed = time_seed % 2;
        int num_cache = time_seed;
        
        int time_seed_2 = t.elapsed() * pow(10, 7);
        time_seed_2 = time_seed_2 % 2;
        int num_cache_2 = time_seed_2;

        int xor_bin_check = num_cache + num_cache_2;

        if (xor_bin_check == 0)
            xor_bin_num0_time++; // 00
        else if (xor_bin_check == 2)
            xor_bin_num0_time++; // 11
        else if (xor_bin_check == 1)
            xor_bin_num1_time++; // 01 10
    }

    cout << "|C++ PRNG| |Nanosecond| |C++ Binary| |Nano Binary| |C++ XOR Binary| |Nano XOR Binary|" << endl;
    cout << "num0 " << num0 << " " << num0_time << " " << bin_num0 << " " << bin_num0_time << " " << xor_bin_num0 << " " << xor_bin_num0_time << endl;
    cout << "num1 " << num1 << " " << num1_time << " " << bin_num1 << " " << bin_num1_time << " " << xor_bin_num1 << " " << xor_bin_num1_time << endl;
    cout << "num2 " << num2 << " " << num2_time << endl;
    cout << "num3 " << num3 << " " << num3_time << endl;
    cout << "num4 " << num4 << " " << num4_time << endl;
    cout << "num5 " << num5 << " " << num5_time << endl;
    cout << "num6 " << num6 << " " << num6_time << endl;
    cout << "num7 " << num7 << " " << num7_time << endl;
    cout << "num8 " << num8 << " " << num8_time << endl;
    cout << "num9 " << num9 << " " << num9_time << endl;

    cout << "C++ Bias: " << bias_calc(10, num0, num1, num2, num3, num4, num5, num6, num7, num8, num9) << endl;
    cout << "Nanosecond Bias: " << bias_calc(10, num0_time, num1_time, num2_time, num3_time, num4_time, num5_time, num6_time, num7_time, num8_time, num9_time) << endl;
    cout << "Binary C++ Bias: " << binary_bias_calc(2, bin_num0, bin_num1) << endl;
    cout << "Binary Nanosecond Bias: " << binary_bias_calc(2, bin_num0_time, bin_num1_time) << endl;
    cout << "XOR Binary C++ Bias: " << binary_bias_calc(2, xor_bin_num0, xor_bin_num1) << endl;
    cout << "XOR Binary Nanosecond Bias: " << binary_bias_calc(2, xor_bin_num0_time, xor_bin_num1_time) << endl;

    return 0;
}

And so feel free to run this program on your own compiler but I feel showing this program above is necessary for the argument I'm presenting. The PRNG algorithm provided by C++ will output the same values every single time, so long as the seed value stays the same or there are no changes to the code impacting it's calculations. The TRNG algorithm provided by the timer however, will never output the same numbers. The Nanosecond Bias won't always be lower than the C++ Bias, but many times it will be. When this is the case, I can not say. I could add a loop, make it so that if I perform a test and it's bias is higher than the C++ bias (which in this case is basically a constant value) then to simply rerun until that is no longer the case, but that's not really the point of having this kind of tool in a program.

So here's my question: when is it a good time to use a PRNG algorithm vs a TRNG, and vise versa. Is there a way I could improve my program above, and is the combination of a high tick clock and the human element a good means of generating random values?

[Eigenvektor]

1 hour ago, adammartin13 said:

So here's my question: when is it a good time to use a PRNG algorithm vs a TRNG, and vise versa. Is there a way I could improve my program above, and is the combination of a high tick clock and the human element a good means of generating random values?

If you just need values that are sufficiently random (e.g. for a game) then a PRNG should work, provided it is random enough. When you're talking about security related algorithms then I would always prefer a TRNG. A PRGN is predictable, which weakens e.g. random keys you generate with it.

 

Not sure an algorithm based on the time and some human element is sufficiently random to count as a true random number generator. The time is definitely predictable and you might be able to influence the human enough to make output sufficiently predictable. But I don't have enough of a math background to argue about it in depth. As far as I'm aware most TRNGs use some natural phenomenon to provide truly unpredictable numbers.

 

Here are some things to read:

- https://www.random.org/analysis/

- https://www.drdobbs.com/testing-random-number-generators/184403185

[slashqpbyte]

1 hour ago, adammartin13 said:

So I was making a random number generator in C++ and I decided to do something like this:
<snip>

Bad idea...

Quote

one test will generate a thousand numbers between 0-9,

<snip>

Your sample size is wayyyyyyy to small.

Quote

The PRNG algorithm provided by C++ will output the same values every single time, so long as the seed value stays the same or there are no changes to the code impacting it's calculations.

<snip>

....yes

Quote

The TRNG algorithm provided by the timer however, will never output the same numbers.

<snip>

Not a TRNG....

Quote

So here's my question: when is it a good time to use a PRNG algorithm vs a TRNG, and vise versa.

<snip>

Great question!

 

I too chase the random number dragon, shes a hard one to catch. If you care at all about the quality of random numbers, never use a PRNG, they are however good for testing things (or for stretching your TRNG numbers). You essentially have the ability to generate the same super large set of numbers every time the program is run. Maybe use it to test a compression algorithm, idk sky's the limit.

 

TRNG are typically valued in the security sector, IE cryptography, lottery numbers, security tokens, password hashing, nuclear launch codes.

 

Quote

Is there a way I could improve my program above, and is the combination of a high tick clock and the human element a good means of generating random values?

Yes, and no, the bit-rate is too slow.

 

I'm gonna dump a bunch of links, resources are your friend, enjoy the reading material.

https://www.fourmilab.ch/random/
https://sites.google.com/site/astudyofentropy/background-information/whitening
https://www.random.org/randomness/
- hotbits links -
https://www.fourmilab.ch/hotbits/
https://www.fourmilab.ch/hotbits/how3.html
https://www.fourmilab.ch/hotbits/statistical_testing/stattest.html
- hotbits end -
https://en.wikipedia.org/wiki/Linear-feedback_shift_register
https://en.wikipedia.org/wiki/Mersenne_Twister
http://www.cplusplus.com/reference/random/mt19937/
https://cryptography.fandom.com/wiki/Linear_feedback_shift_register
https://blog.cloudflare.com/ensuring-randomness-with-linuxs-random-number-generator/
https://hackaday.com/2017/11/02/what-is-entropy-and-how-do-i-get-more-of-it/
https://www.crowdsupply.com/13-37/infinite-noise-trng
http://holdenc.altervista.org/avalanche/
https://www.maximintegrated.com/en/design/technical-documents/app-notes/4/4527.html

 

[JacobFW]

 

Ahhh, one of my favorite topics.

First off, I need to dispel one notion that really needs to curl up in a corner and die.

There is no such thing as a "True Random Number Generator"  There are both theoretical and practical reasons for this.

 

There are hardware random number generators, but quite frankly even this is a bit of a misnomer.  Any Hardware RNG worth it's salt will have some way of harvesting entropy from a physical source (usually a sensor of some kind), which it then proceeds to run through various hashes or ciphers, before outputting it the final result as data. 

Generally there will be some safety margin to help maximize security, so for example, for every byte that it outputs to you, it will have to gather 8 bytes from it's entropy source.

 

The reason they do all that instead of just outputting the data from the entropy source is because while it's difficult (but doable) to build device that outputs high quality random bytes, it's damn near impossible to make one that reliably does it for the device's entire workable life span.  Remember, they're physical hardware, and physical hardware can break, and it is very, very difficult to tell if a hardware random number generator is broken or not, and usually don't find out until it's too late.

 

This is why usually when you see descriptions of Secure RNG Systems, they'll usually involve an entropy pool, which basically just mashes together a lot of data from one or more entropy sources, that way even if there are certain biases in the entropy data, as long as there are some random influence or chaotic perturbation to the data, with enough data the final output should be infeasible to predict or reproduce, because from an engineering perspective, the actual goal of a Secure RNG is to be:

• Unpredictable
• Irreproducible

 

Apologies for the long winded approach (see above; favorite topic).  To actually answer your question:  it depends, what do you plan to use it for?

 

For instance you mentioned that the random number generator in C/C++ will output the same number every time.  This is in fact, completely intentional.  The standard PRNG wasn't designed to give you a high quality random stream of numbers;  it was designed to give you a bunch of various bytes that way you didn't have to come up with a bunch of test data and store it some where, and it was designed to repeat to help you debug your code.  Imagine if you ran your code once, it crashed, you go back in and think you've figured out the bug, recompile and run it again, and this time it works.  If it uses the same sequence as the time it crashed, you can be pretty sure you got the bug, but if it uses a completely different sequence of code, you can't be sure.

 

Just to note as well, C typically uses a Linear Congruential Generator, due to it's speed and low memory.

You can actually another low memory and even faster PRNG using a variation of the famous Middle Square Method.

 

Quite honestly, most PRNG's out there are designed to be reproducible.  It's really only in a security context that you truly don't want the numbers to start repeating.  In pretty much every other situation, you at least want to have the choice, so while you might use data from an entropy source to seed your PRNG, you'll want to save that seed, just in case you need to run it again.

 

So again, it really just depends

[adammartin13]

I appreciate all the comments and the resources you have provided; I'll be sure to look through all of them. Thank you.

[straight_stewie]

Just for fun, here's a pseudo-random number generator in C#. It is only 41 lines long, including comments. It uses the Middle-Square Weyl Sequence algorithm, and this implementation passes BigCrush.

 

This algorithm is extremely limited, however. For example, you cannot use it to produce random numbers in a given range in deterministic time.

The base algorithm always produces the same sequence given the same seed. However, this implementation always produces the same result given the same seed or seed + 1 if the seed is even, or the same seed or seed - 1 if the seed is odd. It is necessary for the seed to be an odd number otherwise the output will only contain even numbers.

 

    public class WeylPRNG
    {
        private ulong x = 0;
        private ulong w = 0;
        private ulong _seed;

        public WeylPRNG(ulong seed)
        {
            // The seed cannot be zero
            if (seed == 0)
                throw new ArgumentException("The seed cannot be zero");

            // The seed must be odd
            if (seed % 2 == 0)
                seed += 1;

            _seed = seed;
        }

        public uint GetNext()
        {
            x *= x;
            w += _seed;
            x += w;

            // I need a function to extract the middle 32 bits from x.
            return ExtractMiddle(x);
        }

        private uint ExtractMiddle(ulong bigNum)
        {
            byte[] longBytes = BitConverter.GetBytes(bigNum);

            // a ulong is 8 bytes, I always want the middle 4 bytes.
            // therefore I need to start at index 2 and get 4 bytes
            byte[] shortBytes = new byte[4];
            for (int i = 2; i < 6; i++)
                shortBytes[i - 2] = longBytes[i];

            return BitConverter.ToUInt32(shortBytes);
        }
    }