Loading
Notes d'étude
Study Reminders
Support
Text Version

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

    +

Foundations of CryptographyDr. Ashish ChoudhuryDepartment of Computer ScienceInternational Institute of Information Technology – BangaloreLecture – 45RSA AssumptionHello everyone, welcome to this lecture.(Reportez-vous à la page Diapositive: 00:42)So to recap in the last lecture, we have seen Candidate Public Encryption Scheme, CPA secure Public Encryption Scheme, mainly El Gamal encryption scheme. Dans cette conférence et la prochaine conférence, nous discuterons d'un autre schéma de chiffrement public candidat basé sur le problème dur différent, que nous appelons l'hypothèse RSA, qui nous mènera à un autre schéma de chiffrement public , à savoir le schéma de chiffrement public RSA.(Reportez-vous à la page Diapositive: 00:58)Pour comprendre l'hypothèse RSA, essayons d'abord de comprendre l'ensemble ZN*. ZN*est donc un ensemble d'entiers modulo N, qui sont co-premiers avec le module N, à savoir ZN* est la collection de tous les éléments b dans la gamme { 1, …, N-1 } de sorte que l'élément b est co-prime à le module N. Namely, leur GCD est 1. Par exemple, l'ensemble Z10 * n'est rien d'autre que les éléments 1,3,7 et 9.Parce que tous ces éléments 1, 3,7 et 9, ils sont co-premiers avec le module 10, et il est facile de voir que si le module N est premier, alors l'ensemble ZN* est constitué de tous les éléments 1 à N-1.Ainsi, un fait bien connu de la théorie des nombres dont la preuve que je suis ignorée est que le jeu ZN*avec l'opération modulo N constitue un groupe et satisfait tous les axiomes du groupe.Ainsi, par exemple, j'ai dessiné la matrice pour les éléments de Z10 *, à savoir 1, 3, 7 et 9, et le résultat de l'exécution. La multiplication d'opération modulo 10 pour tout élément de paire à partir de l'ensemble, et maintenant vous pouvez voir que tous les axiomes des groupes sont satisfaits et c'est pourquoi est un groupe. De plus, un fait bien connu de la théorie des nombres est que nous avons des algorithmes polytime pour le calcul de l'inverse multiplicatif, que je dénote, a-1, pour n'importe quel élément dans l'ensemble ZN*. Et il y a un algorithme bien connu pour cela, que nous appelons l'algorithme GCD d'Euclide étendu, dont nous discuterons dans l'une de nos conférences ultérieures, et le temps d'exécution de que l'algorithme est polynomial dans le nombre de bits dont nous avons besoin pour représenter le module N.(voir Heure de la diapositive: 02:47)So, let us next discutons Euler ’ s Totient Function, φ function. La fonction d'Euler ’ s Totient, , qui est désignée par le symbole φ (N), est essentiellement la cardinalité de l'ensemble ZN*, à savoir est le nombre d'éléments dans l'ensemble 1 à N-1, qui sont co-premiers à votre module N. Certains des faits connus à nouveau empruntés à partir de la théorie des nombres sont les suivants. Si N est le premier p, alors la valeur de φ (p) n'est rien d'autre que la valeur p -1. Parce qu'il y a exactement des éléments p-1, qui sont co-premiers à p. Par contre, si n est le produit de 2 nombres premiers distincts, p et q, alors φ (N) n'est rien d'autre que p-1 fois q-1. Cela signifie que contient ces nombreux éléments, à savoir p-1 fois q-1 éléments dans la plage { 1, …., N-1 }, qui sera co-prime à votre module N. Pour vérifier cela, prenons un exemple, disons N = 10, que vous pouvez écrire comme produit de 2 et 5, où 2 et 5 sont premiers. Donc votre p est 2 et votre q est 5, alors nous savons qu'il y a 4 éléments dans l'ensemble Z10 *, donc φ (10) doit être 4, et 4 n'est rien d'autre que p-1, à savoir 2-1 multiplié par q-1, qui est 5-1, et enfin une autre propriété intéressante que nous utiliserons à partir de la théorie des nombres est que, pour tout élément a dans le ZN*, un φ (N) modulo N est 1. Cela signifie que si N est un p, alors ce φ (N) n'est rien d'autre que p-1, donc nous obtenons ap-1 modulo p to be 1.Cette propriété ou ce résultat est également appelé Fermat ’ s Little Theorem, et nous obtenons également à cause de ce fait, le corollaire que si vous avez un élément appartenant à l'ensemble ZN*, alors ax modulo N est exactement le même que le ax modulo φ (N) modulo N. Cela signifie que dans l'exposant vous pouvez réduire l'exposant x à x modulo φ (N). La raison pour laquelle cette question corollaire est que, si votre x est de toute façon inférieur à φ (N), alors L.H.S. et R.H.S. sont identiques, mais si votre x est supérieur à φ (N)puis à calculer ax modulo φ (N), ce que vous pouvez faire est, vous pouvez réécrire le axsous forme de plusieurs lots d'un φ (N)avec φ (N) dans l'exposant. Un φ (N) en fonction de la relation entre x et φ (N), et le dernier lot de sera ax modulo φ (N), et tout ce qui se trouve dans le module de base N. Maintenant, nous savons que a φ (N) modulo N est 1, c'est-à-dire que chacun de ces lots, vous avez plein d'une φ (N) modulo N, vous allez pour vous donner la réponse 1. Donc, tous ces lots vont vous donner la réponse 1, 1, 1, 1 et 1 multiplié par 1 va vous donner 1. Donc, vous êtes enfin parti avec le dernier lot, qui a ax modulo φ (N). Donc, c'est ainsi que nous obtenons ce corollaire.(voir la diapositive: 06:03)Donc, avec toutes ces mathématiques en place, essayons maintenant de comprendre la permutation RSA. cette permutation RSA est donc un mappage de l'ensemble ZN* vers ZN*, de sorte que la façon dont cette permutation est est définie comme suit. Imaginez, vous avez un exposant e, qui est supérieur à 2, de sorte que l'exposant e est co-prime à votre valeur φ (N). Donc, je souligne qu'elle est co-primée à φ (N), pas à N.Now, un fait bien connu de la théorie des nombres est que si vous avez un e, qui est co-prime à φ (N), alors vous pouvez trouver l'inverse multiplicatif de ce e modulo φ (N).En général, si vous avez 2 nombres, disons a et b, de sorte que GCD de a et b est 1, cela signifie qu'un et b sont co-premiers entre eux, alors vous pouvez toujours trouver l'inverse multiplicatif d'un module modulo b. Donc, mon module dans ce cas est φ (N), car e est co-prime à φ (N), et si e est co-prime à φ (N), en utilisant l'algorithme Euclide étendu, je peux trouver d où e et d constituent leurs inverses multiplicatifs mutuels.Cela signifie, e fois d modulo φ (N), et d fois e modulo φ (N) est 1. Maintenant, la permutation RSA est définie comme suit. Pour aller dans la direction vers l'avant, la fonction est fe, et à calculer la valeur de fe (x) où x est un membre de ZN*, nous calculons en gros xeet faisons mod N. D'autre part, la fonction de direction inverse est fondamentalement une fonction d, à savoir, fd (y), et cette fonction est essentiellement si je veux calculer fd (y), je calculerai yd, et ensuite exécuter mod N.Je demande ici que la fonction fd est l'inverse de la fonction fe et vice versa. Donc, pour que considère n'importe quel x arbitraire ici, appartenant à ZN*, et que je le mappeais à y, selon la fonction fe,donc mon y n'est rien d'autre que xe, et maintenant laissez ’ voir ce que nous obtenons en inversant cette valeur y comme par la fonction fd. Si je renverse cette y comme par fd, alors j'obtiens xe mod N, puis j'ai une augmentation de la puissance d mod N.So I can take the overall mod outside, and I obtenons that this is the same as xetimes d modulo N, and by using the corollary that we have énoncé in the last slide, xed modulo N in the exponent, I can reduce this exponent e*d to e*d modulo φ (N). Je sais que e*d modulo φ (N), qui est là dans l'exposant, me donne la valeur 1, parce que j'ai choisi e et d de telle sorte que ils sont multiplicatifs entre eux.Donc, dans l'exposant, c'est e fois d modulo φ (N) réduit à 1, donc j'obtiens que ce module xedmodulo N n'est rien d'autre que x modulo N, et puisque j'ai choisi mon x pour appartenir à l'ensemble ZN*.Cela signifie que x est de toute façon inférieur à N, et si x est inférieur à N, alors x modulo N vous donne x de telle sorte que l'effet du mod ne se produit pas du tout. Donc cela prouve que votre fonction fd et fesont mutuellement inverses.Je prouve également ici que ma fonction fe (x) est une bijection, et cela signifie qu'il s'agit d'un un à un sur le mappage. Pour cela, considérons une paire arbitraire d'entrées x1, x2, de l'ensemble ZN*, et disent que les images résultantes de x1 et x2 selon la fonction fe sont y1 et y2. Maintenant, si y1 et y2 sont identiques, cela signifie que x1e modulo N, c'est le même que x2e modulo N, c'est-à-dire que si je soulève les deux faces à l'exposant d, j'ai x1ed modulo N est le même que le x2ed modulo N.Cela signifie essentiellement que x1 est égal à x2, car x1ed modulo N, n'est rien que x1 et x2edmodulo N n'est rien que x2. Donc, si je prends un mappage x1, x2 arbitraire à la même y, , alors je finens par montrer que x1 est égal à x2, et donc j'obtiens que ma fonction fe est une permutation ici.(Référez-vous à la diapositive: 10:32)Maintenant, discutons de l'hypothèse résultante, qui sera liée à l'hypothèse RSA, que nous enfin discuter. C'est ce qu'on appelle l'hypothèse de Factoring, et l'intuition qui sous-tend cette hypothèse est que, si on vous donne le produit de deux grands nombres premiers arbitraires, il s'avère que la des facteurs principaux est effectivement une tâche difficile. Il s'agit d'un problème très connu et bien étudié, pendant plusieurs siècles. Et jusqu'à présent, nous n'avons pas d'algorithmes de polytime efficaces pour factoriser un produit de deux premiers arbitraires, si ces nombres premiers sont choisis arbitrairement. Donc, cette intuition ou la dureté de ce problème va être formalisée par une expérience, et pour cette expérience , définissons d'abord un algorithme, que nous appelons l'algorithme GenModulus. En gros, sélectionne deux nombres premiers aléatoires n-bit, par exemple p et q, et il existe des algorithmes bien connus pour sélectionner des nombres premiers aléatoires.Je ne vais pas dans les détails exacts sur la façon exacte de choisir ces deux nombres premiers aléatoires , en poly (n) temps. Vous pouvez vous référer au livre de Katz et Lindell pour l'algorithme exact. Maintenant, une fois p et q sont choisis, vous calculez le module, à savoir N, qui est le produit p et q. Maintenant, l'hypothèse de l'affacturage, à l'égard de l'algorithme GenModulus, est modélisée comme une expérience, que nous appelons Experiment en facteur, et les règles de cette expérience sont les suivantes.Le challenger exécute l'algorithme GenModulus, génère le paramètre N, p, et q, et le défi est lancé à l'adversaire, à savoir N, et le défi pour l'adversaire est de trouver sa factorisation principale, à savoir p et q. Donc, il soumet une paire de nombres, p ’ et q ’, et nous disons que la sortie de l'expérience est 1, c'est-à-dire que l'adversaire a gagné l'expérience si, en effet, la paire p ’, q ’ est exactement la même que la factorisation principale de votre module N, et nous disons que l'Assomption de Factoring tient compte de notre algorithme GenModulus, si pour chaque adversaire polytime, la probabilité que l'adversaire puisse arriver avec la factorisation correcte du module N, est délimitée par une fonction négligeable. Remarquez que, il y a toujours une stratégie de deviner par un adversaire, il peut deviner quelques p ’ et q ’, et avec une probabilité non nulle, il peut en effet avec la factorisation correcte de N. (voir Diapositive Heure: 13:00)Ce que nous voulons, c'est qu'aucun adversaire polytime ne devrait être en mesure de faire quoi que ce soit de mieux que cela. C'est essentiellement l'intuition de cette expérience. Maintenant, voyons enfin l'hypothèse RSA ici. Ainsi, il s'avère que Factoring Assumption, même s'il ressemble à une fonction One-Way candidate à , c'est-à-dire que si je vous donne le produit de deux grands nombres premiers arbitraires et que vous vous défier de la factorisation, cela ressemble à une fonction One-Way candidate . Mais sur la base de cette fonction One-Way, nous ne pouvons obtenir directement un cryptosystème à clé publique pratique. Donc, pour contourner cela, nous introduisons un problème lié, que nous appelons comme un problème RSA, dont la difficulté est liée à la dureté du problème de factorisation . Donc, ce problème RSA est décrit par rapport à un autre algorithme de génération paramètres , que nous appelons GenRSA.Donc, ce que fait l'algorithme GenRSA, c'est qu'il exécute d'abord l'algorithme GenModulus et qu'il prend les nombres premiers aléatoires p et q de taille n-bits chacun, et les multiples pour obtenir le module N, et maintenant il calcule la valeur φ (N) et il est calculable car φ (N) n'est rien d'autre que le produit de p-1 et q-1. Ensuite, cet algorithme GenRSA sélectionne un exposant e de sorte que e est relativement premier ou co-prime à φ (N).Et comme e est co-prime à φ (N), en exécutant l'algorithme Euclid Extended, l'inverse multiplicatif de d de e modulo φ (N) peut être calculé. Dans l'ensemble, cet algorithme GenRSA génère maintenant N, p, q, e et d. Intuitivement, le problème RSA est, si vous n'avez qu'un public modulo N et l'exposant public e, et l'élément aléatoire y de l'ensemble ZN*, alors le défi pour vous est de calculer la racine de Y modulo N sans connaître la valeur réelle de d ou sans connaître la factorisation principale de N.Je souligne que le défi est de calculer la racine modulo N parce que si je vous mets au défi de calculer la racine de la eth sans modulo N, c'est très facile à faire. Le défi est ici de la valeur de la racine de eth modulo N, qui est formalisée par cette expérience que j'appelle expérimentation RSA-inv.L'expérience est la suivante: le challenger exécute l'algorithme GenRSA pour générer les paramètres N, p, q, e, d sont choisis au hasard à partir de l'ensemble ZN*. Encore une fois, si vous êtes en vous demandant que le choix d'un élément aléatoire à partir de l'ensemble ZN* est possible en poly (n) , vous pouvez voir le manuel de référence de Katz et Lindell où l'algorithme est donné pour choisir des éléments aléatoires.Maintenant, le défi pour l'adversaire est de découvrir la racine de cette ie aléatoire basée sur la connaissance du module public N et de l'exposant public e. Donc, il doit générer un élément de groupe dire x et nous disons que l'adversaire a gagné l'expérience ou que la sortie de l'expérience est 1, si et seulement si, x est en effet la racine de l'aléatoire y modulo N, à savoir si xemodulo N est y. Nous disons que l'hypothèse RSA tient compte de cet algorithme GenRSA, si pour chaque algorithme polytime participant à cette expérience, la probabilité qu'il puisse arriver avec la racine correcte d'un y est délimitée par une probabilité négligeable.(Référez-vous à l'heure de la diapositive: 16:23)Maintenant, laissez ’ essayer de comparer l'hypothèse RSA et la prise en charge Factoring, car sur un niveau élevé, ils pourraient ressembler à vous. Ainsi, sur votre gauche, vous disposez de l'expérience de factoring où le défi pour l'adversaire est de trouver les facteurs principaux du module public N. Sur le côté droit, vous avez la modélisation de l'expérimentation du problème RSA où l'adversaire est désormais doté de quelques informations supplémentaires dans le cadre de son défi, , c'est-à-dire qu'il est donné à l'exposant public e et au hasard y de l'ensemble ZN*, et que son but est de arriver avec la racine de x modulo N.Il s'avère que nous pouvons prouver que si l'hypothèse RSA détient, alors Factoring Assumption aussi contient et ceci peut être prouvé par Controltive, à savoir, si vous supposez que l'affacturage est facile à calculer , cela signifie qu'il est possible pour un adversaire polytime de générer une factorisation primaire p, q d'un module N. Ensuite, une fois que vous factorisez votre module N dans sa factorisation principale de p et q, vous pouvez facilement calculer φ (N) car φ (N) n'est rien d'autre que p-1 fois q-1.Et si φ (N) est calculable en polytime et de toute façon, en exécutant l'algorithme Extended Euclid, vous pouvez calculer l'inverse multiplicatif de e, à savoir d, et une fois que vous avez calculé d, la racine eth De y n'est rien d'autre que yd modulo N. Cela signifie que cette implication est en effet vraie. D'autre part, laissez ’ essayer de considérer la relation entre la prise en charge Factoring et RSA, dans le sens, peut-on dire que si Factoring Assumption tient, alors l'hypothèse RSA est valable et nous n'avons pas de réponse à cela. Cela signifie que nous ne peut pas prouver que si l'hypothèse RSA ne tient pas et que la prise en charge Factoring n'est pas . Il s'agit d'un problème d'ouverture car il peut y avoir un moyen de résoudre efficacement le problème RSA sans tenir compte de votre module. Etant donné que l'une des manières de résoudre le problème RSA peut être de factoriser votre N, puis une fois que la factorisation est connue, revenez avec la valeur d et ainsi de suite, mais ce n'est pas le seul moyen de résoudre le problème RSA. Il peut y avoir d'autres façons de résoudre le problème RSA dans le temps polynomial sans tenir compte de la factorisation de votre module, et dans ce sens , la prise en charge de RSA est une hypothèse très forte par rapport à la prise en compte de l'hypothèse de l'affacturage , car la difficulté à prendre en compte la difficulté, le problème de l'affacturage semble être un problème plus difficile , un problème plus difficile que la résolution du problème RSA.(Référez-vous à la diapositive: 19:05)Donc, nous allons enfin discuter de la façon dont vous pouvez utiliser votre Permutation RSA comme une permutation Permutation car lors de notre prochaine conférence, nous allons traiter Notre permutation RSA en tant que permutationTrapdoor, et nous verrons comment nous pouvons formuler une instanciation du schéma de cryptage public à partir de cette permutation RSA. Par conséquent, pour ce rappel, la définition de la permutation One-Way Trapdoor.Ainsi, il s'agit d'une fonction de l'ensemble x à l'ensemble x, qui est facile à calculer pour n'importe quelle entrée du domaine , mais qui est difficile à inverser à partir d'une entrée aléatoire du co-domaine, jusqu'à , sauf si vous avez reçu des informations de trapdoor spéciales. Ainsi, ceci est formalisé en disant que plus formellement nous avons un schéma de permutation trapdoor sur l'ensemble x, qui consiste en un algorithme de génération de clé , une fonction trapdoor f, et son inverse où l'algorithme de génération de paramètres va générer un paramètre public et un paramètre secret, la fonction f est fondamentalement, une fonction de clé , indexée par la clé publique pk et elle prend de la valeur à partir de l'ensemble x et elle vous donne sortie de l'ensemble x et il s'agit d'un algorithme déterministe et l'algorithme inverse est utilisé par une clé secrète, donc votre clé secrète agit essentiellement comme une clé secrète. Informations sur le fichier trapdoor ici et à l'aide de ces informations trapdoor, vous pouvez inverser n'importe quelle y à partir du codomaine , à savoir l'ensemble x. La propriété correcte que nous avons besoin du schéma de permutation de trapdoor est que pour chaque paire de paramètre générée par l'algorithme de génération, pour chaque x de votre domaine, si vous calculez la valeur de fpk (x), et que vous obtenez la sortie y, et maintenant si vous inversez cette y avec la clé secrète sk, vous devez récupérer le x, et une seconde exigence est l'exigence d'une "wayness", qui indique que votre fonction f doit se comporter comme une fonction unidirectionnelle, même si un adversaire connaît la valeur du paramètre public pk.(voir la diapositive: 21:09)So, let us see how Nous pouvons visualiser la permutation RSA de l'ensemble ZN* à ZN* en tant qu'instanciation de la permutation Trapdoor. Ainsi, l'algorithme RSA Trapdoor Permutation est composé dede trois algorithmes, l'algorithme de génération de paramètres n'est rien d'autre que l'algorithme GenRSA, , c'est-à-dire qu'il choisit les nombres premiers aléatoires uniformément aléatoires, p et q, calculent le module N, , puis calculent la taille de ZN*, à savoir φ (N).Il sélectionne l'exposant public e, de sorte que e est co-prime à φ (N). Etant donné que e est co-prime à φ (N), en exécutant l'algorithme Euclide étendu, l'inverse multiplicatif de e modulo φ (N) est calculé et les paramètres publics sont N, e, et les paramètres secrets sont N, d. La fonction de direction aval , à savoir la fonction fRSA, et gérée avec la clé publique N, e est la suivante: . Pour calculer la valeur de cette fonction fRSA sur une entrée x, vous ne pouvez utiliser que la sortie modulo N, et le module de modulation N peut être calculé en poly (n) time. Nous verrons plus loin comment exactement ce groupe exponentiation peut être calculé en polynôme en n quantité de temps. D'autre part, si vous avez une trappe, à savoir un paramètre secret n, d et si vous voulez inverser tout donné à partir de l'ensemble ZN*. Fondamentalement, vous devez calculer yd modulo N. So, let ’ s voir si cette carte RSA Trapdoor Permutation satisfait en effet à l'exigence d'un schéma générique de permutation de trappe. Par conséquent, l'exigence de correction indique que, elle doit tenir que xesuivi de l'élévation à d modulo N, devrait me donner mon x et nous avons déjà prouvé que c'est le cas lorsque nous avons montré que la fonction f et la fonction RSA inverse sont inverses.D'autre part, la propriété One-Wayness de cette permutation RSA requiert que quiconque connaisse uniquement le paramètre public, à savoir N, e, mais ne connaisse pas les informations de trapdoor , par exemple d, sans que la connaissance des informations de la porte du trapu soit faite, il est difficile de calculer la racine de tout aléatoire. Y, et il s'avère que c'est le cas si l'hypothèse de RSA tient compte de votre algorithme de génération de paramètres.Si le problème RSA est en effet difficile à résoudre en ce qui concerne cet algorithme de génération de paramètres RSA alors ce que l'on appelle la permutation RSA peut être considéré comme une instanciation de votre Trapdoor Permutation. Par conséquent, rappelez-vous que dans l'une de nos conférences précédentes, nous avons vu que nous pouvons, de façon générique, convertir le schéma de permutation de Trapdoor en un protocole avec une notion de secret faible.Et maintenant si vous instanciez la permutation Trapdoor par une permutation de Trapdoor RSA, puis par à l'aide du protocole RSA Trapdoor Permutation, nous obtenons en fait un protocole d'échange de clés RSA, qui vous donne une notion de secret faible, à savoir que la clé résultante sera connue de l'expéditeur et du récepteur, et que l'adversaire ne saura pas la clé complète dans son intégralité. Dans l'autre main , la fonction de journalisation discrète dont nous avons discuté précédemment, elle ne peut pas être considérée comme une instanciation de la permutation Trapdoor. Parce que nous connaissons la fonction d'acheminement vers l'avant, c'est-à-dire que gxpeut être traitée comme la fonction de direction avancée de , mais nous ne savons pas ce qui doit être les informations de trapdoor correspondant à l'aide desquelles nous pouvons utiliser et inverser cette fonction. C'est une sorte de gros problème qui est là. D'autre part, dans le contexte de la permutation RSA, nous avons la trappe correspondante associée, à savoir l'exposant d, qui est l'inverse multiplicatif de e, modulo φ (N). Cela m'amène à la fin de cette conférence. Dans cette conférence, nous avons introduit l'hypothèse RSA , et nous avons vu la relation entre le problème RSA et le problème de factoring . Je vous remercie.