Hachage (hashing)
Le hachage est la transformation d'une chaîne de caractères en valeur ou en clé de longueur fixe, généralement plus courte, représentant la chaîne d'origine. Le hachage est notamment employé pour indexer et récupérer les éléments d'une base de données. Il est en effet plus rapide de trouver l'élément d'après la clé de hachage réduite plutôt qu'à l'aide de la valeur d'origine. Cette fonction est également utilisée dans de nombreux algorithmes de chiffrement.
Pour illustrer l'utilisation du hachage, imaginons un groupe de contacts organisés comme suit dans une base de données :
Amblard, Sarah Epadingue, Roger Mourié, Vincent Santi, David (et de nombreux autres triés par ordre alphabétique)
Chacun de ces noms est la clé représentant les données du contact dans la base de données. Un mécanisme de recherche devra tout d'abord rechercher les caractères du nom un à un, jusqu'à trouver la correspondance (ou éliminer les autres entrées). Toutefois, si chaque nom était haché, il serait possible (selon le nombre de noms dans la base de données) de générer une clé unique de quatre chiffres pour chacun d'eux. Par exemple :
7864 Amblard, Sarah 9802 Epadingue, Roger 1990 Mourié, Vincent 8822 Santi, David (et ainsi de suite)
Dans ce cas de figure, la recherche d'un nom implique le calcul de la valeur de hachage (au moyen de la fonction de hachage utilisée pour stocker l'élément), puis la comparaison des éléments afin de trouver une correspondance à l'aide de cette valeur. En règle générale, il est beaucoup plus rapide de rechercher une correspondance sur quatre chiffres - chacun n'offrant que dix possibilités -, plutôt que sur des valeurs de longueur imprévisible, dont chaque caractère aurait 26 possibilités.
L'algorithme utilisé est appelé fonction de hachage (hash), probablement parce que la valeur résultante est en quelque sorte une version « hachée » de la chaîne qu'elle représente.
Chiffrer et déchiffrer la signature numérique
En plus d'accélérer la récupération des données, le hachage permet de chiffrer et déchiffrer les signatures numériques (servant à authentifier les expéditeurs et les destinataires des messages). La signature numérique est transformée au moyen de la fonction de hachage, puis la valeur hachée (appelée empreinte numérique ou condensé de message) et la signature sont envoyées séparément au destinataire. Ce dernier, à l'aide de la même fonction que celle utilisée par l'expéditeur, extrait une empreinte de la signature et la compare à l'empreinte reçue (les deux doivent être identiques).
La fonction de hachage permet d'indexer la valeur d'origine (ou clé) afin de l'utiliser par la suite chaque fois que les données qui y sont associées doivent être extraites. Par conséquent, il s'agit toujours d'une opération à sens unique et il n'est pas nécessaire « d'inverser » la fonction en analysant les valeurs de hachage. Dans l'idéal, il ne devrait d'ailleurs pas être possible de déduire une fonction de hachage au moyen d'une analyse de ce type. En outre, pour être efficace, cette fonction ne doit pas produire une même valeur de hachage pour deux entrées différentes car il y aurait dans ce cas collision. Une fonction de hachage offrant un risque extrêmement faible de collision est considérée comme acceptable.
Voici des exemples de fonctions de hachage relativement simples :
- Transformation par division (ou modulo) : la taille du nombre d'éléments de la table est d'abord estimé. Ce nombre sert ensuite de diviseur pour chaque valeur originale ou clé, de façon à extraire un quotient et un reste. Le reste correspond à la valeur de hachage. Cette méthode étant susceptible de générer plusieurs collisions, les mécanismes de recherche doivent être capables de reconnaître une collision et de proposer un autre mécanisme de recherche.
- Pliage : cette méthode divise la valeur originale (des chiffres dans notre exemple) en plusieurs parties, ajoute ces parties les unes aux autres, puis utilise les quatre derniers chiffres (ou tout autre nombre de chiffres déterminé arbitrairement) comme clé ou valeur de hachage.
- Conversion de base : lorsque la valeur ou la clé est numérique, la base de numération est modifiée de façon à changer la séquence des chiffres. Par exemple, une clé numérique décimale peut passer en numération hexadécimale. Le chiffre de poids fort peut être ignoré afin que la valeur de hachage soit de longueur uniforme.
- Réorganisation des chiffres : cette méthode consiste à inverser simplement l'ordre des chiffres d'une partie de la valeur d'origine ou de la clé, par exemple les chiffres occupant les positions 3 à 6. Cette nouvelle séquence de chiffres représente l'empreinte ou la clé.
Plusieurs fonctions de hachage sont fréquemment utilisées dans le chiffrement. Ainsi, MD2, MD4 et MD5 permettent de « hacher » les signatures numériques en valeurs plus courtes (les empreintes numériques), tandis que le SHA (Secure Hash Algorithm), un algorithme standard semblable au MD4, génère une empreinte plus longue (60 bits). Notons toutefois qu'une fonction de hachage adaptée au stockage et à la récupération des éléments d'une base de données ne conviendra pas nécessairement au chiffrement ou au contrôle d'erreurs.
