Для алгоритмов сжатия действительно ли возможно генерировать идентичный вывод для двух различных файлов?
$.get(
"somepage.php",
{paramOne : 1, paramX : 'abc'},
function(data) {
alert('page content: ' + data);
}
);
10 ответов
Сжатие без потерь (используемое в ZIP-файлах) всегда будет давать разные результаты для разных файлов - в противном случае вы не сможете надежно восстановить исходные данные. Однако выходные данные могут иметь любой размер, а для некоторых входных данных он будет больше, чем исходный. Как таковой, он обычно не очень полезен в качестве хэша, который обычно требует вывода фиксированного размера.
Сжатие с потерями (например, MP3, JPEG и т. Д.) Может давать одинаковый вывод для разных входов - поэтому вы не может восстановить исходные данные, а вместо этого получить что-то похожее на них. Из-за этого принцип "голубятни" не является проблемой, и поэтому вы можете гарантировать, что он уменьшит размер вывода, часто даже указывая желаемый размер вывода. Однако,
Конечно, сжатие с потерями может дать тот же результат, что уже отмечалось.
Но я думаю, что очень важный момент, о котором не упоминалось, заключается в том, что криптографические хэши должно быть очень трудно реверсировать (или воспроизводить один и тот же хеш через два разных входа). По этой причине алгоритмы сжатия без потерь и, следовательно, обратимые алгоритмы сжатия, такие как zip-архивы, не подходят в качестве криптографического хэша.
Это должно быть очевидно: если сжатые файлы идентичны, то как распаковщик может узнать, делать из них A или B ??
Это не дает полезного хеша, хотя, поскольку длина будет переменной.
Пусть 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 является биекцией.
Это невозможно. Если бы сжатые файлы были идентичны, как они могли бы дать разные результаты при распаковке?
Функции сжатия должны быть инъективными, то есть каждый вход отображается на уникальный выход. Если бы это было не так, как бы алгоритм узнал, следует ли распаковывать обратно в A или B?
Обратите внимание, что это верно только для сжатия (данных) без потерь. Например, можно сжать 2 изображения и получить тот же результат, но только если изображения были очень близки с самого начала.
Ну, ваш вопрос носит общий характер, но поскольку вы указываете алгоритмы сжатия на основе файлов (например, ваш тег pkzip), то нет. Невозможно, чтобы два разных алгоритма сжатия без потерь могли выдавать один и тот же вывод с разных входов.
Однако для алгоритмов сжатия с потерями, таких как JPEG, конечно, это, конечно, возможно, но тогда файлы будут почти идентичными для начала. с.
Например, возьмите файл .PNG, сохраните его как .JPEG, измените один пиксель, чтобы сделать его на 1 градус светлее или темнее в одном из каналов, пересохраните его как .JPEG, и у вас есть шанс, что у вас есть два идентичных файла, хотя входные данные были разными, хотя и немного.
Итак, алгоритмы без потерь, нет, этого не может быть. Для алгоритмов с потерями - да.
Криптографические хэш-функции предъявляют очень специфическое требование: очень затруднять их обратное изменение. Сжатие по определению легко инвертировать, поэтому это очень плохой выбор для криптографического хэша.
РЕДАКТИРОВАТЬ:
Обратите внимание, что когда я говорю «по определению» выше, я имею в виду обычное определение. Строго говоря, алгоритмами сжатия можно также считать MD5, SHA-1 и т. Д.
Это возможно только для алгоритмов сжатия с потерями (в отличие от сжатия данных без потерь ). Теоретически они могут дать одинаковый результат для похожих (но все же разных) входных данных.
Для того чтобы алгоритм был приличным криптографическим хешем, небольшое локализованное изменение на входе должно вызвать большое дисперсное изменение на выходе. Кроме того, хеш-функция - это преобразование входных данных произвольного размера в выходные данные фиксированного размера.