4 ms·
A modern "pseudo random number" is simply a sequence of numbers that visits the state-space in an order that's difficult to detect with modern statistical tests
by dragontamer 5y ago
A modern "pseudo random number" is simply a sequence of numbers that visits the state-space in an order that's difficult to detect with modern statistical tests. (Chi-squared, among others). See PractRand or TestU01 as two packages for testing these sequences. That is to say: instead of the sequence "0, 1, 2, 3, 4, 5... 4294967296... 0", your RNG will do some other sequence.
Yes, "0, 3, 6, 9... 4294967295, 2, 5, 8... 4294967294, 1, 4, 7... 4294967293, 0, 3..." is a RNG of sorts, but an example of a really, really bad one that would instantly fail most statistical tests. :-) But conceptually, the Mersenne Twister, LCGRNG, and LSFR all accomplish this. Its a "reordering" of the sequence. That's it.
A "cryptographic random number" just adds a few additional tests to the pool of statistical tests. In particular: differential cryptography gets into the nitty gritty about which bits can predict the results of other bits. You have to assume that the "opponent" is willing to use extraordinary amounts of computing power to detect patterns.
If bit#25 has a 51% correlation with bit#30, you fail cryptographic random numbers. You need to be within 2^128 (at least) worth of security or more. That means a near 50% correlation (maybe 50.00000000001% is fine) between bits and future bits.
For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. If the "opponent" doesn't know the key, the bitwise correlations are cryptographically sound (thanks to the hard work of the engineers behind AES).
A true random number generator is just a cryptographic number generator applied to a truly random seed. White noise generators are a well known electronic-engineer trick: resistor noise is everywhere but is rather small (but you can build a white-noise generator from Johnson Nyquist noise if you really wanted). More likely, you use shot-noise from a transistor junction, at least at the hobbyist level.
Intel / AMD have true random number generators from some kind of electrical noise generator on every CPU, which feeds into cryptographic random number generators.
There are other sources of noise: radiation is a well known one but I'm not sure if they're practical.
There's a "speed limit" to white noise generators. You only can extract so much entropy from them in a given time (ex: Remember: CPUs operate at 4GHz, or 0.25 nanoseconds per clock tick). Cryptographic random number generators "stretch" the true seed of randomness, while the white-noise generator continues to grab more entropy.
- SavantIdiot 5y agoPRNGs can actually be better than true RNGs, which is why RNGs generally provide a seed for a DRBG. RNG conditioning has to do things like remove extremely long series of 1's or 0's, and RNGs often cannot generate enough material fast enough for today's demands (e.g, <1Kbps).
- MauranKilom 5y ago> Its a "reordering" of the sequence. That's it. Technically a PRNG state sequence could also have distinct loops, returning a reordering of only a subset of the sequence for any given seed. For example, `return state += 2;` would return two separate sequences for odd or even seeds. We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at smaller intervals. > For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. In light of the above, is it possible to prove this (through some property of AES)? (Also, we can't really prove that AES, or any other current algorithm, is cryptographically secure. Tomorrow, a new cryptanalysis technique could be revealed which breaks it.)
- dragontamer 5y ago> We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at smaller intervals. Yes, that's somewhat important for "smaller" 64-bit or 128-bit states. But at 512-bit states, the "average loop" is 2^256 (birthday paradox), so no one really cares at that point. We can see that Mersenne Twister is overprovisioned: 19937 bits of state and all 2^19937 visited in some order. But in practice, 64-bits worth of cycles (18-quintrillion) is sufficient for single-threaded simulations, and 128-bits is sufficient for multithreaded simulations. > In light of the above, is it possible to prove this (through some property of AES)? Yeah. AES is a block cipher that maps 128 bit blocks into "encrypted" 128-bit blocks. The reverse-AES (I'll call it unAES in this post) provides us the 1-to-1 unmapping as well. Meaning unAES(AES(0, key), key) == 0. unAES(AES(1, key), key) == 1. unAES(AES(2, key), key) == 2. (Etc. etc. for all possible 2^128 blocks) By the pidgeon-hole principle, we have 2^128 blocks associated with AES-encrypted blocks (named AES(0, key), AES(1, key)... AES(2^128-1, key)), and 2^128 blocks associated with our plaintexts (0, 1, 2, 3... 2^128-1). The only way all 2^128 map to each other is through a 1-to-1 bijection. Or in another way: AES(X, key) == AES(Y, key) if-and-only-if X == Y. This is because deAES(AES(X, key), key) == deAES(AES(Y, key), key) if-and-only if X == Y. Done. We know the AES-crypto method therefore only "loops" after 2^128, exploring the entire state-space. 2^128 possible inputs, 2^128 possible outputs, pigeonhole principle. QED, done.