Fonction de hashage

Nicolas George

05/01/2006 à 11:20

Yves Martin wrote in message :

Je cherche une fonction de hachage - au mieux celle utilisée pour manipuler
les 'hash'. Quelle est-elle ?

Celle utilisée par perl pour ses tabes associative n'est pas documentée, il
me semble, et peut changer d'une version à l'autre.

Quel est ton objectif ?

FDA

05/01/2006 à 11:45

Bonjour,

Je cherche une fonction de hachage - au mieux celle utilisée pour manipuler
les 'hash'. Quelle est-elle ?

Celle-là, Larry Wall a exprimé son regret de ne pas l'avoir brevetée. Et
en effet son idée est très bonne :

Imaginons un hashing sur 8 bits : ça conviendra très bien pour un hash
de, disons, 100 éléments. Au-delà, si le hash s'étend, mieux vaudra
avoir, disons 32; puis d'il s'étend au-delà de 10 000 éléments,
peut-être passer à 64.

L'idée de Larry Wall a été de prendre un algorithme de hashing qui ne
demande pas un recalcul intégral des clés de hashs existantes, mais se
contente de leur faire subir un décalage. Je ne me rappelle plus si ça
marche par bit, par octet ou par mot, mais il en parle dans une
interview, et le code source des Perl v5 est disponible. En fouillant
bien, ça doit pouvoir donc se trouver.

Yves Martin

05/01/2006 à 14:01

Nicolas George <nicolas$ writes:

Yves Martin wrote in message :
Je cherche une fonction de hachage - au mieux celle utilisée pour manipuler
les 'hash'. Quelle est-elle ?

Celle utilisée par perl pour ses tabes associative n'est pas documentée, il
me semble, et peut changer d'une version à l'autre.

Quel est ton objectif ?

J'ai juste besoin d'une fonction de hachage pour faire dépendre un nombre
(dans un OID d'arbre SNMP) d'un script listé dans un répertoire.

L'objectif est de ne pas perdre la numérotation existante des scripts
présents dans le répertoire, lors d'une nouvelle génération après l'ajout
d'un nouveau script...

Première génération du snmpd.conf:
/scripts/a.sh -> .1.3. ..... .324234
/scripts/b.sh -> .1.3. ..... .769806

Deuxième génération du snmpd.conf:
/scripts/a.sh -> .1.3. ..... .324234
/scripts/ancien.sh -> .1.3. ..... .560798
/scripts/b.sh -> .1.3. ..... .769806

Le tri alphabétique des scripts n'est pas une solution, d'où mon espoir dans
une fonction de hachage, quelle qu'elle soit.

Merci d'avance
--
Yves Martin

Nicolas George

05/01/2006 à 23:57

Yves Martin wrote in message :

J'ai juste besoin d'une fonction de hachage pour faire dépendre un nombre
(dans un OID d'arbre SNMP) d'un script listé dans un répertoire.

C'est un peu un marteau-piqueur pour ouvrir une noix, mais tu peux utiliser
une vraie fonction de hashage cryptographique pour ce genre de choses.
Typiquement, Digest::MD5 (inclus dans la distribution standard de perl, mais
on sait produire des collisions) ou Digest::SHA (distribué séparément, mais
des fonctions plus solides).

FDA

06/01/2006 à 00:08

Yves Martin wrote in message :

J'ai juste besoin d'une fonction de hachage pour faire dépendre un nombre
(dans un OID d'arbre SNMP) d'un script listé dans un répertoire.

C'est un peu un marteau-piqueur pour ouvrir une noix, mais tu peux utiliser
une vraie fonction de hashage cryptographique pour ce genre de choses.
Typiquement, Digest::MD5 (inclus dans la distribution standard de perl, mais
on sait produire des collisions)

On sait même davantage que produire des collisions : j'ai vu deux pages
web parfaitement correctes à l'affichage sans rapport l'une avec
l'autre, et qui avaient la même signature MD5. On doit d'ailleurs
pouvoir les trouver sur le Net.

C'est fondé sur une propriété mathématique assez simple du MD5, mais je
ne me souviens plus de laquelle hormis qu'il y avait une addition dedans.

Nicolas George

06/01/2006 à 00:22

FDA wrote in message
<43bda6b7$0$18027$:

C'est fondé sur une propriété mathématique assez simple du MD5, mais je
ne me souviens plus de laquelle hormis qu'il y avait une addition dedans.

C'est basé sur la propriété que si A et B ont le même MD5 (et la même
longueur, peut-être, alors ajouter C à la fin donne AC et BC qui ont le même
MD5. Ça veut dire que si on peut produire une collision dont les deux termes
commencent par <!--, on peut produire des fichiers HTML différents dont le
début qui produit la collision sera identique.

Yves Martin

06/01/2006 à 13:08

Nicolas George <nicolas$ writes:

FDA wrote in message
<43bda6b7$0$18027$:
C'est fondé sur une propriété mathématique assez simple du MD5, mais je
ne me souviens plus de laquelle hormis qu'il y avait une addition dedans.

C'est basé sur la propriété que si A et B ont le même MD5 (et la même
longueur, peut-être, alors ajouter C à la fin donne AC et BC qui ont le même
MD5. Ça veut dire que si on peut produire une collision dont les deux termes
commencent par <!--, on peut produire des fichiers HTML différents dont le
début qui produit la collision sera identique.

Merci pour les informations
--
Yves Martin

jl_morel

06/01/2006 à 13:42

Dans l'article , a dit...

Je cherche une fonction de hachage - au mieux celle utilisée pour manipuler
les 'hash'. Quelle est-elle ?

La fonction de hachage utilisée par Perl est implémentée sous forme d'un
macro (voir dans votre distribution le fichier perl/lib/CORE/hv.h)

* Pour Perl 5.6 c'est assez simple :

/* hash a key */
#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh = str;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = 0;
while (i_PeRlHaSh--)
hash_PeRlHaSh = hash_PeRlHaSh * 33 + *s_PeRlHaSh++;
(hash) = hash_PeRlHaSh + (hash_PeRlHaSh>>5);
} STMT_END

Traduit en Perl, ça donne la fonction :

sub hash56 {
use Math::BigInt;
my $s = shift;
my $h = Math::BigInt->new('0');
foreach my $c (unpack("c*", $s)) {
$h = ($h * 33 + $c) % 2**32;
}
return ($h + ($h >> 5)) % 2**32;
}

(J'utilise Math::BigInt et des modulo 2**32 car avec 'use integer;' les
entiers son signés. Les caractères sont signés pour mon compilateur favori
MSVC6, d'où le "c*" dans le unpack.)

* Pour perl 5.8 c'est plus compliqué
("One-at-a-Time Hash" voir http://burtleburtle.net/bob/hash/doobs.html
d'après les commentaires)

#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh_tmp = str;
register const unsigned char *s_PeRlHaSh = (const unsigned char *)
s_PeRlHaSh_tmp;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = PERL_HASH_SEED;
while (i_PeRlHaSh--) {
hash_PeRlHaSh += *s_PeRlHaSh++;
hash_PeRlHaSh += (hash_PeRlHaSh << 10);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6);
}
hash_PeRlHaSh += (hash_PeRlHaSh << 3);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11);
(hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15));
} STMT_END

