IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Fonction de hachage


Sujet :

C

  1. #1
    Candidat au Club
    Inscrit en
    septembre 2002
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : septembre 2002
    Messages : 5
    Points : 2
    Points
    2
    Par défaut [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.

  2. #2
    Membre éclairé
    Avatar de D[r]eadLock
    Profil pro
    Inscrit en
    mai 2002
    Messages
    504
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France

    Informations forums :
    Inscription : mai 2002
    Messages : 504
    Points : 747
    Points
    747
    Par défaut
    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

  3. #3
    gl
    gl est déconnecté
    Rédacteur

    Homme Profil pro
    Inscrit en
    juin 2002
    Messages
    2 165
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Isère (Rhône Alpes)

    Informations forums :
    Inscription : juin 2002
    Messages : 2 165
    Points : 4 605
    Points
    4 605
    Par défaut
    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.

  4. #4
    Candidat au Club
    Inscrit en
    septembre 2002
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : septembre 2002
    Messages : 5
    Points : 2
    Points
    2
    Par défaut
    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!)

    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)

  5. #5
    Membre éclairé
    Avatar de D[r]eadLock
    Profil pro
    Inscrit en
    mai 2002
    Messages
    504
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France

    Informations forums :
    Inscription : mai 2002
    Messages : 504
    Points : 747
    Points
    747
    Par défaut
    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/

  6. #6
    Candidat au Club
    Inscrit en
    septembre 2002
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : septembre 2002
    Messages : 5
    Points : 2
    Points
    2
    Par défaut
    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)

  7. #7
    gl
    gl est déconnecté
    Rédacteur

    Homme Profil pro
    Inscrit en
    juin 2002
    Messages
    2 165
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Isère (Rhône Alpes)

    Informations forums :
    Inscription : juin 2002
    Messages : 2 165
    Points : 4 605
    Points
    4 605
    Par défaut
    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.

  8. #8
    Ol'
    Ol' est déconnecté
    Membre du Club
    Profil pro
    Inscrit en
    mai 2002
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mai 2002
    Messages : 56
    Points : 67
    Points
    67
    Par défaut
    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'

  9. #9
    Membre à l'essai
    Profil pro
    Inscrit en
    mai 2002
    Messages
    19
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : mai 2002
    Messages : 19
    Points : 21
    Points
    21
    Par défaut
    Salut

    un petit code maison
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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&#40;x,y&#41; &#40;&#40;x>>y&#41;|&#40;x<<&#40;8-y&#41;&#41;&#41;
    #define rotr&#40;x,y&#41; &#40;&#40;x<<y&#41;|&#40;x>>&#40;8-y&#41;&#41;&#41;
     
    int main&#40;int argc, char * argv&#91;&#93;&#41;
    &#123;
            unsigned char variable&#91;100&#93;,hash&#91;2&#93;;
            int x,y,len;
     
            memset&#40;hash,0,2&#41;;
            sprintf&#40;variable,"tess"&#41;;
            len = strlen&#40;variable&#41;;
            for&#40;x=0;x<8;x++&#41;
            &#123;
                    for&#40;y=0;y<len-2;y++&#41;
                            hash&#91;0&#93;=&#40;rotl&#40;variable&#91;y&#93;,x&#41;^0x55&#41;^&#40;rotr&#40;variable&#91;y+1&#93;,x&#41;^hash&#91;1&#93;&#41;;
     
                    for&#40;y=len-1;y>0;y--&#41;
                            hash&#91;1&#93;+=&#40;&#40;rotl&#40;variable&#91;y&#93;,x&#41;^0x55&#41;^rotr&#40;variable&#91;y-1&#93;,x&#41;&#41;^hash&#91;0&#93;;
     
            &#125;
     
            printf&#40;"tess -> hash&#91;0&#93; = 0x%02X - hash&#91;1&#93; = 0x%02X\n",hash&#91;0&#93;,hash&#91;1&#93;&#41;;
     
            memset&#40;hash,0,2&#41;;
            sprintf&#40;variable,"test"&#41;;
            len = strlen&#40;variable&#41;;
            for&#40;x=0;x<8;x++&#41;
            &#123;
                    for&#40;y=0;y<len-2;y++&#41;
                             hash&#91;0&#93;=&#40;rotl&#40;variable&#91;y&#93;,x&#41;^0x55&#41;^&#40;rotr&#40;variable&#91;y+1&#93;,x&#41;^hash&#91;0&#93;&#41;;
                    for&#40;y=len-1;y>0;y--&#41;
                            hash&#91;1&#93;+=&#40;&#40;rotl&#40;variable&#91;y&#93;,x&#41;^0x55&#41;^rotr&#40;variable&#91;y-1&#93;,x&#41;&#41;^hash&#91;0&#93;;
            &#125;
     
            printf&#40;"test -> hash&#91;0&#93; = 0x%02X - hash&#91;1&#93; = 0x%02X\n",hash&#91;0&#93;,hash&#91;1&#93;&#41;;
     
            return&#40;0&#41;;
    &#125;
    Resultat :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    tess -> hash[0] = 0x20 - hash[1] = 0xD6
    test -> hash[0] = 0xFF - hash[1] = 0x7F
    Hot Metal

  10. #10
    Membre averti

    Inscrit en
    juin 2002
    Messages
    97
    Détails du profil
    Informations forums :
    Inscription : juin 2002
    Messages : 97
    Points : 300
    Points
    300
    Par défaut
    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 ?
    "J'ai toujours rêvé d'un ordinateur qui soit aussi facile à utiliser qu'un téléphone. Mon rêve s'est réalisé : je ne sais plus comment utiliser mon téléphone."-Bjarne Stroustrup
    www.stroustrup.com

  11. #11
    Candidat au Club
    Inscrit en
    septembre 2002
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : septembre 2002
    Messages : 5
    Points : 2
    Points
    2
    Par défaut
    Merci de votre aide, j'ai trouvé ce qu'il me faut.

  12. #12
    Membre éclairé
    Avatar de D[r]eadLock
    Profil pro
    Inscrit en
    mai 2002
    Messages
    504
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France

    Informations forums :
    Inscription : mai 2002
    Messages : 504
    Points : 747
    Points
    747
    Par défaut
    Citation Envoyé par killer crok
    Merci de votre aide, j'ai trouvé ce qu'il me faut.
    Par curiosite, algo retenu ?

  13. #13
    Candidat au Club
    Inscrit en
    septembre 2002
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : septembre 2002
    Messages : 5
    Points : 2
    Points
    2
    Par défaut
    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.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Appliquer la fonction de hachage MD5 à un texte
    Par 9tita dans le forum Sécurité
    Réponses: 2
    Dernier message: 01/05/2011, 17h13
  2. Recherche d'une fonction de hachage
    Par druzy dans le forum Langage
    Réponses: 13
    Dernier message: 26/11/2007, 22h09
  3. Probleme Fonction de Hachage
    Par 1pedro1 dans le forum C
    Réponses: 6
    Dernier message: 25/11/2007, 18h43
  4. [Oracle / Fonction hachage] Fonction de hachage SHA / MD5
    Par shaun_the_sheep dans le forum Oracle
    Réponses: 8
    Dernier message: 26/01/2006, 09h58
  5. Fonction de Hachage
    Par Schlada dans le forum C
    Réponses: 7
    Dernier message: 26/01/2003, 21h42

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo