Is it possible to compress random sequence with high entropy

I have an algorithm that generates pseudo random sequence with length of 100k and high entropy. I would like to check the quality of randomness. So, I used a popular software to compress the generated file and it could manage to compress the original file into a file with just one-third of original file. I have come across to some random test suites out there. 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 of the generated file can be compressed?

Any comment is appreciated.

• 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? – Paul Uszak Oct 1 '17 at 1:00
• @PaulUszak, Yes, it is in ASCII code. – David Oct 1 '17 at 6:58
• Then I'm confused. How did you determine that your generator is high entropy? – Paul Uszak Oct 1 '17 at 12:06
• @Paul Uszak: using the NIST-800-90B compression test XD – Owl Aug 12 '19 at 16:05

2 Answers

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.

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.