dark mode light mode Search Menu
Search

PRNG

Vladimer Shioshvili on Flickr

Imagine the following scenario: you’re planning a surprise party for your friend Amelia. It’s going to be epic: glow in the dark balloons, dancing monkeys, five-story cake. You want to hand out the invites in person, but Amelia is a little nosy and sometimes reads over peoples’ shoulders. What to do?

PRNG stands for Pseudo-Random Number Generator (all the short, snappy names were taken). It’s a piece of software that spits out random numbers on command. Or if not random numbers, then at least numbers that could pass for random.

Enter encryption. Encryption is a mathematical way of garbling a message so that it can only be read by people who know the “secret key”.

Here’s an example. We’re going to use a Vigenere Cipher, one of many existing encryption methods. If you’ve got a computer handy, navigate to http://planetcalc.com/2468/ and scroll down until you see the following screen:

Try Creating Vigniere Ciphers at http://planetcalc.com/2468/

Enter the text and the key in the text boxes, as shown, then hit the orange Calculate button. Out pops the result:

cmopka’c tcrdc ks yr hrshcy kjvebrqox ev mkb’u hyyue

Looks like a string of random letters, right? Not even a world-class genius could deduce that this message is about a surprise party. Only people who know the key — Cake — can access the details within. (If you want to test that decryption works properly, copy the Transformed Text selection back into the input box. Select Decryption, click Calculate, and watch as the original message is revealed).

In short, the security of our message depends entirely on the secrecy of the key — Cake — and the inability of Amelia to guess this key.

That’s why random numbers are used everywhere in computer security; they’re our keys, nonces, or initialization vectors. Every electronic device, from laptops to phones, generates random numbers to ensure the confidentiality and integrity of its communications.

Except computers can’t do anything random!

Computers follow software (or hardware) instructions and only do exactly what they’re told. Asking a computer to create a random number – all by itself – is like asking a tortoise to fly.

PRNGs are software’s attempt to mimic the wonderful world of randomness.

A PRNG starts with a seed. As the name implies, this seed is used to grow a sequence of seemingly random numbers. PRNGs use mathematical equations that twist and tweak the seed in unexpected ways, until it’s impossible to see how the seed and its generated numbers could be related.

Take a look at the following sequence:

4, 7, 10, 13, 16, 19…

Not too hard to guess that 22 is next, right? We’re just adding 3 to the previous number. In this case, the seed of our PRNG is 1; we added 3, then got 4. If we’d started with a seed of 5, this PRNG would have generated the sequence 8, 11, 14, 17…

Here’s another one (slightly less lame):

13, 19, 31, 45, 83, 159…

Can you guess what’s coming next? You might have noticed that the last digit is a repeating sequence: 3, 9, 1, 5, 3, 9… There may be a way to use that knowledge to you advantage.
The answer is to multiply the previous number by 2 and subtract 7. For example:

(13 * 2) – 7 = 26 – 7 = 19

Therefore, the next number is: (159 * 2) – 7 = 311

Can you figure out what the seed of this sequence is?

Standard, real-life PRNGs produce sequences that are very hard to predict, since most are using a nifty trick called modular arithmetic. Essentially, you choose a very large upper bound (say, a thousand or a million), and any number larger than that is truncated. 1001 mod 1000 = 1; 1002 mod 1000 = 2; and so on. This makes the relationship between the PRNG’s numbers very convoluted. Attackers trying and figure out the seed won’t have much luck; and if they can’t guess the next number, they can’t guess a secret key or decrypt a message.

In our dummy scenario, if Amelia decrypts the secret message, well… she’ll get a regular party instead of a surprise party (and since both have cake, no one’s going to mind.) In real life scenarios, encryption protects important private information like names, addresses, bank accounts, and credit card numbers. Keys needs to be secret, hard to guess, and easy to generate. Thankfully, we have math and computers to take on the challenge.

Learn More

Planet Calc

http://planetcalc.com/search/?tag=1462
http://planetcalc.com/2468/

Pseudorandom Number Generator

https://en.wikipedia.org/wiki/Pseudorandom_number_generator
https://en.wikipedia.org/wiki/List_of_random_number_generators

Random Number Generation

https://en.wikipedia.org/wiki/Random_number_generation

A Short History of Random Numbers, and Why You Need to Care

https://conferences.oreilly.com/oscon/oscon2013/public/schedule/detail/28777
http://www.codon.org.uk/~mjg59/oscon_random_2013.odp

Introduction to Randomness and Random Numbers

https://www.random.org/randomness/