Algorithmes de hachage de données. Fonctions de hachage cryptographique

Dans cet article, je vais vous dire qu'est-ce que le hachage, pourquoi il est nécessaire, où et comment il est utilisé, ainsi que les exemples les plus célèbres.

De nombreuses tâches dans le domaine des technologies de l'information sont très critiques pour les volumes de données. Par exemple, si vous devez comparer deux fichiers de 1 Ko et deux fichiers de 10 Go, alors c'est un moment complètement différent. Par conséquent, les algorithmes qui vous permettent d'opérer avec des valeurs plus courtes et plus volumineuses sont considérés comme très demandés.

L'une de ces technologies est le hachage, qui a trouvé son application pour résoudre de nombreux problèmes. Mais je pense que vous, en tant qu'utilisateur ordinaire, ne comprenez toujours pas de quel type d'animal il s'agit et à quoi il sert. Par conséquent, je vais essayer de tout expliquer avec les mots les plus simples.

Note: Le matériel est conçu pour les utilisateurs ordinaires et ne contient pas beaucoup d'aspects techniques, mais il est plus que suffisant pour une familiarisation de base.

Qu'est-ce que le hachage ou le hachage ?

Je vais commencer par les termes.

Fonction de hachage, fonction de convolution- il s'agit d'un type spécial de fonction qui vous permet de convertir des textes de longueur arbitraire en un code de longueur fixe (généralement une courte notation alphanumérique).

Hachage- c'est le processus de conversion des textes sources.

Hachage, code de hachage, valeur de hachage, somme de hachage est la valeur de sortie de la fonction de hachage, c'est-à-dire que le bloc résultant est d'une longueur fixe.

