Re:Generating Cryptographically Secure Random Numbers with C...
by Taek on Tuesday December 22, 2020 @07:26AM
(#25505578)
A run like 0000000 is only compressible if it appears more often than it would in a fully random output. And in a fully random output, we would expect the run '0000000' to appear about once every 16 bytes.
When you compress 0000000 to something smaller, you have to replace '0000000' in the plaintext with a smaller symbol in the squash text. Which means if that smaller symbol appears in the plaintext, you have to replace it with a larger symbol in the squash text. And if your smaller symbol appears more frequently than '0000000', you are going to end up with a "squash" text that is larger than the plaintext.
Re:Generating Cryptographically Secure Random Numbers with C...
by john_alan on Tuesday December 22, 2020 @04:02AM
(#25504378)
So you agree with me, uniformity is important?
Re:Generating Cryptographically Secure Random Numbers with C...
by rurban on Wednesday December 23, 2020 @10:43AM
(#25518719)
Yes, but I don't like the abbrevated term that much. I prefer the Kolmogorov complexity, precisely a discrete uniform distribution. It's not only important, it's the only factor.
Primitive runs like 0000000 are compressible patterns. Other patterns similarly, like 01010101, or 00110001110011. That's why you check generators visually by printing out bitmaps, and ideally by running it through a couple of compressors. Afaik this is not yet done by the 4 most common PRNG testsuites yet, but I'm working on it.