Bon, j'ai mis ça dans php, mais ça concerne toutes les catégories je pense... Bon, tout est dans la question  

ben à obtenir une clef de taille fixe à partir de donénes de taille variable. les fonctions te hashage doivent tendre à etre injectives. exemple : md5

Oui, mais je comprends pas ce qu'il se passe exactement ? J'ai jamais fait de crypto, j'aimerais bien, si possible, avoir une réponse compréhensible pour un newbie Parce que "tendre à être injectif", c'est un peu du chinois pour moi là...

une fonction de hachage permet de trouver une empreinte fixe à partir d'un texte variable. et tu ne dois pas pouvoir trouver le texte original à partir de l'empreinte. une bonne fonction de hachage doit aussi t'assurer que trouver 2 textes avec une meme empreinte est tres difficile.
un exemple en + de celui de taz: sha

Ce que je ne comprend pas, c'est que la commande md5() en php donne toujours le même résultat, ce qui est logique. Celà veut dire pour moi que le programme fait toujours exactement le même encodage. Mais alors pk ce ne serait pas possible de le faire dans l'autre sens ?

heuresement que t'as toujours le meme resultat a partir de la meme source.
les fonctions de hachage ne sont pas bijectives. ca n'a rien a voir avec du cryptage

g vu qq part kon partait du fait kil était plus facile de multiplier des nbres premiers pour obtenir un résultat tjrs différent ke résoudre l'équation ki ferait ressortir ces nbres premiers, définis à partir d'une fonction. mais y'a longtps ke g lu ça et ct ptetre des conneries... ^^

ben c'est vrai avec les processuers acutles. mais pas avec les processeurs quantiques

si tu pouvais eviter d'ecrire comme un porc, je pourrais comprendre  ta question  

