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

Construction de fonctions de compression de longueur fixe

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 – 28 Cryptographic Hash Functions-Part II (Référez-vous à la diapositive: 00:32) Bonjour à tous, bienvenue à cette conférence. Alors juste pour rappeler, lors de la dernière conférence, nous avons vu le paradigme Merkle-Damgard pour construire des fonctions de hachage résistantes aux collisions pour toutes les entrées de taille et dans cette conférence nous allons voir la phase 1 du paradigme Merkle-Damgard, à savoir comment construire une fonction de compression de longueur fixe. (Reportez-vous à la page Heure de la diapositive: 00:49) Pour vous rappeler, il s'agit de savoir comment un paradigme Merkle-Damgard prendra n'importe quelle fonction de compression à longueur fixe h qui est résistante aux collisions et l'applique de façon itérative pour obtenir une fonction de hachage qui peut hacher des entrées de n'importe quelle taille. Donc maintenant la question intéressante est de savoir comment exactement vous obtenez cette fonction de compression à longueur fixe, une fonction de compression à la première place? Donc pictorially, cette fonction h prend une entrée de taille l + bits, qui peut être analysée comme 2 entrées, une entrée de l bits et une autre entrée de bits. Il la compresse et vous donne une sortie de bits de taille. C'est ainsi que vous pouvez interpréter cette fonction de compression à longueur fixe et il s'avère qu'il y a 2 approches pour construire cette fonction h. La première approche consiste à concevoir une construction basée sur des hypothèses théoriques de problèmes de nombres ou de théorèmes de nombres. Donc, quand nous allons commencer notre discussion sur la théorie des nombres et la cryptographie à clé publique, nous revierons et nous verrons comment utiliser des hypothèses de dureté de la théorie des nombres pour construire cette fonction h. Cette approche n'est pas utilisée pratiquement parce que même si les constructions, leur temps de fonctionnement, elles sont polynomiales dans le paramètre de sécurité, le temps d'exécution réel lorsqu'il est déployé dans la pratique est d'ordre de plusieurs grandeurs et c'est pourquoi nous n'utilisons pas les instanciations de la fonction h basées sur des hypothèses de dureté de la théorie des nombres. Au lieu de ce que nous faisons, nous concevons des constructions, nous allons pour des constructions basées sur des chiffrements par blocs, nous pouvons prendre n'importe lequel des algorithmes de chiffrement existants dire AES, des ou nous pouvons concevoir des chiffrements de blocs dédiés. Ce sont les constructions, ce sont les instanciations de la fonction h, que nous utilisons dans la pratique. Cependant, de façon intéressante la preuve de sécurité des constructions basées sur les chiffrements par blocs, ils sont dans un modèle très peu conventionnel. Ce sont des modèles non conventionnels dans le sens, nous faisons des suppositions très fortes du modèle sous-jacent puis donnons la preuve de sécurité. (Référez-vous à la diapositive: 03 :06) Donc, voyons cette approche de la façon de construire une fonction de compression à longueur fixe résistante aux collisions, à partir des chiffrements par bloc. Et il y a plusieurs constructions disponibles. Nous verrons l'une des constructions que l'on appelle la construction Davies-Meyer. Donc ce que vous êtes donné est un algorithme de chiffrement par bloc que vous pouvez interpréter comme une permutation pseudo-om à clé, en prenant une clé de l'espace clé et de l'entrée de l'espace bloc et en vous donnant une sortie, où la sortie et la taille de bloc sont les mêmes. Nous concevons une fonction de compression h, que je dénote comme h, c'est-à-dire que nous pouvons l'appeler par la fonction de compression Davies Meyer, qui prend une entrée de taille |, c'est-à-dire qu'elle prend 2 entrées, 1 entrée est considérée / interprétée comme et la sortie de cette fonction de compression est définie comme (. Nous évaluons le code de chiffrement par rapport à la clé et le traitement de la pièce comme étant le bloc et la sortie est à nouveau XORed avec la partie de l'entrée de cette fonction de compression de hachage Davies-Meyer, donc c'est ainsi que cette fonction de compression Davies-Meyer est évaluée. La partie intéressante ici est que le bloc de message dans la chaîne de hachage (rappelez-vous que cette fonction h va être branchée dans la chaîne de hachage du paradigme Merkle-Damgard juste lorsque nous évaluons la fonction de hachage globale. C'est pourquoi pictoriellement je représente cette fonction h composée de 2 entrées, une entrée sera la partie bloc du message que nous voulons haschisch dans le message plus grand et l'autre sera la partie qui viendra du résultat de l'appel précédent de la fonction h). La façon dont nous concevons cette fonction de compression Davies-Meyer est fondamentalement le bloc de message sur lequel nous allons utiliser cette instruction Davies-Meyer sera traitée comme la clé de la permutation pseudorandom du chiffrement bloc. Il n'a pas besoin d'être uniformément aléatoire. Parce que l'attaquant pourrait avoir un contrôle total sur le message plus grand qu'il veut hachage selon le paradigme Merkle-Damgard et cela signifie qu'il donne à l'agresseur un contrôle total sur ce qui sert exactement comme clé pour le chiffrement par bloc lorsqu'un algorithme de chiffrement par bloc est utilisé à l'interne dans la conception de la fonction de compression Davies-Meyer. Cependant, même si l'adversaire a le contrôle total de la clé qui est utilisée dans l'instanciation sous-jacente du chiffrement par bloc dans cette fonction de compression Davies-Meyer, il peut être prouvé que la construction globale de cette fonction de compression Davies-Meyer est effectivement résistante aux collisions dans des conditions spéciales. Cela signifie qu'il n'y a rien à craindre ici, même si vous vous demandez peut-être que nous avons discuté que les chiffrements par bloc restent en sécurité seulement si la clé n'est pas connue de l'attaquant et que la clé est uniformément aléatoire, mais la façon dont nous opérons ou utilise le chiffrement par bloc dans cette fonction de compression Davies-Meyer est que, le bloc du message que nous allons utiliser ou appliquer la fonction de hachage h, il est entièrement sous le contrôle de l'adversaire et c'est en fait servir de clé pour votre instanciation sous-jacente de votre algorithme de chiffrement et ce besoin ne doit pas être aléatoire. Mais nous pouvons encore prouver que dans des conditions spéciales, la façon dont la production de la construction Davies-Meyer est définie, dans l'ensemble la fonction dans la construction Davies-Meyer que nous avons construite ici est en effet résistante aux collisions. Donc voici comment nous avons construit la fonction de compression Davies-Meyer et comme je dis continuellement que nous pouvons prouver la résistance à la collision de la construction Davies-Meyer sous des hypothèses spéciales, c'est parce que nous ne savons pas comment prouver la résistance à la collision de la construction Davies-Meyer que nous avons donnée, en supposant que le chiffrement du bloc sous-jacent est une forte permutation pseudorandom. Il ne suffit pas de supposer que la fonction sous-jacente est une forte permutation de pseudorandom et donne une preuve que la construction Davies-Meyer est effectivement résistante aux collisions. Cependant, il est intéressant de noter que la preuve de la résistance à la collision de la construction Davies-Meyer est connue dans le modèle de chiffrement idéal qui est une sorte de paramètre hypothétique, parce qu'il fait des suppositions très fortes sur le chiffrement de bloc sous-jacent. Alors, voyons ce qu'est exactement ce modèle de chiffrement idéal? Ainsi, dans le modèle de chiffrement idéal, le chiffrement par bloc sous-jacent ou la permutation à clé est abstrait en tant que collection de plusieurs permutations réellement aléatoires, où chaque membre de cette famille ou chaque membre de cette collection est indexé par la clé sous-jacente avec laquelle nous allons exploiter la fonction. Souvenez-vous, le chiffrement par bloc nécessite une entrée de bloc et une entrée clé. Donc ce que nous supposons en gros dans ce modèle idéal-cipher est que même si on nous donne la description d'une fonction unique, dès que nous fixons la valeur de, qui donne une instanciation de la fonction, qui peut être traitée comme un membre d'une plus grande famille. Donc différentes valeurs de la qui sont utilisées dans votre fonction, vont vous donner différents membres de la famille plus grande et c'est pourquoi nous sommes en train de considérer que même si on nous donne la description d'une fonction unique, lorsqu'elle est utilisée avec différentes, elle vous donne différents membres d'une famille plus grande et c'est ce que nous entendons par fonction abstrait comme une collection de permutations vraiment aléatoires. La deuxième propriété de ce modèle idéal-cipher est qu'une fois que nous avons un membre de la famille 1 et un autre membre de la famille 2, c'est-à-dire l'instanciation de votre algorithme de chiffrement avec la clé 1 et la clé 2, l'hypothèse ici est que le membre de la famille 1 et le membre de la famille 2, à savoir les permutations à clé 1 et 2, sont indépendants l'un de l'autre même si les clés 1 et 2 sont dépendantes ou liées entre elles. Cela signifie que même si 1 est presque la même que 2 sauf dire le dernier bit, l'hypothèse dans ce modèle idéal-cipher est que la fonction 1 sera complètement indépendante dans le sens, sa sortie sera uniformément aléatoire et elle sera complètement indépendante des sorties de la fonction 2. Donc c'est la deuxième propriété dans ce modèle de chiffrement idéal. Donc, jusqu'à présent, il n'y a rien de non conventionnel ici que nous assumons à propos de la fonction. Parce que lorsque nous supposons que la fonction est une forte permutation pseudorandom, cela signifie que même si ce n'est pas une permutation vraiment aléatoire, elle vous donne une pseudo-garantie de randomité. Cela signifie que nous pouvons supposer qu'elle se comporte comme une permutation aléatoire. Mais dans le modèle de chiffrement idéal, nous faisons des hypothèses légèrement plus solides, nous supposons que chaque membre de cette famille plus grande est effectivement une permutation vraiment aléatoire et indépendante l'une de l'autre. La propriété la plus forte ou vous pouvez l'appeler comme la propriété la plus non conventionnelle dans ce modèle de chiffrement idéal est qu'aucune partie ou aucune entité du système qui va utiliser une primitive cryptographique, qui utilise ce code de chiffrement, aura accès au code de la fonction et au code de la fonction − 1. Cela signifie que si chez toutes les entités veut calculer la valeur de la fonction par rapport à une clé, elle fera un accès oracle ou elle fera des appels oracle à la permutation à clé et elle redonnera simplement la valeur de la permutation à clé sur l'entrée pour laquelle elle veut la valeur du. De la même manière, si une entité souhaite connaître la valeur de − 1 en ce qui a une touche d'entrée et une certaine entrée, elle peut faire simplement un appel oracle à − 1 oracle et elle va récupérer la sortie correspondante, mais elle n'aura pas accès au code du code de chiffrement du bloc. C'est donc l'hypothèse la plus non conventionnelle que nous faisons dans le modèle de chiffrement idéal parce que, en réalité, lorsque nous concevons la construction de Davies-Meyer et que nous l'instancions, nous avons besoin du chiffrement par bloc réel que nous allons mettre en place dans cette construction de la construction Davies-Meyer. Chaque entité qui va utiliser cette instanciation de la construction Davies-Meyer connaira le code de la fonction, y compris l'adversaire, mais quand nous analysons la sécurité de la construction Davies-Meyer, l'hypothèse que nous faisons dans le modèle de chiffrement idéal est que personne ne saura le code de la fonction, c'est juste une collection de plusieurs membres aléatoires, si vous voulez parler à un membre aléatoire, faites un appel oracle. (Voir le diaporama: 12 :17) Donc, supposons que maintenant nous sommes dans le modèle de chiffrement idéal, ce que nous allons prouver, c'est que cette construction Davies Meyer de la fonction de compression à longueur fixe que nous avons donnée ici est en effet une fonction de résistance aux collisions. Rappelez-vous donc qu'il s'agit bien d'une fonction de compression parce que nous prenons une entrée de bits de taille et que nous vous donnons une sortie de bits de taille, donc il s'agit d'une fonction de compression. Ce que nous devons prouver, c'est qu'en quantité polynomiale de temps, il est difficile pour un adversaire de se présenter avec une paire (et (), telle que la sortie de la fonction Davies-Meyer est la même où la construction Davies-Meyer utilise un algorithme de chiffrement par bloc. Donc, puisque nous allons analyser la sécurité de cette fonction de compression dans le modèle idéal-cipher, tout adversaire qui voudrait découvrir une collision pour cette construction Davies-Meyer, il a besoin d'évaluer la fonction Davies-Meyer sur plusieurs messages de son choix, alors seulement il pourrait arriver avec une collision. Pour évaluer la fonction Davies-Meyer sur les messages de son choix, elle a besoin en interne d'évaluer la fonction et − 1 ainsi, parce que nous ne savons pas exactement quelle est la stratégie de l'adversaire ; elle peut évaluer le sous-jacent sur plusieurs (paires, elle pourrait évaluer le sous-jacent − 1 également sur plusieurs entrées de son choix, et ensuite seulement elle pourrait arriver avec une collision correspondante. Mais puisque nous sommes maintenant dans le modèle de chiffrement idéal, ce que nous allons supposer, c'est que même l'adversaire qui voudrait évaluer le sous-jacent et le − 1 sur les entrées de son choix de venir avec une collision pour cette fonction Davies-Meyer, fera des requêtes d'oracle, parce qu'il ne connairait pas le code de la fonction et le code de la fonction − 1. C'est pourquoi, pour incorporer ces requêtes oracle de l'adversaire pour découvrir la collision, ces requêtes d'oracle sont incorporées dans l'expérience de collision avec hachage lorsque nous analysons la sécurité de cette construction Davies-Meyer dans le modèle de chiffrement idéal. Rappelez-vous donc dans l'expérience de collision de hachage réelle dans le modèle non-idéal-cipher ou dans le modèle standard, l'adversaire n'a pas eu à interroger quoi que ce soit, car il aura accès au code de la fonction ou − 1 si nous utilisons tout ou − 1 dans la conception de la fonction de hachage sous-jacente. Mais maintenant, puisque nous sommes dans le modèle de chiffrement idéal, même l'interaction de l'adversaire avec la fonction et − 1 sera à travers des requêtes oracle et c'est pourquoi elles doivent également être incorporées dans l'expérience de collision avec hachage modifiée. L'expérience de collision avec hachage modifiée est donc la suivante. Nous supposons maintenant que tant l'expérience que l'adversaire auront un accès oracle à la famille des fonctions et à la famille des fonctions. Donc vous pouvez imaginer ces oracles et sont en quelque sorte dans le ciel, où personne ne peut voir ce qui est exactement le code de la fonction et l'inverse et si quelqu'un veut calculer la valeur de la fonction pour n'importe quel de son choix, il crie au ciel que s'il vous plaît donnez-moi la valeur de cette fonction sur cette entrée et il verra la valeur de sur cette entrée et de même façon que l'interaction avec est manipulé ici. C'est pourquoi je mets cette famille de fonctions et dans une boîte ici. Personne ne peut voir ce qui se passe exactement à l'intérieur de la boîte, toutes les interactions vont passer par une interface, vous fournissez des entrées et vous obtenez la sortie. L'expérience de collision avec hachage modifiée est donc la suivante. Souvenez-vous de l'objectif de l'adversaire est, il connaît la description de votre fonction de hachage Davies-Meyer, c'est-à-dire qu'il sait que la fonction de hachage de Davies-Meyer ’ est fondamentalement (. Le but de l'adversaire est essentiellement de trouver une paire (et (), qui constitue une collision par rapport à cette fonction Davies-Meyer. Mais comme nous sommes dans le modèle de chiffrement idéal, toute valeur que l'adversaire aimerait calculer ou n'importe quelle valeur de − 1 que l'adversaire aimerait calculer, sera disponible par le biais de requêtes Oracle. Imaginez si l'adversaire aimerait connaître la valeur de la clé et de l'entrée. Donc, il peut faire une requête oracle et ce que l'oracle va revenir en arrière est, il va retourner la valeur de la fonction par rapport à la clé sur l'entrée, et si l'adversaire voit cette réponse, alors fondamentalement ce que l'adversaire voit est la valeur de la fonction Davies Meyer sur la paire d'entrée (,), parce que la valeur de la fonction Davies-Meyer sur cette entrée combinée (,), sera la valeur de la fonction ou le code de chiffrement sur l'entrée avec la clé, XOR avec l'entrée. Mais comme l'adversaire est dans le modèle de chiffrement idéal, il ne peut pas calculer la valeur de () et c'est pourquoi il a fait une requête oracle. C'est ainsi que l'adversaire va calculer la valeur des fonctions Davies-Meyer sur les messages de son choix. Il s'avère que ce n'est pas la seule façon pour l'adversaire de calculer la valeur de la fonction Davies-Meyer sur les entrées de son choix. Il pourrait prendre l'aide de l'accès en oracle inverse aussi, par exemple, il peut demander, hey inverse oracle me donne la valeur de l'inverse de la fonction sous la clé sur l'entrée et en réponse ce que l'oracle va faire est, il va retourner l'inverse de cette fonction sur l'entrée sous la clé, désolé pour la faute de frappe ici, il devrait être sous la clé, et une fois que l'adversaire apprend l'inverse de ceci sous la clé, qui lui donne la valeur de la fonction Davies-Meyer sur l'entrée (,). Parce que la fonction Davies-Meyer est construite, la sortie de la fonction Davies-Meyer sur cette entrée (,) Serait comme ça. Donc en faisant des requêtes d'oracle à la famille et en faisant des requêtes d'oracle à la famille, on peut supposer que l'adversaire va maintenant calculer la sortie de la fonction Davies-Meyer sur plusieurs messages de son choix, à savoir le nombre polynomial de messages parce que notre adversaire est polynomiquement délimité et, enfin, il soumet une collision, à savoir une paire d'entrées (et (). La définition de la sécurité ici est que, nous dirons que cette expérience de résistance aux collisions est un succès pour l'adversaire dans le modèle de chiffrement idéal si, dans ce modèle, où l'adversaire fait ou donne un accès oracle à la famille et à la famille, la probabilité que l'adversaire puisse trouver une collision est délimitée par une fonction négligeable et la collision est maintenant spécifique parce que maintenant nous analysons la collision par rapport à la construction Davies Meyer. Ainsi, la sortie de la construction Davies-Meyer pour le (message que l'adversaire est soumis sera), et la sortie de la fonction Davies-Meyer pour le message (c'est-à-dire, le message) que l'adversaire a soumis sera le suivant: Notre but est d'analyser quelle est la probabilité que la condition (aléatoire) soit mise en attente. La définition de la sécurité est que nous allons dire que la construction Davies-Meyer est résistante aux collisions dans le modèle de chiffrement idéal si la probabilité qu'un adversaire de poly-time puisse trouver une réponse spéciale (et (secondaire,) satisfaisant cette condition est bornée par une fonction négligeable. (Voir la diapositive: 20:15) Ce que nous allons prouver, c'est que la construction Davies-Meyer que nous avons donnée constitue une fonction de résistance aux collisions dans le modèle de chiffrement idéal, à condition que la taille de l'est suffisamment grande. Plus précisément, ce que nous allons prouver ici, c'est que n'importe quel adversaire de poly-time ou tout adversaire Un certain nombre de requêtes idéales pour la famille et − 1 famille peut trouver une collision avec une probabilité supérieure bornée par. | Voici donc le nombre total de requêtes que l'adversaire est autorisé à poser à la famille et à la famille − 1. Il n'est donc pas pour et pour − 1. Donc, s'il fait le nombre de requêtes et le nombre de requêtes à − 1, alors c'est en gros et ce que nous allons prouver est que dans le modèle de chiffrement idéal, tout adversaire polytime faisant le nombre de requêtes, sa probabilité de succès de trouver une collision dans la fonction Davies-Meyer est délimité par. | Donc ce que nous allons faire ici est que nous considérons les numéros de requête,, où. En d'autres termes, supposons que l'adversaire a déjà demandé des requêtes à la famille et à la famille − 1, et maintenant il fait la requête et n'importe quand lorsqu'il fait une requête, la réponse pour la requête lui donne la valeur de la fonction Davies-Meyer sur une paire d'entrée, parce que c'est ce que nous avions déjà vu précédemment. Donc, s'il fait des requêtes à la famille, alors basé sur la réponse, il obtient la valeur de la fonction Davies-Meyer sur certaines entrées ou s'il fait une requête à la famille − 1, puis à nouveau en fonction de la réponse, il lui donne la valeur de la fonction Davies-Meyer sur quelques entrées. Donc laissez la main hdenote les valeurs de hachage, que l'adversaire apprend, en se basant sur la réponse de la requête et de la requête, respectivement. Nous sommes intéressés à calculer la probabilité que h= hales. Il pourrait donc y avoir 2 cas ici. Supposons que la requête que l'adversaire est en train de faire est pour la famille. Donc quand il fait une requête à la famille, il demande la valeur du membre de la famille sur l'entrée. Donc il verra la réponse que je dénote comme. Et en se basant sur la réponse, il apprend en gros la valeur de la fonction Davies-Meyer sur certaines entrées, fondamentalement il apprend la valeur de la fonction Davies-Meyer sur l'entrée (,). Et cela est dénoté par h et ce hra sera (). Donc nous sommes intéressés d'analyser la probabilité que la valeur de hachage que l'adversaire a appris en faisant cette requête à la famille, c'est la même que la valeur de hachage que l'adversaire a déjà apprise lors de la requête. Et rappelez-vous que la requête peut être soit à la famille, soit à la famille. Donc la probabilité que la valeur de hachage que l'adversaire a appris est la même que la valeur de hachage que l'adversaire vient d'apprendre, est la même que la probabilité que le membre de la famille lorsqu'il est évalué à l'entrée, donne la sortie hache. Si tel est le cas, la main sera la même. Mais comme nous sommes dans le modèle de code de chiffrement idéal, quelle est la valeur du membre de la famille sur l'entrée? Eh bien, c'est une valeur uniformément aléatoire indépendante l'une de l'autre. Il s'agit d'une valeur uniformément aléatoire sur l'ensemble et elle est différente de toutes les valeurs précédentes pour lesquelles l'adversaire a peut-être déjà demandé la valeur de sortie. Alors, rappelez-vous que nous sommes dans le cas où, nous analysons la probabilité par rapport à la collision pour la sortie de la requête et de la requête. Donc, dans le pire des cas, il peut arriver que pour toutes les requêtes précédentes, l'adversaire ait pu demander la valeur de la famille de fonctions par rapport à la clé. En réponse, l'adversaire aurait pu voir la sortie du membre de la famille pour diverses entrées et puisque c'est une permutation, quand l'oracle lui donne la réponse pour la famille sur l'entrée, il doit être différent de toutes les sorties précédentes, cet oracle est déjà retourné à l'adversaire. Donc la probabilité avec laquelle cette condition, à savoir la sortie de la requête sous la clé est égale à ceci, est toujours délimitée par 1 |. Donc c'est la probabilité avec laquelle, en faisant la requête à la fonction, l'adversaire peut espérer qu'il obtient une collision par rapport à la sortie de la requête, ce qu'il avait fait dans l'interaction précédente avec l'oracle. D'autre part, il peut arriver que la requête de l'adversaire soit pour la fonction − 1. Il peut donc demander la valeur de l'inverse, il peut demander le service oracle pour cette entrée, à partir de − 1 oracle et en réponse il revient à la sortie, en gros il voit l'inverse de l'entrée sous le bon droit. Il demande donc en gros l'accès au membre − 1 sur l'entrée et il revient à la sortie et s'appuie sur le fait qu'il apprend la valeur de hachage, à savoir la valeur de la fonction Davies-Meyer et que la sortie doit être − 1 (). Dans ce cas, quelle est la probabilité que la valeur que l'adversaire a appris ici soit la même que celle de la requête que l'adversaire a déjà appris dans l'interaction précédente? Eh bien, la probabilité que cela soit le même que la probabilité que votre − 1 fonctionne sous la clé de l'entrée, vous donne une sortie qui est la même que XOR de la main et, encore une fois, nous pouvons exécuter le même argument que nous avons fait pour le cas précédent. Souvenez-vous que dans le modèle de chiffrement idéal, chacun des membres de la famille et, ils sont vraiment aléatoires et indépendants l'un de l'autre. Alors, c'est pourquoi nous pouvons maintenant conclure en toute sécurité que la probabilité que h = hache où il est maintenant défini comme celui-ci, par l'adversaire faisant un appel oracle pour la fonction inverse est borné par 1 |. Donc dans les deux cas, indépendamment du fait que la requête soit pour la fonction ou la requête est pour la fonction, la probabilité que la valeur de hachage que l'adversaire apprend à cause de cette requête correspond à la sortie de la requête est délimitée par 1 |. C'est donc le fait que nous avons établi maintenant. (Référez-vous à la diapositive: 28:58) Combien de questions l'adversaire est-il en train de faire? Nous partons de l'hypothèse que l'adversaire fait le nombre total de requêtes, et ce que nous avons analysé, c'est qu'en dehors de ces requêtes, quelle est la probabilité qu'une paire de requêtes distinctes lui donne une collision pour la construction Davies-Meyer dans le modèle de code de chiffrement idéal, cette probabilité que nous avons calculée tout à l'heure. Donc maintenant ce que nous devons faire, c'est que nous devons appliquer la borne de l'union, c'est-à-dire que nous devons prendre cette probabilité et la somme sur toutes les paires de distinctes, où et vont de 1 à. Alors, laissons la collision être l'événement qui, en faisant le nombre de requêtes à la famille et − 1, l'adversaire obtient au moins une paire de collisions. Cela signifie que l'adversaire obtient au moins une paire, où la valeur hvalue et les valeurs sont les mêmes. Il s'avère donc qu'en appliquant la borne d'union, la probabilité de collision peut être facilement délimitée par ∑ ∑ Pr [ h = h ] − 1 1. Ce que je peux faire, c'est que je peux substituer la valeur de la sommation interne parce que maintenant je sais que la valeur de chacune des probabilités présentes dans la sommation interne est limitée par 1 |, et puisque les plages de 1 à et il existe de telles termes, donc dans le numérateur, nous obtenons et chacune de ces probabilités est 1 |. Donc, c'est ce que nous obtenons et si nous simplifient davantage, alors nous pouvons remplacer cette inégalité par ∑ 1 | | −, c'est-à-dire ce que nous avons fait ici, c'est que je peux toujours remplacer chacun de ces − par −, car est toujours borné par. Si je prends finalement cette sommation, depuis les plages de 1 à, je peux à la limite supérieure la probabilité de collision d'événements par (1) 2 (| | −). Alors, analysons maintenant cette inégalité finale pour 2 cas. Si le nombre de requêtes que l'adversaire a fait dans ce modèle idéal-cipher est délimité par la taille de plus de 2, alors nous pouvons faire une certaine simplification ici et finir par montrer que la probabilité de collision est en effet délimitée par des temps sur la taille de l'ensemble. D'autre part, si le nombre de requêtes que l'adversaire a fait est supérieur à la taille de plus de 2, alors trivialement il retient que la probabilité de collision est délimitée par ceci. Cela signifie que peu importe si nous sommes dans le cas 1 ou dans le cas 2, dans les deux cas, la probabilité de collision en faisant des requêtes est délimitée par des temps sur la taille de et qui établit le fait que nous avons déclaré dans ce théorème. Cela signifie que si on dit une fonction polynomiale dans le paramètre de sécurité et si |est une quantité significativement importante, par exemple une grande quantité exponentiellement grande dans le paramètre de sécurité, alors dans l'ensemble ce temps de probabilité sur la taille de s'avère être une fonction négligeable dans le paramètre de sécurité et c'est pourquoi nous pouvons maintenant conclure en toute sécurité que la construction de Davies Meyer est résistante aux collisions dans le modèle de chiffrement idéal et l'adversaire en évaluant la fonction Davies-Meyer pour le nombre de messages dans le modèle idéal-le modèle de chiffrement n'a pas pu aboutir avec une collision sauf avec un succès négligeable La probabilité. Cela m'amène à la fin de cette conférence. Pour résumer au cours de cette conférence, nous avons discuté de la façon de construire la fonction de compression à longueur fixe et il y a deux approches pour cela, une approche où nous utilisons des hypothèses de dureté de la théorie des nombres et nous obtenons des garanties prouvables dans le modèle standard, mais nous ne choisissons pas ces constructions dans la pratique parce que la quantité de calculs qui sont impliqués dans ces constructions sont d'ordre de plusieurs ordres de grandeur. Construction qui est très simple, mais il s'avère que même si pratiquement aucune attaque n'a été signalée sur ce

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