Comme vous pouvez le constater, les termes ont une description quelque peu figurative, à partir de laquelle il est difficile de comprendre pourquoi tout cela est nécessaire. Je vais donc donner immédiatement un petit exemple (je vous parlerai d'autres applications un peu plus tard). Disons que vous disposez de 2 fichiers de 10 Go. Comment savoir rapidement lequel a raison ? Vous pouvez utiliser le nom du fichier, mais il est facile de le renommer. Vous pouvez afficher les dates, mais après avoir copié les fichiers, les dates peuvent être identiques ou dans un ordre différent. La taille, comme vous le comprenez, ne peut pas beaucoup aider (surtout si les tailles sont les mêmes ou si vous n’avez pas regardé les valeurs exactes des octets).

C'est là que ce hachage est nécessaire, qui est un court bloc formé à partir du texte source du fichier. Ces deux fichiers de 10 Go auront deux codes de hachage différents mais courts (quelque chose comme « ACCAC43535 » et « BBB3232A42 »). En les utilisant, vous pouvez trouver rapidement le fichier souhaité, même après avoir copié et modifié les noms.

Note: Etant donné que le Hash est un concept très connu dans le monde informatique et sur Internet, souvent tout ce qui concerne le Hash est abrégé par ce même mot. Par exemple, l'expression « J'utilise le hachage MD5 », une fois traduite, signifie que le site Web ou ailleurs utilise l'algorithme de hachage standard MD5.

Propriétés des fonctions de hachage

Maintenant, je vais vous parler des propriétés des fonctions de hachage pour vous permettre de comprendre plus facilement où le hachage est utilisé et pourquoi il est nécessaire. Mais d’abord, encore une définition.

Collision- il s'agit d'une situation où la même somme de hachage est obtenue pour deux textes différents. Comme vous l'avez compris, puisqu'un bloc est d'une longueur fixe, il a un nombre limité de valeurs possibles, et donc des répétitions sont possibles.

Et maintenant les propriétés des fonctions de hachage elles-mêmes :

1. Un texte de n'importe quelle taille peut être saisi et la sortie est un bloc de données d'une longueur fixe. Cela découle de la définition.

2. La somme de hachage des mêmes textes doit être la même. Sinon, de telles fonctions sont tout simplement inutiles - c'est comme un nombre aléatoire.

3. Une bonne fonction de convolution doit avoir une bonne distribution. Convenez que si la taille du hachage de sortie est, par exemple, de 16 octets, alors si la fonction ne renvoie que 3 valeurs différentes pour des textes, alors une telle fonction et ces 16 octets ne sont d'aucune utilité (16 octets valent 2 ^ 128 options, ce qui équivaut approximativement à 3, 4 * 10 ^ 38 degrés).

4. Dans quelle mesure la fonction réagit aux moindres changements dans le texte source. Un exemple simple. Nous avons modifié 1 lettre dans un fichier de 10 Go, la valeur de la fonction devrait devenir différente. Si ce n'est pas le cas, l'utilisation d'une telle fonction est très problématique.

5. Probabilité d'une collision. Un paramètre très complexe calculé sous certaines conditions. Mais l’essentiel est de savoir à quoi sert une fonction de hachage si la somme de hachage résultante coïncide souvent.

6. Vitesse de calcul du hachage. À quoi sert une fonction de convolution si son calcul prend beaucoup de temps ? Aucun, car il est alors plus facile de comparer les données des fichiers ou d’utiliser une approche différente.

7. Difficulté à restaurer les données originales à partir de la valeur de hachage. Cette caractéristique est plus spécifique que générale, puisqu’elle n’est pas exigée partout. Cependant, pour les algorithmes les plus connus, cette caractéristique est estimée. Par exemple, il est peu probable que vous puissiez obtenir le fichier source à partir de cette fonction. Cependant, s'il y a un problème de collision (par exemple, vous devez trouver un texte correspondant à un tel hachage), alors une telle caractéristique peut être importante. Par exemple, les mots de passe, mais nous y reviendrons plus tard.

8. Le code source d'une telle fonction est ouvert ou fermé. Si le code n’est pas ouvert, la complexité de la récupération des données, à savoir la force cryptographique, reste remise en question. Il s’agit en partie d’un problème de cryptage.

Nous pouvons maintenant passer à la question « à quoi ça sert ? »

Pourquoi le hachage est-il nécessaire ?

Les fonctions de hachage n'ont que trois objectifs principaux (ou plutôt leurs objectifs).

1. Contrôle de l'intégrité des données. Dans ce cas, tout est simple, une telle fonction doit être calculée rapidement et permettre également de vérifier rapidement que, par exemple, un fichier téléchargé sur Internet n'a pas été endommagé lors de la transmission.

2. Augmentation de la vitesse de récupération des données. Une taille de bloc fixe vous permet d'obtenir de nombreux avantages pour résoudre les problèmes de recherche. Dans ce cas, nous parlons du fait que, d'un point de vue purement technique, l'utilisation de fonctions de hachage peut avoir un effet positif sur les performances. Pour de telles fonctions, la probabilité de collision et une bonne distribution sont très importantes.

3. Pour les besoins cryptographiques. Ce type de fonction de convolution est utilisé dans les domaines de sécurité où il est important que les résultats soient difficiles à remplacer ou où il est nécessaire de rendre aussi difficile que possible la tâche d'obtention d'informations utiles à partir du Hash.

Où et comment le hash est-il utilisé ?

Comme vous l’avez probablement déjà deviné, le hachage est utilisé pour résoudre de nombreux problèmes. En voici quelques-uns :

1. Les mots de passe ne sont généralement pas stockés en texte clair, mais sous forme de sommes de hachage, ce qui permet un degré de sécurité plus élevé. Après tout, même si un attaquant accède à une telle base de données, il lui faudra quand même beaucoup de temps pour trouver les textes correspondants à ces Hash Codes. C’est là que la caractéristique « difficulté à restaurer les données originales à partir des valeurs de hachage » est importante.

Note: Je vous conseille de lire l'article : quelques conseils pour augmenter le niveau de sécurité des mots de passe.

2. En programmation, y compris les bases de données. Bien entendu, nous parlons le plus souvent de structures de données permettant des recherches rapides. Aspect purement technique.

3. Lors de la transmission de données sur un réseau (y compris Internet). De nombreux protocoles, tels que TCP/IP, incluent des champs de contrôle spéciaux contenant la somme de hachage du message d'origine, de sorte que s'il y a un échec quelque part, cela n'affectera pas le transfert de données.

4. Pour divers algorithmes liés à la sécurité. Par exemple, le hachage est utilisé dans les signatures numériques électroniques.

5. Pour vérifier l'intégrité des fichiers. Si vous y avez prêté attention, vous pouvez souvent trouver sur Internet des descriptions supplémentaires avec un code de hachage pour les fichiers (par exemple, les archives). Cette mesure est utilisée non seulement pour garantir que vous ne lancez pas accidentellement un fichier endommagé lors du téléchargement depuis Internet, mais également pour éviter de simples pannes d'hébergement. Dans de tels cas, vous pouvez rapidement vérifier le hachage et, si nécessaire, télécharger à nouveau le fichier.

6. Parfois, les fonctions de hachage sont utilisées pour créer des identifiants uniques (dans le cadre de). Par exemple, lors de l'enregistrement d'images ou simplement de fichiers, ils utilisent généralement un hachage dans les noms ainsi que la date et l'heure. Cela vous permet d'éviter d'écraser des fichiers portant les mêmes noms.

En fait, plus les fonctions de hachage sont utilisées dans les technologies de l'information. Principalement dû au fait que le volume de données et la puissance des ordinateurs les plus simples ont considérablement augmenté. Dans le premier cas, nous parlons davantage de recherche, et dans le second, nous parlons davantage de problèmes de sécurité.

Fonctions de hachage célèbres

Les trois fonctions de hachage suivantes sont considérées comme les plus connues.

Annotation: Cette conférence formule le concept de fonction de hachage et fournit également un bref aperçu des algorithmes de génération de fonctions de hachage. De plus, la possibilité d'utiliser des algorithmes de chiffrement par blocs pour générer une fonction de hachage est envisagée.

Le but du cours : se familiariser avec le concept de fonction de hachage, ainsi que les principes de fonctionnement de telles fonctions.

Le concept de fonction de hachage

Fonction de hachage est une fonction mathématique ou autre qui, pour une chaîne de longueur arbitraire, calcule une valeur entière ou une autre chaîne de longueur fixe. Mathématiquement, cela peut s'écrire ainsi :

où M est le message original, parfois appelé prototype, et h est le résultat, appelé valeur de hachage (et aussi code de hachage ou résumé du message(de l'anglais résumé du message)).

La signification de la fonction de hachage est de déterminer la caractéristique de la pré-image - la valeur de la fonction de hachage. Cette valeur a généralement une taille fixe, telle que 64 ou 128 bits. Le code de hachage peut être analysé plus en détail pour résoudre tout problème. Par exemple, le hachage peut être utilisé pour comparer des données : si deux tableaux de données ont des codes de hachage différents, les tableaux sont garantis différents ; s'ils sont identiques, les tableaux sont probablement les mêmes. En général, il n'y a pas de correspondance biunivoque entre les données source et le code de hachage car le nombre de valeurs de la fonction de hachage est toujours inférieur au nombre d'options de données d'entrée. Par conséquent, il existe de nombreux messages d'entrée qui donnent les mêmes codes de hachage (de telles situations sont appelées collisions). La probabilité de collisions joue un rôle important dans l'évaluation de la qualité des fonctions de hachage.

Les fonctions de hachage sont largement utilisées dans la cryptographie moderne.

La fonction de hachage la plus simple peut être construite en utilisant l'opération « somme modulo 2 » comme suit : nous obtenons la chaîne d'entrée, ajoutons tous les octets modulo 2 et renvoyons l'octet résultat comme valeur de hachage. Dans ce cas, la longueur de la valeur de la fonction de hachage sera de 8 bits, quelle que soit la taille du message d'entrée.

Par exemple, disons que le message original, traduit sous forme numérique, était le suivant (en hexadécimal) :

Convertissons le message sous forme binaire, écrivons les octets les uns en dessous des autres et ajoutons les bits dans chaque colonne modulo 2 :

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Le résultat (0110 0101 (2) ou 65 (16)) sera la valeur de hachage.

Cependant, une telle fonction de hachage ne peut pas être utilisée à des fins cryptographiques, telles que la génération d'une signature électronique, car il est assez simple de modifier le contenu du message signé sans modifier la valeur de la somme de contrôle.

Par conséquent, la fonction de hachage considérée n’est pas adaptée aux applications cryptographiques. En cryptographie, une fonction de hachage est considérée comme bonne s'il est difficile de créer deux pré-images avec la même valeur de hachage, et également si la sortie de la fonction ne dépend pas explicitement de l'entrée.

Formulons les exigences de base pour les fonctions de hachage cryptographique :

• la fonction de hachage doit être applicable à un message de n'importe quelle taille ;
• le calcul de la valeur de la fonction doit être effectué assez rapidement ;
• Étant donné une valeur de fonction de hachage connue, il devrait être difficile (pratiquement impossible) de trouver une image inverse appropriée de M ;
• étant donné un message M connu, il devrait être difficile de trouver un autre message M' avec la même valeur de hachage que le message d'origine ;
• il devrait être difficile de trouver une paire de messages distincts de manière aléatoire avec la même valeur de hachage.

Créer une fonction de hachage qui répond à toutes les exigences ci-dessus n'est pas une tâche facile. Il est également nécessaire de se rappeler que l'entrée de la fonction reçoit des données de taille arbitraire et que le résultat du hachage ne doit pas être le même pour des données de tailles différentes.

Actuellement, en pratique, les fonctions qui traitent le message d'entrée bloc par bloc et calculent la valeur de hachage h i pour chaque bloc M i du message d'entrée en fonction des dépendances de la forme sont utilisées comme fonctions de hachage.

h je = H (M je , h je-1),

où h i-1 est le résultat obtenu lors du calcul de la fonction de hachage pour le bloc précédent de données d'entrée.

En conséquence, la sortie de la fonction de hachage h n est fonction de l'ensemble des n blocs du message d'entrée.

Utiliser des algorithmes de chiffrement par blocs pour générer une fonction de hachage

Vous pouvez utiliser une fonction de hachage de bloc comme fonction de hachage. Si l’algorithme de bloc utilisé est cryptographiquement fort, alors la fonction de hachage qui en découle sera sécurisée.

La manière la plus simple d’utiliser un algorithme de bloc pour obtenir un code de hachage est de chiffrer le message en mode CBC. Dans ce cas, le message est représenté comme une séquence de blocs dont la longueur est égale à la longueur du bloc de l'algorithme de chiffrement. Si nécessaire, le dernier bloc est complété à droite par des zéros pour créer un bloc de la longueur requise. La valeur de hachage sera le dernier bloc de texte crypté. À condition qu'un algorithme de chiffrement par bloc puissant soit utilisé, la valeur de hachage résultante aura les propriétés suivantes :

• Il est presque impossible de calculer une valeur de hachage pour un ensemble ouvert d'informations donné sans connaître la clé de cryptage ;
• Sans connaître la clé de cryptage, il est presque impossible de sélectionner des données ouvertes pour une valeur de fonction de hachage donnée.

La valeur de hachage ainsi générée est généralement appelée insertion d'imitations ou authentificateur et est utilisé pour vérifier l'intégrité du message. Ainsi, l'insert imitatif est une combinaison de contrôle qui dépend de données ouvertes et d'informations de clé secrète. Le but de l’insertion imitative est de détecter tous les changements accidentels ou intentionnels dans le tableau d’informations. La valeur obtenue par la fonction de hachage lors du traitement du message d'entrée est ajoutée au message au moment où le message est connu comme étant correct. Le destinataire vérifie l'intégrité du message en calculant le message imité du message reçu et en le comparant au code de hachage reçu, qui doit être transmis de manière sécurisée. L’une de ces méthodes sécurisées pourrait consister à chiffrer l’insert imitatif avec la clé privée de l’expéditeur, c’est-à-dire créer une signature. Il est également possible de chiffrer le code de hachage obtenu avec un algorithme de chiffrement symétrique si l'expéditeur et le destinataire disposent d'une clé de chiffrement symétrique commune.

Le processus spécifié d'obtention et d'utilisation d'inserts d'imitation est décrit dans la norme nationale GOST 28147-89. La norme propose d'utiliser les 32 bits de poids faible du bloc obtenu à la sortie de l'ensemble de l'opération de chiffrement du message en mode chaînage de blocs de chiffrement pour contrôler l'intégrité du message transmis. De la même manière, vous pouvez utiliser n’importe quel bloc pour former un insert simulé. algorithme de chiffrement symétrique.

Une autre façon possible d’utiliser un chiffrement par bloc pour générer un code de hachage est la suivante. Le message d'origine est traité séquentiellement par blocs. Le dernier bloc est complété par des zéros si nécessaire ; parfois la longueur du message sous la forme d'un nombre binaire est ajoutée au dernier bloc. À chaque étape, nous chiffrons la valeur de hachage obtenue à l'étape précédente, en utilisant le bloc de message actuel comme clé. La dernière valeur cryptée reçue sera le résultat final du hachage.

En fait, il existe plusieurs autres schémas possibles pour utiliser un chiffrement par bloc pour générer une fonction de hachage. Soit M i le bloc du message d'origine, h i la valeur de la fonction de hachage à la i-ème étape, f l'algorithme de chiffrement par blocs utilisé dans le mode de remplacement simple, et soit l'opération d'addition modulo 2. Alors , par exemple, les schémas suivants pour générer une fonction de hachage sont possibles :

Dans tous ces schémas, la longueur de la valeur de hachage générée est égale à la longueur du bloc de chiffrement. Tous ces éléments, ainsi que d'autres schémas permettant d'utiliser un algorithme de chiffrement par blocs pour calculer les valeurs de hachage, peuvent être utilisés dans la pratique.

Le principal inconvénient des fonctions de hachage conçues sur la base d’algorithmes de blocs est la vitesse de fonctionnement relativement faible. La force cryptographique requise peut être obtenue avec moins d'opérations sur les données d'entrée. Il existe des algorithmes de hachage plus rapides, conçus indépendamment, à partir de zéro, sur la base d'exigences de force cryptographique (les plus courants d'entre eux sont MD5, SHA-1, SHA-2 et GOST R 34.11-94).

Le hachage est une méthode spéciale d'adressage des données (un algorithme d'arrangement) par leurs clés uniques ( clé ) pour trouver rapidement les informations dont vous avez besoin.

Concepts de base

Table de hachage

Une table de hachage est un tableau régulier avec un adressage spécial spécifié par une fonction (fonction de hachage).

Fonction de hachage

Une fonction qui mappe la clé d'un élément de données à un index dans une table ( table de hachage), appelé fonction de hachage ou fonction de hachage :

je = h (clé );

Où clé- clé convertible, je- l'index de la table résultant, c'est-à-dire la clé est affichée dans un ensemble, par exemple, d'entiers ( adresses de hachage ), qui sont ensuite utilisés pour accéder aux données.

Le hachage de cette manière est une technique qui consiste à utiliser la valeur d'une clé pour déterminer sa position dans une table spéciale.

Cependant, la fonction d'arrangement peut plusieurs les valeurs clés uniques donnent la même valeur de position je dans la table de hachage. Une situation dans laquelle deux clés ou plus partagent le même index (adresse de hachage) est appelée collision (conflit) lors du hachage. Par conséquent, le schéma de hachage doit inclure. algorithme de résolution de conflits , qui détermine l'ordre des actions si la position je=h(clé) s'avère être déjà occupé par un enregistrement avec une clé différente.

Il existe de nombreux schémas de hachage, en fonction de la fonction de hachage utilisée. h(clé) et des algorithmes de résolution de conflits.

La méthode la plus courante pour spécifier une fonction de hachage est : Méthode de division.

Les données initiales sont : - une clé entière clé et taille du tableau m. Le résultat de cette fonction est le reste lorsque cette clé est divisée par la taille du tableau. La vue générale d’une telle fonction dans le langage de programmation C/C++ est la suivante :

int h (int clé , int m ) {

Pour m= 10 La fonction de hachage renvoie le chiffre le moins significatif de la clé.

Pour m= 100, la fonction de hachage renvoie les deux chiffres les moins significatifs de la clé.

Dans les exemples considérés, la fonction de hachage je=h(clé) définit uniquement la position à partir de laquelle rechercher (ou placer initialement dans la table) un enregistrement avec une clé clé. Ensuite, vous devez utiliser un schéma de hachage (algorithme).

Schémas de hachage

Dans la plupart des problèmes, deux clés ou plus ont le même hachage, mais elles ne peuvent pas occuper la même cellule de la table de hachage. Il existe deux options possibles : soit rechercher une position différente pour la nouvelle clé, soit créer une liste distincte pour chaque index de table de hachage contenant toutes les clés mappées à cet index.

Ces options représentent deux schémas de hachage classiques :

hachage en utilisant la méthode d'adressage ouvert avec échantillonnage linéaire - linéaire sonde ouvrir adressage.

hachage utilisant la méthode de la chaîne (avec des listes), ou hachage dit multidimensionnel - enchaînement avec séparé listes;

Méthode d'adressage ouverte avec échantillonnage linéaire . Initialement, toutes les cellules de la table de hachage, qui est un tableau unidimensionnel régulier, sont marquées comme inoccupées. Par conséquent, lors de l'ajout d'une nouvelle clé, il est vérifié si la cellule donnée est occupée. Si la cellule est occupée, alors l'algorithme recherche dans un cercle jusqu'à ce qu'un espace libre soit trouvé (« adresse ouverte »).

Ceux. les éléments avec des clés homogènes sont placés à proximité de l'index résultant.

À l'avenir, lors de la recherche, recherchez d'abord la position par clé je dans le tableau, et si la clé ne correspond pas, alors la recherche ultérieure est effectuée conformément à l'algorithme de résolution des conflits, en commençant par la position je. .

Méthode en chaîne est la stratégie dominante . Dans ce cas je, obtenu à partir de la fonction de hachage sélectionnée h(clé)=je, est traité comme un index dans une table de hachage de listes, c'est-à-dire clé d'abord clé l'entrée suivante est mappée à la position je = h(clé) tableaux. Si la position est libre, alors un élément avec une clé y est placé clé, s'il est occupé, un algorithme de résolution de conflit est élaboré, à la suite duquel ces clés sont placées dans une liste commençant à je-cette cellule de la table de hachage. Par exemple

En conséquence, nous avons un tableau d’un tableau de listes ou d’arbres chaînés.

Le processus de remplissage (lecture) d'une table de hachage est simple, mais l'accès aux éléments nécessite les opérations suivantes :

Calcul de l'indice je;

Recherchez dans le fil de discussion correspondant.

Pour améliorer la recherche lors de l'ajout d'un nouvel élément, vous pouvez utiliser l'algorithme d'insertion non pas en fin de liste, mais avec ordre, c'est-à-dire ajoutez un élément à l'emplacement souhaité.

Un exemple de mise en œuvre de la méthode d'adressage direct avec échantillonnage linéaire . Les données sources sont constituées de 7 enregistrements (pour plus de simplicité, la partie information est constituée uniquement de données entières), type de structure déclaré :

clé entière ; // Clé

informations internationales ; // Information

(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9) ; taille de la table de hachage m=10.

Fonction de hachage je=h(données) =données.clé%10 ; ceux. reste de la division par 10 - je.

Sur la base des données initiales, nous remplissons séquentiellement la table de hachage.

Le hachage des cinq premières clés donne différents index (adresses de hachage) :

La première collision se produit entre les touches 81 et 41 - la place avec l'index 1 est occupée. Par conséquent, nous parcourons la table de hachage pour trouver l'espace libre le plus proche, dans ce cas il s'agit de je = 2.

La touche suivante 79 génère également une collision : la position 9 est déjà occupée. L'efficacité de l'algorithme chute fortement, car il a fallu 6 échantillons (comparaisons) pour trouver un espace libre, l'index s'est avéré libre je= 4.

Le nombre total d'échantillons de cette méthode est compris entre 1 et n-1 échantillons par élément, où n est la taille de la table de hachage.

Mise en œuvre de la méthode en chaîne pour l'exemple précédent. Nous déclarons un type structuré pour un élément de liste (unidirectionnel) :

clé entière ; // Clé

informations internationales ; // Information

zapper*Suivant ; // Pointeur vers l'élément suivant de la liste

Sur la base des données initiales, nous remplissons séquentiellement la table de hachage, en ajoutant un nouvel élément à la fin de la liste si la place est déjà prise.

Le hachage des cinq premières clés, comme dans le cas précédent, donne différents indices (adresses de hachage) : 9, 0, 6, 1 et 3.

Lorsqu'une collision se produit, un nouvel élément est ajouté à la fin de la liste. Par conséquent, l'élément avec la clé 41 est placé après l'élément avec la clé 81, et l'élément avec la clé 79 est placé après l'élément avec la clé 59.

Tâches individuelles

1. Arbres binaires.À l'aide du programme de détection de nombres aléatoires, obtenez 10 valeurs de 1 à 99 et construisez un arbre binaire.

Faites un détour :

1.a Traversée de gauche à droite : Gauche-Racine-Droite : on visite d'abord le sous-arbre de gauche, puis la racine et enfin le sous-arbre de droite.

(Ou vice versa, de droite à gauche : Droite -Racine- Gauche)

1.b Traversée de haut en bas : Racine-Gauche-Droite : on visite la racine des sous-arbres.

1.c Traversée de bas en haut : Gauche-Droite-Racine : visiter la racine après les sous-arbres

Hachage(parfois hachage, hachage anglais) - conversion d'un tableau de données d'entrée de longueur arbitraire en une chaîne de sortie d'une longueur fixe. De telles transformations sont également appelées fonctions de hachage ou fonctions de convolution, tableau d'entrée – prototype, et les résultats de la transformation sont hachage, code de hachage, image de hachage, empreinte digitale ou résumé du message(Résumé du message en anglais).

Fonction de hachage– une fonction facilement calculable qui convertit un message initial de longueur arbitraire (préimage) en un message de longueur fixe (image de hachage), pour lequel il n'existe pas d'algorithme de recherche de collision efficace.

Collision pour la fonction h appelé une paire de valeurs x, y, x ≠ y, tel que h(x) = h(y). Que. La fonction de hachage doit avoir les propriétés suivantes :

Pour une valeur donnée h(x) impossible de trouver la valeur de l'argument x. De telles fonctions de hachage sont appelées persistant en termes de traitement ou persistant au sens fort;

Pour un argument donné x je ne trouve pas d'autre argument oui tel que h(x) = h(y). De telles fonctions de hachage sont appelées robuste en termes de calculs de collision ou persistant dans un sens faible.

Dans le cas où la valeur de la fonction de hachage dépend non seulement de la pré-image, mais également de la clé privée, alors cette valeur est appelée Code d'authentification de message (MAC), Code d'authentification de données (DAC) ou insertion d'imitations.

En pratique, les fonctions de hachage sont utilisées aux fins suivantes :

Pour accélérer la recherche de données dans la base de données ;

Accélérez la récupération des données. Par exemple, lorsque des champs de texte sont écrits dans une base de données, leur code de hachage peut être calculé et les données peuvent être placées dans une section correspondant à ce code de hachage. Ensuite, lors de la recherche de données, vous devrez d'abord calculer le code de hachage du texte et vous saurez immédiatement dans quelle section vous devez le rechercher, c'est-à-dire Vous devrez effectuer une recherche non pas dans toute la base de données, mais seulement dans une section de celle-ci (cela accélère considérablement la recherche).

Un analogue domestique du hachage dans ce cas peut être le placement des mots dans le dictionnaire par ordre alphabétique. La première lettre d'un mot est son code de hachage, et lors de la recherche, nous ne parcourons pas tout le dictionnaire, mais uniquement la section contenant la lettre souhaitée.

La procédure de calcul (schéma d'algorithme standard) de la fonction de hachage est présentée dans la figure suivante.

Figure 10.1. Procédure de calcul d'une valeur de hachage

1) Vers le message d'origine T des informations auxiliaires sont ajoutées (par exemple, la longueur de la pré-image, les symboles auxiliaires, etc.) de sorte que la longueur de la pré-image X est devenu un multiple de Lbl, défini par la spécification de la fonction de hachage (standard).

2) Pour initialiser la procédure de hachage, un message de synchronisation est utilisé oui 0.

3) Prototypes X se décompose en n blocs x je(i = 1 .. n) longueur fixe Lbl, sur lequel le même type de procédure de hachage est effectué f(y je-1 , x je), en fonction du résultat de hachage du bloc précédent y i-1.

