How are pseudorandom and truly random numbers different and why does it matter? | Hacker News Reader

How are pseudorandom and truly random numbers different and why does it matter?

superuser.com

So I think the most up-voted response does a great job of explaining the "why it matters" part of the question, but he never really touched on the "whats the difference"... IE the fact the pseudo-random basically means generating statistically random data, using a deterministic process.

That's really interesting, in that case I've understood it wrong all this time! So you are saying pseudo-random really is honest-to-god random, following all the accepted rules for random distributions and such, with the critical difference simply being that the output of the pseudo-random function can be predicted if you understand the generating process?

That's a good way to think about it. A quality PRNG tells an undetectable lie.

As I understand it, yes your basically correct.

Imagine a function like this:

  def init_prng(int x):
    state = x

  def prng():
    state = md5(state) 
    return state

So while this is a good, simple PRNG its very recoverable if you know the initial x (or if the space of possible x values is small, ie a 32-bit number). One of the goals of a PRNG function is to extend the usefulness of truly random data, because fully random data is hard to come by.

There is no such thing as "true" randomness, in fact in rigorous mathematical probability theory "randomness" itself belongs to the class of undefined concepts like the concept of a line in Euclidean geometry. In the end probability theory is sort of like elementary algebra/arithmetic/set theory, but repeated with distributions instead of simple numbers or "pure" set members. The only sensible way of talking about the issues with number generators is through the notion of entropy, which is a quantification of uncertainty (which is subjective, while "true" randomness would have to be objective, which leads into a fuzzy philosophical discussion of the "free will" kind).

Previous discussion: https://news.ycombinator.com/item?id=7189334

Discussed yesterday: https://news.ycombinator.com/item?id=7189334

Let's say your friend calls you and asks you how to generate a secure password. You say to your friend, "just slide your finger down the keyboard to get a bunch of letters. then capitalize 1 or 2 of them."

This is how it looks if I do this:

qasWdfghjzUkilo

Those 15 characters look pretty random.

Yet, if you KNEW a thousand people were following those instructions, then you could build a model of the actual entropy that goes into the password: 1) Where did they start and stop sliding their keyboard 2) What is their keyboard layout 3) Which is the FIRST letter they chose to capitalize? 4) Did they choose to capitalize a second letter, and if so which one?

The above is very low entropy. If a thousand people are following your instructions, you can guess one in WAY less time than brute-forcing 15 random letters.

The issue is that although the result LOOKS random, very low entropy is entering it - you can repeat the steps, if you know the algorithm.

Likewise, pseudorandom number generators take SPECIFIC steps (algorithmically.) If you know the "seed", such as the time-stamp, that they're initiated with, you can simply repeat the steps.

This is a huge vulnerability if the result is supposed to contain a high degree of entropy.

I've simplified a bit, of course. Good pseudorandom algorithms have very good, equal-looking distributions.

But make no mistake: at their heart they're just steps that anyone can follow along with, if they know the entropy entering the algorithm they can come up with the same result.

Reply on news.ycombinator.com