Возможно ли для алгоритмов сжатия генерировать идентичные выходные данные для двух разных файлов?

Question

Я хотел бы знать, всегда ли алгоритмы сжатия генерируют уникальные выходные данные для двух разных наборов файлов.

Скажем, у меня есть два файла A и B, и я говорю, что применяю алгоритм сжатия (например, PKZIP - это может быть любой алгоритм сжатия) для каждого из этих файлов, чтобы получить A.zip и B.zip соответственно. Возможно ли, чтобы A.zip был точно идентичным B.zip на двоичном уровне для некоторой комбинации A и B. Если это невозможно, можем ли мы с уверенностью предположить, что сжатие эквивалентно криптографическому хешированию, когда речь идет о гарантировании уникальности ? С другой стороны, если это возможно, не могли бы вы предоставить мне образец файла A и B вместе с алгоритмом сжатия, чтобы использовать его для проверки этой двойственности?

Answer 1

Сжатие без потерь (как используется в ZIP-файлах) всегда будет приводить к разным выводам для разных файлов - в противном случае вы не сможете надежно восстановить исходные данные. Однако выходные данные могут иметь любой размер - и для некоторых входных данных они будут больше, чем исходные. Таким образом, это обычно не очень полезно в качестве хэша, который обычно требует вывода фиксированного размера.

Сжатие с потерями (например, MP3, JPEG и т. Д.) Может давать один и тот же вывод для разных входов - поэтому вы не можете восстановить исходные данные, а вместо этого получить что-то похожее на это. Из-за этого принцип pigeonhole не является проблемой, и поэтому вы можете гарантировать, что он уменьшит выходной размер, часто даже указывая желаемый выходной размер. Однако, поскольку одинаковые, но немного отличающиеся входы часто дают одинаковый результат, это также бесполезно для хеширования, поскольку хеширование требует небольших изменений во входных данных для больших изменений в выходных данных.

Answer 2

Это невозможно. Если сжатые файлы были идентичны, как они могли генерировать разные результаты, когда вы распаковывали их?

Answer 3

Конечно, сжатие с потерями может дать такой же результат, как уже отмечалось.

Но я думаю, что очень важный момент, который не был упомянут, заключается в том, что криптографические хэши должны быть очень трудно перевернуть (или воспроизвести один и тот же хеш через два разных входа). По этой причине алгоритмы сжатия без потерь и, следовательно, обратимые, такие как zips, были бы непригодны в качестве криптографического хэша.

Answer 4

Пусть f - алгоритм сжатия. Если при сжатии A и B получается один и тот же файл, то f (A) = f (B) = C для некоторых C . Теперь пусть f ' будет алгоритмом распаковки. тогда f '(f (A)) = f' (C) = f '(f (B)) . Следовательно, f ' распаковывает A.zip и B.zip в один и тот же файл.

Итак, либо f является бесполезным алгоритмом сжатия (потому что это не биекция), либо A и B фактически являются одним и тем же файлом. (Когда я говорю бесполезный, я имею в виду бесполезный для сжатия без потерь!)

Что касается вашего другого вопроса, обратите внимание, что алгоритм сжатия без потерь по определению не как алгоритм хеширования, поскольку хеш-функция h отображает домен A на (обычно) меньшем домене B . Следовательно, h не может быть биекцией, а мы только что заявили, что наша функция сжатия без потерь f является биекцией.

Answer 5

Криптографические хеш-функции предъявляют очень специфические требования: сделать их обратное очень сложным. Сжатие, по определению, легко инвертировать, поэтому он очень плох для крипто-хеша.

EDIT:

Обратите внимание, что когда я говорю «по определению» выше, я имею в виду под обычным определением. Строго говоря, алгоритмы сжатия также можно рассматривать как MD5, SHA-1 и т. Д.

Answer 6

Что ж, ваш вопрос носит общий характер, но, поскольку вы указываете алгоритмы сжатия на основе файлов (например, ваш тег pkzip), то нет. Нет никакого способа, чтобы два разных алгоритма сжатия без потерь могли выдавать один и тот же результат на разных входах.

Однако, для алгоритмов сжатия с потерями, таких как JPEG, тогда, конечно, это возможно, но тогда файлы будут почти идентичны для начала.

Например, возьмите файл .PNG, сохраните его как .JPEG, измените один пиксель, чтобы сделать его на 1 градус ярче или темнее в одном из каналов, сохраните его как .JPEG, и у вас есть шанс, что вы получили два идентичных файла, хотя входные данные были разными, хотя и немного.

Так что алгоритмы без потерь, нет, этого не может быть. Для алгоритмов с потерями - да.

Answer 7

Функции сжатия должны быть инъективными, то есть каждый вход сопоставляется с уникальным выходом. Если бы это было не так, как бы алгоритм узнал, распаковывать ли обратно в A или B?

Обратите внимание, что это верно только для сжатия без потерь (данных). Например, можно сжать 2 изображения и получить тот же результат, но только если изображения были очень близки к началу.

Answer 8

Это должно быть очевидно: если сжатые файлы идентичны, то как декомпрессор узнает, сделать ли из него A или B ??

Это не делает пригодным для использования хешем, так как длина будет переменной.

Answer 9

Чтобы алгоритм представлял собой достойный криптографический хеш, небольшое локализованное изменение на входе должно вызывать большое дисперсное изменение на выходе. Кроме того, хеш-функция представляет собой отображение из входных данных произвольного размера в выходные данные фиксированного размера.

Answer 10

Это возможно только для алгоритмов сжатия с потерями алгоритмов (в отличие от сжатия данных без потерь ). Теоретически они могут дать один и тот же результат для похожих (но все же разных) входных данных.