Fonction de hachage : qu'est-ce que c'est, pourquoi elle est nécessaire et qu'est-ce que c'est. Fonction de hachage cryptographique Types de fonctions de hachage

Souvent, lors du téléchargement de torrents ou des fichiers eux-mêmes, la description indique quelque chose comme « » (par exemple, dans ex.ua), souvent avec le préfixe « md5 ». Il s'agit du code de hachage - le résultat produit par la fonction de hachage après le traitement des données entrantes. Traduit de l'anglais, hash signifie confusion, marijuana, herbe ou un plat de viande et de légumes finement hachés. très, très difficile, on pourrait dire presque impossible. Alors la question se pose : "Pourquoi tout cela est-il nécessaire ? Ils diffusent un charabia incompréhensible, qui n'est pas non plus déchiffrable ?" Ceci sera discuté dans cet article.

Qu’est-ce qu’une fonction de hachage et comment ça marche ?

Cette fonction est conçue pour convertir des données entrantes de taille arbitrairement grande en un résultat de longueur fixe. Le processus d'une telle conversion est appelé hachage et le résultat est un hachage ou un code de hachage. Parfois, les mots « empreinte digitale » ou « résumé de message » sont également utilisés, mais dans la pratique, ils sont beaucoup moins courants. Il existe de nombreux algorithmes différents pour transformer n'importe quel tableau de données en une certaine séquence de caractères d'une certaine longueur. L’algorithme le plus largement utilisé s’appelle md5 et a été développé en 1991. Malgré le fait qu'aujourd'hui md5 soit quelque peu obsolète et son utilisation n'est pas recommandée, il est toujours utilisé et souvent, au lieu du mot « code de hachage », les sites écrivent simplement md5 et indiquent le code lui-même.

Pourquoi une fonction de hachage est-elle nécessaire ?

Connaissant le résultat, il est presque impossible de déterminer les données d'entrée, mais les mêmes données d'entrée donnent le même résultat. Par conséquent, la fonction de hachage (également appelée fonction de convolution) est souvent utilisée pour stocker des informations très importantes telles que le mot de passe, l'identifiant, le numéro d'identification et d'autres informations personnelles. Au lieu de comparer les informations saisies par l’utilisateur avec celles stockées dans la base de données, leurs hachages sont comparés. Cela garantit qu’en cas de fuite accidentelle d’informations, personne ne pourra utiliser des données importantes à ses propres fins. En comparant le code de hachage, il est également pratique de vérifier que les fichiers sont correctement téléchargés depuis Internet, surtout s'il y a eu des interruptions de connexion pendant le téléchargement.

Fonctions de hachage : qu’est-ce que c’est ? T

Selon son objectif, une fonction de hachage peut être de trois types :

1. Fonction de vérification de l'intégrité des informations

Lorsque cela se produit sur le réseau, un hachage du paquet est calculé et ce résultat est également transmis avec le fichier. A réception, le code de hachage est à nouveau calculé et comparé à la valeur reçue sur le réseau. Si le code ne correspond pas, cela indique des erreurs et le paquet endommagé sera à nouveau transmis. Cette fonction a une vitesse de calcul rapide, mais un petit nombre de valeurs de hachage et une mauvaise stabilité. Un exemple de ce type : CRC32, qui n'a que 232 valeurs différentes.

2. Fonction cryptographique

Utilisé pour la protection contre (ND). Ils vous permettent de vérifier si une corruption des données s'est produite à la suite d'un accident lors du transfert de fichiers sur le réseau. Dans ce cas, le véritable hachage est accessible au public et le hachage du fichier résultant peut être calculé à l'aide de nombreux programmes différents. De telles fonctions ont une durée de vie longue et stable, et la recherche de collisions (coïncidences possibles de résultats provenant de différentes sources de données) est très difficile. Ce sont les fonctions utilisées pour stocker les mots de passe (SH1, SH2, MD5) et d'autres informations précieuses dans la base de données.

3. Une fonction conçue pour créer une structure de données efficace

Son objectif est une organisation compacte et assez ordonnée des informations dans une structure spéciale appelée table de hachage. Un tel tableau vous permet d'ajouter de nouvelles informations, de supprimer des informations et de rechercher les données nécessaires à très grande vitesse.

Un très grand nombre de technologies de sécurité (par exemple authentification, signature numérique) utilisent des fonctions de chiffrement unidirectionnel, également appelées fonctions de hachage. L'objectif principal de ces fonctions est d'obtenir à partir d'un message de taille arbitraire son résumé - une valeur de taille fixe. Le résumé peut être utilisé comme somme de contrôle du message d'origine, fournissant ainsi (lors de l'utilisation du protocole approprié) un contrôle de l'intégrité des informations. Propriétés de base d'une fonction de hachage :

1. un message de longueur arbitraire est fourni à l'entrée de la fonction de hachage ;
2. en sortie de la fonction de hachage, un bloc de données de longueur fixe est formé ;
3. les valeurs de sortie de la fonction de hachage sont uniformément distribuées ;
4. changer un bit de l'entrée de la fonction de hachage modifie considérablement la sortie.

De plus, pour garantir qu’une fonction de hachage résiste aux attaques, elle doit satisfaire aux exigences suivantes :

1. si nous connaissons la valeur de la fonction de hachage h, puis la tâche de trouver un message M tel que H(M) = h, doit être difficile en termes de calcul ;
2. étant donné un message M, la tâche de trouver un autre message M' tel que H(M) = H(M') doit être informatiquement difficile.

Si la fonction de hachage satisfait aux propriétés répertoriées, la valeur qu'elle génère identifiera de manière unique les messages, et toute tentative de modification du message pendant la transmission sera détectée en effectuant un hachage du côté réception et en la comparant avec le résumé reçu du côté envoi.

Une autre caractéristique des fonctions de hachage est qu'elles ne permettent pas la conversion inverse : il est impossible d'obtenir le message original à partir de son résumé. Par conséquent, elles sont également appelées fonctions de chiffrement unidirectionnel.

Les fonctions de hachage sont construites à l'aide d'un schéma itératif, dans lequel le message d'origine est divisé en blocs d'une certaine taille et une série de transformations y est effectuée à l'aide d'opérations à la fois réversibles et irréversibles. Généralement, une transformation de hachage inclut une fonction de compression car sa sortie est souvent plus petite que le bloc d'entrée. L'entrée de chaque cycle de hachage est la sortie du cycle précédent, ainsi que le bloc de message suivant. Ainsi, à chaque cycle, la sortie de la fonction de hachage est Salut est un hachage du premier je blocs.

Si vous vous souvenez de la manière dont les chiffrements par blocs randomisent le message d'entrée, vous pouvez utiliser une sorte de chiffrement par blocs comme fonction de transformation de hachage. Le fait que les chiffrements par blocs soient des transformations réversibles ne contredit pas les propriétés de la fonction de hachage, puisqu'un chiffrement par blocs est irréversible par rapport à la clé de chiffrement, et si le résultat de l'étape de transformation de hachage précédente est utilisé comme clé de chiffrement, et que le chiffrement par bloc est une transformation réversible. le bloc de message suivant est utilisé comme message chiffré (ou vice versa), vous pouvez alors obtenir une fonction de hachage avec de bonnes caractéristiques cryptographiques. Cette approche est utilisée, par exemple, dans la norme de hachage russe - GOST R 34.11-94. Cette fonction de hachage génère une valeur de sortie de 256 bits en utilisant le chiffrement par bloc GOST 28147-89 comme opération de conversion (Fig. 2.17). La fonction de hachage H reçoit en entrée le hachage obtenu à l'étape précédente (la valeur h 0 numéro de départ arbitraire), ainsi que le bloc de message suivant je suis. Sa structure interne est illustrée à la Fig. 2.18. Ici dans le bloc de transformation de chiffrement pour modification Salut V et je Le chiffrement par bloc GOST 28147-89 est utilisé. La transformation de mélange est une permutation de Feishtel modifiée. Pour le dernier bloc m SUBST(N est le nombre total de blocs de message), le remplissage est effectué jusqu'à une taille de 256 bits avec l'ajout de la vraie longueur du message. En parallèle, la somme de contrôle du message ∑ et la longueur totale L sont calculées, qui participent à la compression finale fonction.

Le principal inconvénient des fonctions de hachage basées sur les chiffrements par blocs est leur faible vitesse. Par conséquent, un certain nombre d'algorithmes spécialisés ont été conçus qui, tout en offrant une résistance similaire aux attaques, effectuent un nombre beaucoup plus réduit d'opérations sur les données d'entrée et offrent une plus grande vitesse de fonctionnement. Des exemples de ce type d'algorithmes sont : MD2, MD4, MD5, RIPEMD – 160, SHA. Examinons de plus près la structure de l'algorithme de hachage SHA (Secure Hash Algorithm), qui est décrit dans la norme SHS et assure la sécurité de la signature numérique électronique DSA en générant un résumé de message de 160 bits.

Tout d’abord, le message est divisé en blocs de 512 bits. Si la longueur du message n'est pas un multiple de 512, un 1 est ajouté à droite du dernier bloc, après quoi il est complété par des zéros jusqu'à 512 bits. Le code de longueur du message est écrit à la fin du dernier bloc. En conséquence, le message prend la forme n Blocs de 512 bits M 1, M 2, ..., M n.

L'algorithme SHA utilise 80 fonctions logiques f 0 , f 1 , ..., f 79 , qui effectuent des opérations sur trois mots de 32 bits (B, C, D) :

L'algorithme utilise également 4 constantes K i spécialement initialisées et 5 valeurs initiales H i .

On divise le tableau M en groupes de 16 mots W 0, W 1,…, W 15 (W 0 est le mot le plus à gauche).
Pour t= 16 - 79 W t = S 1 (W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16)
S k désigne l'opération d'un décalage cyclique vers la gauche par k décharges.
Soit maintenant A = H 0, B = H 1, C = H 2, D = H 3, E = H 4.
pour t= 0 à 79 faire
TEMP = S 5 (A) + ft(B, C, D) + E + W t + K i .
E = D ; D = C ; C = S 30 (B); B=A ; A = TEMPÉRATURE ;
Soit H 0 = H 0 + A ; H 1 = H 1 + B ; H 2 = H 2 + C; H 3 = H 3 + D; H4 = H4 + E.

Graphiquement, un cycle SHA est présenté sur la figure 2.19.

À la suite du traitement du tableau M, 5 mots H 0, H 1, H 2, H 3, H 4 d'une longueur totale de 160 bits seront obtenus, qui forment le résumé du message.

Il ressort clairement des données ci-dessus que la complexité de la norme de hachage américaine est inférieure à celle de la norme russe. La norme russe implique d'effectuer quatre cryptages en un seul cycle de génération de hachage, soit un total de 128 tours. Chaque cycle de cryptage nécessite environ une douzaine d'opérations machine élémentaires, ce qui augmente considérablement le coût du temps informatique nécessaire à la réalisation des opérations de mélange linéaire. Un cycle de génération de hachage SHA est beaucoup plus simple : tout cela peut être implémenté en 15 à 20 commandes environ, le nombre total de cycles n'est que de 80, et dans un cycle de génération de hachage, deux fois plus de données initiales sont traitées - 512 contre 256 dans GOST P34.ll - 94. Ainsi, on peut supposer que les performances des implémentations logicielles de SHA seront environ 3 à 6 fois plus rapides que celles de la norme nationale.