4) Méthode de hachage h(T) message original T sera le résultat de la procédure de hachage o n, obtenu après traitement du dernier bloc xn.

10.2. MD5

MD5 Message Digest 5 est un algorithme de hachage de 128 bits développé par le professeur Ronald L. Rivest du Massachusetts Institute of Technology (MIT) en 1991. Il s'agit d'une version sécurisée de MD4.

Vous trouverez ci-dessous l'algorithme de calcul de hachage.

1. Égalisation du débit.

A la fin du message original, longueur L, ajoutez un bit, puis le nombre requis de bits zéro pour que la nouvelle taille L"était comparable à 448 modulo 512 (L’ mod 512 = 448). L'ajout de bits zéro est effectué même si la nouvelle longueur, y compris le bit un, est déjà comparable à 448.

2. Ajout de la longueur du message.

Une représentation sur 64 bits de la longueur des données (le nombre de bits dans le message) est ajoutée au message modifié. Ceux. longueur du message T devient un multiple de 512 (T mod 512 = 0). Si la longueur du message d'origine dépasse 2 64 - 1, alors seuls les 64 bits inférieurs sont ajoutés. De plus, pour une représentation de longueur spécifiée de 64 bits, les 32 bits de poids faible sont écrits en premier, suivis des 32 bits de poids fort.

