3 ms·

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

25 points by reinhardt1053 13y ago

deleted 13y ago
[deleted]
mmcnickle 13y ago
Previous discussion: https://news.ycombinator.com/item?id=7189334 https://news.ycombinator.com/item?id=7189334
jffry 13y ago
Discussed yesterday: https://news.ycombinator.com/item?id=7189334 https://news.ycombinator.com/item?id=7189334
logicallee 13y ago
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.
mox1 13y ago
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.
- sliverstorm 13y ago
  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?
  - davidst 13y ago
    That's a good way to think about it. A quality PRNG tells an undetectable lie.
  - mox1 13y ago
    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.
stiff 13y ago
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).

25 points by reinhardt1053 13y ago

deleted 13y ago

[deleted]

mmcnickle 13y ago

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

jffry 13y ago

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

logicallee 13y ago

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.

mox1 13y ago

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.

sliverstorm 13y ago
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?
- davidst 13y ago
  That's a good way to think about it. A quality PRNG tells an undetectable lie.
- mox1 13y ago
  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.

stiff 13y ago

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).