La tâche principale des fonctions de hachage est de générer des résumés uniques à un document spécifique. Si la fonction de hachage produit le même résumé pour deux blocs d'entrée différents, cette situation est appelée collision de hachage. D'un théorème appelé paradoxe de l'anniversaire, il s'ensuit qu'une valeur de hachage de n bits nécessite une moyenne de 2 n/2 différents messages d'entrée afin qu'une collision se produise. Cela rend presque impossible la modification d'un document lorsqu'il est signé en utilisant, par exemple, l'algorithme SHA par simple sélection, car avec cette approche, il faudrait générer environ 280 messages différents pour en obtenir un similaire à celui à remplacer. par le résumé reçu. Ce chiffre est inatteignable avec le niveau technologique actuel.

Et ainsi de suite.). Le choix de l'une ou l'autre fonction de hachage est déterminé par les spécificités du problème à résoudre. Les exemples les plus simples de fonctions de hachage sont la somme de contrôle ou le CRC.

En général, il n’y a pas de correspondance biunivoque entre les données source et le code de hachage. Par conséquent, il existe de nombreux ensembles de données qui donnent les mêmes codes de hachage – ce que l’on appelle les collisions. La probabilité de collisions joue un rôle important dans l’évaluation de la « qualité » des fonctions de hachage.

Sommes de contrôle

Des algorithmes matériels simples, extrêmement rapides et faciles à mettre en œuvre utilisés pour se protéger contre les distorsions involontaires, y compris les erreurs matérielles.

La vitesse de calcul est des dizaines et des centaines de fois plus rapide que celle des fonctions de hachage cryptographique, et beaucoup plus simple dans la mise en œuvre matérielle.

Le prix à payer pour une vitesse aussi élevée est le manque de force cryptographique – une opportunité facile d’ajuster le message à un montant pré-connu. De plus, les sommes de contrôle (typiquement : 32 bits) ont généralement une largeur inférieure à celle des hachages cryptographiques (typiquement : 128, 160 et 256 bits), ce qui signifie que des collisions involontaires peuvent se produire.

Le cas le plus simple d'un tel algorithme consiste à diviser un message en mots de 32 ou 16 bits et à les additionner, ce qui est utilisé par exemple dans TCP/IP.

En règle générale, un tel algorithme est nécessaire pour suivre les erreurs matérielles typiques, telles que plusieurs bits erronés consécutifs jusqu'à une longueur donnée. La soi-disant famille d'algorithmes "code de redondance cyclique" satisfait à ces exigences. Il s'agit par exemple du CRC32, utilisé dans les équipements ZIP.

Fonctions de hachage cryptographique

Parmi les nombreuses fonctions de hachage existantes, il est d'usage de distinguer les fonctions de hachage cryptographiquement fortes utilisées en cryptographie. Une fonction de hachage crypto-résistante doit avant tout avoir résistant aux collisions deux types:

Utiliser le hachage

Les fonctions de hachage sont également utilisées dans certaines structures de données : tables de hachage et arbres cartésiens. Les exigences pour la fonction de hachage dans ce cas sont différentes :

• bonne mixabilité des données
• algorithme de calcul rapide

Rapprochement des données

En général, cette application peut être décrite comme vérifiant que certaines informations sont identiques à l'original, sans utiliser l'original. Pour le rapprochement, la valeur de hachage des informations vérifiées est utilisée. Il y a deux domaines principaux de cette application :

Vérification des erreurs

Par exemple, la somme de contrôle peut être transmise via le canal de communication avec le texte principal. À la réception, la somme de contrôle peut être recalculée et comparée à la valeur transmise. Si une divergence est détectée, cela signifie qu'une distorsion s'est produite pendant la transmission et qu'une répétition peut être demandée.

Un analogue domestique du hachage dans ce cas peut être la technique selon laquelle, lors du déplacement, le nombre de bagages est conservé en mémoire. Ensuite, pour vérifier, vous n’avez pas besoin de vous souvenir de chaque valise, mais simplement de les compter. Un match signifie qu'aucune valise n'est perdue. Autrement dit, le nombre de bagages correspond à leur code de hachage.

Vérification de la phrase secrète

Dans la plupart des cas, les phrases secrètes ne sont pas stockées sur les cibles, seules leurs valeurs de hachage sont stockées. Il n'est pas conseillé de stocker les phrases secrètes, car en cas d'accès non autorisé à un fichier contenant des phrases, l'attaquant découvrira toutes les phrases secrètes et pourra les utiliser immédiatement, et lors du stockage des valeurs de hachage, il n'apprendra que les valeurs de hachage. ​​qui ne sont pas réversibles dans les données d'origine, dans ce cas, la phrase secrète. Au cours de la procédure d'authentification, la valeur de hachage de la phrase secrète saisie est calculée et comparée à celle enregistrée.

Un exemple dans ce cas serait GNU/Linux et Microsoft Windows XP. Ils stockent uniquement les valeurs de hachage des phrases secrètes des comptes d'utilisateurs.

Accélérer 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 que vous devrez rechercher non pas dans toute la base de données, mais uniquement dans une section (cela accélère considérablement la recherche).

Un analogue courant du hachage dans ce cas peut consister à placer les mots dans un 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 lettre souhaitée.

Liste des algorithmes

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snéfrou
• Tigre (Tourbillon
• Somme de contrôle Internet IP (RFC 1071)

Liens

Fondation Wikimédia. 2010.

• Heshan Moheyan
• Code de hachage

Découvrez ce qu'est une « fonction de hachage » dans d'autres dictionnaires :

Fonction de hachage- une fonction qui effectue le hachage d'un tableau de données en mappant les valeurs d'un (très) grand ensemble de valeurs dans un ensemble de valeurs (considérablement) plus petit. En anglais : Fonction de hachage Voir aussi : Algorithmes cryptographiques Financier... ... Dictionnaire financier

fonction de hachage cryptographique- Une fonction qui convertit un texte de longueur arbitraire en texte d'une longueur fixe (dans la plupart des cas plus petite). La principale application des fonctions de hachage réside dans le schéma de signature numérique. Puisque la fonction de hachage est calculée plus rapidement qu'une signature numérique, alors au lieu de... ...

Fonction de hachage à sens unique- la fonction de hachage, qui est une fonction irréversible sur le plan informatique. En anglais : Fonction de hachage à sens unique Voir aussi : Algorithmes cryptographiques Dictionnaire financier Finam... Dictionnaire financier

TIGRE - fonction de hachage- Fonction de hachage TIGER développée par Ros Anderson et Eli Beham en 1996. La fonction de hachage TIGER est une nouvelle fonction de hachage rapide conçue pour être très rapide sur les ordinateurs modernes, en particulier les ordinateurs 64 bits. TIGRE... ... Wikipédia

fonction de hachage unidirectionnelle- Pour une fonction unidirectionnelle, il est informatiquement impossible de trouver deux arguments différents pour lesquels ses valeurs sont les mêmes. [] Sujets sécurité de l'information FR fonction de hachage à sens unique... Guide du traducteur technique

Tigre (fonction de hachage)- Fonction de hachage Tiger développée par Ros Anderson et Eli Beham en 1995. Tiger a été conçu pour fonctionner particulièrement rapidement sur les ordinateurs 64 bits. Tiger n'a aucune restriction de brevet, peut être utilisé librement avec... ... Wikipedia

fonction de hachage- fonction de hachage 1. Une fonction qui contrôle le processus de saisie des données dans une table de hachage, déterminant (les adresses des cellules libres. 2. Une fonction qui représente un mappage d'un fragment d'un message ouvert dans une chaîne cryptée d'une longueur fixe. Dans ... ... Guide du traducteur technique

Table de hachage- En programmation, une table de hachage est une structure de données qui implémente l'interface de tableau associatif, à savoir, elle permet de stocker des couples (clé, valeur) et d'effectuer trois opérations : l'opération d'ajout d'un nouveau couple, l'opération de recherche et la suppression opération... Wikipédia

Code de hachage- Conversion par hachage (parfois hachage, hachage anglais) d'un tableau de données d'entrée de longueur arbitraire en une chaîne de bits de sortie d'une longueur fixe. De telles transformations sont également appelées fonctions de hachage ou fonctions de convolution, et leurs résultats... ... Wikipédia

Collision de fonction de hachage- Une collision de fonction de hachage H est constituée de deux blocs de données d'entrée différents x et y tels que H(x) = H(y). Des collisions existent pour la plupart des fonctions de hachage, mais pour les « bonnes » fonctions de hachage, la fréquence de leur apparition est proche du minimum théorique. Dans... ... Wikipédia

hachage lors de la résolution de problèmes en C++.

Le processus de recherche de données dans de grands volumes d'informations prend du temps en raison de la nécessité de visualiser et de comparer un nombre important d'éléments avec la clé de recherche. La réduction de la recherche peut être effectuée en localisant la zone de visualisation. Par exemple, triez les données par clé de recherche, divisez-les en blocs qui ne se chevauchent pas selon certaines caractéristiques du groupe ou faites correspondre les données réelles avec un certain code qui simplifiera la procédure de recherche.

Actuellement, une méthode largement utilisée pour fournir un accès rapide aux informations stockées dans la mémoire externe est le hachage.

Hachage(ou hachage, Anglais hachage) est une transformation d'un tableau de données d'entrée d'un certain type et d'une longueur arbitraire en une chaîne de bits de sortie d'une longueur fixe. De telles transformations sont également appelées fonctions de hachage ou fonctions de convolution, et leurs résultats sont appelés hachage, code de hachage, table de hachage ou digérer messages (anglais) résumé du message).

Table de hachage- Ce Structure de données, qui implémente l'interface de tableau associatif, c'est-à-dire qu'il permet de stocker des paires clé-valeur et d'effectuer trois opérations : l'opération d'ajout d'une nouvelle paire, l'opération de recherche et l'opération de suppression d'une paire par clé. Une table de hachage est un tableau formé dans un ordre spécifique par une fonction de hachage.

• la fonction doit être simple d'un point de vue informatique ;
• la fonction doit répartir les clés dans la table de hachage aussi uniformément que possible ;
• la fonction ne doit mapper aucune relation entre les valeurs clés dans une relation entre les valeurs d'adresse ;
• la fonction doit minimiser le nombre de collisions, c'est-à-dire les situations où différentes clés correspondent à la même valeur de hachage (les clés dans ce cas sont appelées synonymes).

Dans ce cas, la première propriété d'une bonne fonction de hachage dépend des caractéristiques de l'ordinateur et la seconde des valeurs des données.

Si toutes les données étaient aléatoires, les fonctions de hachage seraient très simples (par exemple, quelques bits de clé). Cependant, en pratique, les données aléatoires sont suffisamment rares pour qu'il soit nécessaire de créer une fonction qui dépend de la clé entière. Si une fonction de hachage distribue une population clés possibles uniformément sur plusieurs index, le hachage divise efficacement plusieurs clés. Le pire des cas est lorsque toutes les clés sont hachées dans un seul index.

Lorsque des collisions se produisent, il est nécessaire de trouver un nouvel emplacement pour stocker les clés revendiquant la même cellule de la table de hachage. De plus, si les collisions sont autorisées, leur nombre doit être minimisé. Dans certains cas particuliers, il est possible d’éviter complètement les collisions. Par exemple, si toutes les clés d'éléments sont connues à l'avance (ou changent très rarement), alors une fonction de hachage injective peut être trouvée pour elles qui les distribuera dans les cellules de la table de hachage sans collisions. Les tables de hachage qui utilisent des fonctions de hachage similaires n'ont pas besoin d'un mécanisme de résolution de collision et sont appelées tables de hachage avec adressage direct.

Les tables de hachage doivent correspondre aux éléments suivants propriétés.

• Effectuer une opération sur une table de hachage commence par calculer la fonction de hachage de la clé. La valeur de hachage résultante est un index dans le tableau d'origine.
• Le nombre d'éléments de tableau stockés divisé par le nombre de valeurs de hachage possibles est appelé facteur de remplissage de la table de hachage (facteur de charge) et constitue un paramètre important dont dépend le temps d'exécution moyen des opérations.
• Les opérations de recherche, d'insertion et de suppression doivent être effectuées en moyenne en un temps O(1). Cependant, cette estimation ne prend pas en compte les coûts matériels possibles liés à la reconstruction de l'index de la table de hachage associés à l'augmentation de la valeur de la taille du tableau et à l'ajout d'une nouvelle paire à la table de hachage.
• Le mécanisme de résolution des collisions est un élément important de toute table de hachage.

Le hachage est utile lorsqu'un large éventail de valeurs possibles doit être stocké dans une petite quantité de mémoire et qu'un moyen d'accès rapide et quasi aléatoire est nécessaire. Les tables de hachage sont souvent utilisées dans les bases de données, et notamment dans processeurs de langage tels que les compilateurs et les assembleurs, où ils augmentent la vitesse de traitement de la table d'identifiants. Des exemples d'utilisation du hachage dans la vie quotidienne incluent la répartition des livres d'une bibliothèque dans des catalogues thématiques, le classement dans les dictionnaires par les premières lettres des mots, le cryptage des spécialités dans les universités, etc.

Méthodes de résolution des collisions

Les collisions compliquent l'utilisation des tables de hachage car elles rompent la correspondance unique entre les codes de hachage et les données. Il existe cependant des moyens de surmonter les difficultés qui surviennent :

• méthode de chaînage (hachage externe ou ouvert) ;
• méthode d'adressage ouverte (hachage fermé).

Méthode en chaîne. La technologie d'adhésion des éléments est celle éléments de l'ensemble, qui correspondent à la même valeur de hachage, sont liés dans une liste de chaînes. Le numéro de position i stocke un pointeur vers la tête de la liste des éléments dont la valeur de hachage de clé est égale à i ; s'il n'y a pas de tels éléments dans l'ensemble, NULL est écrit à la position i. En figue. La figure 38.1 montre la mise en œuvre de la méthode de chaînage pour résoudre les collisions. La clé 002 est revendiquée par deux valeurs, organisées en une liste linéaire.

Riz. 38.1.

Chaque cellule du tableau est un pointeur vers une liste chaînée (chaîne) de paires clé-valeur correspondant à la même valeur de hachage de la clé. Les collisions entraînent simplement des chaînes plus longues qu'un élément.

Les opérations de recherche ou de suppression nécessitent de visualiser tous les éléments de la chaîne correspondante afin de trouver un élément contenant une clé donnée. Pour ajouter des données, vous devez ajouter un élément à la fin ou au début de la liste correspondante et, si le facteur de remplissage devient trop grand, augmenter la taille du tableau et reconstruire la table.

En supposant que chaque élément peut tomber dans n'importe quelle position du tableau avec une probabilité égale et quel que soit l'endroit où se trouve tout autre élément,

Méthodes de compression des données converties basées sur des fonctions de hachage unidirectionnelles

Une fonction de hachage (hash, hash-function) est une transformation qui obtient une certaine valeur (convolution) d'une longueur fixe à partir de données de longueur arbitraire. Les exemples les plus simples sont les sommes de contrôle (par exemple crc32). Il y a:

· hachages cryptographiques ;

· Hachages du programmeur.

Un hachage cryptographique diffère d'un hachage de programmeur par les deux propriétés suivantes : l'irréversibilité et l'absence de collision. Dénoter:

m - données initiales,

h(m) est une fonction de hachage d'eux.

L'irréversibilité signifie que si le nombre h0 est connu, alors il est difficile de choisir m tel que h(m) = h0.

Sans collision signifie qu'il est difficile de trouver m1 et m2 tels que m1 ne soit pas égal à m2, mais h(m1) = h(m2).

Les fonctions de hachage cryptographique sont divisées en deux classes :

Fonctions de hachage sans clé (codes MDC (Modification (Manipulation) Detect Code)),

Fonctions de hachage avec une clé (codes MAC (Message Authentication Code)).

Les fonctions de hachage sans clé sont divisées en deux sous-classes : les fonctions de hachage faibles et les fonctions de hachage fortes.

Une fonction de hachage faible est une fonction unidirectionnelle H(x) qui satisfait aux conditions suivantes :

1. l'argument x peut être une chaîne de bits de longueur arbitraire ;

2. la valeur de h(x) doit être une chaîne de bits de longueur fixe ;

3. la valeur de h(x) est facile à calculer ;

4. pour tout x fixe, il est impossible par calcul de trouver un autre x" ≠ x tel que h(x")=h(x).

La paire x" ≠ x lorsque h(x")=h(x) est appelée collision de fonctions de hachage.

