Auteur Sujet: Algorithme Compression  (Lu 21701 fois)

0 Membres et 1 Invité sur ce sujet

Effectivement, j'ai revérifié tous mes calculs farfelus et c'est absolument pas cohérent

mea-culpa, la compression c'est pas pour moi !

Hors ligne Ap0

░░░░▄▄▄▄▀▀▀▀▀▀▀▀▄▄▄▄▄▄
░░░█░░░░▒▒▒▒▒▒▒▒▒▒▒▒░░▀▀▄
░░█░░░▒▒▒▒▒▒░░░░░░░░▒▒▒░░█
░█░░░░░░▄██▀▄▄░░░░░▄▄▄░░░█
█░▄▄▄▒░█▀▀▀▀▄▄█░░░██▄▄█░░░█
█░▒▄░▀▄▄▄▀░░░░░░░░█░░░▒▒▒▒▒█
█░░░█▄░█▀▄▄░▀░▀▀░▄▄▀░░░░█░░█
░█░░▀▄▀█▄▄░█▀▀▀▄▄▄▄▀▀█▀██░█
░░█░░██░░▀█▄▄▄█▄▄█▄████░█
░░░█░░░▀▀▄░█░░░█░███████░█
░░░░▀▄░░░▀▀▄▄▄█▄█▄█▄█▄▀░░█
░░░░░░▀▄▄░▒▒▒▒░░░░░░░░░░█
░░░░░░░░█▀▀▄▄░▒▒▒▒▒▒▒▒▒▒░█
░░░░░░░░█░░░░▀▄▄▄▄▄▄▄▄▄▄█

Joli troll par Ap0 qui gagne ainsi un ban.

Cela dit je pense qu'on peut le laisser le topic qui a amené à des discussions et des links sympas (vous gérez :p).


infosmerci

  • Invité
bonjour ; excusez-moi de déranger peut-être ; s'il vous plaît (question / idée sérieuse ; mais oui lacune dans les savoirs) :

flngr, ça ne marche pas, tu auras des collisions.
Compte combien de valeurs différentes tu peux représenter avec tes deux, trois, quatre... hashs. Compte combien de valeurs différentes on peut former avec 100 Mo (ou 1 Go ou ce que tu veux). Il y a forcément des millions de fichiers qui mènent aux mêmes hashs. Un hash n'est pas bijectif, ce n'est pas de la compression.

Pour une même taille de fichier ; 4 valeurs de hash (crc32 + md5 + sha-1 + sha-256) ne protège pas des collisions ?

Si on a le nom du fichier d'origine, et la description humaine et surtout machine (signature numérique par exemple) on peut discriminer les collisions ? oui ?

(note en passant : on peut faire plusieurs recherches et avoir un fichier sur un support mémoire vive spécialisée permettant de dynamisé la taille du fichier (on incrémente de + 1 = 000 001 010 ... et quand l'incrémentation atteint la taille maximum 111, on augmente la taille du fichier 1000 dans la table d'allocation ; la taille sert juste pour la lecture en fait (et pour incrémenter, oui), quand on test le hash) ; on a plusieurs hash pour plusieurs fichiers et on cherche une correspondance en commençant avec un petit fichier dont les bit sont tous à zéro = 0 hash 1 hash =taille> 10 hash 11 hash  =taille> 100 hash 101 hash =taille> ...)

Combien de temps il faut pour incrémenter de +1 en hexadécimale avec un outil logiciel / matériel dédié le contenu d'un fichier image égale à la taille d'une disquette pour faire simple et tester si le hash générer à chaque itération (avec tous les bits à 0 aussi) correspond à la valeur cherchée ? Au départ, tous les bits du fichier image sont à 0, puis on incrémente de +1 et on test le hash à chaque incrémentation (le plus rapide uniquement ; et les autres lents que si il y a un résultat positif). Sous linux et windows on peut faire des fichiers vides ; ex: dd if=/dev/zero of=foobar count=1024 bs=1024 et fsutil file createnew exemple.ext 1024 (en octets). Il est possible de faire des supports virtuels en mémoire vive (plus rapide que sur disque dur) avec l'outil "ImDisk" virtual disk driver.

merci (et oui aussi, le terme "bijectif" est trop compliqué à comprendre (ou mal expliqué) pour moi ; du moins, présentement.)

Bonjour

Pour une même taille de fichier ; 4 valeurs de hash (crc32 + md5 + sha-1 + sha-256) ne protège pas des collisions ?
Tu peux avoir des collisions dans tous ces algos sauf le sha-256, me semble-t-il (pas prouvé).
Si tu valides avec plusieurs algorithmes, pour le même fichier, des collisions en cascade, c’est que tu n’as pas de chances.

