Можно ли распаковать случайный массив байтов? Какой алгоритм будет использоваться?
Я могу вставить любой байтовый массив в алгоритм сжатия, такой как Лемпель-Зив, и получить обратно сжатый байтовый массив без потерь. Я могу распаковать это снова.
Но существует ли алгоритм, который может распаковать любой случайный массив байтов?
Я пробовал использовать gzip, но он выдал ошибку System.IO.InvalidDataException: 'The archive entry was compressed using an unsupported compression method.'
Каков будет результат? Будет ли это что-то случайное, но с повторяющимися закономерностями? Дайте мне знать, что вы думаете!
Да, и кстати, вот код, который я использовал:
public class Compresser
{
public static string CompressString(string text)
{
byte[] byteArray = Encoding.UTF8.GetBytes(text);
using (MemoryStream memoryStream = new MemoryStream())
{
using (GZipStream gzipStream = new GZipStream(memoryStream, CompressionMode.Compress))
{
gzipStream.Write(byteArray, 0, byteArray.Length);
}
return Convert.ToBase64String(memoryStream.ToArray());
}
}
public static string DecompressString(string compressedText)
{
byte[] byteArray = Convert.FromBase64String(compressedText);
using (MemoryStream memoryStream = new MemoryStream(byteArray))
{
using (GZipStream gzipStream = new GZipStream(memoryStream, CompressionMode.Decompress))
{
using (MemoryStream decompressedStream = new MemoryStream())
{
gzipStream.CopyTo(decompressedStream);
byte[] decompressedBytes = decompressedStream.ToArray();
return Encoding.UTF8.GetString(decompressedBytes);
}
}
}
}
}
public class Base64RandomFiller
{
private static Random random = new Random();
public static string GenerateRandomBase64String(int length)
{
byte[] randomBytes = new byte[(length * 3) / 4];
using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
{
rng.GetBytes(randomBytes);
}
return Convert.ToBase64String(randomBytes);
}
}
string randomBase64String = Base64RandomFiller.GenerateRandomBase64String(10);
Console.WriteLine("Random String: " + randomBase64String);
Thread.Sleep(1000);
string decompressedRandomString = Compresser.DecompressString(randomBase64String);
Console.WriteLine("Decompressed Random String: " + decompressedRandomString);
В качестве мысленного упражнения рассмотрим простой компрессор без каких-либо байтов заголовка или контрольной суммы. Выход компрессора всегда представляет собой четное количество байтов в формате l0,v0,l1,v1,... где l0 — длина серии байтов v0 от 0 до 255. Вы можете предоставить декомпрессору любую последовательность случайных байтов, если общая длина четна и она будет выдавать выходные данные.
@PresidentJamesK.Polk С таким же успехом вы можете написать эти два комментария в качестве ответа. Конечно, большинство форматов сжатия используют контрольные суммы, так что...
Более формально, если сжатый формат позволяет любому байту иметь любое случайное значение в каждом месте, его можно распаковать. Распаковка может выглядеть несколько случайной, но, вероятно, она не будет такой случайной, поскольку распаковка, вероятно, покажет такие шаблоны, как повторяющиеся значения.
@MaartenBodewes Ярким примером этого является рассмотрение LLM как декомпрессора. Вы можете передать ему случайную последовательность битов, и он выдаст понятный результат.
Ответы 1
Для gzip нет. Если вы загружаете в него случайные данные, даже если вы случайно пропустите заголовок, вы в конечном итоге почти наверняка столкнетесь с недействительными сжатыми данными.
Конечно, можно случайным образом сгенерировать действительный поток gzip, но вероятность исчезающе мала. Самый короткий такой поток составляет 20 байт, из которых фактически 42 бита могут быть любым значением, а 118 бит остаются с одним значением. Если вы сгенерируете 20 случайных байтов, существует вероятность 2-118 ~ 3x10-36, что это будет действительный поток gzip. (Если вы каким-то образом генерируете терабайт случайных данных в секунду, для получения действительного потока gzip потребуется в среднем десять квадриллионов лет.)
Это справедливо для большинства широко используемых декомпрессоров, каждый из которых ограничивает набор возможных допустимых битовых потоков. Например. xz, zstd, lz4 и т. д. Даже если вы начнете с допустимого заголовка, а затем будете передавать им случайные байты, в конечном итоге они с почти наверняка обнаружат недействительные данные. Даже если вы каким-то образом сгенерируете действительные сжатые данные, вам придется пройти 32- или 64-битную проверку целостности.
Можно написать биективный компрессор-декомпрессор, в котором допустимы все возможные потоки битов. В принципе, использование всех возможных сжатых битовых потоков максимизирует эффективность сжатия. Однако эта конкретная максимизация несущественна по сравнению с другими действиями, которые вы делаете для улучшения сжатия, поэтому вы не найдете широко используемых биективных компрессоров-декомпрессоров. Хотя они были написаны. Дополнительную информацию можно найти на уже не существующей веб-странице , сохраненной в Wayback Machine. (Рассмотрите возможность пожертвования им.)
Существует аргумент в пользу биективного компрессора-декомпрессора для использования с шифрованием. Тогда не будет атаки с использованием открытого текста только на сжатые данные, поскольку все потоки битов действительны. Однако в реальном мире эта проблема решается путем простого добавления к сжатым данным короткой строки случайных данных.
Brotli - это самый близкий из всех, которые я видел в обычном использовании, способный распаковывать случайные данные. Он имеет гораздо более высокую вероятность того, что случайные данные действительны, чем другие, упомянутые здесь, при условии отсутствия проверки заголовка или целостности. См. этот ответ, чтобы узнать, почему вероятность случайной генерации правильных сжатых данных Бротли составляет около 5%.
Забавно, что большинство алгоритмов сжатия все еще имеют контрольные суммы. В большинстве случаев лучше просто проверить, действителен ли весь архив, и зачастую такая проверка вообще не требуется. Кажется, что для чего-то, что предлагает сжатие, в большинстве сценариев действительно можно обойтись без накладных расходов на контрольную сумму.
@MaartenBodewes Да, но только если вы предполагаете, что реализации сжатия и распаковки не содержат ошибок. В противном случае проверка целостности будет полезна. Их поместили сюда авторы этих реализаций, осознав свою собственную ошибочность и преимущество немедленного получения отчетов при обнаружении ошибки. Добавленные биты для проверки целостности несущественны.
Интересно, я еще не слышал такого аргумента! Что касается сжатия/декомпрессии, я думаю, это имеет некоторый смысл, хотя я надеюсь, что это также можно сделать излишним, протестировав достаточное количество (граничных) случаев.
В мире проводится гораздо больше тестов на крайние случаи, чем я когда-либо мог.
@MarkAdler Это означает, что если мне нужен такой алгоритм, мне лучше прочитать реализацию и адаптировать ее для своих нужд. Спасибо за удивительно подробный ответ.
Я не могу себе представить, зачем вам нужен биективный компрессор.
Конечно, вы можете распаковать случайные значения. Декомпрессор — это всего лишь алгоритм, и этот алгоритм не может узнать, имеют ли данные, над которыми он работает, смысл (результат сжатия) или нет. Однако вы должны, по крайней мере, получить правильные метаданные алгоритма, такие как байты заголовка. Вполне возможно, что существуют и другие ограничения, которые необходимо соблюдать. Вы можете обнаружить это, изучив характеристики конкретного алгоритма.