Une fonction de hachage forte est une fonction unidirectionnelle h(x) qui satisfait aux conditions 1 à 4 pour une fonction de hachage faible et à la propriété 5 :

5. Il est informatiquement impossible de trouver une paire x" ≠ x telle que h(x")=h(x).
Puisqu'il résulte des propriétés 1 et 2 que l'ensemble de définitions d'une fonction de hachage est beaucoup plus large que l'ensemble des valeurs, des collisions doivent exister. La propriété 4 exige que les trouver pour une valeur donnée de x soit presque impossible. L'exigence 5 indique qu'il est informatiquement impossible pour une fonction de hachage forte de trouver une quelconque collision.

Il existe plusieurs algorithmes pour calculer les fonctions de hachage

MD2 (Message Digest) est un algorithme de réduction cryptographique. Produit un bloc de 128 bits à partir d'un message de longueur arbitraire. Schéma général de fonctionnement du MD2 :

un. remplir le texte du message à une longueur qui est un multiple de 128 bits ;

b. calcul d'une somme de contrôle de 16 bits, les bits les plus significatifs sont ignorés ;

c. ajouter une somme de contrôle au texte ;

d. recalcul de la somme de contrôle.

L'algorithme MD2 est très lent, c'est pourquoi MD4, MD5, SHA (Secure Hash Algorithm) sont plus souvent utilisés. Le hachage résultant fait 160 bits.