3. Initialisation du tampon.

Pour les calculs, 4 variables de 32 bits chacune sont initialisées et des valeurs initiales sont définies (représentation hexadécimale) :

UN = 67 45 23 01;
B= EF CD AB 89 ;
C= 98 BA CC FE ;
D = 10 32 54 76.

Ces variables stockeront les résultats des calculs intermédiaires. État initial ABCD appelé vecteur d'initialisation.

4. Calcul de hachage en boucle.

Le message original est divisé en blocs T, 512 bits de long. Pour chaque bloc du cycle, la procédure illustrée à la Fig. 10.2 est effectuée. Le résultat du traitement de tous les blocs du message d'origine comme une union de valeurs variables de 32 bits ABCD et ce sera un hachage.

Figure 10.2. Étape principale de la boucle de calcul du hachage

À chaque tour sur des variables ABCD et bloc de texte source T dans un cycle (16 itérations), des transformations similaires sont effectuées selon le schéma suivant.

Figure 10.3. Une itération en boucle ronde

Conventions.

1) RF- fonction ronde déterminée selon le tableau suivant.

Tableau 10.1. Fonctions RF rondes

2) tj- j-ème partie de 32 bits du bloc de message d'origine T gros boutien;

3) ok je- partie entière d'une constante déterminée par la formule

k je = 2 32 * | péché(i + 16 * (r - 1)) |, (10.1)

où i est le numéro d'itération de la boucle (i = 1..16) ;
r – nombre rond (r = 1..4).

L'argument de la fonction sin est mesuré en radians.

4) ⊞ – addition modulo 2 32.

5) <<< et je– décalage cyclique vers la gauche de s i chiffres.

Partie de 32 bits utilisée du bloc de message d'origine tj et la quantité de décalage cyclique vers la gauche et je dépendent du numéro d’itération et sont indiqués dans le tableau suivant.

Tableau 10.2. Quantités utilisées dans l'étape du cycle rond

Numéro d'itération		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Tour 1	tj	t1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
	et je	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
Tour 2	tj	t 2	t 7	t 12	t1	t 6	t 11	t 16	t 5	t 10	t 15	t 4	t 9	t 14	t 3	t 8	t 13
	et je	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
Tour 3	tj	t 6	t 9	t 12	t 15	t 2	t 5	t 8	t 11	t 14	t1	t 4	t 7	t 10	t 13	t 16	t 3
	et je	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
Tour 4	tj	t1	t 8	t 15	t 6	t 13	t 4	t 11	t 2	t 9	t 16	t 7	t 14	t 5	t 12	t 3	t 10
	et je	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

Après 4 tours, nouvelle valeur (modifiée) pour chaque variable ABCD ajoute (⊞) à l'original (la valeur de la variable avant le 1er tour).

5. Réorganisation des octets dans les variables ABCD. Après avoir traité tous les blocs du message d'origine, un échange d'octets inversé est effectué pour chaque variable.

Recherchez des collisions.

En 2004, les chercheurs chinois Wang Xiaoyun, Feng Dengguo, Lai Xuejia et Yu Hongbo ont annoncé avoir découvert une vulnérabilité dans un algorithme permettant à IBM p690) de détecter des collisions.

10.3. Utiliser le cryptage pour obtenir une image de hachage

Pour générer une image de hachage résistante aux collisions, des modes spéciaux fournis dans les chiffrements par blocs (par exemple, la concaténation de blocs de chiffrement y) peuvent être utilisés, ou dans la fonction de hachage elle-même, en tant que composant, l'un des modes de chiffrement par blocs peut être utilisé ( par exemple, un composant de fonctions de hachage selon GOST 34.11-94 1 est un mode de remplacement simple de l'algorithme de conversion cryptographique selon 2).

Rappelons que dans le cas où la valeur de la fonction de hachage dépend non seulement du prototype, mais également de la clé privée, l'image de hachage est appelée Message Authentication Code (MAC), Data Authentication Code (DAC) ou insertion d'imitations.

