J'ai quelques questions auxquelles je ne parviens pas à trouver de
réponses avec mes lectures, je me permets de vous les poser (crosspost sur
fr.misc.cryptologie et sur fr.comp.algorithmes).
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le
principe. Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir
correspondre qu'un et un seul fichier. La chose me semble étrange,
démonstration du pourquoi.
J'ai un fichier, mettons de 100 caractères ASCII. J'ai donc 255^100
possibilités différentes pour le fichier. Après le hash, j'ai, mettons, un
résultat qui fait 16 caractères ASCII (128 bits). J'ai donc 255^16
possibilités différentes de clefs.
255^16, c'est largement assez pour se dire qu'en prenant deux fichiers
différents, il y a une chance infime pour qu'ils aient le même hash. Mais il
est impossible qu'à un hash donné ne corresponde qu'un et un seul fichier
(il faudrait un hash qui fasse au moins la même taille que le fichier de
départ).
Par contre, pour le fait qu'un et un seul hash doit être associé à un
fichier précis, pas de problèmes.
Deux demandes de précisions : quels sont les conditions nécessaires et
suffisantes qui permettent de dire qu'un hash est un bon hash ? Comment
fonctionne SHA-256 ?
J'ai bien une idée pour un algorithme de hash, mais ça me semble "trop
simpliste" alors je demande un peu les critères.
2. A ce que j'ai cru comprendre, les (ou plutôt certains types de) bons
algos de cryptage se décomposent en deux parties majeures :
- une consolidation du texte à crypter (on rend les caractères
interdépendants) - en gros, un encodage ;
- on crypte le texte.
Je lis quelque part que si la consolidation ne fait pas appel à la clef,
alors elle est inutile ; il suffirait à un cryptanalyste d'appliquer la
dé-consolidation au message crypté, puis de décrypter le texte par après.
Déjà, le fait de dire ça me semble assez vaseux, ça me semble même tout à
fait faux... Confirmation / infirmation ?
Donc la consolidation ferait appel à la clef. Mais dans ce cas, c'est
déjà du cryptage, et plus de la consolidation/encodage !?!?
3. Quand on fait un algo de cryptage qui fait intervenir une liste de
nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de vue de
la sortie (on n'y comprend rien...) mais si l'algo est public, alors
n'importe quel cryptanalyste pourra faire machine arrière sans problèmes.
Donc la sécurité est faible, je me trompe ? A moins qu'on ne fasse dépendre
la liste pseudo-aléatoire de caractères qui dépendent du texte (comme sa
taille en octet, ou bien d'une forme de hash de celui-ci (ce qu'on appelle
le digest ?))... ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Grindipo
Bonsoir. Hum, un mystère d'Usenet : j'ai reçu ce message vers midi... Peut-être les
fuseaux horaires ;) Bonjour
J'ai quelques questions auxquelles je ne parviens pas à trouver de réponses avec mes lectures, je me permets de vous les poser (crosspost sur fr.misc.cryptologie et sur fr.comp.algorithmes). Je poursuis sur fmc. Juste une remarque : il me semble que tu aurais dû
préciser sur quel forum poursuivre la discussion, ça permet de mettre de l'ordre.
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le principe. Je me suis intéressé à md5, un algo particulier de hash. Il en existe
d'autres, mais je ne les connais guère... Mes recherches sur md5 ont abouti à la conclusion que l'on ne peut dire grand'chose sur lui, en particulier son "opération" inverse.
Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir correspondre qu'un et un seul fichier. La chose me semble étrange, démonstration du pourquoi. J'ai un fichier, mettons de 100 caractères ASCII. J'ai donc 255^100 possibilités différentes pour le fichier. Après le hash, j'ai, mettons, un résultat qui fait 16 caractères ASCII (128 bits). J'ai donc 255^16 possibilités différentes de clefs. Exact.
255^16, c'est largement assez pour se dire qu'en prenant deux fichiers différents, il y a une chance infime pour qu'ils aient le même hash. Oui.
Mais il est impossible qu'à un hash donné ne corresponde qu'un et un seul fichier (il faudrait un hash qui fasse au moins la même taille que le fichier de départ). Erreur.
Par exemple pour md5, j'ai l'impression que l'on ne sait rien sur la répartition des résultats. Mais : - md5(x) n'est pas injective puisqu'il suffit de prendre (2^128+1) x différents pour en trouver (au moins) 2 qui ont le même hash (principe des tiroirs : 10 objets dans 9 tiroirs : il y a au moins un tiroir qui contient 2 objets MAIS il se peut par ailleurs qu'un tiroir soit vide) - On ne sait pas si md5 est surjective. Il se peut que 84C6B5274CE3EB297335DA00466A5715 ne soit le hash d'AUCUN fichier. De plus le seul moyen connu de répondre à cette question par l'affirmative est d'exhiber un fichier qui va bien. On ne sait pas y répondre par la négative. Donc, un hash donné peut correspondre à zéro, un, deux... une infinité de fichiers différents. Et on ne sait pas le prévoir. - Puisque le nombre de fichiers possibles est infini, tout ce qu'on peut dire est qu'il y a AU MOINS UN hash qui corresponde à une infinité de fichiers. Bien sûr, il peut y en avoir plus qu'un, mais on ne sait pas le(s)quel(s). Peut-être que tous les fichiers plus grand que 1 peta-octet ont tous le même hash md5 ?
Par contre, pour le fait qu'un et un seul hash doit être associé à un fichier précis, pas de problèmes. Encore heureux ;)
Le hash est une fonction, au sens mathématique du terme. Donc Hash(x) est parfaitement défini (et unique) pour tout x.
Deux demandes de précisions : quels sont les conditions nécessaires et suffisantes qui permettent de dire qu'un hash est un bon hash ? Ca dépend de ce que tu veux en faire. Dans tous les cas, qu'il soit
calculable assez rapidement est un plus. - Pour réaliser des hash-tables : Propriétés de bon mélange.
- Cryptologie : Fonction difficilement inversible. En fait pour être précis, il y a plusieurs attaques possibles sur une fonction de hash : -- Recherche de collisions : trouver deux fichiers différents ayant le même hash. Forcément possible (il suffit de prendre 255^10+1 fichiers) Je crois qu'il existe des tentatives dans cette voie (calcul bourrin). Résultats ? -- Attaque à hash choisi : trouver un fichier qui corresponde à un hash donné. Plus difficile. On ne sait même pas si c'est possible. Bien sûr si tu me donnes un hash d'un mot du dictionnaire, je trouverai assez vite.
Comment fonctionne SHA-256 ? Euh... Quelqu'un dans la salle ? Tu as essayé google ?
J'ai bien une idée pour un algorithme de hash, mais ça me semble "trop simpliste" alors je demande un peu les critères. J'ai fortement l'impression que personne n'a "prouvé" md5. Seule
l'expérience a montré qu'il était adapté à l'utilisation qui en est faite.
2.
3. Quand on fait un algo de cryptage qui fait intervenir une liste de nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de vue de
la sortie (on n'y comprend rien...) mais si l'algo est public, alors n'importe quel cryptanalyste pourra faire machine arrière sans problèmes. En général, ne pas se fier au secret de l'algorithme. Ben faire machine
arrière est justement ce qui est difficile avec certaines fonctions de hachage.
Donc la sécurité est faible, je me trompe ? Pas forcément. Je propose un exemple :
a|b représente la concaténation des chaînes a et b. h(x) une fonction de hachage telle md5 (décidément, j'en fais une fixette ;) On choisit S, chaîne de caractères, une graine. U(0) = h(S) U(n+1) = h(U(n)|S) Même en connaissant autant de valeurs de U, je ne pourrait pas en trouver d'autres sans connaître S, non ? Car connaissant U(n), il me faut connaître S pour calculer U(n+1) et il me faut "inverser" h pour trouver U(n-1).
Grindipo
Bonsoir.
Hum, un mystère d'Usenet : j'ai reçu ce message vers midi... Peut-être les
fuseaux horaires ;)
Bonjour
J'ai quelques questions auxquelles je ne parviens pas à trouver de
réponses avec mes lectures, je me permets de vous les poser (crosspost sur
fr.misc.cryptologie et sur fr.comp.algorithmes).
Je poursuis sur fmc. Juste une remarque : il me semble que tu aurais dû
préciser sur quel forum poursuivre la discussion, ça permet de mettre de
l'ordre.
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le
principe.
Je me suis intéressé à md5, un algo particulier de hash. Il en existe
d'autres, mais je ne les connais guère...
Mes recherches sur md5 ont abouti à la conclusion que l'on ne peut dire
grand'chose sur lui, en particulier son "opération" inverse.
Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir
correspondre qu'un et un seul fichier. La chose me semble étrange,
démonstration du pourquoi.
J'ai un fichier, mettons de 100 caractères ASCII. J'ai donc 255^100
possibilités différentes pour le fichier. Après le hash, j'ai, mettons, un
résultat qui fait 16 caractères ASCII (128 bits). J'ai donc 255^16
possibilités différentes de clefs.
Exact.
255^16, c'est largement assez pour se dire qu'en prenant deux fichiers
différents, il y a une chance infime pour qu'ils aient le même hash.
Oui.
Mais il
est impossible qu'à un hash donné ne corresponde qu'un et un seul fichier
(il faudrait un hash qui fasse au moins la même taille que le fichier de
départ).
Erreur.
Par exemple pour md5, j'ai l'impression que l'on ne sait rien sur la
répartition des résultats. Mais :
- md5(x) n'est pas injective puisqu'il suffit de prendre (2^128+1) x
différents pour en trouver (au moins) 2 qui ont le même hash (principe des
tiroirs : 10 objets dans 9 tiroirs : il y a au moins un tiroir qui contient
2 objets MAIS il se peut par ailleurs qu'un tiroir soit vide)
- On ne sait pas si md5 est surjective. Il se peut que
84C6B5274CE3EB297335DA00466A5715 ne soit le hash d'AUCUN fichier. De plus le
seul moyen connu de répondre à cette question par l'affirmative est
d'exhiber un fichier qui va bien. On ne sait pas y répondre par la négative.
Donc, un hash donné peut correspondre à zéro, un, deux... une infinité de
fichiers différents. Et on ne sait pas le prévoir.
- Puisque le nombre de fichiers possibles est infini, tout ce qu'on peut
dire est qu'il y a AU MOINS UN hash qui corresponde à une infinité de
fichiers. Bien sûr, il peut y en avoir plus qu'un, mais on ne sait pas
le(s)quel(s). Peut-être que tous les fichiers plus grand que 1 peta-octet
ont tous le même hash md5 ?
Par contre, pour le fait qu'un et un seul hash doit être associé à un
fichier précis, pas de problèmes.
Encore heureux ;)
Le hash est une fonction, au sens mathématique du terme. Donc Hash(x) est
parfaitement défini (et unique) pour tout x.
Deux demandes de précisions : quels sont les conditions nécessaires et
suffisantes qui permettent de dire qu'un hash est un bon hash ?
Ca dépend de ce que tu veux en faire. Dans tous les cas, qu'il soit
calculable assez rapidement est un plus.
- Pour réaliser des hash-tables :
Propriétés de bon mélange.
- Cryptologie :
Fonction difficilement inversible. En fait pour être précis, il y a
plusieurs
attaques possibles sur une fonction de hash :
-- Recherche de collisions : trouver deux fichiers différents ayant le même
hash. Forcément possible (il suffit de prendre 255^10+1 fichiers)
Je crois qu'il existe des tentatives dans cette voie (calcul bourrin).
Résultats ?
-- Attaque à hash choisi : trouver un fichier qui corresponde à un hash
donné. Plus difficile. On ne sait même pas si c'est possible.
Bien sûr si tu me donnes un hash d'un mot du dictionnaire, je trouverai
assez vite.
Comment fonctionne SHA-256 ?
Euh... Quelqu'un dans la salle ? Tu as essayé google ?
J'ai bien une idée pour un algorithme de hash, mais ça me semble "trop
simpliste" alors je demande un peu les critères.
J'ai fortement l'impression que personne n'a "prouvé" md5. Seule
l'expérience a montré qu'il était adapté à l'utilisation qui en est faite.
2.
3. Quand on fait un algo de cryptage qui fait intervenir une liste de
nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de vue
de
la sortie (on n'y comprend rien...) mais si l'algo est public, alors
n'importe quel cryptanalyste pourra faire machine arrière sans problèmes.
En général, ne pas se fier au secret de l'algorithme. Ben faire machine
arrière est justement ce qui est difficile avec certaines fonctions de
hachage.
Donc la sécurité est faible, je me trompe ?
Pas forcément. Je propose un exemple :
a|b représente la concaténation des chaînes a et b. h(x) une fonction de
hachage telle md5 (décidément, j'en fais une fixette ;)
On choisit S, chaîne de caractères, une graine.
U(0) = h(S)
U(n+1) = h(U(n)|S)
Même en connaissant autant de valeurs de U, je ne pourrait pas en trouver
d'autres sans connaître S, non ? Car connaissant U(n), il me faut connaître
S pour calculer U(n+1) et il me faut "inverser" h pour trouver U(n-1).
Bonsoir. Hum, un mystère d'Usenet : j'ai reçu ce message vers midi... Peut-être les
fuseaux horaires ;) Bonjour
J'ai quelques questions auxquelles je ne parviens pas à trouver de réponses avec mes lectures, je me permets de vous les poser (crosspost sur fr.misc.cryptologie et sur fr.comp.algorithmes). Je poursuis sur fmc. Juste une remarque : il me semble que tu aurais dû
préciser sur quel forum poursuivre la discussion, ça permet de mettre de l'ordre.
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le principe. Je me suis intéressé à md5, un algo particulier de hash. Il en existe
d'autres, mais je ne les connais guère... Mes recherches sur md5 ont abouti à la conclusion que l'on ne peut dire grand'chose sur lui, en particulier son "opération" inverse.
Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir correspondre qu'un et un seul fichier. La chose me semble étrange, démonstration du pourquoi. J'ai un fichier, mettons de 100 caractères ASCII. J'ai donc 255^100 possibilités différentes pour le fichier. Après le hash, j'ai, mettons, un résultat qui fait 16 caractères ASCII (128 bits). J'ai donc 255^16 possibilités différentes de clefs. Exact.
255^16, c'est largement assez pour se dire qu'en prenant deux fichiers différents, il y a une chance infime pour qu'ils aient le même hash. Oui.
Mais il est impossible qu'à un hash donné ne corresponde qu'un et un seul fichier (il faudrait un hash qui fasse au moins la même taille que le fichier de départ). Erreur.
Par exemple pour md5, j'ai l'impression que l'on ne sait rien sur la répartition des résultats. Mais : - md5(x) n'est pas injective puisqu'il suffit de prendre (2^128+1) x différents pour en trouver (au moins) 2 qui ont le même hash (principe des tiroirs : 10 objets dans 9 tiroirs : il y a au moins un tiroir qui contient 2 objets MAIS il se peut par ailleurs qu'un tiroir soit vide) - On ne sait pas si md5 est surjective. Il se peut que 84C6B5274CE3EB297335DA00466A5715 ne soit le hash d'AUCUN fichier. De plus le seul moyen connu de répondre à cette question par l'affirmative est d'exhiber un fichier qui va bien. On ne sait pas y répondre par la négative. Donc, un hash donné peut correspondre à zéro, un, deux... une infinité de fichiers différents. Et on ne sait pas le prévoir. - Puisque le nombre de fichiers possibles est infini, tout ce qu'on peut dire est qu'il y a AU MOINS UN hash qui corresponde à une infinité de fichiers. Bien sûr, il peut y en avoir plus qu'un, mais on ne sait pas le(s)quel(s). Peut-être que tous les fichiers plus grand que 1 peta-octet ont tous le même hash md5 ?
Par contre, pour le fait qu'un et un seul hash doit être associé à un fichier précis, pas de problèmes. Encore heureux ;)
Le hash est une fonction, au sens mathématique du terme. Donc Hash(x) est parfaitement défini (et unique) pour tout x.
Deux demandes de précisions : quels sont les conditions nécessaires et suffisantes qui permettent de dire qu'un hash est un bon hash ? Ca dépend de ce que tu veux en faire. Dans tous les cas, qu'il soit
calculable assez rapidement est un plus. - Pour réaliser des hash-tables : Propriétés de bon mélange.
- Cryptologie : Fonction difficilement inversible. En fait pour être précis, il y a plusieurs attaques possibles sur une fonction de hash : -- Recherche de collisions : trouver deux fichiers différents ayant le même hash. Forcément possible (il suffit de prendre 255^10+1 fichiers) Je crois qu'il existe des tentatives dans cette voie (calcul bourrin). Résultats ? -- Attaque à hash choisi : trouver un fichier qui corresponde à un hash donné. Plus difficile. On ne sait même pas si c'est possible. Bien sûr si tu me donnes un hash d'un mot du dictionnaire, je trouverai assez vite.
Comment fonctionne SHA-256 ? Euh... Quelqu'un dans la salle ? Tu as essayé google ?
J'ai bien une idée pour un algorithme de hash, mais ça me semble "trop simpliste" alors je demande un peu les critères. J'ai fortement l'impression que personne n'a "prouvé" md5. Seule
l'expérience a montré qu'il était adapté à l'utilisation qui en est faite.
2.
3. Quand on fait un algo de cryptage qui fait intervenir une liste de nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de vue de
la sortie (on n'y comprend rien...) mais si l'algo est public, alors n'importe quel cryptanalyste pourra faire machine arrière sans problèmes. En général, ne pas se fier au secret de l'algorithme. Ben faire machine
arrière est justement ce qui est difficile avec certaines fonctions de hachage.
Donc la sécurité est faible, je me trompe ? Pas forcément. Je propose un exemple :
a|b représente la concaténation des chaînes a et b. h(x) une fonction de hachage telle md5 (décidément, j'en fais une fixette ;) On choisit S, chaîne de caractères, une graine. U(0) = h(S) U(n+1) = h(U(n)|S) Même en connaissant autant de valeurs de U, je ne pourrait pas en trouver d'autres sans connaître S, non ? Car connaissant U(n), il me faut connaître S pour calculer U(n+1) et il me faut "inverser" h pour trouver U(n-1).
Grindipo
Jacques Caron
fu2 fr.misc.cryptologie
On Sat, 7 Aug 2004 12:24:16 +0200, Horace wrote:
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le principe. Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir correspondre qu'un et un seul fichier. La chose me semble étrange, démonstration du pourquoi.
Ce n'est clairement pas étrange, c'est totalement faux. Un hash a un nombre de valeurs fini, alors que les valeurs "hashées" font partie d'un ensemble infini. Mais: - un fichier donné a un hash unique (pour un algo donné, bien entendu) - avec un hash cryptographique (comme MD5, par exemple), il est très difficile de trouver deux fichiers ayant la même valeur de hash. Il est clair qu'il existe des valeurs de hashs qui sont communes à plusieurs fichiers (voire une infinité), mais trouver une "collision" est très difficile. Voir par exemple http://www.md5crk.com/ pour un tel effort. - avec un hash cryptographique, il est très difficile de retrouver le fichier original à partir du hash.
Deux demandes de précisions : quels sont les conditions nécessaires et suffisantes qui permettent de dire qu'un hash est un bon hash ?
Pour que ce soit un bon hash cryptographique, il faut qu'il respecte au moins les deux conditions données ci-dessus: difficile de trouver une collision, difficile de trouver l'origine. Mais il n'existe généralement pas de preuve absolue, seule l'épreuve du temps permet de voir si personne ne trouve un moyen d'arriver à trouver une collision ou l'original.
3. Quand on fait un algo de cryptage qui fait intervenir une liste de nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de vue de la sortie (on n'y comprend rien...) mais si l'algo est public, alors n'importe quel cryptanalyste pourra faire machine arrière sans problèmes.
Il y a 4 éléments de base en crypto: - le clair - l'algo - la clef - le chiffré
En général, si on a 3 éléments on peut trouver le 4e (pas forcément aisément, mais en théorie c'est possible). Si l'algo n'utilise pas de clef (ou une clef fixe ou déterminable par un élément externe), il est clair qu'on peut déchiffrer le chiffré avec juste l'algo (en supposant bien entendu que c'est un algo réversible, sinon ce n'est pas du chiffrement mais un hash). En général l'algo est public, le chiffré l'est aussi, donc il faut tenir la clef secrète...
Il faut noter que la règle des 3 éléments explique qu'il est très dangeureux de faire circuler les versions claire et chiffrée d'un même message: on peut alors finir par trouver la clef.
Jacques. -- Interactive Media Factory Création, développement et hébergement de services interactifs: SMS, SMS+, Audiotel... http://www.imfeurope.com/
fu2 fr.misc.cryptologie
On Sat, 7 Aug 2004 12:24:16 +0200, Horace <ERROR@ERROR.fr> wrote:
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le
principe. Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir
correspondre qu'un et un seul fichier. La chose me semble étrange,
démonstration du pourquoi.
Ce n'est clairement pas étrange, c'est totalement faux. Un hash a un
nombre de valeurs fini, alors que les valeurs "hashées" font partie d'un
ensemble infini. Mais:
- un fichier donné a un hash unique (pour un algo donné, bien entendu)
- avec un hash cryptographique (comme MD5, par exemple), il est très
difficile de trouver deux fichiers ayant la même valeur de hash. Il est
clair qu'il existe des valeurs de hashs qui sont communes à plusieurs
fichiers (voire une infinité), mais trouver une "collision" est très
difficile. Voir par exemple http://www.md5crk.com/ pour un tel effort.
- avec un hash cryptographique, il est très difficile de retrouver le
fichier original à partir du hash.
Deux demandes de précisions : quels sont les conditions nécessaires et
suffisantes qui permettent de dire qu'un hash est un bon hash ?
Pour que ce soit un bon hash cryptographique, il faut qu'il respecte au
moins les deux conditions données ci-dessus: difficile de trouver une
collision, difficile de trouver l'origine. Mais il n'existe généralement
pas de preuve absolue, seule l'épreuve du temps permet de voir si personne
ne trouve un moyen d'arriver à trouver une collision ou l'original.
3. Quand on fait un algo de cryptage qui fait intervenir une liste de
nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de
vue de la sortie (on n'y comprend rien...) mais si l'algo est public,
alors
n'importe quel cryptanalyste pourra faire machine arrière sans problèmes.
Il y a 4 éléments de base en crypto:
- le clair
- l'algo
- la clef
- le chiffré
En général, si on a 3 éléments on peut trouver le 4e (pas forcément
aisément, mais en théorie c'est possible). Si l'algo n'utilise pas de clef
(ou une clef fixe ou déterminable par un élément externe), il est clair
qu'on peut déchiffrer le chiffré avec juste l'algo (en supposant bien
entendu que c'est un algo réversible, sinon ce n'est pas du chiffrement
mais un hash). En général l'algo est public, le chiffré l'est aussi, donc
il faut tenir la clef secrète...
Il faut noter que la règle des 3 éléments explique qu'il est très
dangeureux de faire circuler les versions claire et chiffrée d'un même
message: on peut alors finir par trouver la clef.
Jacques.
--
Interactive Media Factory
Création, développement et hébergement
de services interactifs: SMS, SMS+, Audiotel...
http://www.imfeurope.com/
1. J'ai compris ce qu'était un algorithme de hash, du moins dans le principe. Mais j'ai lu parfois qu'à un hash précis ne devait pouvoir correspondre qu'un et un seul fichier. La chose me semble étrange, démonstration du pourquoi.
Ce n'est clairement pas étrange, c'est totalement faux. Un hash a un nombre de valeurs fini, alors que les valeurs "hashées" font partie d'un ensemble infini. Mais: - un fichier donné a un hash unique (pour un algo donné, bien entendu) - avec un hash cryptographique (comme MD5, par exemple), il est très difficile de trouver deux fichiers ayant la même valeur de hash. Il est clair qu'il existe des valeurs de hashs qui sont communes à plusieurs fichiers (voire une infinité), mais trouver une "collision" est très difficile. Voir par exemple http://www.md5crk.com/ pour un tel effort. - avec un hash cryptographique, il est très difficile de retrouver le fichier original à partir du hash.
Deux demandes de précisions : quels sont les conditions nécessaires et suffisantes qui permettent de dire qu'un hash est un bon hash ?
Pour que ce soit un bon hash cryptographique, il faut qu'il respecte au moins les deux conditions données ci-dessus: difficile de trouver une collision, difficile de trouver l'origine. Mais il n'existe généralement pas de preuve absolue, seule l'épreuve du temps permet de voir si personne ne trouve un moyen d'arriver à trouver une collision ou l'original.
3. Quand on fait un algo de cryptage qui fait intervenir une liste de nombres pseudo-aléatoires, le résultat a l'air plutôt bon du point de vue de la sortie (on n'y comprend rien...) mais si l'algo est public, alors n'importe quel cryptanalyste pourra faire machine arrière sans problèmes.
Il y a 4 éléments de base en crypto: - le clair - l'algo - la clef - le chiffré
En général, si on a 3 éléments on peut trouver le 4e (pas forcément aisément, mais en théorie c'est possible). Si l'algo n'utilise pas de clef (ou une clef fixe ou déterminable par un élément externe), il est clair qu'on peut déchiffrer le chiffré avec juste l'algo (en supposant bien entendu que c'est un algo réversible, sinon ce n'est pas du chiffrement mais un hash). En général l'algo est public, le chiffré l'est aussi, donc il faut tenir la clef secrète...
Il faut noter que la règle des 3 éléments explique qu'il est très dangeureux de faire circuler les versions claire et chiffrée d'un même message: on peut alors finir par trouver la clef.
Jacques. -- Interactive Media Factory Création, développement et hébergement de services interactifs: SMS, SMS+, Audiotel... http://www.imfeurope.com/
Horace
... merci, votre réponse est très claire et répond bien à mes questions (rare sur internet !!).
Bien à vous, Christophe
... merci, votre réponse est très claire et répond bien à mes questions
(rare sur internet !!).
... merci, votre réponse est très claire et répond bien à mes questions (rare sur internet !!).
Bien à vous, Christophe
Vincent Schmid
Jacques Caron wrote:
Ce n'est clairement pas étrange, c'est totalement faux. Un hash a un nombre de valeurs fini, alors que les valeurs "hashées" font partie d'un ensemble infini. Mais: - un fichier donné a un hash unique (pour un algo donné, bien entendu) - avec un hash cryptographique (comme MD5, par exemple), il est très difficile de trouver deux fichiers ayant la même valeur de hash.
Bonjour,
Y a-t-il des hashs non "cryptographiques" ? avez-vous quelques noms ?
Vincent
Jacques Caron wrote:
Ce n'est clairement pas étrange, c'est totalement faux. Un hash a un
nombre de valeurs fini, alors que les valeurs "hashées" font partie
d'un ensemble infini. Mais:
- un fichier donné a un hash unique (pour un algo donné, bien entendu)
- avec un hash cryptographique (comme MD5, par exemple), il est très
difficile de trouver deux fichiers ayant la même valeur de hash.
Bonjour,
Y a-t-il des hashs non "cryptographiques" ? avez-vous quelques noms ?
Ce n'est clairement pas étrange, c'est totalement faux. Un hash a un nombre de valeurs fini, alors que les valeurs "hashées" font partie d'un ensemble infini. Mais: - un fichier donné a un hash unique (pour un algo donné, bien entendu) - avec un hash cryptographique (comme MD5, par exemple), il est très difficile de trouver deux fichiers ayant la même valeur de hash.
Bonjour,
Y a-t-il des hashs non "cryptographiques" ? avez-vous quelques noms ?
Vincent
Jacques Caron
On Sat, 07 Aug 2004 22:24:44 +0200, Vincent Schmid wrote:
Y a-t-il des hashs non "cryptographiques" ? avez-vous quelques noms ?
Oui, tout plein. C'est utilisé de façon assez courante en programmation pour limiter le nombre d'enregistrements à parcourir lors d'une recherche. On définit par exemple un hash sur 8 bits, donc pour chaque enregistrement on calcule un hash quelconque (un checksum, par exemple) sur 8 bits, et on stocke l'enregistrement dans une liste chaînée dont le départ est stocké dans un table de 256 entrées. On diminue donc par 256 (statistiquement) le nombre d'entrées à parcourir pour trouver l'enregistrement recherché. Ca se fait aussi bien en mémoire que pour des bases de données. Voir dbm ou postgresql par exemple (même si on utilise plus volontiers des B-Trees et autres arbres qui sont beaucoup plus efficaces).
Jacques. -- Interactive Media Factory Création, développement et hébergement de services interactifs: SMS, SMS+, Audiotel... http://www.imfeurope.com/
On Sat, 07 Aug 2004 22:24:44 +0200, Vincent Schmid <nospam@nospam.com>
wrote:
Y a-t-il des hashs non "cryptographiques" ? avez-vous quelques noms ?
Oui, tout plein. C'est utilisé de façon assez courante en programmation
pour limiter le nombre d'enregistrements à parcourir lors d'une recherche.
On définit par exemple un hash sur 8 bits, donc pour chaque enregistrement
on calcule un hash quelconque (un checksum, par exemple) sur 8 bits, et on
stocke l'enregistrement dans une liste chaînée dont le départ est stocké
dans un table de 256 entrées. On diminue donc par 256 (statistiquement) le
nombre d'entrées à parcourir pour trouver l'enregistrement recherché. Ca
se fait aussi bien en mémoire que pour des bases de données. Voir dbm ou
postgresql par exemple (même si on utilise plus volontiers des B-Trees et
autres arbres qui sont beaucoup plus efficaces).
Jacques.
--
Interactive Media Factory
Création, développement et hébergement
de services interactifs: SMS, SMS+, Audiotel...
http://www.imfeurope.com/
On Sat, 07 Aug 2004 22:24:44 +0200, Vincent Schmid wrote:
Y a-t-il des hashs non "cryptographiques" ? avez-vous quelques noms ?
Oui, tout plein. C'est utilisé de façon assez courante en programmation pour limiter le nombre d'enregistrements à parcourir lors d'une recherche. On définit par exemple un hash sur 8 bits, donc pour chaque enregistrement on calcule un hash quelconque (un checksum, par exemple) sur 8 bits, et on stocke l'enregistrement dans une liste chaînée dont le départ est stocké dans un table de 256 entrées. On diminue donc par 256 (statistiquement) le nombre d'entrées à parcourir pour trouver l'enregistrement recherché. Ca se fait aussi bien en mémoire que pour des bases de données. Voir dbm ou postgresql par exemple (même si on utilise plus volontiers des B-Trees et autres arbres qui sont beaucoup plus efficaces).
Jacques. -- Interactive Media Factory Création, développement et hébergement de services interactifs: SMS, SMS+, Audiotel... http://www.imfeurope.com/
Vincent Schmid
Jacques Caron wrote:
Oui, tout plein. C'est utilisé de façon assez courante en programmation pour limiter le nombre d'enregistrements à parcourir lors d'une recherche. On définit par exemple un hash sur 8 bits, donc pour chaque enregistrement on calcule un hash quelconque (un checksum, par exemple) sur 8 bits, et on stocke l'enregistrement dans une liste chaînée dont le départ est stocké dans un table de 256 entrées. On diminue donc par 256 (statistiquement) le nombre d'entrées à parcourir pour trouver l'enregistrement recherché. Ca se fait aussi bien en mémoire que pour des bases de données. Voir dbm ou postgresql par exemple (même si on utilise plus volontiers des B-Trees et autres arbres qui sont beaucoup plus efficaces).
Merci pour ces précisions! Vincent
Jacques Caron wrote:
Oui, tout plein. C'est utilisé de façon assez courante en programmation
pour limiter le nombre d'enregistrements à parcourir lors d'une
recherche. On définit par exemple un hash sur 8 bits, donc pour chaque
enregistrement on calcule un hash quelconque (un checksum, par exemple)
sur 8 bits, et on stocke l'enregistrement dans une liste chaînée dont
le départ est stocké dans un table de 256 entrées. On diminue donc par
256 (statistiquement) le nombre d'entrées à parcourir pour trouver
l'enregistrement recherché. Ca se fait aussi bien en mémoire que pour
des bases de données. Voir dbm ou postgresql par exemple (même si on
utilise plus volontiers des B-Trees et autres arbres qui sont beaucoup
plus efficaces).
Oui, tout plein. C'est utilisé de façon assez courante en programmation pour limiter le nombre d'enregistrements à parcourir lors d'une recherche. On définit par exemple un hash sur 8 bits, donc pour chaque enregistrement on calcule un hash quelconque (un checksum, par exemple) sur 8 bits, et on stocke l'enregistrement dans une liste chaînée dont le départ est stocké dans un table de 256 entrées. On diminue donc par 256 (statistiquement) le nombre d'entrées à parcourir pour trouver l'enregistrement recherché. Ca se fait aussi bien en mémoire que pour des bases de données. Voir dbm ou postgresql par exemple (même si on utilise plus volontiers des B-Trees et autres arbres qui sont beaucoup plus efficaces).
