1
$\begingroup$

I have an algorithm that generates a pseudorandom sequence with a length of 100k and high entropy. I would like to check the quality of its randomness. So, I used a popular software program to compress the generated file, which reduced it to one-third of its original size.

I have come across some random test suites, but I have no idea why a random sequence with high capacity can be compressed like this.

My question is whether compressing the generated file is a proper test? Does the algorithm fail because the generated file can be compressed?

Any comment is appreciated.

$\endgroup$
4
  • 5
    $\begingroup$ Before we jump into a full answer, was your file to be compressed ASCII format by any chance? I.e. could you actually read the numbers? $\endgroup$
    – Paul Uszak
    Oct 1 '17 at 1:00
  • $\begingroup$ @PaulUszak, Yes, it is in ASCII code. $\endgroup$
    – David
    Oct 1 '17 at 6:58
  • $\begingroup$ Then I'm confused. How did you determine that your generator is high entropy? $\endgroup$
    – Paul Uszak
    Oct 1 '17 at 12:06
  • $\begingroup$ @Paul Uszak: using the NIST-800-90B compression test XD $\endgroup$
    – Owl
    Aug 12 '19 at 16:05
7
$\begingroup$

Random data can not be compressed. Good pseudo random data can not be compressed(with generic algorithm). As Paul commented if you use an inefficient encoding such as hexadecimal or Decimal ASCII characters you are using a full 8 bit character to represent less information. Hexadecimal is compressible to 50% and decimal to $\log_2(10)/8$ which is approx 41%. If your data is in binary or compresses significantly more than the inherit encoding used. This is a significant flaw in your random number generator. A compression test with a Lempel-Ziv based compression algorithm is a good important but not sufficient test. It essentially tests for repeating sequences of arbitrary length. So it can find all sorts of biases in your algorithm.

However for cryptographic security, the chances your homegrown algorithm is secure are slim even it passes all generic statistical tests with flying color.

$\endgroup$
3
$\begingroup$

My question is whether compressing the generated file is a proper test? Does the algorithm fail because of the generated file can be compressed?

Yes. No.

You've misinterpreted a small but crucial step in your randomness test. It is perfectly acceptable to output encoded data for randomness testing via compression. HEX, ASCII or plain Klingon is fine. It's a good litmus test without resorting to further exotic testing. Your compression calculation was wrong.

When you output a 100K sequence, that must mean you output 100K samples, not digits. If your generator is RC4, you will be outputting bytes that might be represented by up to three characters. If you're using Java's Random() you will be outputting 32 bit values that might be 10 characters long. There might also be spaces, commas, carriage returns and newlines. These latter artefacts will effectively create what's termed a bit fixing entropy source. In extremis, you might print "It's a bit!" and "I got nought" for each Blum Blum Shub (BBS) output. No matter.

  1. Output 100K samples, with any encoding.
  2. This might occupy 1200K storage bytes as ASCII representations of bits from BBS using my special encoding above.
  3. Compress with the best squeezer. fp8 is better than 7z which is better than zip.
  4. Divide the resulting compressed size by 100K to get the entropy rate/ sample.

If your secret algorithm is any good, you'll get an entropy rate approaching 1 bit /sample which is equivalent to 1 bit /bit and expected of BBS.

If the answer is significantly less than 1 bit /bit, it's not random.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.