A titre d'exemple, nous donnerons le mode (chaînage de blocs de chiffrement).

Figure 10.4. Schéma de l'algorithme DES en mode chaînage de blocs de chiffrement

Dernier bloc chiffré CN et il y a une image hachée du message T = (T 1, T 2, …, T n).

1 GOST 34.11-94 « Technologie de l'information. Protection des informations cryptographiques. Fonction de hachage."

2 GOST 28147-89 « Systèmes de traitement de l'information. Protection cryptographique. Algorithme de conversion cryptographique".

Questions d'auto-test

1. Définir les concepts : "", "", "".

Pour résoudre le problème de trouver l'élément requis parmi les données volumineuses, un algorithme a été proposé hachage (hachage- shuffling), dans lequel des clés sont créées qui définissent les données du tableau et, sur la base d'elles, les données sont écrites dans une table appelée table de hachage . Les clés d'enregistrement sont déterminées à l'aide de la fonction je = h(clé) , appelé fonction de hachage . L'algorithme de hachage détermine la position de l'élément recherché dans la table de hachage en fonction de la valeur de sa clé obtenue par la fonction de hachage.

Concept hachage– Il s'agit du partitionnement d'un ensemble commun (de base) de clés uniques d'éléments de données en ensembles disjoints dotés d'une certaine propriété.

Prenons, par exemple, un dictionnaire ou une encyclopédie. Dans ce cas, les lettres de l'alphabet peuvent être prises comme clés de recherche, c'est-à-dire L'élément principal de l'algorithme de hachage est clé (clé). Dans la plupart des applications, la clé fournit une référence indirecte aux données.

En fait, le hachage est une méthode particulière d'adressage des données pour trouver rapidement les informations nécessaires. par clés .

