J'aimerais savoir si les algorithmes de compression génèrent toujours une sortie unique pour deux ensembles différents de fichiers.
Dites, j'ai deux fichiers A et B, et dis-je l'application d'un algorithme de compression (par exemple comme Pkzip - cela pourrait être n'importe quel algorithme de compression) pour que chacun de ces fichiers pour obtenir respectivement A.ZIP et B.ZIP. Est-il possible que A.Zip soit exactement identique à b.zip au niveau binaire pour une combinaison d'une combinaison de A et B. Si cela n'est pas possible, pouvons-nous supposer de manière sûre la compression pour être équivalente à la hachage cryptographique lorsqu'il s'agit de garantir des uniquenes ? D'autre part si cela est possible, pourriez-vous me fournir un exemple de fichier A et B ainsi que l'algorithme de compression à utiliser pour vérifier cette duplicité?
10 Réponses :
Ce n'est pas possible. Si les fichiers compressés étaient identiques, comment pourraient-ils générer des résultats différents lorsque vous les décompressez?
Clair et simple: +1. Remarque Ceci s'applique uniquement à la compression sans perte (que l'OP suggère en parlant de pkzip, mais ne mentionne pas explicitement).
Quand j'ai écrit la réponse, je n'avais même pas envisagé la possibilité d'une compression pertinente, en raison de la manière dont la question était libellée. Merci pour la clarification.
Il devrait être évident: si les fichiers compressés sont identiques, alors comment le décompresseur peut-il savoir s'il est de faire un ou un de celui-ci ??
Cela ne fait pas de hash utilisable, car la longueur sera variable.
La compression sans perte (telle que utilisée dans les fichiers zip) produira toujours des sorties différentes pour différents fichiers - sinon, vous ne seriez pas en mesure de récupérer de manière fiable les données d'origine. Cependant, les données de sortie peuvent être de toute taille - et pour certaines entrées, il sera plus grand que l'entrée d'origine. En tant que tel, ce n'est généralement pas très utile en tant que hachage, qui nécessite généralement une sortie de taille fixe.
La compression avec perte (par exemple, MP3, JPEG, etc.) peut produire la même sortie pour différentes entrées - en tant que telles, vous ne pouvez pas récupérer les données d'origine, mais obtenir quelque chose de similaire à celui-ci. À cause de cela, le Principe du pigeonhole n'est pas un problème, et vous pouvez donc vous garantir que ce sera Réduisez la taille de la sortie, même en spécifiant même la taille de sortie souhaitée. Cependant, comme des entrées similaires mais légèrement différentes produiront souvent la même sortie, cela n'est pas utile pour le hachage non plus, comme le hasard nécessite de petits changements dans l'entrée pour produire de grandes modifications dans la sortie.
+1 pour le principe du pigeonhole parce que je suis une ventouse pour les mathématiques. Cependant, cela adresse-t-il la question de Hash cryptographique?
Sûr. Lossless ne fonctionne pas car sa taille variable, perte, car de petits changements n'entraînent pas de gros changements de hachage (effet d'avalanche).
@bdonian Quelle est l'exigence sur les hachages à avoir une longueur fixe? En outre, l'idée d'informations «perdant» (c'est-à-dire la perte) n'arrête pas un algorithme d'être un bon hachage. MD5 ou SHA-1 sont des algorithmes de compression avec perte, n'est-ce pas? Je pense que la chose importante à noter ici est que toutes les fonctions de hachage de crypto sont des algorithmes de compression, mais pas l'inverse. (Les fonctions de hachage de crypto doivent être «difficiles» à inverser) et, après avoir dit cela, je note que cela contraignait quelque peu ma réponse ci-dessous: P
Je n'ai jamais dit perdre des informations empêchant quelque chose d'être un bon hachage. En effet, tout bon hash perd toutes les informations (c'est-à-dire que vous ne pouvez récupérer aucune information sur le message d'origine du tout). En outre, généralement des hachages sont plus petits que le message d'entrée, qui ne peut pas être assuré avec un algorithme de compression sans perte.
Les fonctions de compression sont nécessaires pour être injectives, c'est-à-dire que chaque entrée correspond à une sortie unique. Si cela n'était pas vrai, comment l'algorithme peut-il savoir s'il faut se décompresser à A ou B?
Notez que cela n'est vrai que pour la compression sans perte (données). Il est possible de compresser 2 images, par exemple, et d'obtenir le même résultat, mais seulement si les images étaient très proches de commencer.
Eh bien, votre question est un peu généraliste, mais comme vous indiquez des algorithmes de compression basés sur des fichiers (votre étiquette PKZip pour une chose), alors non. Il n'y a aucun moyen de deux algorithmes de compression sans perte sans perte peuvent produire la même sortie à partir de différentes entrées.
Toutefois, pour les algorithmes de compression à perte, comme JPEG, alors sûr, c'est bien sûr une possibilité, mais les fichiers seraient presque identiques au début.
Par exemple, prenez un fichier .png, enregistrez-le sous forme de fichier .JPEG, changez un pixel pour en faire un degré plus brillant ou plus sombre dans l'un des canaux, la resouez comme un .jpeg, et vous avez une chance que vous ayez eu la chance de recevoir deux fichiers identiques, même si l'entrée était différente, même légèrement.
Algorithmes sans perte, non, cela ne peut pas arriver. Pour les algorithmes de perte, oui.
Il est uniquement possible pour Pertey Compression algorithmes (en face de
Laissez f être un algorithme de compression. Si compressez donc, f est un algorithme de compression sans valeur (car il n'est pas une bijection), ou Quant à votre autre question, notez qu'un algorithme de compression sans perte est par définition pas comme algorithme de hachage, puisque une fonction de hachage h mappe un domaine a < / em> sur un domaine (généralement) plus petit b . Par conséquent, h ne peut pas être être une bijection, tandis que nous venons d'affirmer que notre fonction de compression sans perte f est une bijection. < / p> A et B donne le même fichier, puis f (a) = f (b) = c , pour certains c . Maintenant, laissez f ' l'algorithme de décompression. puis f '(f (a)) = f' (c) = f '(f (b)) . Par conséquent, f ' raquette A.zip et b.zip dans le même fichier.
A et B sont en fait la même fichier. (Quand je dis sans valeur, je veux dire sans valeur pour la compression sans perte!)
Sans valeur est un peu fort; Les algorithmes de perte (c.-à-d. non bijectif) sont utilisés pour l'audio et l'imagerie tout le temps
@bdonlan: Tu as raison. J'ai mis à jour la réponse pour clarifier ce que je veux dire par «sans valeur» :)
Certainement, la compression de pertes peut donner la même sortie que jamais notée.
Mais je pense qu'un point très important qui n'a pas été mentionné est que les hachages cryptographiques devraient être très difficiles à inverser (ou à reproduire le même hachage via deux entrées différentes). Pour cette raison, des algorithmes de compression réversibles tels que des zips ne conviendraient pas comme un hachage cryptographique.
+1 Pour souligner l'inutilité de la compression en tant que mesure de sécurité, mais je pense que l'OP était principalement intéressé par l'utilisation de sorties comprimées pour garantir l'unicité - et garantir l'unicité est quelque chose que la compression sans perte fait mieux que Hashes cryptographiques (bien que l'inconvénient évidente de produire une sortie variable de longueur).
Les fonctions de hachage cryptographique ont une exigence très spécifique: pour que cela soit très difficile de les inverser. La compression, par définition, est facile à inverser, donc c'est un très mauvais choix pour un hachage de crypto.
Notez que lorsque je dis «par définition» ci-dessus, je veux dire par définition conventionnelle. Strictement parlant, MD5, SHA-1, etc. pourrait également être considéré comme des algorithmes de compression.
Pour un algorithme d'être un hachage cryptographique décent, un petit changement localisé dans l'entrée devrait provoquer une variation de la production de grande taille dans la production. En outre, une fonction de hachage est un mappage d'une entrée arbitraire de la taille d'une sortie de taille fixe.
Votre mention de «hachage cryptographique» a suscité certaines personnes de penser que vous avez l'intention d'utiliser une compression sans perte à des fins de sécurité - est-ce correct? Si oui, c'est une idée terrible, pour toutes les raisons qu'ils donnent. Mais si vous êtes intéressé uniquement à garantir l'unicité et que vous êtes prêt à faire face à la compression des sorties de longueur variable vous donne, il peut s'agir d'un choix raisonnable (bien que, à toutes fins pratiques, l'utilisation d'un hachage cryptographique de longueur fixe sera plus rapide et Bien travailler - la probabilité de collision clé avec des clés par exemple 128 bits est plus négligeable).