En Perl, ça peut se traduire par

sub hash58 {
use Math::BigInt;
my $s = shift;
my $h = Math::BigInt->new('0'); # PERL_HASH_SEED =0
foreach my $c (unpack("c*", $s)) {
$h += $c;
$h += ($h << 10);
$h %= 2**32;
$h ^= ($h >> 6);
}
$h += ($h << 3);
$h %= 2**32;
$h ^= ($h >>11);
return ($h +($h<<15)) % 2**32;
}

J'ai testé ces deux fonctions; elles donnent les mêmes résultats que leurs
équivalents en C.

HTH

--
J-L.M.
http://www.bribes.org/perl

Dans l'article <f64q4jhx4r.fsf@pcyma.elca.ch>, ymartin@nospam.fr a dit...

Je cherche une fonction de hachage - au mieux celle utilisée pour manipuler
les 'hash'. Quelle est-elle ?

La fonction de hachage utilisée par Perl est implémentée sous forme d'un
macro (voir dans votre distribution le fichier perl/lib/CORE/hv.h)

* Pour Perl 5.6 c'est assez simple :

/* hash a key */
#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh = str;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = 0;
while (i_PeRlHaSh--)
hash_PeRlHaSh = hash_PeRlHaSh * 33 + *s_PeRlHaSh++;
(hash) = hash_PeRlHaSh + (hash_PeRlHaSh>>5);
} STMT_END

Traduit en Perl, ça donne la fonction :

sub hash56 {
use Math::BigInt;
my $s = shift;
my $h = Math::BigInt->new('0');
foreach my $c (unpack("c*", $s)) {
$h = ($h * 33 + $c) % 2**32;
}
return ($h + ($h >> 5)) % 2**32;
}

(J'utilise Math::BigInt et des modulo 2**32 car avec 'use integer;' les
entiers son signés. Les caractères sont signés pour mon compilateur favori
MSVC6, d'où le "c*" dans le unpack.)

* Pour perl 5.8 c'est plus compliqué
("One-at-a-Time Hash" voir http://burtleburtle.net/bob/hash/doobs.html
d'après les commentaires)

#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh_tmp = str;
register const unsigned char *s_PeRlHaSh = (const unsigned char *)
s_PeRlHaSh_tmp;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = PERL_HASH_SEED;
while (i_PeRlHaSh--) {
hash_PeRlHaSh += *s_PeRlHaSh++;
hash_PeRlHaSh += (hash_PeRlHaSh << 10);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6);
}
hash_PeRlHaSh += (hash_PeRlHaSh << 3);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11);
(hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15));
} STMT_END

En Perl, ça peut se traduire par

sub hash58 {
use Math::BigInt;
my $s = shift;
my $h = Math::BigInt->new('0'); # PERL_HASH_SEED =0
foreach my $c (unpack("c*", $s)) {
$h += $c;
$h += ($h << 10);
$h %= 2**32;
$h ^= ($h >> 6);
}
$h += ($h << 3);
$h %= 2**32;
$h ^= ($h >>11);
return ($h +($h<<15)) % 2**32;
}

J'ai testé ces deux fonctions; elles donnent les mêmes résultats que leurs
équivalents en C.

HTH

--
J-L.M.
http://www.bribes.org/perl

Vous avez filtré cet utilisateur ! Consultez son message

Dans l'article , a dit...

Je cherche une fonction de hachage - au mieux celle utilisée pour manipuler
les 'hash'. Quelle est-elle ?

La fonction de hachage utilisée par Perl est implémentée sous forme d'un
macro (voir dans votre distribution le fichier perl/lib/CORE/hv.h)

* Pour Perl 5.6 c'est assez simple :

/* hash a key */
#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh = str;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = 0;
while (i_PeRlHaSh--)
hash_PeRlHaSh = hash_PeRlHaSh * 33 + *s_PeRlHaSh++;
(hash) = hash_PeRlHaSh + (hash_PeRlHaSh>>5);
} STMT_END

Traduit en Perl, ça donne la fonction :

sub hash56 {
use Math::BigInt;
my $s = shift;
my $h = Math::BigInt->new('0');
foreach my $c (unpack("c*", $s)) {
$h = ($h * 33 + $c) % 2**32;
}
return ($h + ($h >> 5)) % 2**32;
}

(J'utilise Math::BigInt et des modulo 2**32 car avec 'use integer;' les
entiers son signés. Les caractères sont signés pour mon compilateur favori
MSVC6, d'où le "c*" dans le unpack.)

* Pour perl 5.8 c'est plus compliqué
("One-at-a-Time Hash" voir http://burtleburtle.net/bob/hash/doobs.html
d'après les commentaires)

#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh_tmp = str;
register const unsigned char *s_PeRlHaSh = (const unsigned char *)
s_PeRlHaSh_tmp;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = PERL_HASH_SEED;
while (i_PeRlHaSh--) {
hash_PeRlHaSh += *s_PeRlHaSh++;
hash_PeRlHaSh += (hash_PeRlHaSh << 10);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6);
}
hash_PeRlHaSh += (hash_PeRlHaSh << 3);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11);
(hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15));
} STMT_END

En Perl, ça peut se traduire par

sub hash58 {
use Math::BigInt;
my $s = shift;
my $h = Math::BigInt->new('0'); # PERL_HASH_SEED =0
foreach my $c (unpack("c*", $s)) {
$h += $c;
$h += ($h << 10);
$h %= 2**32;
$h ^= ($h >> 6);
}
$h += ($h << 3);
$h %= 2**32;
$h ^= ($h >>11);
return ($h +($h<<15)) % 2**32;
}

J'ai testé ces deux fonctions; elles donnent les mêmes résultats que leurs
équivalents en C.

HTH

--
J-L.M.
http://www.bribes.org/perl

Loïc Restoux

08/01/2006 à 11:41

Le 05 jan, à 22:57, Nicolas George papotait :

J'ai juste besoin d'une fonction de hachage pour faire
dépendre un nombre (dans un OID d'arbre SNMP) d'un script
listé dans un répertoire.

C'est un peu un marteau-piqueur pour ouvrir une noix, mais tu
peux utiliser une vraie fonction de hashage cryptographique
pour ce genre de choses. Typiquement, Digest::MD5 (inclus dans
la distribution standard de perl, mais on sait produire des
collisions) ou Digest::SHA (distribué séparément, mais des
fonctions plus solides).

Toute fonction de hachage produit des collisions. Le tout est que
ces collisions soient le moins pénalisant possible pour les
performances du hachage.

--
No fortunes found

Nicolas George

08/01/2006 à 18:02

Loïc Restoux wrote in message
:

Toute fonction de hachage produit des collisions.

Oui, évidemment. Mais il y en a où on sait produire des collisions presque à
volonté, avec des contraintes plus ou moins fortes, et il y en a où on ne
connaît aucun exemple de collision. MD5 est dnas le premier cas, SHA1 dans
le second pour le moment.

Fonction de hashage

10 réponses

Veuillez sélectionner un problème