Fonctions de hachage cryptographiques | Authentification des messages | Alison
Loading
Notes d'étude
Study Reminders
Support
Text Version

Fonctions de hachage et applications

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondations de la cryptographie Prof. Dr. Ashish Choudhury (ancienne) Infosys Foundation Career Development Chair Professeur Indian Institute of Technology – Bangalore Lecture – 30 Generic Attacks on Hash Functions and Additional Applications Hello everyone, welcome to this lecture. Juste un rapide récapitulation. Lors de la dernière conférence, nous avons vu comment utiliser la fonction de hachage résistant aux collisions pour créer des codes d'authentification de message pour les messages longs arbitraires. (Reportez-vous à la diapositive: 00:31) Ainsi, le plan de cette conférence est le suivant. Dans cette conférence, nous allons discuter des attaques d'anniversaire, qui est une classe d'attaques génériques qui peuvent être lancées contre n'importe quelle fonction de hachage et nous discuterons également des attaques d'anniversaire pour les petits espaces pour trouver des collisions dans des fonctions de hachage, et enfin, nous discuterons de certaines autres applications de fonctions de hachage à l'exception des codes d'authentification des messages. (Reportez-vous à la page Heure de la diapositive: 01 :03) Commet donc les attaques d'anniversaire pour trouver des collisions. Alors, imaginez que vous vous êtes donné une fonction de hachage déterministe qui est publiquement connue. Ensuite, l'algorithme naïf pour trouver une collision dans cette fonction de hachage est le suivant: vous pouvez évaluer cette fonction de hachage à 2l + 1 nombre d'entrées distinctes et il est garanti qu'avec 100% de succès vous obtiendrez une collision. La probabilité de succès de la collision est de 1. C'est à cause du principe pigeonhole car au mieux vous pouvez espérer que 2l entrées distinctes vont à 2l sorties distinctes, mais puisque vous évaluez une fonction de hachage à plus d'entrées que 2l entrées, alors il y aura certainement 2 entrées qui vous donneront la même valeur de hachage et qui vous donneront une collision. Donc, la probabilité de succès de cet algorithme de détection de collision na ï est 1, elle vous donne 100% de garantie de succès, mais malheureusement le temps de fonctionnement de cet algorithme naïf est de l'ordre de 2l et si l est important, alors bien sûr cet algorithme de détection de collision na ï n'est pas pratique. Alors maintenant, voyons une généralisation de cet algorithme naïf et la généralisation va comme suit: vous évaluez cette fonction de hachage à q entrées distinctes, que je dénote par x1, … xq et vous obtenez les valeurs de hachage et vous transmettez ces valeurs (entrée, sortie) et vérifiez si existe une paire (xi, xj) telle que vos valeurs de hachage sont identiques. Maintenant, nous sommes intéressés à discuter ici quelle est la probabilité de succès de cet algorithme généralisé? Alors, rappelez-vous si q est dit être 2l + 1, puis fondamentalement cet algorithme généralisé devient un algorithme naïf dans ce cas, la probabilité de succès est 1, mais maintenant votre q n'a pas besoin d'être 2l + 1. ça pourrait être n'importe quelle fonction et maintenant notre but est d'analyser la probabilité de succès de cet algorithme naïf en fonction de q et la taille de votre fonction de hachage. Donc, tout en faisant l'analyse, ce que nous supposerons, c'est que nous supposerons que la fonction H se comporte comme une fonction vraiment aléatoire, et pourquoi donc parce que c'est le meilleur que vous pouvez espérer. Parce que si votre fonction H se comporte comme une fonction vraiment aléatoire, c'est la tâche la plus difficile pour l'adversaire, où l'objectif de l'adversaire est de trouver une collision. Parce qu'il peut être prouvé que la probabilité de trouver une collision pour cet algorithme généralisé s'améliore si votre fonction sous-jacente H est une fonction non aléatoire et si au lieu de s'interroger sur des entrées distinctes x1 à xq, votre algorithme fait des requêtes pour un ensemble aléatoire de valeurs x. Donc, nous ne faisons pas de supposition plus forte en supposant que la fonction H est une fonction aléatoire parce que la probabilité de succès de cet algorithme naïf est limitée par la probabilité de succès que cet algorithme naïf qui vous donnera le cas où nous supposons que votre fonction sous-jacente H est une fonction aléatoire. (Référez-vous à la diapositive: 04:30) Alors, définissez le paramètre pour le cas généralisé ici. Donc, on vous donne une fonction vraiment aléatoire de l'ensemble des chaînes binaires à un domaine fixe où la taille du domaine est L et dire que vous avez fait q nombre de requêtes pour ces valeurs de hachage sur des entrées distinctes x1 à xq et que les valeurs de sortie correspondantes sont y1 à yq. Puisque je suppose que ma fonction de hachage est une fonction aléatoire, chacune de ces valeurs yi est des valeurs uniformément aléatoires de l'ensemble de valeurs N que ma fonction de hachage peut lancer en outputs.I indique l'événement Coll (q, N), l'événement qui =, où ≠ Mon but est de calculer une limite inférieure sur la probabilité de cet événement Coll (q, N). Donc, je veux prouver ici que si le nombre de requêtes que je fais ici est délimité par, alors Pr [ Coll (,) ] ≥ ((− 1)) /4. Voyons comment nous pouvons en dériver. Donc, laissez-moi signaler l'événement NoColli pour être l'événement lorsque nous avons fait les premières requêtes i, toutes les valeurs de sortie de hachage sont distinctes, cela signifie que les valeurs y1, y2, yi sont toutes distinctes. C'est le cas de H (x1), H (x2), … H (xi), ils sont tous distincts et aucune collision n'a eu lieu et c'est l'événement NoColli. Il est facile de voir que puisque nous faisons q nombre de requêtes, alors l'événement parce que si l'événement NoCollq se produit qui signifie toutes vos valeurs y y1, y2, yq sont distinctes et cela signifie qu'il n'existe pas de collision, que j'ai obtenu en exécutant par un algorithme généralisé. Il est donc facile de voir qu'en appliquant des règles de probabilité simples, nous obtenons la probabilité que l'événement Pr [ NoCollq ] = Pr [ NoColl1 ] * Pr [ NoColl2 | NoColl1 ] .. Pr [ NoCollq | NoCollq-1 ]. Cela signifie que les premières requêtes q-1 vous donnent une sortie distincte, quelle est la probabilité que l'événement lorsque vous faites la requête q, il n'existe toujours pas de collision. Si je multipliais toutes ces probabilités, j'obtiais la probabilité de l'événement NoCollq. Calculons donc chacune des probabilités qui sont là dans votre côté droit. Il est donc facile de voir clairement que l'événement NoColl1 se produit avec la probabilité 1 car lors de la première requête, aucune collision n'a eu lieu. Cela signifie que l'y1 est distinct. Donc je peux tout simplement désactiver ça, ignorer cette probabilité parce que c'est 1. Maintenant, calculons le terme de la moelle dans l'expression de votre côté droit. A savoir, calculons la probabilité Pr [ NoColli + 1 | NoColli ], c'est-à-dire que votre événement est le suivant: votre y1 ≠ y2 …. ≠ yi sont tous distincts qui vous sont données, et quand vous avez fait la requête pour xi + 1, vous avez obtenu yi + 1 et nous voulons analyser quelle est la probabilité que yi + 1 soit différente de toutes les valeurs y1 à yi. Il n'est pas difficile de voir que cette probabilité n'est rien d'autre que 1-i + 1, pourquoi? Parce que 1 – i/N indique la probabilité avec laquelle cette valeur i + 1ième peut être identique à au moins une de ces valeurs i et si vous soustrayez cette quantité de 1 qui vous donne la probabilité requise, et je peux toujours remplacer ce 1-i/N par e -i/N et ceci vient de votre inégalité de base du fait que 1 x peut toujours être délimité par e -x pour tous x. Alors maintenant, je connais la valeur de chacun des termes de mon côté droit, c'est ce que j'ai dérivé. Donc ce que je dois faire, c'est que je dois juste remplacer ici. Donc, j'ai obtenu que la probabilité que l'événement NoCollq se produise est le produit de ces entités et si je prends le produit dans l'exposant, en fait, je termine en faisant la sommation dans l'exposant. Donc, j'ai obtenu que même NoColli se trouve avec cette probabilité beaucoup, et si je prends la somme à l'intérieur, j'obtiens que c'est inférieur à e -q * (q-1 )/2N et ensuite je peux enfin le remplacer par cette inégalité. C'est parce que q * (q-1 )/2N est inférieur à N parce que je suppose que q est délimité par une racine carrée de 2N. Si c'est le cas, alors q * (q-1 )/2N est inférieur à N, et si c'est le cas, alors je peux utiliser le fait que e à la puissance -x est inférieur à égal à (1-x) /2. Donc en utilisant tous ces faits et en faisant les substitutions et en résolvant les inégalités, j'ai obtenu que l'événement NoColl se produit avec autant de probabilité, mais ce n'est pas notre but. Notre but est de calculer la probabilité de l'événement Coll (q, N) à se produire et puisque l'événement appelé NoCollq et l'événement complémentaire Coll (q, N) sont liés par ceci. Nous avons simplement obtenu que la probabilité de l'événement Coll (q, N) se produise au moins q * (q-1 )/ 4N. (Voir la diapositive: 10:38) Donc c'est la borne inférieure que nous avons établie ici en supposant que votre fonction H est une fonction aléatoire et nous avons évalué la fonction H à q valeurs x distinctes, et nous avons établi que la probabilité de collision est au moins aussi importante. Maintenant vous vous demandez peut-être pourquoi cet algorithme générique pour trouver la collision est appelé ou est donné une attaque d'anniversaire de nom de fantaisie. Fondamentalement, cela est dû au fait que l'analyse que nous avons effectuée peut modéliser le problème de la science informatique. Imaginez que vous avez un ensemble de q personnes assises dans une pièce qui sont l'ensemble aléatoire de personnes, et chacune d'elles a un anniversaire. Donc, vous pouvez imaginer que la fonction H ici n'est rien, mais c'est une fonction qui mappe les gens à leurs anniversaires et nous supposons que les anniversaires de la population tombent dans une année non bissantile. Ainsi, le nombre de jours de naissance du candidat, que ces personnes pourraient avoir, est de 365 valeurs possibles. Donc, vous avez q nombre de personnes, disons la personne 1, la personne 2, et la personne q et leurs anniversaires sont H (P1), H (P2), H (P3) et ainsi de suite. Nous voulons savoir quelle est la probabilité que parmi ces personnes, il y ait au moins 2 personnes qui ont le même anniversaire. Je ne suis pas intéressé par l'année, même je ne dispute pas la journée. Je n'ai pas besoin qu'ils aient dit la même année de naissance. Je suis juste curieux de savoir s'ils ont le même anniversaire ou pas et vous pouvez imaginer que la fonction H ici est de les mapper aux anniversaires. Donc, il s'avère que quelle que soit l'analyse que nous avons faite ici dans le contexte de la fonction de hachage, elle pourrait être réalisée même dans le contexte de ce problème d'anniversaire et il pourrait être prouvé que s'il y a 27 personnes au hasard dans la pièce, alors la chance qu'au moins 2 d'entre eux ont le même anniversaire est d'environ 50%, donc ce qui est une bonne probabilité. Vous n'avez pas besoin d'un grand nombre de personnes pour s'assurer qu'avec une bonne probabilité 2 personnes ont le même anniversaire. Revenir au contexte des fonctions de hachage cryptographiques, alors quelles sont exactement les implications de cette attaque d'anniversaire? Cela dit, imaginez que votre espace de co-domaine est 2l. Cela signifie que vos sorties de hachage peuvent être n'importe quelle chaîne de bits de l, alors ce qui est l'analyse de l'attaque d'anniversaire, c'est que si vous évaluez votre fonction de hachage à ces nombreux nombres d'entrées distinctes, à savoir 2l + 1 sur 2 nombres d'entrées distinctes. Si je remplace cette valeur de q ici dans cette expression et la valeur de n à être 2l, alors je trouve que la probabilité de la collision s'avère être une constante indépendante de la taille de l et une probabilité de succès constant est une probabilité assez bonne pour un adversaire de trouver une collision dans votre fonction de hachage sous-jacente dans un temps polynomial. Cela signifie que votre valeur de l doit être importante parce que si vous vous assurerez que votre valeur de l est importante pour que ces nombreuses requêtes soient nombreuses, l'adversaire doit faire une quantité de calcul peu pratique et cela va exclure les implications d'une attaque d'anniversaire. En théorie, les implications sont toujours là. C'est seulement que nous allons exploiter notre hachage sous-jacent avec une si grande valeur de l que réaliser ces nombreuses évaluations de hachage ne sera pas pratique, et c'est pourquoi une condition nécessaire à l'obtention d'une fonction de hachage résistante aux collisions est que vous devriez avoir une grande valeur de l. Parce que si l est petit, alors juste en faisant ces nombreuses requêtes, l'adversaire pourrait arriver avec une collision avec une probabilité presque constante de succès. C'est pourquoi la valeur minimale de l qui est recommandée pour les instanciations pratiques actuelles des fonctions de hachage est 256. Parce que si vous définissez l à être 256, alors fondamentalement l'adversaire a à faire des calculs de l'ordre 2 128 pour obtenir des collisions avec une probabilité de réussite constante, mais 2 128 calculs est vraiment une énorme quantité de calcul. (Référez-vous à la diapositive: 14:52) Alors, discutons maintenant d'un autre type d'attaque d'anniversaire, que nous appelons une petite attaque d'anniversaire pour trouver la collision. L'idée reste la même. Alors, rappelez-vous dans l'algorithme de détection de collision généralisé, nous avons évalué la fonction de hachage à q nombre d'entrées distinctes, et nous avons dû stocker toutes ces valeurs de hachage parce que lorsque nous comparons l'entrée x et vos valeurs de hachage pour savoir s'il existe une collision ou non, nous avons besoin de toutes les paires (xi, xj) et de leurs valeurs de hachage correspondantes. Il s'avère que la complexité de l'espace ici est de l'ordre q. Donc, si vous considérez dans les systèmes informatiques modernes, le temps n'est pas un problème, la vitesse de traitement n'est pas un problème, jour après jour, la vitesse de traitement augmente. Ce qui compte, c'est la complexité de l'espace parce que l'espace est vraiment une ressource très critique ici et c'est pourquoi ce qui sera intéressant ici, c'est de savoir si nous pouvons réaliser l'attaque d'anniversaire ou l'attaque d'anniversaire généralisée que nous avions vue plus tôt où la complexité de l'espace n'est pas O (q), mais plutôt dire que c'est une constante? Maintenant, vous vous demandez peut-être comment en stockant un nombre constant de valeurs, nous pouvons encore effectuer une attaque similaire à l'attaque généralisée que nous avions vue dans le contexte d'une attaque d'anniversaire. Donc, l'idée derrière cette complexité de l'espace constant ou une petite attaque d'anniversaire de complexité de l'espace est la suivante: imaginez que vous avez une séquence de valeurs y1 à yq qui sont essentiellement obtenues par une séquence d'une chaîne d'évaluation de hachage. Donc, vous commencez par dire un y1 distinct ou aléatoire et alors y2 n'est rien d'autre que le hachage de y1 et ensuite de ce y2 j'obtiens y3 ce qui est le même que le hachage de y2, qui à son tour est le même que le hachage de hachage de y1 et ainsi de suite. Donc, vous pouvez imaginer que j'ai une chaîne comme celle-ci et que chaque valeur y suivante est liée à la valeur y précédente par la fonction de hachage H. Donc, c'est ainsi que j'ai calculé ces valeurs y. Maintenant, nous pouvons prouver que si vous avez 2 indices I et J de telle sorte que votre valeur de yI et les valeurs yJ sont identiques. Cela signifie que vous avez cette chaîne de valeurs y1, y2, et dites que vous avez 2 indices intermédiaires indices yI et yJ et vous avez dit avoir fait q nombre de tels calculs et vous avez dit 2 de ces indices yI et yJ tels que yI et yJ sont les mêmes. Ensuite, cela signifie qu'il existe au moins un indice yi ou une valeur y que je dénote par yi de telle sorte que yi et y y2i seront les mêmes qui constituent une collision pour vous. Donc c'est une revendication ici d'accord. Donc, je ne vais pas entrer dans les détails des preuves de cette affirmation, mais vous devez me croire que si nous avons effectivement calculé des valeurs y comme celle-ci et si nous avons cette condition pour être là pour être vrai, alors cette condition se tient aussi. Cela vous donne une idée de la façon de trouver une collision avec une complexité d'espace de constante. Donc, ce que vous devez faire c'est que vous devez effectuer la même analyse que celle que vous avez faite pour le cas précédent, mais maintenant vous avez juste besoin de stocker 2 valeurs de hachage. Donc, ce que vous devez faire est dans chaque itération, vous devez calculer la valeur y suivante. Donc tu dois aller de yi à yi + 1 et en même temps, tu dois garder une trace de y2i aussi. Dès que vous obtenez un index i tel que yi et y2i sont identiques. Cela signifie qu'il existe une collision dans la séquence de valeurs y que vous avez calculée jusqu'à y2i. Donc, ce que vous devez faire, c'est que vous devez effectuer un suivi et découvrir la collision exacte. Donc, je souligne que cette affirmation ne vous donne pas la garantie que yi et y2i est exactement la collision parce que yi est obtenu de la valeur H (yi-1) et y2i est obtenu en évaluant y2i-1. Ainsi, il n'est pas garanti que yi-1 et y2i-1 constituent une collision. C'est ce que vous devez vérifier en faisant le suivi. Donc, la partie intéressante ici est que tant pour l'étape 1 que pour l'étape 2, nous avons juste besoin de stocker 2 valeurs de hachage. Donc, à l'étape 1, on peut aller dans la direction vers l'avant et s'arrêter dès que cette condition se tient et ce qui va devenir vrai avec une probabilité très élevée, nous pouvons prouver que, et si cette condition devient vraie, on s'arrête là et ensuite on fait un retour en arrière en gardant la trace de 2 valeurs de hachage et nous finirons par trouver la collision exacte dans la chaîne de valeurs que nous avons. L'analyse de probabilité reste plus ou moins la même. C'est donc l'idée d'une petite fête d'anniversaire pour trouver des collisions. (Référez-vous à la diapositive: 20:23) Discutons maintenant de certaines applications supplémentaires de la fonction de hachage résistant aux collisions. Donc, la principale application dont nous avons discuté lors de la dernière conférence était de construire des codes d'authentification de messages pour des entrées de longueur arbitraire, mais dans cette conférence, nous verrons aussi d'autres applications. Alors, imaginez que vous vous êtes donné une fonction de hachage résistante aux collisions et que l'une des idées principales que nous pouvons utiliser dans plusieurs applications impliquant la fonction de hachage est que le hachage d'un fichier peut servir d'identificateur unique court où la taille de l'identificateur sera corrigée, disons l bits et sa taille serait l bits quel que soit le fichier que vous alimentant comme entrée à la valeur de hachage. Ça pourrait être un petit fichier, ça pourrait être un gros fichier, je m'en fiche. Le digest du fichier sera pris comme un identifiant et puisque nous supposons que votre fonction de hachage sous-jacente est résistante aux collisions qui signifie en temps pratique, il sera très difficile de trouver 2 fichiers, par exemple X et X ’ de sorte que les deux vous donnent le même digest. Parce que si c'est le cas, alors toute cette idée ne fonctionnerait pas, mais comme je suppose que ma fonction de hachage sous-jacente est une fonction de hachage résistante aux collisions, alors cela signifie qu'en temps pratique, il est très difficile de trouver 2 deux fichiers X et X ’ ayant le même identificateur ou le même condensé de message et il s'avère que ce petit concept que vous pouvez utiliser dans plusieurs applications du monde réel. Discutons donc de quelques-uns d'entre eux. La première application qui nous permet d'utiliser cette idée est celle de l'empreinte du virus. Ce que nous faisons ici, c'est que les anti-virus ou le détecteur de virus stockaient les hacheurs de virus connus dans leur base de données et chaque fois que nous avons une pièce jointe de courriel ou que nous téléchargons une application de courriel, et si nous voulons vérifier si la pièce jointe téléchargée ou l'application de téléchargement a un virus ou non. Ce que nous faisons, c'est que le scanner de virus calcule essentiellement le hachage de la pièce jointe téléchargée ou de l'application, puis il correspond au hachage avec les hachages connus des virus, qu'il a déjà stockés dans sa base de données. S'il y a une correspondance, alors un message d'erreur nous est donné qu'il soupçonne une pièce jointe de données que nous avons obtenue ou que l'application que nous avons téléchargée contient un virus potentiel. Notez qu'il peut être possible que vous avez une pièce jointe qui est une pièce jointe authentique, mais malheureusement son hachage correspond au hachage de l'un des virus connus. Dans ce cas, même pour une pièce jointe, vous pourriez recevoir un message d'erreur, mais cela implique que vous obtenez une collision, ou vous êtes en train de trouver une collision dans un laps de temps réalisable. Mais puisque je suppose que ma fonction de hachage sous-jacente est résistante aux collisions, si à tout un message d'erreur m'est envoyé, cela signifie à très haute probabilité que le hachage de la pièce jointe que je téléchargerai contient des virus. (Reportez-vous à la page Heure de la diapositive: 23:20) La deuxième application où nous pouvons utiliser cette idée est celle de la duplication et, ici, l'idée est que nous voulons éliminer les copies en double des mêmes données. Donc, imaginez que nous sommes dans un scénario de stockage de nuages où dire que nous avons plusieurs utilisateurs, user1, user2 et dire n nombre d'utilisateurs et chacun d'eux cache un stockage de cloud commun pour le téléchargement de leurs données. Maintenant, puisque les utilisateurs sont indépendants les uns des autres, il est possible que user1 et user2 finissent par télécharger un même fichier. Si le stockage en nuage donne ou stocke naïvement les deux copies de X, alors ce sera un gaspillage d'espace. Donc ce qui peut être une solution intéressante ou intelligente sera chaque fois qu'un utilisateur essaie de télécharger un fichier, ce que peut faire la mémoire de cloud est qu'il peut calculer un hachage du fichier pour lequel la requête est venue et il peut comparer cette valeur de hachage avec toutes les hachures des fichiers précédents qu'elle a stockés. Si la valeur de hachage correspond à ce qui signifie que le fichier qui a été demandé à être téléchargé est déjà présent dans la mémoire de cloud, il n'est donc pas nécessaire de créer une nouvelle copie de ce fichier. C'est donc l'idée de la déduplication ici, et encore une fois, nous utilisons l'idée de hachage le fichier et d'utiliser le hachage du fichier comme son identifiant. (Reportez-vous à la page Heure de la diapositive: 24 :38) Maintenant, voyons d'autres applications de fonctions de hachage et c'est ce que nous appelons des pointeurs de hachage. Je suppose donc que vous connaissez tous les pointeurs en langage de programmation. Fondamentalement, les pointeurs sont un type particulier de variable ou vous pouvez imaginer que les variables de pointeur pointant vers un emplacement de mémoire où certaines données sont stockées. Donc si dire 1884 est un emplacement mémoire, et si j'ai une variable de pointeur, alors dans cette variable de pointeur l'adresse 1884 est stockée. Donc, en suivant l'adresse que vous pouvez ou en suivant ce pointeur, vous pouvez venir à l'emplacement 1884 et voir ce qui est exactement stocké. Ce pointeur de hachage est à peu près le même qu'un pointeur dans l'esprit, mais en plus de pointer vers les données, ce pointeur stocke également le hachage de la valeur stockée dans cet emplacement. Cela signifie que si c'est quelques données qui sont stockées dans un endroit arbitraire, et si je dis qu'il s'agit de votre pointeur de hachage, alors ce pointeur de hachage aura un pointeur vers les données ainsi que le hachage des données stockées dans cet emplacement. L'avantage de ce pointeur de hachage est qu'en suivant ce pointeur, non seulement vous pouvez récupérer les données, donc si vous suivez le pointeur vous pouvez récupérer les données, et une fois que les données sont extraites si vous voulez vérifier si vous avez récupéré les bonnes données ou non, vous pouvez le faire de nouveau et le comparer avec la valeur de hachage qui est stockée avec ce point. Donc c'est l'avantage ou la propriété supplémentaire qui est disponible avec le pointeur de hachage par rapport aux pointeurs traditionnels. (Référez-vous à la diapositive: 26 :10) Maintenant, il s'avère que toute structure de données que nous pouvons concevoir à l'aide des pointeurs standard en langage de programmation, toutes peuvent être repensées en remplaçant les pointeurs standard par des pointeurs de hachage. Ainsi, par exemple, il s'agit de votre liste liée standard où vous avez une collection de noeuds et chaque nœud a une séquence de données dont nous appelons le bloc de données et un pointeur vers le bloc suivant, comme celui-ci, donc c'est votre dernier bloc, et comme il n'y a rien après, c'est pourquoi le prochain pointeur pour elle est défini comme nul. Nous avons le bloc précédent où nous avons les données et un pointeur pointant vers le bloc suivant et ainsi de suite et comme nous avons le pointeur de la tête. Il s'agit donc d'une liste de liens standard, dont je suppose que vous êtes tous au courant. Ce que nous faisons maintenant, c'est que nous prenons la même liste liée, mais remplacez tous les pointeurs par des pointeurs de hachage. Donc, nous avons maintenant une séquence de blocs ici, chaque bloc aura son propre contenu de données et avec ça au lieu d'un pointeur régulier, nous avons un pointeur de hachage, qui pointe vers le bloc après lui avec le hachage des données ainsi que le pointeur de hachage stocké ici. Cela signifie que si je considère ce pointeur de hachage, il pointe vers le noeud suivant et quand je dis noeud, noeud signifie noeud dans son ensemble qui signifie les données concaténées avec le pointeur de hachage stocké là-bas. Donc ce pointeur de hachage va pointer vers ce bloc de données et avec qu'un hachage de toute cette chaîne binaire bloc entier, le contenu binaire entier qui est conservé ici sera stocké dans ce pointeur de hachage. Maintenant il s'avère que dès que je prends la liste des liens standard et que je remplace tous les pointeurs par des pointeurs de hachage, j'obtient une structure de données très sympa, qui a un nom très fantaisie dans ce monde d'aujourd'hui, à savoir Block chain.Donc, si quelqu'un vous demande quelle est exactement une chaîne de blocs? La chaîne de blocs n'est rien d'autre qu'une liste de liens linéaires où tous les pointeurs sont remplacés par des pointeurs de hachage. Cela signifie que vous avez une séquence de bloc, chaque bloc a sa propre partie de données et le bref résumé de la totalité du contenu du bloc après, et ainsi de suite et comme vous avez un bref résumé de la totalité de la chaîne de blocs ou de la totalité de la liste liée, ce qui n'est rien d'autre que la valeur de hachage du bloc de données de la tête. (Référez-vous à la diapositive: 28:44) Donc, cette chaîne de blocs, elle vous donne une très belle structure de données. Il vous aide à instancier ce que nous appelons un journal inviolable. Qu'est-ce qu'un journal inviolé? Il s'agit d'une structure de données de journal, c'est-à-dire qu'elle stockera beaucoup d'informations et qu'elle devrait être une structure de données dynamique dans le sens où elle devrait vous permettre d'ajouter des données au journal. Cela signifie que, quel que soit le journal existant, vous pouvez y ajouter des données. Et à part cela, tout changement dans ce journal ou dans le journal existant devrait être déductible. Alors, voyons si nous pouvons instancier ce journal inviolé à l'aide de la chaîne Block. Donc il s'avère que, en effet, nous pouvons utiliser la chaîne de blocs pour instancier le journal invioler-évident et l'idée ici est que nous pouvons utiliser le pointeur de hachage de la tête comme un court résumé pour l'ensemble du journal. Cela veut dire que je n'ai pas besoin de stocker tout le log.Donc, à cette couche il doit me donner le contenu binaire ici, à la deuxième couche il doit me donner le contenu binaire de ce nœud, à la troisième couche il doit me donner le contenu binaire de ce nœud, et à la dernière couche, il doit me donner le i ème bloc de données, dans ce cas le sixième bloc de données. Cela veut dire, si vous avez un arbre Merkle où il y a 2k nombre de blocs de données et si vous voulez extraire seulement un bloc de données particulier i ème bloc de données, alors le nombre de chaînes binaires que la personne doit me donner est de l'ordre k seulement, pas 2k et cela rend cette structure de données très puissante. Vous pouvez prouver l'appartenance de certains blocs de données à l'ensemble de l'arbre sans fournir l'intégralité de l'arborescence. Il suffit de fournir un nombre logarithmique d'informations, il suffit pour une entité de prouver si un certain bloc de données est présent dans l'arbre ou non. Donc, ça m'amène à la fin de cette conférence. Pour résumer, dans cette conférence, nous avons vu quelques-unes des applications des fonctions de hachage. Nous avons vu comment le hachage d'un fichier peut ou le hachage d'une entité peut servir à son identificateur unique en supposant que les collisions sont difficiles, et ce concept a des applications formidelles. L'application principale est dans le contexte des pointeurs de hachage, où nous pouvons remplacer toutes les structures de données basées sur des pointeurs standards par des pointeurs de hachage. Nous avons vu comment les chaînes de blocs peuvent être utilisées comme journal inviolé basé sur ce principe.  

Notification
You have received a new notification
Click here to view them all