About Pseudo Random Number Generators

Random Numbers

Pseudo Random Number Generators, or PRNGs, are extremely important, as randomness is needed by computers for many purposes. As computers are "deterministic" machines, meaning they follow a specific procedure for everything, they are terrible at making randomness. Because of this, there has been an enormous amount of studying on how to simulate randomness on computers. The algorithms that are developed to simulate randomness are called PRNGs.

Websites that use TLS/SSL (to get the lock symbol in the address bar) use randomness to establish a secure connection to someone visiting their website. If they didn't use randomness, and used a non-random encryption key with someone who visited their website, then any malicious actor could visit the website, and get the same encryption and decryption key as you got. This would allow a hacker to decrypt your communications with the website. Imagine if this could occur with your banking website, and it becomes clear why this is important.

As another example, what if you're playing a video game, and there was a random chance that you'll miss a shot at an enemy. If there wasn't randomness, it would be easy to determine whether or not your shot would hit or miss.

PRNG Basics

PRNGs are essentially mathematical functions that take an initial input, called a "seed", and have a seemingly random output. The randomness of the output orĀ  is determined by the length of the seed.

The seed used by these functions must remain protected and confidential, as if two people use the same seed with the same PRNG, they both will get the same result.

A (Very) Simplified Example

In this example, we'll use the "Middle Square Method" to demonstrate how this works. I chose this PRNG because it's extremely simple to understand.

In the Middle Square Method, we take an input seed, square it, then use the middle digits of a length that matches the input seed's length.

For example if we choose to use 92 as an input seed, this is the process we'd use to get the output:

    1. 92^2 = 8464
    2. Because 92 is two digits long, we take the middle two digits of 8464 , which is 46
    3. 46 is our pseudo-random number

To generate a stream (series) of random numbers, we take that output, and use it as a seed again. Beginning with 92, this would create a stream of 46, 11, 12, 14, 19, ...

Notice that this is a PRNG, because the stream of numbers seem random, but they're truly not, as it's just following a formula.

Since any two people using the seed of 92 will generate the same "random" stream, 92 should be treated as a password, and kept secret.

Awesome, What About Reality Though?

In reality, this would be a terrible algorithm to use as this algorithm would begin repeating quickly. A way that many computer PRNGs increase security over time is by getting additional numbers from somewhere, and modifying the last output of the algorithm based on the additional number.

For example, a real computer system will have a seed from the last time the PRNG ran. When you type on your keyboard, it may do something along these lines:

72 was the last output of the PRNG. The user took 52 milliseconds to press another key. I'll add 52 to 72, which is 124, and use that number as the seed the next time I need a random number.

Because more disc accesses are done, more characters are typed, and the mouse is used more the longer the computer is on, computer's PRNGs increase in "randomness" (or "entropy"), over time.

Leave a Reply