Algorithmes de hachage
- Sécurité des informations
Comme je le pense, beaucoup savent que depuis 2007, le National Institute of Standards and Technology (NIST) des États-Unis organise un concours pour développer un algorithme de hachage pour remplacer SHA-1 et la famille d'algorithmes SHA-2. mais ce sujet, pour une raison quelconque, est privé d'attention sur le site. En fait, cela m'a conduit à vous. Je porte à votre attention une série d'articles sur les algorithmes de hachage. Dans cette série, nous étudierons ensemble les bases des fonctions de hachage, examinerons les algorithmes de hachage les plus célèbres, plongerons dans l'atmosphère de la compétition SHA-3 et examinerons les algorithmes qui prétendent y gagner, nous les testerons certainement. De plus, si possible, les normes de hachage russes seront prises en compte.
À propos de moi
Étudiant du Département de la sécurité de l'information.À propos du hachage
Actuellement, pratiquement aucune application de cryptographie n'est complète sans l'utilisation du hachage.Les fonctions de hachage sont des fonctions conçues pour « compresser » un message ou un ensemble de données arbitraires, généralement écrits dans un alphabet binaire, en un motif binaire de longueur fixe appelé convolution. Les fonctions de hachage ont diverses utilisations dans les expériences statistiques, dans le test de dispositifs logiques, dans la construction d'algorithmes. recherche rapide et vérifier l'intégrité des enregistrements dans les bases de données. La principale exigence pour les fonctions de hachage est l'uniformité de la distribution de leurs valeurs pour une sélection aléatoire des valeurs de l'argument.
Une fonction de hachage cryptographique est toute fonction de hachage qui est cryptographiquement forte, c'est-à-dire qui satisfait un certain nombre d'exigences spécifiques aux applications cryptographiques. En cryptographie, les fonctions de hachage sont utilisées pour résoudre les problèmes suivants :
- construire des systèmes de contrôle de l'intégrité des données lors de leur transfert ou de leur stockage,
- authentification des sources de données.
Toute fonction est appelée fonction de hachage h : X -> Y, facilement calculable et tel que pour tout message M valeur h (M) = H (convolution) a une longueur de bit fixe. X- beaucoup de tous les messages, Oui- un ensemble de vecteurs binaires de longueur fixe.
En règle générale, les fonctions de hachage sont construites sur la base des fonctions de compression en une étape y = f (x 1, x 2) deux variables, où x 1, x 2 et oui- vecteurs binaires de longueur m, m et m respectivement, et m est la longueur de la circonvolution, et m- la longueur du bloc de message.
Pour obtenir la valeur h (M) le message est d'abord divisé en blocs de longueur m(dans ce cas, si la longueur du message n'est pas un multiple de m puis le dernier bloc est complété d'une manière spéciale pour terminer), puis aux blocs résultants M 1, M 2, .., M N appliquer la procédure de calcul de convolution séquentielle suivante :
H o = v,
H i = f (M i, H i-1), i = 1, .., N,
h (M) = H N
Ici v- une constante, souvent appelée vecteur d'initialisation. elle sort
pour diverses raisons et peut être une constante secrète ou un ensemble de données aléatoires (échantillon de date et d'heure, par exemple).
Avec cette approche, les propriétés de la fonction de hachage sont complètement déterminées par les propriétés de la fonction de contraction en une étape.
Il existe deux types importants de fonctions de hachage cryptographique : à clé et sans clé. Les fonctions de hachage de clé sont appelées codes d'authentification de message. Ils permettent, sans moyens supplémentaires, de garantir à la fois l'exactitude de la source de données et l'intégrité des données dans des systèmes avec des utilisateurs qui se font confiance.
Les fonctions de hachage sans clé sont appelées codes de détection d'erreur. Ils permettent à l'aide de moyens supplémentaires (cryptage par exemple) de garantir l'intégrité des données. Ces fonctions de hachage peuvent être utilisées dans des systèmes avec des utilisateurs confiants et méfiants.
À propos des propriétés et des exigences statistiques
Comme je l'ai déjà dit, la principale exigence pour les fonctions de hachage est la distribution uniforme de leurs valeurs pour une sélection aléatoire des valeurs d'argument. Pour les fonctions de hachage cryptographiques, il est également important que le moindre changement dans l'argument modifie beaucoup la valeur de la fonction. C'est ce qu'on appelle l'effet d'avalanche.
À fonctions clés le hachage a les exigences suivantes :
- impossibilité de fabrication,
- impossibilité de modification.
La première exigence signifie qu'il est très difficile de trouver un message avec la valeur de pliage correcte. La seconde est la grande complexité de la correspondance pour un message donné avec une valeur de pliage connue d'un autre message avec la valeur de pliage correcte.
Les exigences suivantes sont imposées aux fonctions sans clé :
- l'unidirectionnalité,
- résistance aux collisions,
- résistance à trouver la deuxième préimage.
L'unidirectionnalité est comprise comme la grande complexité de trouver un message par une valeur de convolution donnée. Il faut noter que sur ce moment aucune fonction de hachage utilisée avec une unidirectionnalité prouvée.
La résistance aux collisions fait référence à la difficulté de trouver une paire de messages avec les mêmes valeurs de pliage. Habituellement, c'est la découverte par les cryptanalystes d'une méthode pour construire des collisions qui sert de premier signal que l'algorithme est obsolète et la nécessité de le remplacer bientôt.
La résistance à trouver la deuxième préimage est comprise comme la complexité de trouver un deuxième message avec la même valeur de convolution pour un message donné avec une valeur de convolution connue.
C'était une partie théorique qui nous sera utile dans le futur...
À propos des algorithmes de hachage populaires
Algorithmes CRC16 / 32- somme de contrôle (pas de conversion cryptographique).
Algorithmes MD2 / 4/5/6... Ils sont la création de Ron Rivest, l'un des auteurs de l'algorithme RSA.
L'algorithme MD5 était autrefois très populaire, mais les premières conditions préalables au piratage sont apparues à la fin des années 90, et maintenant sa popularité décline rapidement.
L'algorithme MD6 est un algorithme très intéressant d'un point de vue constructif. Il a été nominé pour le concours SHA-3, mais, malheureusement, les auteurs n'ont pas eu le temps de le mettre à niveau, et cet algorithme est absent de la liste des candidats passés au second tour.
Algorithmes de règle SHA Algorithmes largement utilisés maintenant. Il y a une transition active des normes de version SHA-1 à SHA-2. SHA-2 est le nom collectif des algorithmes SHA224, SHA256, SHA384 et SHA512. SHA224 et SHA384 sont essentiellement des analogues de SHA256 et SHA512, respectivement, seulement après avoir calculé la convolution, certaines des informations qu'il contient sont supprimées. Ils ne doivent être utilisés que pour assurer la compatibilité avec des équipements plus anciens.
Standard russe - GOST 34.11-94.
Dans le prochain article
Présentation des algorithmes MD (MD4, MD5, MD6).
Littérature
A.P. Alferov, Fondements de la cryptographie.
Bruce Schneier, Cryptographie appliquée.
Pour résoudre le problème de trouver l'élément nécessaire parmi les données volumineuses, un algorithme a été proposé hachage (hachage- brassage), dans lesquelles des clés sont créées qui déterminent les données du tableau et, en fonction de celles-ci, les données sont écrites dans une table appelée table de hachage ... Les clés d'enregistrement sont définies à l'aide de la fonction je = h(clé) appelé fonction de hachage ... L'algorithme de hachage détermine la position de l'élément souhaité dans la table de hachage par la valeur de sa clé obtenue par la fonction de hachage.
Concept hachage - c'est une division d'un ensemble commun (de base) de clés uniques d'éléments de données en ensembles disjoints avec une certaine propriété.
Prenez un dictionnaire ou une encyclopédie, par exemple. 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 spéciale d'adressage des données pour une récupération rapide. les informations dont vous avez besoin par clés .
Si un ensemble de base contient Néléments, alors il peut être divisé en 2 N différents 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 (indices dans la table - table de hachage ) est appelé fonction de hachage , ou alors fonction de hachage :
je = h(clé);
Où clé- la clé à convertir, je- l'indice résultant de la table, c'est-à-dire la clé correspond à 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 donner la même valeur de position je dans la table. Une situation dans laquelle deux clés ou plus obtiennent 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 sur l'ensemble de la table, et une fonction de hachage parfaite est une fonction qui ne génère pas de collisions :
Il existe deux manières de résoudre les collisions de hachage :
- méthode d'adressage ouverte avec palpage linéaire ;
- par la méthode des chaînes.
Table de hachage
La table de hachage est un tableau ordinaire 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 direct rapide aux données par index.
Il existe de nombreux schémas de hachage, différant par le choix d'une bonne fonction h(clé) et l'algorithme de résolution des conflits. L'efficacité de la résolution d'un problème pratique réel dépendra de manière significative 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 sur les index existants sur la table. Bien entendu, il est impossible de déterminer si une fonction de hachage particulière distribuera correctement les clés si les clés ne sont pas connues à l'avance. Cependant, bien que les clés elles-mêmes soient rarement connues avant de choisir une fonction de hachage, certaines des propriétés de ces clés qui affectent leur distribution sont généralement connues. Considérons les méthodes les plus courantes pour définir une fonction de hachage.
Méthode de division... Les données initiales sont - une clé entière clé et la taille de la table m... Le résultat de cette fonction est le reste de la division de cette clé par la taille de la table. Vue générale de la fonction :
int h (touche 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 fonction de hachage renvoie les deux chiffres les moins significatifs de la clé.
Méthode additive où la clé est une chaîne de caractères. La fonction de hachage convertit une chaîne en un entier en additionnant tous les caractères et renvoie le reste de la division par m(généralement la taille de la table m= 256).
int h (caractère *, int m) (
Des collisions se produisent sur des chaînes contenant le 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 le premier et le dernier caractère de la chaîne de clé.
int h (caractère *, 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 chaînes, par exemple, abc et amc.
Méthode du carré moyen, 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 les 10 bits du milieu de son carré :
int h (touche int) (
touche >> = 11 ; // Ignorer les 11 bits les moins significatifs
clé de retour% 1024 ; // Retourne les 10 bits les moins significatifs
Méthode OU exclusif pour les clés de ligne (généralement la taille de la table m= 256). Cette méthode est similaire à la méthode additive, mais elle différencie les mots similaires. La méthode consiste dans le fait que l'opération "OU exclusif" est séquentiellement appliquée 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 de la table m, alors toute la partie du produit résultant donnera une valeur comprise entre 0 et m–1.
int h (touche int, int m) (
double r = clé * rnd ();
r = r - (entier) r; // Partie fractionnaire allouée
Dans le cas général, pour grandes valeurs m les index générés par la fonction de hachage varient considérablement. De plus, la théorie mathématique prétend 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éfinit uniquement la position à partir de laquelle rechercher (ou initialement - placer dans la table) un enregistrement avec une clé clé... Par conséquent, le schéma de hachage doit inclure algorithme de résolution de conflit définir l'ordre des actions si la position je = h(clé) s'avère être un enregistrement déjà occupé avec une clé différente.
Il hacher Fonction de hachage
Trouvé sur la liste.
hachage lors de la résolution de problèmes en C++.Le processus de recherche de données dans de grandes quantités d'informations prend du temps, ce qui est dû à la nécessité de visualiser et de comparer un nombre important d'éléments avec la clé de recherche. La recherche peut être raccourcie en localisant la zone de visualisation. Par exemple, triez les données par la clé de recherche, divisez-les en blocs qui ne se chevauchent pas selon un critère de groupe ou mettez un code en correspondance avec les données réelles qui simplifieront la procédure de recherche.
Actuellement, une méthode répandue de fourniture accès rapide aux informations stockées dans mémoire externe- hachage.
Hachage(ou alors hachage, ing. hachage) Est une conversion 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 aussi appelées fonctions de hachage ou des fonctions de convolution, et leurs résultats sont appelés hachage, code de hachage, table de hachage ou alors digérer messages (eng. résumé de message).
Table de hachage- c'est Structure de données, qui implémente l'interface tableau associatif, c'est-à-dire qu'elle 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 en termes de calcul ;
- la fonction doit distribuer 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 à 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 (dans ce cas, les clés 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 dépend des valeurs des données.
Si toutes les données étaient aléatoires, alors les fonctions de hachage seraient très simples (par exemple, quelques bits de la clé). Cependant, en pratique, les données aléatoires sont assez rares, et vous devez créer une fonction qui dépendrait de la clé entière. Si la fonction de hachage alloue une collection clés possibles uniformément sur l'ensemble d'indices, puis le hachage divise efficacement l'ensemble de clés. Le pire des cas est lorsque toutes les clés sont hachées dans un seul index.
En cas de collisions, il est nécessaire de trouver un nouvel emplacement pour stocker les clés qui réclament 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, les collisions peuvent être complètement évitées. Par exemple, si toutes les clés des éléments sont connues à l'avance (ou changent très rarement), alors une fonction de hachage injective peut être trouvée pour eux, qui les répartira entre les cellules de la table de hachage sans collisions. Les tables de hachage utilisant de telles fonctions de hachage n'ont pas besoin de 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.
- L'opération dans la table de hachage commence par le calcul de la fonction de hachage à partir de la clé. La valeur de hachage résultante est l'index dans le tableau d'origine.
- Le nombre d'éléments de tableau stockés divisé par le nombre de valeurs possibles de la fonction de hachage est appelé facteur de remplissage de la table de hachage (facteur de charge) et est 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 dans un temps O (1). Cependant, cette estimation ne prend pas en compte les coûts matériels possibles de la reconstruction de l'index de la table de hachage associé à l'augmentation de la valeur de la taille du tableau et à l'ajout d'une nouvelle paire à la table de hachage.
- La résolution des collisions est une partie importante 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'une méthode 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 en particulier dans processeurs de langage tels que les compilateurs et les assembleurs, où ils accélèrent le traitement de la table d'ID. Comme l'utilisation du hachage dans la vie quotidienne, on peut donner des exemples de répartition des livres en bibliothèque selon des catalogues thématiques, de classement dans les dictionnaires par les premières lettres des mots, de cryptage de 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 violent la correspondance sans ambiguïté entre les codes de hachage et les données. Cependant, il existe 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 de chaînage... La technologie d'adhérence des éléments est celle éléments de l'ensemble qui correspondent à la même valeur de hachage sont chaînés sous forme de liste. 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 en position i. En figue. 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, qui sont organisées en une liste linéaire.
Figure. 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 clé. Les collisions se traduisent simplement par des chaînes de plus d'un élément de longueur.
Trouver ou supprimer des données nécessite de parcourir tous les éléments de la chaîne correspondante afin d'y trouver un élément avec 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 important, augmenter la taille du tableau et reconstruire le tableau.
En supposant que chaque élément peut aller à n'importe quelle position dans le tableau avec une probabilité égale et indépendamment de l'endroit où tout autre élément est allé,
Ou alors La fonction de hachage est fonction, transforme les données d'entrée de n'importe quelle taille (généralement grande) en données de taille fixe. Hachage(parfois r yeshuvannya, ing. Hachage)- conversion 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 aussi appelées fonctions de hachage ou alors fonctions de convolution, et leurs résultats sont appelés hash, code de hachage, somme de hachage, ou alors messages de résumé(eng. Résumé du message).
La fonction de hachage est notamment utilisée dans les structures de données - tables de hachage, est largement utilisée dans Logiciel pour trouver rapidement des données. Les fonctions de hachage sont utilisées pour optimiser les tables et les bases de données en ayant les mêmes valeurs de hachage dans les mêmes enregistrements. Cette approche de recherche de doublons est efficace dans les fichiers grande taille... Un exemple de cette découverte de sites similaires dans des séquences d'ADN. Une fonction de hachage cryptographique permet de vérifier facilement qu'une entrée correspond à une valeur de hachage donnée, mais si l'entrée est inconnue, il est délibérément difficile de reconstruire la valeur d'entrée (ou une alternative équivalente) en connaissant la valeur de hachage stockée. Ceci est utilisé pour assurer l'intégrité des données transmises et constitue le bloc de construction des HMAC, qui fournissent l'authentification des messages.
Les fonctions de hachage sont associées (et sont souvent confondues) avec les sommes, les chiffres de contrôle, les empreintes digitales, la randomisation des fonctions, les codes, la correction d'erreurs et les chiffrements. Bien que ces concepts se chevauchent dans une certaine mesure, chacun a sa propre portée et ses propres exigences et est conçu et optimisé de différentes manières.
Histoire
Donald Knuth attribue la première idée systématique de hachage à l'employé d'IBM Hans Peter Lohn, qui a proposé le hachage en janvier 1953.
En 1956, Arnold Dumy, dans son ouvrage Computers and Automation, a été le premier à introduire le concept de hachage tel que la plupart des programmeurs le connaissent aujourd'hui. Doom considérait le hachage comme une solution au "problème du dictionnaire", et a également suggéré d'utiliser le reste de la division par un nombre premier comme adresse de hachage.
Le premier travail important qui a été associé à la recherche dans gros fichiers, il y avait un article de Wesley Peterson dans Revue IBM de recherche et développement 1957 dans laquelle il a défini l'adressage ouvert, et a également souligné la dégradation des performances lors de la suppression. Six ans plus tard, le travail de Werner Buchholz a été publié, qui a largement exploré les fonctions de hachage. Le hachage a été largement utilisé au cours des années suivantes, mais aucun travail significatif n'a été publié.
En 1967, le hachage au sens moderne a été mentionné dans le livre d'Herbert Hellerman Principles of Digital systèmes informatiques". En 1968, Robert Morris publie dans Communication de l'ACM bon aperçu sur le hachage. Cet ouvrage est considéré comme une publication qui introduit le concept de hachage dans la circulation scientifique et consolide enfin le terme « hachage » chez les spécialistes.
Au début des années 1990, l'équivalent du terme "hachage", grâce aux travaux d'Andrey Ershov, était le mot "constellation" dans l'édition en langue russe du livre de Niklaus Wirth "Algorithmes et structures de données" (1989) ce terme est utilisé.) Cependant, aucune de ces options ne s'est imposée, et dans la littérature, le terme "hachage" est principalement utilisé.
La description
Le hachage est utilisé pour créer des tableaux associatifs, rechercher des doublons dans des séries d'ensembles de données, créer des identifiants uniques pour les ensembles de données, une somme de contrôle pour détecter des erreurs accidentelles ou délibérées lors du stockage ou de la transmission, pour stocker des mots de passe dans des systèmes de sécurité (dans ce cas, l'accès au zone mémoire " mémoire, où se trouvent les mots de passe, ne permet pas de récupérer le mot de passe lui-même), lors de la génération d'une signature électronique (en pratique, ce n'est souvent pas le message lui-même qui est signé, mais son image de hachage).
Dans le cas général, il n'y a pas de correspondance biunivoque entre les données d'origine et le code de hachage du fait que le nombre de valeurs de fonctions de hachage est inférieur au nombre de variantes de valeurs de l'entrée déployer. Il existe de nombreux tableaux avec des contenus différents, mais ils donnent les mêmes codes de hachage - les soi-disant collisions. La probabilité de collisions joue un rôle important dans l'évaluation de la qualité des fonctions de hachage.
Il existe de nombreux algorithmes de hachage avec des propriétés différentes (profondeur de bits, complexité de calcul, force cryptographique, etc.). Le choix d'une fonction de hachage particulière 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.
Types de fonctions de hachage
Une bonne fonction de hachage doit satisfaire deux propriétés :
- Calculez rapidement;
- Minimiser le nombre de collisions
Disons, pour plus de précision, que le nombre de clés et la fonction de hachage n'ont que des valeurs différentes :
Un exemple d'une "mauvaise" fonction de hachage est la fonction c, qui correspond à un nombre naturel à dix chiffres avec trois chiffres, sélectionné à partir du milieu du carré à vingt chiffres du nombre. Il semblerait que la valeur des codes de hachage doive être uniformément répartie entre "000" et "999", mais pour des données réelles, cette méthode ne convient que si les touches n'ont pas un grand nombre de zéros à gauche ou à droite.
Cependant, il existe plusieurs autres méthodes simples et fiables sur lesquelles sont basées de nombreuses fonctions de hachage.
Fonctions de hachage basées sur les divisions
La première méthode est ce que nous utilisons comme hachage - le reste de la division par, où est le nombre de tous les hachages possibles :
En même temps, il est évident qu'avec une paire, le mode d'économie est jumelé, avec une paire. Et impair - avec impair, ce qui peut entraîner un décalage important des données dans les fichiers. De plus, vous ne devez pas utiliser le système de numération de l'ordinateur comme base, car le hachage ne dépendra que de quelques chiffres du nombre de droite, ce qui entraînera de nombreuses collisions. En pratique, le simple est généralement choisi - dans la plupart des cas, ce choix est tout à fait satisfaisant.
Il faut aussi parler de la méthode de hachage, qui est basée sur la division par log modulo deux. DANS cette méthode doit également être une puissance de deux, et les clés binaires () ont la forme de polynômes. Dans ce cas, les valeurs des coefficients du polynôme obtenus comme reste de la division par un degré polynomial présélectionné sont prises comme code de hachage :
Lorsque le bon choix cette méthode garantit qu'il n'y a pas de collisions entre des clés presque identiques.
Schéma de hachage multiplicatif
La deuxième méthode consiste à choisir une constante entière, premier avec, où est le nombre options possibles valeurs sous forme de mot machine (en ordinateurs IBM PC). On peut alors prendre une fonction de hachage de la forme :
Dans ce cas, sur un ordinateur avec système binaire calcul, est une puissance de deux et se compose des bits les plus significatifs de la moitié droite du produit.
Parmi les avantages de ces deux méthodes, il convient de noter qu'elles profitent du fait que les vraies clés ne sont pas aléatoires. Par exemple, si les touches représentent une progression arithmétique (disons la séquence de noms "nom1", "nom2", "nom3"). La méthode multiplicative affichera une progression arithmétique en une progression arithmétique approximative de diverses valeurs de hachage, réduisant le nombre de collisions par rapport à une situation aléatoire.
L'une des variantes de cette méthode est le hachage de Fibonacci, basé sur les propriétés du nombre d'or. Ici l'entier le plus proche de, premier avec
Hachage de chaînes de longueur variable
Les méthodes ci-dessus sont également utilisées lorsque nous devons considérer des clés composées de plusieurs mots ou des clés de longueur variable. Par exemple, vous pouvez combiner des mots en un seul en utilisant l'addition modulo ou l'addition modulo 2. L'un des algorithmes qui fonctionne sur ce principe est la fonction de hachage de Pearson.
Le hachage Pearson est un algorithme proposé par Peter Pearson. Peter Pearson) pour les processeurs avec des registres de 8 bits, dont la tâche est de calculer rapidement le code de hachage pour une chaîne de longueur arbitraire. La fonction reçoit un mot composé de caractères de 1 octet chacun et renvoie une valeur comprise entre 0 et 255. La valeur du code de hachage dépend de chaque caractère du mot d'entrée.
L'algorithme peut être décrit par le pseudocode suivant, qui prend une chaîne en entrée et utilise une table de permutation
h : = 0 Pour chaque c dans W boucle indice : = h xor ch : = T Fin de boucle Revenir h
Parmi les avantages de l'algorithme, il convient de noter :
- facilité de calcul;
- il n'y a pas de données d'entrée pour lesquelles la probabilité de collision est la plus élevée ;
- la possibilité de modification en une fonction de hachage idéale.
Comme manière alternative clés de hachage constituées de caractères (), on peut suggérer des calculs
Utilisation des fonctions de hachage
Les fonctions de hachage sont largement utilisées en cryptographie ainsi que dans de nombreuses structures de données telles que les tables de hachage, les filtres Bloom et les arbres cartésiens.
Fonctions de hachage cryptographique
Parmi les nombreuses fonctions de hachage existantes, il est d'usage de distinguer celles qui sont cryptographiquement fortes utilisées en cryptographie, car des exigences supplémentaires leur sont imposées. Pour qu'une fonction de hachage soit considérée comme sécurisée du point de vue cryptographique, elle doit satisfaire à trois exigences de base sur lesquelles reposent la plupart des utilisations des fonctions de hachage en cryptographie :
- Irréversibilité : pour une valeur de hachage donnée m il doit être informatiquement impossible de trouver le bloc de données pour lequel.
- Durabilité collisions du premier type : pour un message donné M il doit être informatiquement impossible d'en récupérer un autre un message N pour lequel.
- Durabilité à collisions deuxième type : il doit être informatiquement impossible de trouver une paire de messages qui ont le même hachage.
Ces exigences dépendent les unes des autres :
- La fonction inverse n'est pas résistante aux collisions du premier et du deuxième type.
- Fonction non résistante aux collisions du premier type, non résistante aux collisions du second type ; L'inverse est pas vrai.
Il est à noter que l'existence de fonctions de hachage irréversibles n'a pas été prouvée, pour lesquelles il est théoriquement impossible de calculer une quelconque pré-image d'une valeur de hachage donnée. Habituellement, trouver la réciproque n'est qu'une tâche difficile en termes de calcul.
L'attaque d'anniversaire vous permet de trouver des collisions pour une fonction de hachage avec des valeurs de longueur m bits en moyenne pour un calcul approximatif de hachage. donc n- une fonction de hachage binaire est considérée comme cryptique si la complexité de calcul pour trouver des collisions est proche.
Pour les fonctions de hachage cryptographique, il est également important qu'au moindre changement d'argument, la valeur de la fonction change fortement (effet d'avalanche). En particulier, la valeur de hachage ne doit pas divulguer d'informations, même sur des bits individuels de l'argument. Cette exigence est la clé de la force cryptographique des algorithmes de hachage qui hache le mot de passe de l'utilisateur pour obtenir la clé.
Le hachage est souvent utilisé dans les algorithmes signature numérique, où ce n'est pas le message lui-même qui est crypté, mais son hachage, ce qui réduit le temps de calcul et augmente également la force cryptographique. De plus, dans la plupart des cas, au lieu des mots de passe, les valeurs de leurs codes de hachage sont stockées.
Hachage géométrique
Hachage géométrique (eng. hachage géométrique)- largement utilisé dans infographie et une méthode de géométrie computationnelle pour résoudre des problèmes dans un plan ou dans un espace tridimensionnel, par exemple, pour trouver les paires les plus proches dans un ensemble de points ou pour rechercher des images identiques. La fonction de hachage de cette méthode prend généralement un espace métrique en entrée et le divise, créant une grille de cellules. La table dans ce cas est un tableau avec deux indices ou plus et s'appelle un fichier de grille (eng. fichier de grille). Le hachage géométrique est également utilisé dans les télécommunications lorsqu'il s'agit de signaux multidimensionnels.
Accélération de la récupération des données
Une table de hachage est une structure de données qui permet de stocker des paires du formulaire (clé, code de hachage) et prend en charge les opérations de recherche, d'insertion et de suppression d'éléments. La tâche des tables de hachage est d'accélérer les recherches, par exemple, dans le cas d'enregistrements dans des champs de texte dans la base de données, leur code de hachage peut être calculé et les données peuvent être placées dans la section correspondant à ce code de hachage. Ensuite, lors de la recherche de données, il faudra d'abord calculer le hachage du texte et on saura immédiatement dans quelle section elles doivent être recherchées, c'est-à-dire qu'il ne sera pas nécessaire de rechercher dans toute la base de données, mais seulement dans l'une de ses sections (cela accélère grandement la recherche).
L'analogue quotidien 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 seulement la lettre souhaitée.
