Une fonction de hashage simple en C

Le hashage, qui peut être associé au cryptage est un moyen de rendre illisible des données en leur donnant un "identifiant" unique. A ne pas confondre avec le cryptage qui encode un texte à l'aide d'une ou deux clés permettant de décoder ce texte en réutilisant les clés. Avec le hashage, pas de retour en arrière possible. Une fois le texte hashé, on appelle le résultat l'empreinte.

Mais à quoi ca sert ? Simple, un utilisateur s'enregistre sur un site, celui ci entre son mot de passe, on hash le mot de passe et on le stocke dans la base de donnée. Si la bdd est hackée, le pirate ne peut savoir quel est le vrai mot de passe. Cette méthode est aussi utilisé pour stocker les mots de passe des utilisateurs sur les systèmes conforme POSIX (donc UNIX, Linux, etc...).

Il y a de puissant algoritmes de hashage dont le taux de collision (collision = deux données différentes avec la même empreinte) est quasi-nul tel que le MD5 ou le SHA1. Cependant ils restent assez difficiles implémenter dans un programme en C à cause de la complexité de l'algoritme.

Je vais vous présenter une fonction de hashage découverte sur Wikipédia, je cite "Voici l'une des fonctions de hachage les plus puissantes écrite par Daniel J. Bernstein (en langage C)", je l'ai trouvé extrêmement simple, si bien que j'ai quelque doute sur son taux de collision :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

unsigned long hash (unsigned char *str)
{
    unsigned long hash = 5381;
    while (*str != 0)
    {
        int c = *str;
        /* hash = hash * 33 + c */
        hash = ((hash << 5) + hash) + c;
        str++;
    }
    return hash;
}

On en déduit donc que la complexité de l'algoritme est en O(n) (ce qui signifie que selon la taille n de la chaine, l'algoritme va durer plus ou moins longtemps). Cette fonction reste bien pratique si dans un logiciel vous avez besoin d'une table de hashage (un tableau ou on accède à ses éléments via leurs empreinte, un algoritme de complexité O(1) donc). Fonction bien rapide, assez simple et pas trop longue.

Enjoy :D