Fonction de hachage

Version imprimable

01/10/2002, 14h25
killer crok

[RESOLU] Fonction de hachage

Connaissez vous une fonction de hachage qui prendrait entre 2 et 50 octets en entree et qui resort un mot de 2 octets??

Il est possible que ca n'existe pas, j'ai regarde les standards de fonction de hachage mais elle prenne 512 bits en entree et resorte des trucs sur 128 bits.

Merci.
01/10/2002, 14h41
D[r]eadLock

Je ne connais pas exactement les proprietes des fonctions de hachage, mais je propose: de faire :
. soit additions sur 2 octets (tu decoupe ton mot par tranches de 2 octets (pour le dernier tu mettre une valeur arbitraire tq la repartission soit maximun (donc 0x7F, 128).
. soit xor sur 2 octets toujours (pour le rajout 0xAA me semble bien).

Apres tu fais des tests pour voir les repartitions en fonctions des mots que tu as.

Tu peux peut-etre ameliorer la repartition, en ajoutant des decalages sur les octets (voire sur les paires) pour ameliorer encore la repartition
01/10/2002, 15h14
gl

Ca depends beaucoup de ce que tu souhaite hache! Il faudrait precise r un peu ta question

Mais si tu veux quelque chose qui fonctionne sans etre forcement optimal je te conseille de partir de qqch de simple (une addition ou un XOR comme le suggere D[r]eadLock) et d'affiner ensuite pour resoudre le probleme de colisions trop nombreuses.
01/10/2002, 15h51
killer crok

Je peut pas vraiment preciser ce que c'est, c'est confidenciel, de toute maniere se sont des octets.

En fait je bosse sur de l'embarque, donc il faut que ca aille vite et que ca prenne pas de place (je sais je veux le beurre et l'argent du beurre mais on y arrive!) :D

Par contre le truc de l'addition peut etre pas mal, mais je peut savoir que je vais pas avoir des milliers de collisions?

(cette fonction est assez importante pour la securite de mon truc)
01/10/2002, 16h04
D[r]eadLock

Citation:

Envoyé par killer crok

Par contre le truc de l'addition peut etre pas mal, mais je peut savoir que je vais pas avoir des milliers de collisions?

Tu fais les tests sur des exemples de codes/mots que tu vas avoir a traiter. Et tu regarde ce que ca donne (le nombre de mot par code produit par exemple).

Forme toi pour t'améliorer en lisant des cours et tutoriels pour la programmation C : http://c.developpez.com/cours/
01/10/2002, 16h11
killer crok

Le probleme c'est que mes mots vont de 2 à 50 octets, donc si ils faut que je fasse presque toutes les combinaisons et que je traites les données ca va me prendre un peu de temps pour avoir une fonction optimisé!!

J'ai trouve une fonction toute conne je suis en train de faire des tests, mais si vous avez d'autres propositions...

(la fonction que j'ai, consiste à calculer un modulo avec un nombre premier, pour ceux qui y auraient penser)
01/10/2002, 17h32
gl

Citation:

Envoyé par killer crok

Je peut pas vraiment preciser ce que c'est, c'est confidenciel, de toute maniere se sont des octets.

Je ne voulais pas savoir a quoi correspondais les donnees, mais plutot la repartition de celle ci, si la presence de chaque valeur est equiprobable, n'importe quelle focntion simple (additin, XOR, etc.) donne de bon resultat.
Si certain bit sont plus present que d'autre, il faut trouver autre chose. Et si certains sont toujours a une valeur particuliere, on peut ne pas en tenir compte dans le hachage.
01/10/2002, 17h50
Ol'

Il ne faut pas perdre de vue de le résultat doit être très différent pour deux entrées relativement proches. Alors, les additions, c'est pas top. :?

Ol'

Salut

un petit code maison

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
 
#define rotl(x,y) ((x>>y)|(x<<(8-y)))
#define rotr(x,y) ((x<<y)|(x>>(8-y)))
 
int main(int argc, char * argv[])
{
        unsigned char variable[100],hash[2];
        int x,y,len;
 
        memset(hash,0,2);
        sprintf(variable,"tess");
        len = strlen(variable);
        for(x=0;x<8;x++)
        {
                for(y=0;y<len-2;y++)
                        hash[0]=(rotl(variable[y],x)^0x55)^(rotr(variable[y+1],x)^hash[1]);
 
                for(y=len-1;y>0;y--)
                        hash[1]+=((rotl(variable[y],x)^0x55)^rotr(variable[y-1],x))^hash[0];
 
        }
 
        printf("tess -> hash[0] = 0x%02X - hash[1] = 0x%02X\n",hash[0],hash[1]);
 
        memset(hash,0,2);
        sprintf(variable,"test");
        len = strlen(variable);
        for(x=0;x<8;x++)
        {
                for(y=0;y<len-2;y++)
                         hash[0]=(rotl(variable[y],x)^0x55)^(rotr(variable[y+1],x)^hash[0]);
                for(y=len-1;y>0;y--)
                        hash[1]+=((rotl(variable[y],x)^0x55)^rotr(variable[y-1],x))^hash[0];
        }
 
        printf("test -> hash[0] = 0x%02X - hash[1] = 0x%02X\n",hash[0],hash[1]);
 
        return(0);
}

Resultat :

Code:

1
2
tess -> hash[0] = 0x20 - hash[1] = 0xD6
test -> hash[0] = 0xFF - hash[1] = 0x7F

02/10/2002, 02h31
Musaran

Citation:

Envoyé par Ol'

Il ne faut pas perdre de vue de le résultat doit être très différent pour deux entrées relativement proches.

Pourquoi ?
Tant que c'est différent, c'est bon, non ?
02/10/2002, 08h16
killer crok

Merci de votre aide, j'ai trouvé ce qu'il me faut.
02/10/2002, 09h23
D[r]eadLock

Citation:

Envoyé par killer crok

Merci de votre aide, j'ai trouvé ce qu'il me faut.

Par curiosite, algo retenu ?
02/10/2002, 09h48
killer crok

J'ai fait un mix entre l'algo de Hot metal et la fonction qui consiste à calculer le modulo par un nombre premier sur la chaine à hacher.

Voila merci.