Si on a le nom du fichier d'origine, et la description humaine et surtout machine (signature numérique par exemple) on peut discriminer les collisions ? oui ?

(note en passant : on peut faire plusieurs recherches et avoir un fichier sur un support mémoire vive spécialisée permettant de dynamisé la taille du fichier (on incrémente de + 1 = 000 001 010 ... et quand l'incrémentation atteint la taille maximum 111, on augmente la taille du fichier 1000 dans la table d'allocation ; la taille sert juste pour la lecture en fait (et pour incrémenter, oui), quand on test le hash) ; on a plusieurs hash pour plusieurs fichiers et on cherche une correspondance en commençant avec un petit fichier dont les bit sont tous à zéro = 0 hash 1 hash =taille> 10 hash 11 hash  =taille> 100 hash 101 hash =taille> ...)

Combien de temps il faut pour incrémenter de +1 en hexadécimale avec un outil logiciel / matériel dédié le contenu d'un fichier image égale à la taille d'une disquette pour faire simple et tester si le hash générer à chaque itération (avec tous les bits à 0 aussi) correspond à la valeur cherchée ? Au départ, tous les bits du fichier image sont à 0, puis on incrémente de +1 et on test le hash à chaque incrémentation (le plus rapide uniquement ; et les autres lents que si il y a un résultat positif). Sous linux et windows on peut faire des fichiers vides ; ex: dd if=/dev/zero of=foobar count=1024 bs=1024 et fsutil file createnew exemple.ext 1024 (en octets). Il est possible de faire des supports virtuels en mémoire vive (plus rapide que sur disque dur) avec l'outil "ImDisk" virtual disk driver.

merci (et oui aussi, le terme "bijectif" est trop compliqué à comprendre (ou mal expliqué) pour moi ; du moins, présentement.)

Je n’ai pas compris ce que tu disais.

En ce qui concerne une bijection, je te conseille de regarder wikipedia (mot clef : bijection puis Bijection réciproque).
En clair, si bijection : tu es capables à partir de ta valeur d’arrivé en lui appliquant une fonction réciproque de retrouver ta valeur de départ. Ex concret issu de wikipedia :

Ex : f(x) = x^2  sa fonction reciproque (noté f-1) est f-1(x) = racine carré(2) en généralisant : f(x) = x^n => f-1(x) = racine nième(x) En toute rigueur il faudrait préciser son ensemble de définition ce que je n’ai pas fait car redondant avec ce qu’il y a sur wikipedia.

Citer
Tu peux avoir des collisions dans tous ces algos sauf le sha-256, me semble-t-il (pas prouvé).
Quelque soit l'algo de hash, si la taille du hash est plus petite que la taille du message il y a forcément des collisions. Tout simplement parce que le nombre de messages possibles sur une taille plus grande que la taille du hash est supérieur au nombre de valeurs de hash possibles.

Après ça ne dit pas s'il est facile de générer volontairement des fichiers différents qui collisionnent, d'autant plus si leur contenu est cohérent.

infosmerci

  • Invité
Bonjour, s'il vous plaît, merci d'avance :

Si tu valides avec plusieurs algorithmes, pour le même fichier, des collisions en cascade, c’est que tu n’as pas de chances.

Je voudrais une explication (accessible sans maths) pour mieux comprendre et être sûr en fait :
On peut avoir 2 fichiers différents de même taille et le crc32 + md5 + sha-1 + sha-256 pareil pour les 2 fichiers ?
En fait, on ne fait que réduire le nombre des collisions avec plusieurs hashs ? C'est bien ça ? Merci.

