How to compress a random string?

Question

I'm working on a encryptor application that works based on RSA Asymmetric Algorithm. It generates a key-pair and the user have to keep it. As key-pairs are long random strings, I want to create a function that let me compress generated long random strings (key-pairs) based on a pattern.

(For example the function get a string that contains 100 characters and return a string that contains 30 characters)

So when the user enter the compressed string I can regenerate the key-pairs based on the pattern I compressed with.

But a person told me that it is impossible to compress random things because they are Random!

What is your idea ? Is there any way to do this ?

Thanks

Answer 1

It's impossible to compress (nearly any) random data. Learning a bit about information theory, entropy, how compression works, and the pigeonhole principle will make this abundantly clear.

One exception to this rule is if by "random string", you mean, "random data represented in a compressible form, like hexadecimal". In this sort of scenario, you could compress the string or (the better option) simply encode the bytes as base 64 instead to make it shorter. E.g.

// base 16, 50 random bytes (length 100)
be01a140ac0e6f560b1f0e4a9e5ab00ef73397a1fe25c7ea0026b47c213c863f88256a0c2b545463116276583401598a0c36
// base 64, same 50 random bytes (length 68)
vgGhQKwOb1YLHw5KnlqwDvczl6H+JcfqACa0fCE8hj+IJWoMK1RUYxFidlg0AVmKDDY=

You might instead give the user a shorter hash or fingerprint of the value (e.g. the last x bytes). Then by storing the full key and hash somewhere, you could give them the key when they give you the hash. You'd have to have this hash be long enough that security is not compromised. Depending on your application, this might defeat the purpose because the hash would have to be as long as the key, or it might not be a problem.

Answer 2

public static string ZipStr(String str)
{
    using (MemoryStream output = new MemoryStream())
    {
        using (DeflateStream gzip = 
          new DeflateStream(output, CompressionMode.Compress))
        {
            using (StreamWriter writer = 
              new StreamWriter(gzip, System.Text.Encoding.UTF8))
            {
                writer.Write(str);           
            }
        }

        return Convert.ToBase64String(output.ToArray());
    }
}

public static string UnZipStr(string base64)
{
    byte[] input = Convert.FromBase64String(base64);

    using (MemoryStream inputStream = new MemoryStream(input))
    {
        using (DeflateStream gzip = 
          new DeflateStream(inputStream, CompressionMode.Decompress))
        {
            using (StreamReader reader = 
              new StreamReader(gzip, System.Text.Encoding.UTF8))
            {
                return reader.ReadToEnd();
            }
        }
    }
}

Take into account that this doesn't have to be shorter at all... depends on the contents of the string.

Answer 3

Try to use gzip compression and see if it helps you