¿Es posible que los algoritmos de compresión generen resultados idénticos para dos archivos diferentes?

Question

Me gustaría saber si los algoritmos de compresión siempre generan resultados únicos para dos conjuntos diferentes de archivos.

Digamos, tengo dos archivos A y B, y digo que estoy aplicando un algoritmo de compresión (por ejemplo, PKZIP, podría ser cualquier algoritmo de compresión) para cada uno de estos archivos para obtener A.zip y B.zip respectivamente . ¿Es posible que A.zip sea exactamente idéntico a B.zip en el nivel binario para alguna combinación de A y B. Si esto no es posible, podemos suponer con seguridad que la compresión es equivalente al hash criptográfico cuando se trata de garantizar uniquenes ? Por otro lado, si es posible, ¿podría proporcionarme un archivo de muestra A y B junto con el algoritmo de compresión para verificar esta duplicidad?

Answer 1

La compresión sin pérdida (como se usa en los archivos ZIP) producirá siempre salidas diferentes para archivos diferentes; de lo contrario, no podría recuperar de manera confiable los datos originales. Sin embargo, los datos de salida pueden ser de cualquier tamaño, y para algunas entradas, será más grande que la entrada original. Como tal, esto no suele ser muy útil como hash, que generalmente requiere una salida de tamaño fijo.

La compresión con pérdida (por ejemplo, MP3, JPEG, etc.) puede producir la misma salida para diferentes entradas; como tal, no puede recuperar los datos originales, sino que obtiene algo similar. Debido a esto, el pigeonhole principle no es un problema, por lo que puede garantizar que reducirá el tamaño de salida, a menudo incluso especificando el tamaño de salida deseado. Sin embargo, debido a que las entradas similares pero ligeramente diferentes a menudo producen el mismo resultado, esto tampoco es útil para el hashing, ya que el hashing requiere pequeños cambios en la entrada para producir grandes cambios en la salida.

Answer 2

No es posible. Si los archivos comprimidos eran idénticos, ¿cómo podrían generar resultados diferentes al descomprimirlos?

Answer 3

Debería ser obvio: si los archivos comprimidos son idénticos, ¿cómo podría el descompresor saber si hacer A o B?

Esto no hace un hash utilizable, ya que la longitud será variable.

Answer 4

Las funciones de compresión deben ser inyectivas, es decir, cada entrada se asigna a una salida única. Si esto no fuera cierto, ¿cómo sabría el algoritmo si volver a descomprimir en A o B?

Tenga en cuenta que esto solo es cierto para la compresión sin pérdida (de datos). Es posible comprimir 2 imágenes, por ejemplo, y obtener el mismo resultado, pero solo si las imágenes estaban muy cerca para comenzar.

Answer 5

Bueno, su pregunta es un poco general, pero ya que indica algoritmos de compresión basados ​​en archivos (su etiqueta pkzip para una cosa), entonces no. No hay forma de que dos algoritmos de compresión sin pérdidas diferentes puedan producir la misma salida desde diferentes entradas.

Sin embargo, para los algoritmos de compresión con pérdida, como JPEG, entonces claro, eso es una posibilidad, pero entonces los archivos serían casi idénticos para comenzar.

Por ejemplo, tome un archivo .PNG, guárdelo como .JPEG, cambie un píxel para hacerlo 1 grado más brillante o más oscuro en uno de los canales, vuelva a guardarlo como .JPEG, y tiene la posibilidad de que obtuve dos archivos idénticos, aunque la entrada fue diferente, aunque ligeramente.

Algoritmos sin pérdida, no, eso no puede suceder. Para algoritmos con pérdidas, sí.

Answer 6

Solo es posible para los algoritmos lossy compression (en oposición al lossless data compression).Teóricamente, podrían dar el mismo resultado para datos de entrada similares (pero aún diferentes).

Answer 7

Deje f sea un algoritmo de compresión. Si al comprimir A y B se obtiene el mismo archivo, entonces f (A) = f (B) = C, para algunos C. Ahora, deje que f ' sea el algoritmo de descompresión. luego f '(f (A)) = f' (C) = f '(f (B)). Por lo tanto, f ' descomprime A.zip y B.zip en el mismo archivo.

Así que, ya sea f es un algoritmo de compresión sin valor (porque no es una biyección), o A y B son de hecho el mismo archivo. (Cuando digo nada, quiero decir sin valor para la compresión sin pérdidas!)

En cuanto a su otra pregunta, tenga en cuenta que un algoritmo de compresión sin pérdida es, por definición, no como algoritmo de hash, ya que una función hash h los mapas de un dominio A en un dominio (generalmente) más pequeño B. Por lo tanto hno puede ser una biyección, mientras que sólo afirmamos que nuestra función de compresión sin pérdidas fes una biyección.

Answer 8

Ciertamente, la compresión con pérdida puede dar el mismo resultado que el ya mencionado.

Pero creo que un punto muy importante que no se ha mencionado es que los valores hash criptográficos deberían ser muy difíciles de revertir (o reproducir el mismo hash a través de dos entradas diferentes). Por esta razón, los algoritmos de compresión sin pérdidas y por lo tanto reversibles como las cremalleras no serían adecuados como un hash criptográfico.

Answer 9

Las funciones hash criptográficas tienen un requisito muy específico: hacer que sea muy difícil revertirlas. La compresión, por definición, es fácil de invertir, por lo que es una opción muy pobre para un algoritmo hash criptográfico.

EDIT:

Tenga en cuenta que cuando digo 'por definición' arriba, quiero decir, por definición convencional. Estrictamente hablando, MD5, SHA-1, etc. también podrían considerarse algoritmos de compresión.

Answer 10

Para que un algoritmo sea un hash criptográfico decente, un pequeño cambio localizado en la entrada debería causar un gran cambio disperso en la salida. Además, una función hash es un mapeo desde una entrada de tamaño arbitrario a una salida de tamaño fijo.