Un exemple vaut mieux que de longs discours : une fonction de hachage hyper simple et hyper merdique : la parité.
Si le nombre est pair : renvoyer 0.
S'il est impair renvoyer 1.
Quelque soit la taille du nombre, la valeur générée a la même longueur (1 chiffre).
Elle est injective => à partir de h(x), tu peux pas retrouver la valeur de x (y'en a une infinité).

 
Bizarre, ça correspond pas du tout a ma definition de l'injectivité
 
f(x) : S -> T est injective ssi pour tout (s1, s2) dans S², f(s1) = f(s2) => s1 = s2
 
Je dirais même que ta fonction h(x) n'est absolument pas et ne doit pas être injective ...

si elle était injective, alors t'aurais trouver une fonction de hacahge parfaite. attention à ne pas confondre injective et réversible

C'est à dire que ... une petite révision s'imposait !
LOk>
c'était pour illustrer l'histoire du "on peut le faire dans un sens et pas dans l'autre". Pour ce que j'en dit de +, oublie, j'ai mélangé / confondu.

 
t'as un exemple concret ?  ca m'intéresse
Je vois pas comment f(s1)=f(s2) pour tout couple s1 s2 de S.
 
a+

ben f: x -> x est injective
 
par contre g : x -> x² n'est l'est pas

 
j'ai une définition :

 
Ben je pige pas
 
si x² a au plus un antécédent ds A (qui est x) non ?
 
Ok c x² est bijectif. Mais justement, c la nuance que je saisis pas

Ben non ... x² a 2 antécédents : x et (-x)
x² n'est pas bijective sur ]-inf,+inf[. En revanche elle l'est sur [0,+inf[ ou ]-inf,0]

 
LOL kel con je fais  
N'empêche que je suis pas plus avancé pour l'injectif

correct

kristoph a raison
si une fonction de hachage est injective alors elle est réversible. (la plupart des fonctions de cryptage sont injectives sinon pas de decryptage possible : ce n'est pas le cas de md5 qui n'est pas fait pour decrypter)
 
Le fait de ne pas pouvoir trouver le texte original a partir de l'empreinte est important mais ca n'est le plus souvent pas le simple but.
 
Exemple: je veux classer des chaines dans une une structure de donnee ad hoc, je peux utiliser une hash map ou un simple tableau qui a partir d'une fonction de hachage me permettra de trouver rapidement la position approximative de ma chaine dans la structure (et de trouver sa position exacte par affinements successifs).
 
LeGreg

ben pas forcément: si f A -> B est injective, il peut exister y appartenant à B tel que f^-1(y) n'a pas de solutions dans A
 
enfin bref, à vous lire j'ai l'impression que md5 est le meilleur algo de compression du monde.
 
les algorithmes de hashage sont irréversibles. la clef appartient à un ensemble fini alors que les données non. voir l'exemple de la parité. quand on dit injective pour une fonction de hashage, c'est pour dire qu'il est difficile de trouver M1, M2 tel que hash(M1)==hash(M2)
 

Oui, les algo de hashage ne sont pas injectif, ils sont surjectifs !
 

effectivement, on est pas des sodomites matheuses.
 
 
pas tout à fait: les fonctions de hash sont surjectives ce qui entrainent des collisions, mais une fonction parfaite n'est pas surjective.
 
de même elles tendent à etre injectives

 
Euh ... c'est prouvé ça ? Ca veut dire que pour un hachage H donné, il existe au moins une donnée D telle que MD5(D) == H ? Ca ne m'a pas l'air si évident à démontrer que ça ...

 
Ce n'est pas parce que tu n'es pas un sodomite matheux
que tu dois baiser les maths (qui ne t'ont rien demandé )
 
je ne sais pas où tu as été pêcher que md5 pouvait
être utilise pour faire de la compression d'ailleurs ?
(la compression qui nécessite également une fonction injective sinon la décompression ne marche pas..)
 
Après quelques recherches sur google, je commence a me demander
si ta confusion ne vient pas d'une erreur de traduction de
ca:
http://www.php.net/manual/en/function.crypt.php
en ca :
http://www.teaser.fr/docs/php/php4/function.crypt.html
(ou comment embrouiller tout le monde en traduisant "one way" par "injective" )
 
LeGreg

 
Ben une fonction parfaite n'existe pas par définition !
(Un fonction de hachage injective, je veux dire )
 
Une fonction de hachage associe une clef de longeur fixe à des données de taille variable, donc :
 
1- La clef de longueur fixe est un ensemble fini (Corrigé !).
2- Les donnée de taille variable sont dans un ensemble infini.
 
Il n'y a donc aucune chance qu'une fonction de hachage soit injective.
 
En revanche une fonction parfaite doit être surjective.
De plus si possible, les éléments de l'ensemble d'arrivé (les clefs) doivent avoir la même "probabilité" d'être choisi.
 
L'exemple parfait est donc la parité.
Ou n'importe quel "checksum".
 
Celà dit, rien n'empèche de faire une "bonne" fonction de hachage qui ne soit pas surjective, ou pout laquelle la surjectivité soit difficile à démontrer.
 
Si vous pensez que c'est des conneries, merci de développer.

Je ne suis pas d'accord avec le fait qu'une fonction de hashage parfaite doit être surjective.
 
Pour moi, la fonction de hashage parfaite serait injective.
 
Et une fonction de hashage parfaite utilisée pour de la crypto doit être en plus de cela "non inversible". Ou plustot, elle serait quasiment impossible à inverser.
 
Bien sur, il est impossible d'avoir une fonction injective quand tu le resultat de ta fonction tiens dans 32 bits alors que le texte traité necessite 2 Mo

je faisais de l'humour pour la compression, parce qu'apparemment, c'etait pas clair pour tout le monde

Bon, j'ai trouvé çà :
 
http://www.rsasecurity.com/rsalabs/faq/2-1-6.html
 
Et çà :
 
http://www.securite.teamlog.com/pu [...] /19/23/15/
 
Et fanchement je me demande bien comment on peut affirmer un truc pareil :
 

 
Pour moi, c'est mathématiquement impossible !
Mais c'est sans doute par abus de simplification.
 
L'article de RSA est plus détaillé là dessus, même si :
 

 
Me semble contenir des contraintes tout aussi impossible à concilier mathématiquement.
 
En fait l'explication tiens plus à la "difficulté" de calcul qu'à une impossibilité stricte.
 
Mais bon, soit je sais pas lire, soit même chez RSA ils ne savent pas bien expliquer de quoi ils parlent    
 

ET

 
Je ne comprends pas bien en quoi un algo est "weakly collision-free" et en quoi l'autre est "strongly collision-free" ?
 
Sauf que dans le premier cas x, est donné et dans l'autre x et y sont libres, ce qui rend la comparaison douteuse   again.
 
M'enfin, y z'ont sans doute raison.
 
Conclusion, le terme mathématique d'injectivité, est mal adapté pour une fonction de hashage.
 
Il est mathématiquement incorrects, mais algorithmiquement suffisant à cause de la quazi-impossibilité de calcul.

Le terme "injectif" n'est pas algorithmiquement suffisant, il est completement incorrect. Mais il est vrai que être "collision-free", ça ressemble à de la sous injectivité
 
Pour le problème des "weakly collision-free" et "strongly collision-free", il est facile de voir que le deuxième cas englobe le premier. On peut imaginer des situations dans lesquel il serait interressant pour un hacker d'avoir 2 messages differents avec la même signature.
 
Et pour info, md5 est au moins "weakly collision-free" quand vous fixez la taille max des messages. Il est possible d'obtenir un message qui à une clef voulue en fesant grandir un message de façon controlée.

 
il y a suffisamment de confusion dans ce post et j'ai l'impression que tu en rajoutes.
 
Je saurais que tu fais de l'humour si je te connaissais suffisamment pour savoir que tu ne racontes jamais de conneries mais ce n'est pas le cas.
 
LeGreg

qu'est ce que j'ai dit de faux? si c'est sur ces débat d'injection/surjection, on s'est tous emmélés
 
ou tu dis conneries dans un autre sens