Ciphers en bloc | Construction théorique | Alison
Loading
Notes d'étude
Study Reminders
Support
Text Version

Construction théorique des phérères en bloc

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 (Former) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BangaloreLecture-18Theoretical Constructions of Block CiphersHello tout le monde, bienvenue à la conférence 17. Dans cette conférence nous allons voir des constructions théoriques de chiffrements par bloc. Plus précisément, la feuille de route pour cette conférence est la suivante. (Référez-vous à la diaporama: 00 :37) Ainsi, jusqu'à la dernière conférence, nous avons vu que si nous avons une fonction pseudo-aléatoire, nous pouvons concevoir des systèmes sécurisés de CPA candidats à l'aide de la plupart des opérations de pseudo-fonctions aléatoires. Mais maintenant, la question est de savoir comment nous allons réellement concevoir la fonction pseudo-aléatoire. Et il s'avère qu'il y a 2 façons de concevoir des fonctions pseudo aléatoires. La première phase, la première classe des constructions sont les constructions sûres, que nous allons discuter ici. Et ils sont considérés comme des constructions théoriques parce que ce n'est pas ainsi que nous instancions des fonctions pseudo-aléatoires dans les protocoles du monde réel. Dans les conférences ultérieures, nous verrons les constructions pratiques, à savoir les constructions que nous utilisons dans le monde réel pour instancier une fonction pseudo-aléatoire. Cependant, même si nous n'utilisons pas les instanciations théoriques de fonctions pseudo aléatoires, elles sont très fondamentales, elles sont d'une importance fondamentale en cryptographie parce que, mathématiquement, nous montrons que les constructions que nous allons discuter peuvent être sécurisées sur la base de l'hypothèse qu'il existe une fonction de fonctionnement, c'est-à-dire que nous avons maintenant des garanties mathématiques que les constructions que nous allons voir dans cette conférence elles sont sûres, alors que les instanciations dites pratiques que nous allons dire dans les conférences suivantes, pour ces constructions Nous n'avons aucune garantie de sécurité prouvable qui signifie qu'il n'y a pas de preuve mathématique que ces constructions répondent aux définitions de pseudo-fonction aléatoire, de pseudo-permutations aléatoires, etc. Ce n'est qu'une croyance ou une supposition que depuis leur découverte, aucune attaque ou aucune carence n'ont été rapportées dans ces constructions. Et c'est pourquoi nous pensons que ces constructions émulent le comportement d'une fonction pseudo-aléatoire, de permutations pseudo-aléatoires et ainsi de suite. Donc maintenant de revenir à cette conférence, la feuille de route pour cette conférence est la suivante: nous allons voir comment construire des fonctions pseudo-aléatoires sécurisées de manière provablement sécurisée, étant donné que des pseudo-générateurs pseudo-aléatoires sont sécurisés. Ensuite, nous verrons les constructions de permutations pseudo-aléatoires sécurisées de façon prouvable à partir d'une pseudo fonction pseudo-aléatoire sécurisée. Et cette construction est aussi appelée Luby?Rackoff construction attribuée au nom de leurs inventeurs. Et enfin, nous verrons comment construire des permutations pseudo-aléatoires fortes et sécurisées, étant donné la sécurité pseudo-aléatoire de la permutation pseudo-aléatoire. (Référez-vous à la diapositive: 02 :59) Alors, faisons la première chose ici. Nous verrons comment si on vous donne un générateur pseudo-aléatoire sûr, nous verrons comment construire une pseudo-permutation pseudo-aléatoire sécurisée. Et pour le but de la démonstration, je suppose que j'ai un générateur de longueur pseudo-aléatoire. Et vous pouvez construire de façon sécuritaire à partir d'une fonction à sens unique en utilisant la construction de Goldreich-Levin et en supposant qu'il existe un prédicat dur. Donc, rappelez-vous dans l'une de nos conférences précédentes, nous avons vu des constructions sécurisées de pseudo-générateur aléatoire, où nous avons d'abord développer la sortie ou l'entrée du pseudo-générateur aléatoire d'un bit à l'aide d'un prédicat dur, puis nous faisons la composition en série de ce pseudo-générateur pseudo-aléatoire polynomial nombre de fois pour étendre la longueur du pseudo-générateur aléatoire par n'importe quel montant polynomial. Générateur, à savoir un générateur de longueur double pseudo-aléatoire et mon but est essentiellement de construire PRF:. La construction est appelée construction d'arbre. Et la raison pour laquelle il est appelé une construction d'arbre est que, fondamentalement, la façon dont nous définissons la fonction clé Fk est que nous construisons un arbre binaire complet de profondeur constitué de 2nleaf nodesoù chaque nœud de feuille sera constitué de pseudo-chaîne aléatoire de longueur 2n bits déterminée par la valeur de la clé sous-jacente k. Maintenant, la raison pour laquelle nous allons construire un arbre binaire complet de profondeur n est que nous allons avoir 2nfeuilles et chaque nœud de feuille est fondamentalement une valeur de la fonction Fk. Et cela correspond à notre sémantique de la fonction clé Fk que nous sommes intéressés à construire parce que la taille de bloc de ma fonction clé sous-jacente que je veux construire est n bits. Cela signifie que ma fonction Fk (i), à savoir l'intervalle de ce i: 0 ≤ i ≤ 2n-1. Il y a donc 2ncandidats pour cette fonction. C'est pourquoi je suis intéressé à concevoir un arbre constitué de 2nnodes. Et la valeur de la valeur ou la valeur de la fonction clé Fk sur l'entrée i sera essentiellement la pseudo-chaîne aléatoire que Iam va stocker sur le noeud de la moelle dans ce tree.Donc, tout le truc se résume à la façon dont cet arbre va être défini comme une fonction de ma clé sous-jacente k. Donc, pour la démonstration, je suppose que j'ai un pseudo-générateur aléatoire. Et en utilisant que je dois concevoir une fonction pseudo-aléatoire à clé,. La construction est la suivante: il s'agit donc de votre arbre binaire complet de 8 nœuds. Donc c'est ta feuille de 0e. C'est ta première feuille et ça comme ça, c'est ta 7ème feuille. Et cela dénote les chaînes que nous allons stocker dans chacun de ces noeuds terminaux respectifs dénote la valeur de la fonction F que nous allons définir à leurs entrées respectives. Maintenant, voyons ce qui sera exactement les chaînes de bits qui vont être stockées dans chacun de ces noeuds internes et les noeuds terminaux. Donc pour commencer avec à la racine de l'arbre, nous allons stocker la valeur k0k1 qui est une chaîne de longueur de 6 bits, et qui est générée en invoquant en fait le pseudo générateur aléatoire sur la clé k. Donc, rappelez-vous que k est fondamentalement la clé de la fonction pseudo-aléatoire que je suis intéressée de concevoir, mais maintenant cette clé que j'utilise comme graine pour le pseudo-générateur aléatoire. Et comme mon pseudo générateur aléatoire étend la graine et me donne une sortie qui est deux fois la taille de l'entrée, je vais obtenir une sortie pseudo-aléatoire que je peux analyser comme 2 blocs de 3 bits, 3 bits chacun. Maintenant dans ma note de gauche, qui est qu'avec l'enfant gauche de cette racine, j'ai essentiellement stocké la sortie du pseudo-générateur aléatoire sur l'entrée k0. Souvenez-vous, la chaîne k0k1 est une chaîne de longueur 3 bits. Donc vous avez 3 bits ici, vous avez 3 bits ici, la première partie de 3 bits je dénote en k0, et j'appelle la fonction G sur cette entrée pour obtenir à nouveau une nouvelle pseudo-chaîne aléatoire de 6bits, qui encore une fois, je peux diviser en 2 parties. Et le bon enfant de ma racine stocke la valeur de la sortie du pseudo-générateur aléatoire sur la chaîne k1, ce qui va maintenant me donner une autre pseudo-chaîne aléatoire de longueurs 6bits que je peux analyser comme 2 morceaux de 3 bits, 3 bits chacun. Et puis je répète ce processus à la première couche de cet arbre, c'est-à-dire que ce nœud aura désormais le résultat du pseudo-générateur aléatoire sur les 3 bits k00 comme entrée, et cette note aura la sortie du pseudo-générateur aléatoire sur la graine k01. Et encore une fois, j'ai une sortie de 6 bits, et ainsi de suite. C'est ainsi que les notes internes sont remplies. De même, j'ai rempli les notes foliaires en utilisant la même logique. Comment exactement je vais aller à la sortie Fk (i)? Donc imaginez, tout cet arbre est fondamentalement la définition de Fk. Maintenant, je dois définir ce qui sera exactement la sortie de cet arbre sur mon entrée i. Donc rappelez-vous, la fonction clé F prend 2 entrées, l'entrée de clé et l'entrée de bloc réel. Donc, pour ce qui est de l'intrant clé, j'ai défini un arbre comme ça. Maintenant, je dois définir comment je prends la sortie de cet arbre pour l'entrée i. Alors imaginez par exemple, je veux définir ou calculer la valeur de cette fonction appelée Fk à l'entrée 3. Donc 3 en binaire peut être écrit comme 011. Et en gros, l'idée est maintenant que je dois juste passer cet arbre basé sur la représentation binaire de 3.Donc, je passe le premier bit ici qui est 0, si c'est 0, la règle est que je vais à la gauche de mon noeud courant, donc, je commence à explorer à partir du premier bit racine est 0 Je vais à la note de gauche, le bit suivant dans la représentation binaire de 3 est 1. Donc, de ma note actuelle, je vais à la droite et le dernier bit dans la représentation binaire des 3s sont 1. Donc, c'est-à-dire de ma note actuelle, je vais à la droite et ce sera la valeur de ma fonction Fk à l'entrée 3.C' est ainsi que je vais définir ma fonction Fk. Donc, si vous voyez sur un très haut niveau essentiellement la façon dont la fonction Fk est définie, ce n'est rien d'autre que le nombre polynomial de compositions séquentielles du générateur vraiment aléatoire. Je compose essentiellement le pseudo-générateur aléatoire G polynomial nombre de fois en fonction de la représentation binaire de mon entrée i. Dans ce cas, la représentation binaire était 011.Donc, je m'appelle fondamentalement la fonction G trois fois dans la séquence une après l'autre où le résultat de l'appel précédent de G sert d'entrée pour le prochain appel d'une manière spécifique. Selon la représentation binaire de mon entrée i, c'est ainsi que vous pouvez interpréter en interne l'exécution ou la construction de cette fonction clé Fk. (Voir Diapositive Heure: 10 :49) Maintenant, vous vous demandez peut-être si cette construction est efficace ou non, parce que la taille de l'arbre est exponentielle ici. Il se compose de 2n nombre de noeuds et où n est le paramètre de sécurité. Donc cela signifie que si je définit la fonction Fk comme ça, alors on pourrait penser que l'expéditeur et le récepteur doivent maintenir cet arbre parce qu'une fois qu'ils connaissent la valeur du k, ils doivent construire l'arbre comme ça. Parce qu'ils ne savent pas bien à l'avance quelle est la valeur de l'i qu'ils vont utiliser, il pourrait être fini avec n'importe lequel des noeuds terminaux. Donc, s'ils avaient l'arbre entier avec eux à l'avance, mais le stockage de l'arbre entier leur demandera une quantité exponentielle de calcul. Donc, intuitivement, cette construction pourrait ressembler à une construction inefficace, mais il s'avère que l'arbre entier n'est pas calculé et stocké pour calculer la valeur de la fonction discrète sur l'entrée i. Parce que selon l'exigence, cela signifie en fonction de la valeur de i, je peux calculer la partie réelle que j'ai besoin de suivre dans cet arbre en invoquant juste mon pseudo générateur pseudo-aléatoire n nombre de fois. Par exemple, si je veux calculer la valeur de la fonction Fk (i = 3), ce dont j'ai fondamentalement besoin n'est que 3 appels du PRG. C'est tout. Je n'ai pas besoin des autres appels de la PRG.De la même façon supposons plus tard que je suis intéressé par le calcul de la valeur de dire Fk (4) donc, dans la représentation binaire est 100, alors je n'ai pas besoin de l'arbre entier. Je n'ai besoin que de ce noeud, à savoir les appels du PRG, suivi de cet appel du PRG, suivi de cet appel du PRG. Cela signifie que chaque valeur de Fk (i) peut être calculée simplement en exécutant le nombre polynomial d'instances du pseudo-générateur pseudo-aléatoire sous-jacent. C'est pourquoi cette construction est efficace sur le plan informatique. Il ne demande pas une quantité exponentielle de calcul. Maintenant, la grande question est cette construction d'arbre, ou cette façon de définir la fonction clé Fk va effectivement me donner un PRG sécurisé. La réponse est oui. Parce que intuitivement ce qui est Fk (i), quelle est la façon dont j'ai calculé Fk (i). Fk (i) vous pouvez interpréter comme un nombre polynomial de compositions séquentielles de PRG.Remember, lorsque nous discutaient plus tôt de pseudo-générateur aléatoire, nous avions provedrigorously que le nombre polynomial de composition séquentielle de PRG vous donne aussi un générateur pseudo-aléatoire, c'est-à-dire que la sortie sera pseudo-aléatoire et qu'elle ne se distinguera pas du résultat d'un générateur vraiment aléatoire correspondant. Donc, en ce sens, cette façon de définir la fonction Fk basée sur un arbre binaire complet va en effet définir une fonction pseudo-aléatoire. Mais maintenant, si je veux formaliser cette intuition en une preuve rigoureuse, alors il y a beaucoup de subtilités qui sont impliquées ici. (Référez-vous à la diapositive: 13 :52) Donc la preuve réelle est effectivement suttle et elle nécessite beaucoup de détails techniques avancés. Donc, en raison de l'intérêt du temps et puisque la preuve est vraiment hors de portée de ce cours, je vais éviter les détails formels complets de la preuve. Mais si vous êtes vraiment intéressé à voir la preuve complète, vous pouvez voir la preuve disponible dans le livre de Claude Shannon mais laissez-moi discuter de la preuve globale idea.Donc, comme je l'ai dit, la valeur de la Fk (i) n'est rien d'autre que le nombre polynomial d'invocations du pseudo-générateur aléatoire. Donc, mon but est essentiellement de montrer que, si un adversaire interagit avec la fonction keyedfunction Fk en demandant un nombre polynomial de requêtes où il ne connaît pas la valeur de k, il connaît la structure de l'arbre, mais il ne connaît pas la valeur du k et donc, il ne sait pas ce que sont les pseudo-flux aléatoires qui sont stockés dans les différents noeuds. Donc, imaginez si j'ai un adversaire qui interagit avec Fk (i) ou une fonction Fk polynomial nombre de fois, mon but est de montrer qu'il ne devrait pas être capable de distinguer le comportement de la construction de l'arbre du comportement d'une fonction vraiment aléatoire, mais je ne peux pas directement Réduire cette indistinction à la sécurité de la sécurité sous-jacente du pseudo-générateur aléatoire, car il existe un nombre polynomial d'invocations du pseudo-générateur aléatoire impliqué. Donc, ce que nous avons demandé ici, c'est l'argument hybride. (Référez-vous à la diapositive: 15 :19) Donc, voyons la sécurité de la construction de l'arbre essentiellement, nous avons une vue d'ensemble de l'idée de preuve ici. Et pour la démonstration de l'idée de la preuve, je prends le cas où je construis une fonction pseudo-aléatoire, ceci est conçu à l'aide d'un pseudo-générateur aléatoire .Donc, comme dans la construction de l'arbre dont nous avons discuté tout à l'heure, voici comment la fonction Fk ressemblera et maintenant, ce que je vais faire, c'est que je vais comparer cette construction en fonction de l'arbre de la fonction Fk avec une autre construction, où toutes les instances du pseudo générateur aléatoire G vont être remplacées par un générateur vraiment aléatoire G ’. Donc, ce que nous essayons de construire ici, c'est que nous essayons de construire un non-clé. Fonction aléatoire qui prend une entrée de taille 3 bits et elle vous donne une sortie de 6 bits. Et à un niveau très élevé, la construction est exactement la même que celle de l'arbre, sauf que, à chaque nœud, tous les appels de votre fonction G sont remplacés par G ’. Donc, au noeud racine, on appelle la fonction G ’ .Et puisque la fonction G ’ est un générateur aléatoire vrai, elle ne prend aucune entrée. Il vous suffit de vous donner une sortie aléatoire de 6 bits qui sera remplie dans cette racine. Ensuite, lorsque nous allons à nouveau sur le noeud de gauche, nous invoquerons la fonction G ’, ce qui vous donnera une autre chaîne de 6 bits, vraiment aléatoire. Et comme ça, vous pouvez voir que chaque noeud que nous invoquerons simplement par fonction G ’ .Et comme résultat, chacun de ces noeuds dans cet arbre, qui est construit sur la partie droite, aura 2 valeurs aléatoires de longueur 6 bits. C'est ainsi que nous avons construit la fonction f. Donc, maintenant la différence de construction entre les deux fonctions que nous avons construites est que si nous voulons à gauche k, elle définit votre fonction Fk. Et si je veux calculer la valeur de cette fonction à quelques entrées, je dis par exemple, si je veux trouver la valeur de cette fonction, sur votre côté gauche sur l'entrée est égal à dire tous 0s.Ensuite, je dois suivre le chemin 000 et la valeur de mon Fk (i) sera la valeur stockée ici. Et nous disons d'autre main, si je veux calculer la valeur de la fonction f que j'ai construite dans la partie droite sur l'entrée toutes les années 2000, je dois suivre alors que je dois traverser cet arbre comme par la représentation binaire de mon entrée i et où j'ai arrêté le nœud terminal, la valeur qui y est stockée, qui sera considérée comme la valeur de la fonction f sur l'entrée i.Donc, en ce qui concerne la façon dont je suis l'informatique et l'obtention de la sortie de la fonction, elle reste la même dans les deux fonctions. Ce qui diffère dans les deux fonctions est que l'arborescence côté gauche, tous les appels sont pour un générateur pseudo-aléatoire et l'arborescence côté droit tous les appels sont pour un générateur de nombre aléatoire réel. Maintenant de façon informelle, la preuve de l'idée derrière la sécurité de la construction de l'arbre que nous avons donnée est que si la fonction sous-jacente G est un PRG sécurisé, ce que nous allons montrer est dans la preuve qu'aucun temps polynomial ne doit être capable de distinguer la valeur de la fonction, Fk sur l'entrée i de la valeur de la fonction f sur l'intrant i. Cela signifie, peu importe s'il a interagi avec la construction de l'arbre sur le nombre de temps polynomial côté gauche, ou s'il a interagi avec l'arbre sur le nombre polynomial côté droit du temps, du point de vue de L'adversaire, l'interaction doit être presque identique sauf avec une probabilité négligeable. Si, en effet, ma fonction G est un PRG sécurisé. C'est donc ce qui est fondamentalement l'idée générale de la preuve. (Référez-vous à la diapositive: 19 :39) C'est ce que je dois montrer. Et l'idée derrière une preuve ici est que nous définissons en gros n + 1 un arbre binaire complet, chaque profondeur n, où chaque noeud va stocker des chaînes de bits 2n, mais d'une manière différente. Commençons donc par l'arbre T0, qui est en fait un arbre de profondeur dans un arbre binaire complet de profondeur n où chacun des nœuds se compose essentiellement d'une chaîne uniformément aléatoire de 1 n-bit. Et ceci n'est rien d'autre que la façon dont une fonction vraiment aléatoire f va se comporter comme par l'arbre constructionet mon arbre i sera comme suit. Dans mon arbre Ti, les premiers niveaux de n-i, tous les noeuds de ces niveaux n -i sont constitués de chaînes de caractères uniformément aléatoires, alors que tous les niveaux restants seront constitués de chaînes pseudo-aléatoires en appliquant le mécanisme clé ou la construction clé au niveau précédent. Si je vais à la clé i = 1ème la façon dont il diffère de la clé de la moelle est qu'il aura une couche moins de pseudo-chaînes aléatoires et une couche plus de pseudo-chaînes aléatoires par rapport à la chaîne précédente. Et nous savons aussi que nous pouvons construire un système de cryptage sécurisé de CPA à partir de FPR en utilisant des modes de fonctionnement. Plus tard dans ce cours, nous allons voir comment nous pouvons en fait construire un processus de chiffrement symétrique plus puissant, à savoir le chiffrement authentifié et le chiffrement sécurisé CCA juste à l'aide de fonctions pseudo-aléatoires. Il s'avère donc que tout dépend de l'existence d'une seule façon de fonctionner qui signifie que si vous voulez des constructions sécurisées de façon prouvable, un schéma de cryptage sécurisé de l'ACP, un système de cryptage sécurisé, un schéma de cryptage authentifié et sécurisé, il est alors possible d'avoir une seule façon de fonctionner. Cela signifie qu'il suffit d'avoir une fonction unidirectionnelle que vous pouvez tout obtenir gratuitement. Et plus tard dans ce cours, lorsque nous discuterons de la cryptographie à clé publique, nous verrons comment nous pouvons aller exactement et construire des fonctions basées sur des hypothèses de dureté de nombres spécifiques. Donc tout se résume à l'existence de fonctions unidirectionnelles. Donc, ça m'amène à la fin de cette conférence. Pour résumer au cours de cette conférence, nous avons vu une vue d'ensemble très générale de la façon dont nous donnons des constructions sûres de pseudo-fonction aléatoire, de permutation pseudo-aléatoire et de pseudo-compétition pseudo-aléatoire. Merci !

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