beanz Magazine

PRNG

Vladimer Shioshvili on Flickr

Another mysterious four-letter acronym that helps secure information online.

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/

Also In The February 2017 Issue

This cryptography method is based on the fact some tasks are relatively easy to do, but extremely difficult to undo.

There's a way to find out if your online passwords have been stolen, and how to prevent it.

Racket is a fun and easy programming language to learn because it's all about creating colors and shapes as you learn.

Networks are a mostly hidden but critical part of the internet.

Surveillance cameras, satellites, RFID tags, and social media activities all create unique digital footprints.

Developers deal with common problems in their work. Here’s are a few problems and how to overcome them.

Programmers use libraries but instead of books they create and share code, often for free, to help solve common problems.

These cards are a fun way to learn Scratch, look up how to do things, and make applications.

Another mysterious four-letter acronym that helps secure information online.

Dorothy Vaughn, Mary Jackson, and Katherine Johnson not only helped make history, they are part of a long line of women in computing

It's almost time to think about summer tech camps if your kids are interested. Here are a few questions to ask.

Your web browser knows (and tells) a lot more about you than you might realize.

When you pick a programming language to learn first, it helps to figure out what software you want to create.

This odd acronym offers security protection beyond your password. Here are a few examples of how 2FA works.

Links from the bottom of all the February 2017 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for February 2017.