(Vu que mes questions ne sont pas basée sur une recherche aléatoire de collision, la chance n'a rien à faire là.)

Je n’ai pas compris ce que tu disais.

J'aime pas utiliser le terme "brute force de hash" que vous avez l'air de mieux comprendre que la notion d'"incrémenter", puis tester le hash ; ou j'ai vraiment du mal à me faire comprendre.

Je repose la question ; 1 des questions :
Est-ce que par exemple si on se débrouille pour récuperer la signature numérique (sous Windows) d'un fichier exécutable (sous Windows), c'est suffisant pour discriminer deux fichiers différents de la même taille avec les mêmes 4 hashs (crc32 + md5 + sha-1 + sha-256) ?

Maintenant, si on a connaissance du nombre de bit à 1 dans un fichier quelconque (sans signature = pas un exe) et que l'on a aussi le nombre de groupes de bit à 1, est-ce que l'on peut réduire le temps de recherche de la combinaison binaire qui correspond au hash. (( Au lieu de faire une incrémentation pour passer en revue toutes les combinaisons, qui prend du temps, je propose une itération intelligente. ))

Les infos d'origine à récuperer du fichier à compresser ; postulat (à améliorer) :

La taille
Le crc32
Le md5
Le sha-1
Le sha-256
Le nombre de bit à 1
Le nombre de groupes de bit à 1

Pour *décompresser*, on crée un fichier vide et on incrémente à l"intérieur (avec un éditeur de fichier) pour passer en revues toutes les possibilités et on test le hash à chaque itération du contenu ; (le contenu stocké d'un fichier, c'est du binaire).

En ce qui concerne une bijection, je te conseille de regarder wikipedia (mot clef : bijection puis Bijection réciproque).
En clair, si bijection : tu es capables à partir de ta valeur d’arrivé en lui appliquant une fonction réciproque de retrouver ta valeur de départ. Ex concret issu de wikipedia :

Ex : f(x) = x^2  sa fonction reciproque (noté f-1) est f-1(x) = racine carré(2) en généralisant : f(x) = x^n => f-1(x) = racine nième(x) En toute rigueur il faudrait préciser son ensemble de définition ce que je n’ai pas fait car redondant avec ce qu’il y a sur wikipedia.

Je souhaitais une explication vulgarisée (mais complète) accessible à tous ; j'avais déjà regardé sur wikipédia (dico et wiki). Je sèche avec tes formules ; par contre, je comprends +ou- que de façon mathématique donc pas en brute force, on ne peut pas reconstruire la chaîne d'origine ; même si un hash est construit de façon connue. (Il y a trop d'aiguillages et rapidement, voir des trous pour remonter à l'envers <= c'est ça que je veux arriver à visualiser +ou-).

Je réponds juste à ce passage...

Citer
En ce qui concerne une bijection, je te conseille de regarder wikipedia (mot clef : bijection puis Bijection réciproque).

Je souhaitais une explication vulgarisée (mais complète) accessible à tous ; j'avais déjà regardé sur wikipédia (dico et wiki). Je sèche avec tes formules ; par contre, je comprends +ou- que de façon mathématique donc pas en brute force, on ne peut pas reconstruire la chaîne d'origine ; même si un hash est construit de façon connue. (Il y a trop d'aiguillages et rapidement, voir des trous pour remonter à l'envers <= c'est ça que je veux arriver à visualiser +ou-).


Tu peux voir une fonction comme un opérateur qui fait passer d'un ensemble à un autre. Dans la vie courante on a souvent des fonctions qui vont de ℝ dans ℝ, mais ça peut être de n'importe quoi vers n'importe quoi d'autre. Pour chaque élément de l'ensemble de départ, la fonction donne un élément de l'ensemble d'arrivée.

Si chaque élément de l'ensemble d'arrivée peut être obtenu avec cette fonction, on dit qu'elle est surjective. Imagine qu'on a un ensemble E = {A, B} et un ensemble F = {1, 2, 3} : si on a une fonction f E → F (de E vers F) définie par f(A) = 1 et f(B) = 2, cette fonction n'est pas surjective car elle ne renvoie jamais 3.

Si pour chaque élément de l'ensemble d'arrivée, il n'y a qu'un seul élément de l'ensemble de départ qui permet de l'obtenir (un antécédent), on dit qu'elle est injective. Imagine que cette fois on a E = {A, B, C} et F = {1, 2} : si on a une fonction f E → F définie par f(A) = 1, f(B) = 2 et f(C) = 2, elle n'est pas injective car 2 peut être obtenu aussi bien avec B ou C.

Enfin, une fonction qui est à la fois injective et surjective est dite bijective. Concrètement ça veut dire que chaque élément de l'ensemble de départ donne un élément distinct de l'ensemble d'arrivée, et qu'il n'y a pas d'élément de l'ensemble d'arrivée qui ne peut pas être obtenu (les deux ensembles font la même taille). Un exemple de fonction bijective, ce serait avec E = {A, B} et F = {1, 2}, une fonction f E → F définie par f(A) = 1 et f(B) = 2. Pour tout élément de F, on sait quel unique élément de E a permis de l'obtenir.

Quand une fonction est bijective, à partir d'un élément d'arrivée on peut revenir à l'élément de départ, puisqu'il qu'on sait qu'il y en a un, et un seul. Le problème avec un hash, c'est que ce n'est pas du tout injectif, et donc pas bijectif : l'ensemble d'arrivée est beaucoup plus petit que l'ensemble de départ, et ses éléments ont de nombreux antécédents.

C'était la minute ensembles, j'espère que mon résumé est clair. :)

chapeau et sans diagramme de Venn ! \o/