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

Introduction aux fonctions de hachage cryptographique

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 Professor International Institute of Information Technology – Bangalore Lecture – 27 Cryptographic Hash Functions-Part I Hello everyone, welcome to this lecture. Pour rappel lors de la dernière conférence, nous avons vu comment construire des codes d'authentification des messages qui sont sécurisés même contre un adversaire sans limite de calcul. (Référez-vous à la diapositive: 00:46) Donc, dans cette conférence, nous allons introduire une autre primitive de cryptographie intéressante appelée fonctions de hachage cryptographiques, qui a plusieurs applications avec l'une des applications étant la construction de codes d'authentification de message efficaces. Ainsi, nous introduisons la définition formelle de la fonction de hachage cryptographique et nous définissons formellement ce que nous entendons exactement par la propriété de résistance aux collisions de fonctions de hachage cryptographiques, puis nous discuterons du paradigme Merkle-Damgard, qui est un paradigme intéressant et utilisé pour la construction de plusieurs fonctions de hachage pratiques résistantes aux collisions. (Voir Heure de la diapositive: 01 :18) Donc commençons par la définition des fonctions de hachage cryptographiques. Donc, cette primitive a des applications formidelles aussi bien dans la clé symétrique que dans le paramètre de clé publique et l'application principale de cette primitive cryptographique est la compression de données et elle a plusieurs autres applications comme la construction du code d'authentification de message, comme une fonction de dérivation de clé, pour la fonction de dédoublonnage, l'empreinte du virus, et ainsi de suite. Ainsi, à un niveau très élevé, une fonction de hachage cryptographique est une fonction de plusieurs à une, ce qui permet de mapper des chaînes de bits de longueur arbitraire à des chaînes de bits de longueur fixe. Donc le domaine est l'ensemble des chaînes de bits qui peuvent être de n'importe quelle longueur et la sortie est toujours d'une longueur fixe disons l où l est la fonction du paramètre de sécurité et de la propriété nous avons besoin de beaucoup de propriétés de cette fonction de hachage cryptographique, mais la propriété principale qui nous intéresse et dont nous discuterons dans ce cours est la propriété de résistance collision et à un niveau très élevé ou de manière informelle ce que la résistance à la collision signifie qu'un adversaire ou un algorithme, qui est délimité par un calcul même si, si elle est en sachant la description de cette fonction H ne devrait pas être capable de trouver un Une collision ou une paire d'entrées distinctes, ce qui vous donne la même valeur de hachage, à l'exception d'une probabilité négligeable. Cela signifie qu'il devrait être très difficile, sur le plan informatique, de trouver des collisions dans un délai raisonnable. (Référez-vous à la diapositive: 02 :49) Donc, définissons formellement ce que nous entendons exactement par résistance aux collisions. Donc, cela est modélisé par une expérience et l'expérience que nous avons donné la description d'une fonction de hachage connue au public, non? Et le nom de l'expérience est l'expérience de collision avec hachage et nous avons un adversaire temps polynomial. Fondamentalement, l'objectif de l'adversaire est de trouver une paire de messages m, m * du domaine de cette fonction de hachage. La définition de sécurité ici est que nous disons que la fonction H est une fonction de hachage résistant aux collisions ou CRHF si pour chaque adversaire temps polynomial participant à cette expérience, la probabilité que l'adversaire puisse trouver une paire de collision, c'est-à-dire avec une paire d'entrées distinctes m, m * telle que le m comme m * donne la même valeur de hachage est borné par une fonction négligeable, non. Donc en gros l'objectif du challenger, l'objectif de l'adversaire ici est de prendre la description de votre fonction de hachage et de trouver une paire d'entrées de collision. S'il est capable de le faire avec un avantage non négligeable, alors nous disons que notre fonction H n'est pas une fonction de hachage résistante aux collisions, sinon nous disons que la fonction H est une fonction de hachage résistante aux collisions. Notez que la fonction H n'est pas une fonction à clé, elle est une fonction non indexée et la fonction H est une fonction déterministe. Il n'y a pas de caractère aléatoire interne à l'intérieur de la fonction H, non. Donc même si la fonction H est déterministe, il n'y a pas de clé. Le défi pour l'adversaire est de trouver une paire d'entrées de collision. Il s'avère qu'il y a un léger problème technique avec la définition ci-dessus dans le sens où, si ce qui précède est la définition d'une fonction de hachage résistant aux collisions, nous ne pouvons définir aucune fonction H ou nous ne pouvons construire aucune fonction H qui satisfait à la définition ci-dessus. C'est parce que j'ai dit que le domaine de la fonction H est un ensemble de chaînes de bits et qui est significativement plus grand que la taille du co-domaine parce que votre co-domaine se compose uniquement de chaînes de longueur l bits et c'est pourquoi la fonction H est une fonction de plusieurs à une. En conséquence, il y a toujours des collisions qui sont présentes dans la fonction H, qui découle de votre principe pigeon-trou parce que si vous avez une fonction de plusieurs à une, alors vous aurez certainement plusieurs entrées x, x * ou m, m * qui ont la même sortie de hachage. Il existe toujours un adversaire que je dis un adversaire de collision, qui pourrait être codé avec une telle paire d'entrées de collision m, m *. Cela signifie que si une telle Acoll adversaire participe à cette expérience de collision avec hachage, elle peut simplement générer la paire de messages m, m *, qui est codée en dur dans l'adversaire. L'adversaire n'a pas à faire de pas, c'est une attaque à temps constant. Cela signifie, fondamentalement, la façon dont nous avons défini une propriété de résistance aux collisions, il n'est pas possible de satisfaire la définition contre toute construction de fonction de hachage, pas vrai. Cependant, il est intéressant de noter qu'il s'avère que la plupart des instanciations pratiques de la fonction de hachage dont nous allons discuter, il n'y a pas de collisions qui sont codées en dur dans leur conception. Cela signifie que nous croyons qu'il n'existe aucun adversaire qui connaît déjà ou qui est codé en dur avec une paire d'entrées m, m * qui constitue une collision pour la fonction de hachage correspondante. C'est pourquoi, techniquement, même s'il y a un défi associé à la définition, nous nous en tenons à cette définition de la fonction de hachage résistant aux collisions. J'insiste également sur le fait que la propriété de sécurité de la propriété résistante aux collisions n'exige pas qu'il n'y ait pas de collision dans la fonction H parce que par sa conception elle-même, il s'agit d'une fonction de plusieurs à une. Comme je l'ai dit, par le principe du trou de pigeon, il s'ensuit qu'il y aura plusieurs collisions, qui sont présentes par rapport à la fonction H. Le défi consiste à concevoir un algorithme de poly-time ou un algorithme de calcul efficace qui, lorsqu'on donne la description de la fonction H, pourrait présenter au moins une de ces paires de collisions avec un avantage non négligeable qui est une exigence de sécurité ou c'est ce que nous entendons par la propriété de résistance aux collisions. (Référez-vous à la diapositive: 07 :06) Donc maintenant, nous avons la définition de la fonction de hachage résistant aux collisions. Nous serons donc intéressés à voir s'il est effectivement possible de concevoir de telles fonctions ou non. Ce que nous allons discuter est un paradigme bien connu qui est appelé le paradigme Merkle-Damgard et c'est une approche très bien connue en deux étapes qui est utilisée pour la conception de plusieurs instanciations pratiques de fonctions de hachage résistantes aux collisions, telles que la fonction de hachage MD5 et plusieurs fonctions de hachage dans la famille SHA-256. Comme je l'ai dit, il s'agit d'une approche en deux étapes pour la construction d'une fonction de hachage résistant aux collisions. Donc à l'étape 1, ce que nous faisons est de concevoir une fonction de compression à longueur fixe résistante aux collisions et pourquoi elle est de longueur fixe car contrairement à une fonction de hachage résistante aux collisions, le domaine pourrait être constitué de n'importe quelle chaîne de n'importe quelle longueur, ici le domaine est fixé dans le sens qu'il ne peut prendre des entrées que de taille n + l bits. Il est appelé fonction de compression car il prend une entrée de taille n + l bits et produit une sortie de taille de n bits. Donc, la taille de la sortie est certainement inférieure ou inférieure à la taille d'entrée et c'est pourquoi il s'agit d'une fonction de compression. Donc pictorialement, vous pouvez interpréter que nous sommes intéressés par le stade 1 à construire une fonction h, qui prend une entrée de taille n + l bits qui peuvent être transmis en 2 moitiés en entrée, la première moitié de la taille n bits et la seconde moitié de la taille l bits. C'est pourquoi vous pouvez interpréter le domaine de cette fonction h comme étant le produit cartésien d'un ensemble x qui est constitué de chaînes de longueur n bits et d'un autre ensemble y qui est constitué de chaînes de longueur l bits et étant donné une chaîne de longueur n + l bits comme l'entrée, l'objectif de cette fonction de calcul devrait être de produire et de produire des bits de taille n bits de sorte que cette fonction h doit être une fonction de résistance aux collisions. Cela signifie que, compte tenu de la description de cette fonction h, il devrait être difficile de trouver une paire de collisions dans le temps polynomial avec une probabilité significative. Une fois que nous avons une telle fonction de compression à longueur fixe dans l'étape 2, ce que nous faisons est d'appliquer ce paradigme Merkle-Damgard bien connu pour construire une fonction de hachage résistante aux collisions que nous dénotent par HMD, qui peut prendre n'importe quelle chaîne comme entrée de longueur jusqu'à dire L bits. Il n'existe aucune restriction sur la taille d'entrée. L'entrée peut être de taille 1 bit, 2 bit ou elle peut être n'importe quelle chaîne de longueur jusqu'à L bits, et elle vous donne une sortie appartenant à l'ensemble x, droite. Donc, c'est ce que nous allons faire à l'étape 2. La construction de l'étape 2 est une construction très générique, dans le sens où elle peut prendre n'importe quelle fonction de compression de longueur fixe sans entrer dans les détails sous-jacents de cette fonction de compression et magiquement elle vous donnera la fonction de résistance aux collisions HMD que vous êtes intéressés de construire. Donc, ce que nous allons discuter maintenant, c'est ce que nous faisons exactement à l'étape 2. Cela signifie que nous allons supposer que nous avons une fonction de compression à longueur fixe et que nous allons voir comment nous appliquons le paradigme Merkle-Damgard et obtenir la fonction de hachage anti-collision H. Plus tard dans la conférence suivante, nous verrons ce que nous faisons exactement pour l'étape 1, c'est-à-dire comment nous construisons exactement cette fonction de compression de candidat h. (Référez-vous à la diapositive: 10:31) Notre objectif est donc le suivant. Nous avons une fonction de compression à longueur fixe, en prenant des entrées du produit Cartesian de x set et y set et vous donnant une sortie sur l'ensemble x et l'ensemble x consistent essentiellement de chaînes de longueur n bits et l'ensemble y est constitué de chaînes de longueur l bits et notre but est de construire cette fonction H, qui peut prendre n'importe quelle chaîne binaire de longueur jusqu'à L bits et vous donner une sortie de taille fixe, à savoir une chaîne de longueur l bits. Donc si vous vous demandez ce que sont exactement les valeurs de n et l. Pour les instanciations pratiques de la fonction de hachage, donc pour vos informations pour la fonction de hachage SHA256, la valeur de n est 256 et la valeur de l est 512 bits, droite. La première chose que nous faisons en appliquant le paradigme Merkle-Damgard est que nous prenons l'entrée M pour la fonction de hachage H que nous sommes intéressés de construire, et cette entrée M est une chaîne binaire de longueur allant jusqu'à longueur L baits. Donc, nous appliquons une fonction d'encodage ici et le codage est fait pour s'assurer que l'entrée codée est un multiple de l bits. La raison pour laquelle nous voulons nous assurer que l'entrée encodée est un multiple de l bits est que lorsque nous allons appliquer le paradigme Merkle-Damgard, nous allons diviser notre entrée encodée en plusieurs blocs de bits de l et nous allons appliquer de façon itérative la fonction de compression de longueur fixe. Donc, pictorially vous pouvez imaginer que vous êtes donné cette entrée, nous appliquons une fonction de codage déterministe publiquement connue. La sortie codée est représentée par ce qui est constitué de l'original M et concaténé avec quelques bits rembourrés et ensemble, ce M original concaténé avec les bits rembourrés sera constitué de plusieurs blocs de bits de l et le nombre de ces blocs de l bits sera (L/l) + 1. Donc, vous vous demandez peut-être pourquoi ce +1, donc ce sera bientôt clair. Alors, quelle est exactement la forme de ces bits rembourses? Eh bien, les bits rembourses sont définis comme suit. Il commencera par 1 suivi du nombre requis de 0 concaténé avec la représentation binaire du nombre de blocs de bits qui sont présents dans l'original M, droite. Donc, vous avez l'original M qui est l'entrée réelle que vous voulez hachage en utilisant la fonction H que vous êtes intéressé de construire. Ainsi, nous comptons le nombre de blocs de bits qui sont présents dans l'entrée non codée et la représentation binaire du nombre de ces blocs est cette représentation, à savoir le nombre <s> (dans les crochets). Donc, le bit de pions que nous ajoutons en fait aux bits du message que nous voulons hacher est de cette forme, nous avons 1 suivi du nombre requis de 0 suivi de la représentation binaire du nombre de blocs de bits de l qui sont présents dans M et typiquement le nombre de bits qui sont alloués pour cette représentation binaire du nombre de blocs de bits présents dans M est un champ 64 bits, mais vous pouvez avoir ce champ composé de plus de bits, mais je cite ce nombre par rapport à l'une des instanciations pratiques des fonctions de hachage, à savoir la fonction SHA. Donc, ça veut dire que vous pourriez avoir jusqu'à 2 64. L nombre de blocs présents dans votre entrée originale M et chaque bloc est constitué de bits l. Ainsi, cela vous donne une limite supérieure sur la taille maximale du message, que vous pouvez haschisch à l'aide de cette fonction de hachage H que vous êtes intéressé de construire, non. Donc, encore une fois, si je prends l'exemple de SHA256, mon l est 512 et je pourrais avoir jusqu'à 2 64 blocs de ce genre. Donc cela vous donne la longueur maximale du message que vous pouvez encoder, à droite, 273-cette chaîne de longueur que vous pouvez haschisch à l'aide de la fonction HMD que vous êtes intéressé de construire. Il est intéressant de noter que si votre message M que vous voulez haschisch est constitué de nombres de blocs de sorte que sa longueur est déjà un multiple de l bit qui signifie que vous n'avez pas besoin de faire de remplissage, mais comment exactement le récepteur qui va recevoir le message viendra pour savoir si le remplissage a eu lieu ou pas. Donc dans le cas où la longueur du message est déjà un multiple de l, alors ce que nous faisons exactement c'est que nous faisons le padding, où le remplissage consiste essentiellement en un bloc factice complet commençant par la représentation 1000s et la représentation binaire du nombre de blocs de bits de l qui sont déjà présents dans le message. C'est pourquoi il s'agit de savoir si la longueur du message est déjà un multiple de l bits ou non, nous faisons le padding et c'est pourquoi ce + 1 est présent dans le nombre de blocs de l bits dans l'entrée codée, non. Donc si le M est déjà un multiple de l, alors vous avez ces nombreux nombres (L/l) de blocs de bits de l et nous faisons effectivement un remplissage, c'est-à-dire que nous ajoutons un bloc factice complet. C'est pourquoi le nombre de blocs de bits de l qui pourraient être présents dans l'entrée codée est en fait ceci (L/l + 1), non. (Voir Heure de la diapositive: 16 :16) Donc, une fois que vous avez l'entrée codée que vous voulez hacher, de sorte que la façon dont nous calculons le hachage de l'entrée codée est que nous appliquons de façon itérative la fonction de compression résistante aux collisions à longueur fixe que nous sommes disponibles avec et que nous le faisons de façon itérative en ce sens que nous appliquons l'invocation de h sur le bloc actuel de l'entrée encodée et le résultat précédent de l'instanciation de la fonction de collision de longueur fixe. Imaginez donc que c'est votre représentation picturale de l'entrée codée constituée de plusieurs blocs de bits de l. J'ai mis en évidence le dernier bloc parce que le dernier bloc peut ne pas être entièrement composé des bits d'entrée, il pourrait être constitué par les bits rembourses aussi, non. Par conséquent, tous les blocs restants ne sont pas mis en évidence. Ainsi, la façon dont nous appliquons de façon itérative la fonction h ici est la suivante. Donc, le premier appel est sur le premier bloc de bits de l'entrée encodée et avec un IV, que nous dénotent comme t0 appartenant à l'ensemble x, nous allons bientôt voir ce qui est exactement la valeur de IV et maintenant vous voyez l'invocation de h, il faut une entrée de taille l + n bits, non. Il prend essentiellement une entrée de l'ensemble x et il prend une entrée de votre ensemble y, qui satisfait la sémantique de ma fonction h et il vous donnera une sortie appartenant à l'ensemble x. Ainsi, la sortie qui sort du premier appel de la fonction h est notée par t1, elle sera de taille n bits et nous prenons le morceau suivant de l bits de l'entrée encodée et appliquons l'appel suivant de la fonction h et la sortie est notée comme t2, qui sera de nouveau de taille n bits et nous continuons comme cela jusqu'à ce que nous ayons fini avec le dernier appel de la fonction h, qui opère sur le dernier bloc de l'entrée encodée de la taille l bits. Le résultat de l'appel précédent de la fonction h et le résultat final de la fonction de hachage H que nous avons construite pour l'entrée M est considéré comme le résultat de la fonction h. Appel final de la fonction h. Donc c'est comme ça que nous allons hacher le message M, pas vrai. C'est pourquoi la fonction h ici est appliquée de façon itérative et cela vous indique également pourquoi nous voulons exactement encoder l'entrée pour être un multiple de l parce que dans chaque itération, nous prenons un morceau de bits de l et appliquez la fonction h sur le résultat précédent de la fonction h, à droite. Alors vous vous demandez peut-être ce qu'est exactement un IV? Est-ce une entité aléatoire ou non? Donc, comme j'ai dit que les fonctions de hachage sont des fonctions déterministes, alors IV n'est pas une valeur aléatoire, c'est une valeur déterminée publiquement connue, vous pouvez dire que tous les zéros qui sont définis une fois pour tous ou pour certaines instanciations pratiques de la fonction de hachage, ce jeu de IV est une chaîne très compliquée et ces variables intermédiaires t0, t1, t2, ts-1, ts, que nous obtenons en fait le long de cette séquence de chaînage, elles sont appelées des variables chaînage. (Voir Diapositive Heure: 19:40) Alors, voyons maintenant si l'application de ce paradigme Merkle-Damgard de façon itérative sur une fonction de compression à longueur fixe résistante aux collisions se termine en vous donnant ou non une fonction de hachage résistante aux collisions. Donc nous allons prouver que si effectivement la fonction h est une fonction de compression de longueur fixe et aussi bien que résistante aux collisions, puis en appliquant le paradigme Merkle Damgard, la fonction H que nous avons obtenue qui peut hasarder n'importe quelle longueur de longueur jusqu'à L bits est en effet une fonction de résistance aux collisions. La preuve sera par la réduction ou par une contradiction, à savoir que nous pouvons prouver que si vous avez un adversaire poly-time, que je dénote comme AMD, qui, compte tenu de la description du paradigme Merkle-Damgard et une description de votre fonction de compression de longueur fixe, génère une paire de messages distincts ou une collision pour la fonction plus grande ou la fonction H que nous avons construite. Cela signifie que l'algorithme AMD génère une paire M, M ’, où M et M ’ sont distincts, mais la valeur de hachage de M et M ’ exploitée par rapport à la fonction H est la même. La probabilité de collision ici est de dire f (n) où f (n) est une fonction non négligeable. Donc ce que nous allons prouver, c'est que si nous avons un tel adversaire AMD, alors en utilisant cet adversaire AMD que nous pouvons construire ou nous montrons comment construire un autre adversaire de poly-time Ah, qui peut vous donner une collision pour votre fonction de compression de longueur fixe de compression h avec la même probabilité avec laquelle l'adversaire AMD aurait pu vous avoir donné une collision pour la fonction HMD. En gros, l'idée de cet adversaire Ah, c'est que l'adversaire Ah, son but est de découvrir une collision pour la fonction h, c'est-à-dire que son but est de trouver une paire t, m et t *, m * de telle que la sortie de cette fonction h sur ces deux entrées est la même et de trouver est la paire t, m et t *, m *, ce que votre adversaire Ah, c'est, en gros, il analyse la séquence de la chaîne de hachage que votre paradigme Merkle-Damgard aurait créé lors du hachage de ce message M et pour le hachage du message M ’, où le message M et M ’ sont produits par l'adversaire est AMD. Donc picturalement, c'est ainsi que la valeur de hachage du message M aurait été calculée selon le paradigme Merkle-Damgard, à droite. Le message M aurait d'abord été converti en entrée codée, puis nous aurions appliqué la fonction h de façon itérative et de la même façon pour calculer la valeur de la fonction HMD sur le message M ’, nous aurions appliqué la fonction h de façon itérative comme ceci. Nous aurions d'abord converti l'entrée M ’ en entrée codée, puis nous aurions appliqué la fonction H de façon itérative et nous aurions obtenu la valeur de la valeur de hachage sur le message M ’. Donc, ce qui est fondamentalement l'adversaire Ah, c'est qu'il va comparer ces deux chaînes de hachage, la chaîne de hachage sur le côté gauche et la chaîne de hachage sur le côté droit et notre affirmation est que si m, m ’ constitue une collision où m et m ’ sont distincts, alors il y aura certainement au moins une collision présente à un endroit dans la chaîne de hachage de M et la chaîne de hachage de M ’, à droite. (Reportez-vous à la page Heure de la diapositive: 23 :18) Donc, voyons comment exactement la collision pour la fonction h va être obtenue en se basant sur ces deux chaînes de hachage. Donc, puisque la valeur de hachage du message M et la valeur de hachage du message M ’ sont identiques, non, parce que c'est une collision pour votre fonction, HMD. Ce que nous allons faire, c'est que nous allons nous concentrer sur le dernier appel de la fonction h dans la chaîne de hachage pour le message M et le dernier appel de la fonction h dans la chaîne de hachage pour le message M ’, à droite. Ainsi, le dernier appel pour le message M est sur votre côté gauche et le dernier appel de la chaîne de hachage sur M ’ est sur la droite et comme vous pouvez le voir, vous avez les entrées mu et tu-1 pour la chaîne de hachage pour M et l'entrée pour la chaîne de hachage pour M ’ est l'entrée m ’ v et t ’ v-1. Donc, il pourrait y avoir 2 possibilités. Si cette entrée conjointe tu-1 concaténée avec mu est différente de t ’ v-1 concaténée avec m ’ v, elle crée alors une collision pour votre fonction h. Parce que ce qui se passe ici est que même si l'entrée combinée ici est différente de l'entrée combinée ici, leur sortie par rapport à la fonction h est la même car c'est ce qui est la sortie globale de la valeur de hachage H pour le message M et M ’. Donc, si nous sommes dans ce cas, alors nous avons repéré une collision très facilement, c'est-à-dire que nous avons repéré la collision par rapport au dernier appel de la fonction h. Sinon, cela implique que l'entrée combinée tu-1 et mu est la même que l'entrée combinée t ’ v-1 et m ’ v et cela signifie automatiquement que le nombre de blocs présents dans le message M et M ’ est identique, à savoir u = v car nous sommes dans le cas où ce mu et m ’ vare même, droite, et rappelez-vous mu et m ’ v sont constitués d'un certain nombre de bits du message réel et des bits rembours, bien que combinely ils soient les mêmes. Cela signifie que le nombre de blocs de bits de l qui sont présents dans le message M et un certain nombre de blocs de bits de l qui sont présents dans le message M ’ sont en fait identiques. Donc, si vous êtes dans le cas d'autre, cela signifie que nous avons le dernier appel de la fonction h dans la chaîne de hachage de M et le hachage de M ’ ne constitue pas une collision. (Reportez-vous à la diapositive: 26:08) Nous devons donc faire un pas en arrière dans la chaîne de hachage dans les chaînes de hachage respectives et mettre l'accent sur le second appel de la fonction h dans les chaînes de hachage respectives, à droite. Donc, si nous continuons dans l'autre cas, nous sommes ici. Nous avons des messages distincts M et M ’ et maintenant nous nous concentrons sur le second appel de la fonction h dans leurs chaînes de hachage respectives. Maintenant, encore une fois, nous avons 2 cas possibles. Si l'entrée conjointe à la fonction h dans les chaînes de hachage respectives est différente, alors nous avons repéré une collision pour la fonction h parce que maintenant nous sommes dans le cas où même si l'entrée combinée au second appel de la fonction h dans les chaînes de hachage respectives est différente, leurs sorties sont identiques, non? Parce que les sorties sont tu-1 et t ’ u-1 que nous savons déjà qu'elles sont les mêmes parce que nous sommes dans ce cas. Mais encore une fois, s'il se trouve que l'entrée combinée pour l'invocation de second à dernier des fonctions h dans les chaînes de hachage respectives est égale, à droite, alors elle vous donne l'implication que les autres mu et mu ’ sont identiques et que les entrées combinées sont les mêmes, alors nous devons faire un pas en arrière dans les chaînes de hachage respectives et nous devons nous concentrer sur le troisième à l'invocation de la fonction h dans les chaînes de hachage respectives. (Voir Heure de la diapositive: 27:35) Ainsi, si vous allez maintenant au troisième appel de la fonction h dans les chaînes de hachage respectives, nous sommes dans cette condition et nous devons à nouveau nous demander si l'entrée combinée à la fonction h dans les chaînes de hachage respectives est identique ou non. Si ce n'est pas le cas, alors cette instance de h crée fondamentalement une collision pour la fonction h où nous avons une paire d'entrées qui sont différentes, mais la sortie, à savoir t ’ u-2 et tu-2 sont identiques, mais si ce n'est pas le cas, nous devons à nouveau passer à l'appel précédent de la fonction h dans les chaînes de hachage respectives et ainsi de suite. Donc, ce que nous faisons en gros, c'est que nous sommes en train d'analyser la chaîne de hachage des M et M ’, et la revendication est que finalement, nous finissons par trouver une collision parce que si nous ne trouvons pas de collision et si nous finissons par analyser de droite à gauche et venir au début du message, premier bloc de M et le premier bloc de M ’, et cela signifie que même si nous avons des M et M ’ distincts, tous les blocs de M et M ’ sont identiques, ce qui va être une contradiction. Mais puisque M et M ’ sont différents parce que cela constitue une collision pour votre fonction de hachage globale HMD, il y aura certainement une collision qui sera repérée par rapport à la fonction h. Ainsi, cela prouve que si en effet notre fonction h est une fonction de compression à longueur fixe et résistante aux collisions, puis en appliquant le paradigme Merkle-Damgard, la fonction globale que nous allons obtenir est aussi résistante aux collisions. Cela signifie en poly temps, il ne serait pas possible de trouver une paire d'entrées distinctes, ce qui vous donne la même valeur hachée. Donc, cela m'amène à la fin de cette conférence. Maintenant, juste pour résumer, dans cette conférence, nous avons commencé à discuter de la primitive de cryptographie intéressante appelée fonction de hachage cryptographique. Nous avons vu la définition de la résistance aux collisions par rapport aux fonctions de hachage cryptographique. Bien sûr, il y a plusieurs autres propriétés pour les fonctions de hachage cryptographique comme la résistance à la préimage et la seconde résistance à la préimage, mais nous n'allons pas discuter de ces propriétés parce que nous ne les utiliserions pas dans ce cours. Nous avons également discuté du paradigme Merkle-Damgard qui est un paradigme bien connu utilisé dans plusieurs instanciations pratiques de la fonction de hachage cryptographique et ce que le paradigme de Merkle Damgard fait est qu'il faut une fonction de compression à longueur fixe résistante aux collisions, appliquer une fonction de hachage résistant aux collisions pour toute entrée de taille. Je vous remercie.

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