1
$\begingroup$

I'm searching for an algorithm that can generate a set of 500 to 2000 characters from the alphabet a-z, A-Z, 0-9 (no interpunctuation) where the set has the following properties:

  • highly compressible with gzip, ideally compressing 2000 characters input to 200 characters output, and
  • generated text looks "random enough" to the casual human observer, i.e. no obvious repetitions.
$\endgroup$

1 Answer 1

3
$\begingroup$

One obvious/naive idea would be to generate a dictionary of O(256) "words", each of which is O(10) characters drawn randomly from your alphabet. Then string O(200) of them together to generate your 2000 characters of ciphertext. If a decoder/recipient already had the dictionary, we know we'd only need 200 bytes to represent this message, specifically the [0-255] dictionary index of each word. The compression ideas behind zip (LZ algorithm and Huffman coding) will discover this redundancy/reduced representation and emit a correspondingly smaller ziptext **.

** Of course, zip has to also encode/store the dictionary, so you'll probably have to experiment a bit with those O(?) constants to tune everything to just the right desired sizes.

Hopefully, with a sufficiently large dictionary, the ciphertext will look random enough to a human observer. Mixing up the length of words / using variable length words might help here too.

$\endgroup$
4
  • $\begingroup$ I thought about that, but simple repetition doesn't compress well enough. Using a prototype with your parameters yields a compression ratio of just 2:1. $\endgroup$ Oct 16, 2022 at 15:47
  • $\begingroup$ Tweaking the parameters to a much smaller dictionary size of O(16) yields a compression ratio of 5:1. $\endgroup$ Oct 16, 2022 at 16:03
  • $\begingroup$ It might be effective to use a smaller number of longer words. You might also consider running zip on some arbitrary excerpts of text just to see how close you can get to your goals (iirc, plaintext is supposed to compress well using gzip .. maybe you could just take plaintext and shuffle the order of words to make them random/gibberish?). $\endgroup$ Oct 16, 2022 at 18:28
  • $\begingroup$ Yes, that'd imply decreasing the randomness of words, similar to how the letter distribution in English isn't normal but biased towards E, A, R, I and so on. I'll run a few tests to see if that improves the general approach. $\endgroup$ Oct 16, 2022 at 19:33

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.