GOST R34.11-94. Algorithme russe. La longueur de la convolution est de 256 bits (très pratique pour générer une clé pour GOST 28147-89 à l'aide d'un mot de passe).

L'Institut national américain des normes et technologies (NIST) a publié sur son site Web http://www.nist.gov/sha/ les spécifications des nouveaux algorithmes de hachage SHA-256, SHA-384 et SHA-512, dont le but est pour fournir un niveau de force cryptographique de hachage, correspondant aux longueurs de clé de la nouvelle norme de cryptage DES.

Rappelons qu'un hachage de n bits est un mappage d'un message de longueur arbitraire dans une séquence pseudo-aléatoire de n bits (valeur de hachage). Un hachage cryptographique, en tant que type spécial d'une telle fonction, est un hachage de n bits qui possède les propriétés d'« unidirectionnalité » et de « résistance aux collisions ».

Jusqu'à présent, les fonctions de hachage les plus populaires étaient MD4 et MD5, créées par Raivist, qui génèrent des codes de hachage de longueur n=128, et l'algorithme SHA-1, développé par la NSA américaine, qui génère des codes de hachage de longueur n=160. .

GOST R34.10-94 « Procédures de développement et de vérification d'une signature numérique électronique basée sur un algorithme cryptographique asymétrique. »