Si le kit de base contient Néléments, alors il peut être divisé en 2 N divers sous-ensembles.

Table de hachage et fonctions de hachage

Une fonction qui mappe les clés des éléments de données à un ensemble d'entiers (index dans une table - table de hachage ), appelé fonction de hachage , ou fonction de hachage :

je = h(clé);

Où clé– clé convertible, je– l'index de la table résultant, c'est-à-dire la clé est mappée sur un ensemble d'entiers ( adresses de hachage ), qui sont ensuite utilisés pour accéder aux données.

Cependant, une fonction de hachage pour plusieurs valeurs clés peut produire la même valeur de position je dans le tableau. La situation dans laquelle deux clés ou plus partagent le même index (adresse de hachage) est appelée collision lors du hachage.

Une bonne fonction de hachage est une fonction qui minimise les collisions et distribue les données uniformément dans la table, et une fonction de hachage parfaite est une fonction qui ne génère pas de collisions :

Il existe deux méthodes pour résoudre les collisions de hachage :

– méthode d'adressage ouverte avec tests linéaires;

– méthode de la chaîne.

Table de hachage

Une table de hachage est un tableau régulier avec un adressage inhabituel spécifié par une fonction de hachage.

Structure de hachage est considéré comme une généralisation d'un tableau qui fournit un accès rapide et direct aux données par index.

Il existe de nombreux schémas de hachage, qui diffèrent par le choix d'une fonction réussie h(clé), et un algorithme de résolution de conflits. L'efficacité de la résolution d'un problème pratique réel dépendra largement de la stratégie choisie.

Exemples de fonctions de hachage

La fonction de hachage que vous choisissez doit être facile à calculer et créer le moins de collisions possible, c'est-à-dire doit répartir les clés uniformément entre les index existants dans la table. Bien entendu, il est impossible de déterminer si une fonction de hachage particulière distribuera correctement les clés à moins que ces clés ne soient connues à l'avance. Cependant, bien que les clés elles-mêmes soient rarement connues avant de choisir une fonction de hachage, certaines propriétés de ces clés qui affectent leur distribution sont généralement connues. Examinons les méthodes les plus courantes pour spécifier une fonction de hachage.

Méthode de division. Les données initiales sont une clé entière clé et taille du tableau m. Le résultat de cette fonction est le reste lorsque cette clé est divisée par la taille du tableau. Vue générale de la fonction :

int h(clé int, int m) (

clé de retour % m ; // Valeurs

Pour m= 10 La fonction de hachage renvoie le chiffre le moins significatif de la clé.

Pour m= 100 La fonction de hachage renvoie les deux chiffres les moins significatifs de la clé.

Méthode additive, dans lequel la clé est une chaîne de caractères. Dans une fonction de hachage, une chaîne est convertie en entier en additionnant tous les caractères et en renvoyant le reste après division par m(généralement la taille d'une table m= 256).

int h(char *clé, int m) (

Les collisions se produisent dans des chaînes composées du même jeu de caractères, par exemple : abc Et taxi.

Cette méthode peut être légèrement modifiée, obtenant le résultat en additionnant uniquement les premier et dernier caractères de la chaîne clé.

int h(char *clé, int m) (

int len ​​​​= strlen(clé), s = 0;

si(len< 2) // Если длина ключа равна 0 или 1,

s = clé ; // clé de retour

s = clé + clé ;

Dans ce cas, les collisions ne se produiront que dans les lignes, par exemple abc Et amc.

Méthode du milieu du carré, dans lequel la clé est au carré (multipliée par elle-même) et plusieurs chiffres du milieu de la valeur résultante sont utilisés comme index.

Par exemple, la clé est un entier de 32 bits et la fonction de hachage renvoie la moyenne des 10 bits de son carré :

int h(clé int) (

clé >>= 11 ; // Supprime les 11 bits les moins significatifs

clé de retour % 1024 ; // Renvoie les 10 bits les moins significatifs

Méthode OU exclusif pour les clés de ligne (généralement de la taille d'une table) m=256). Cette méthode est similaire à la méthode additive, mais elle distingue les mots similaires. La méthode consiste à appliquer séquentiellement l’opération « OU exclusif » aux éléments de la chaîne.

DANS méthode multiplicative en plus, un nombre réel aléatoire est utilisé r de l'intervalle. Si ce produit est multiplié par la taille du tableau m, alors la partie entière du produit résultant donnera une valeur comprise entre 0 et m–1.

int h(clé int, int m) (

double r = clé * rnd();

r = r – (int)r; // Sélection de la partie fractionnaire

En général, pour les grandes valeurs m les indices générés par la fonction de hachage ont une large diffusion. De plus, la théorie mathématique affirme que la distribution est plus uniforme si m est un nombre premier.

Dans les exemples considérés, la fonction de hachage je = h(clé) détermine uniquement la position à partir de laquelle rechercher (ou placer initialement dans la table) un enregistrement avec une clé clé. Par conséquent, le schéma de hachage doit inclure algorithme de résolution de conflits , qui détermine l'ordre des actions si la position je = h(clé) s'avère être déjà occupé par un enregistrement avec une clé différente.