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

3 Answers 3

8
$\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$
-1
$\begingroup$

I came across this thread accidentally, I am interested in this matter. Data with high entropy is hard to compress. Claud Shannon says that it is impossible.

So, how can you tell how 'random' your test data is? There is a tool I tried, find it here: https://github.com/lsauer/entropy. It is called "ent", it will analyse per byte (8 bits, right?) how random the data is. Try that on your test data. If your test file exceeds 7.9999 you are looking at random data!

Truly random data is hard to get by. The real McCoy is using cosmic 'noise' to produce random data. However, if you are interested in receiving some test random data, I'll be happy to make it availbelt to you. I believe that the samples we can generate are more random (Ent shows 7.999x results) than the legendary "Million Random digits" challenge file. Surely you have heard of that. If your algorithm can compress that, please let me know! :-)

$\endgroup$
3
  • $\begingroup$ Hi Thomey, and welcome to the site. I too am interested in this matter. It’s what I do. So how do you collect cosmic noise and assess its usefulness in cryptography? Plug $\endgroup$
    – Paul Uszak
    Oct 16, 2023 at 1:33
  • $\begingroup$ Hi Paul, we do not collect cosmic noise, I am sorry if my post gave that impression. As I wrote "however... we can provide data with very high entropy". Which you can verify yourself by using the Ent test, I referred to, Our interest lies not in cryptography, which relates to (cyber) security, right? We are after compression, and compressing random data in particular, Which is the subject of this thread. Hope this answers your question. $\endgroup$
    – Thomey
    Oct 16, 2023 at 18:51
  • $\begingroup$ Hi Paul, I read your "plug" and found the site about TRNG's, which is not what 'random data' is about. The latest on TRNG's is all on blockchain technology as far as I know, not our thing, but I will fwd the link to people who are active in that area. $\endgroup$
    – Thomey
    Oct 16, 2023 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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