Loading
Notes d'étude
Study Reminders
Support
Text Version

Cryptosystème de clé publique RSA

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 Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Lecture – 45 RSA Assumption Hello everyone, welcome to this lecture. (Référez-vous à la diapositive: 00:42) Donc juste pour récapitulation lors de la dernière conférence, nous avons vu Public Encryption Scheme, CPA secure Public Encryption Scheme, principalement le programme de cryptage d'El Gamal. Au cours de cette conférence et de la prochaine conférence, nous discuterons d'un autre système de cryptage public des candidats basé sur le problème difficile, que nous appelons l'hypothèse RSA, qui nous mènera à un autre schéma de cryptage public, à savoir le système de cryptage public RSA. (Reportez-vous à la page Heure de la diapositive: 00 :58) Pour comprendre l'hypothèse RSA, essayons d'abord de comprendre l'ensemble ZN*. Donc ZN* est essentiellement un ensemble d'entiers modulo N, qui sont co-premiers au 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 au 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 modulo 10, et il est facile de voir que si le module N est premier, alors l'ensemble ZN* est essentiellement constitué de tous les éléments 1 à N-1. Donc, un fait bien connu de la théorie des nombres dont la preuve je suis sauté est que le set ZN* avec la multiplication d'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 de la multiplication d'opération modulo 10 pour tous les éléments de paires de l'ensemble, et maintenant vous pouvez voir que tous les axiomes des groupes sont satisfaits et c'est pourquoi il s'agit d'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 par, a-1, pour tout élément a 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 cet algorithme est polynomial dans le nombre de bits dont nous avons besoin pour représenter le module N. (Référez-vous à la diapositive: 02 :47) Donc, discuterons ensuite de la fonction d'Euler ’ s Totient, fonction φ. Ainsi, la fonction d'Euler ’ s Totient, qui est désignée par le symbole φ (N), est essentiellement la cardinalité de l'ensemble ZN*, à savoir le nombre d'éléments de 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 un p premier, alors la valeur de φ (p) n'est rien d'autre que 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 qu'il y a ces nombreux éléments, à savoir p-1 fois q-1 éléments dans la gamme { 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 le set Z10 *, donc φ (10) devrait être 4, et 4 n'est rien d'autre que p-1, à savoir 2-1 multiplié par q-1, ce qui est 5-1, et enfin une autre propriété intéressante que nous utiliserons de la théorie des nombres est que, pour n'importe quel é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 l'ap-1 modulo p pour être 1. Cette propriété ou ce résultat est aussi appelé Fermat ’ s Little Theorem, et nous sommes également dus à 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). Donc, 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 plus que φ (N) alors pour calculer le ax modulo φ (N), ce que vous pouvez faire est, vous pouvez réécrire le ax sous forme de plusieurs lots d'un φ (N) avec φ (N) dans l'exposant. A φ (N) en fonction de la relation entre x et φ (N), et le dernier lot aura modulo φ (N), et tout ce qui se trouve dans le module de base N. Maintenant, nous savons qu'une φ (N) modulo N est 1, c'est-à-dire que chacun de ces lots, vous avez pleine une φ (N) modulo N, vous donnera 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 finalement laissé avec le dernier lot, qui a une ax modulo φ (N). Donc, c'est comme ça que nous obtenons ce corollaire. (Référez-vous à la diapositive: 06:03) Donc, avec toutes ces mathématiques en place, essayons maintenant de comprendre la permutation RSA. Donc cette permutation RSA est un mappage de l'ensemble ZN* vers ZN*, donc la façon dont cette permutation 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'il est co-primé à φ (N), pas à N. Now, un fait bien connu de la théorie des nombres c'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, a et b sont co-prime l'un à l'autre, alors vous pouvez toujours trouver l'inverse multiplicatif d'un modulo b. Donc, mon module dans ce cas est φ (N), parce que 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 globalement xe et faisons mod N. D'autre part, la fonction de direction inverse est fondamentalement une fonction d, c'est-à-dire, fd (y), et cette fonction est fondamentalement si je veux calculer fd (y), je calculerai yd, et ensuite effectuer mod N. Je demande ici que la fonction fd est l'inverse de la fonction fe et vice versa. Donc, pour cela, considérer n'importe quel x arbitraire ici, appartenant à ZN*, et dire que je la mappela à 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 selon la fonction fd. Si je renverse cette y comme par fd, alors j'obtiens xe mod N, puis j'ai une augmentation à la puissance d mod N. Donc je peux prendre le mod global à l'extérieur, et j'obtiens que c'est le même que les temps de xe d modulo N, et en utilisant le corollaire que nous avons indiqué dans la dernière diapositive, xed modulo N dans l'exposant, je peux réduire cet exposant e*d à 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 qu'ils sont de multiplicative inverse l'un de l'autre. Donc, dans l'exposant, c'est e fois d modulo φ (N) réduit à 1, donc j'ai obtenu que ce module xed modulo 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 telle que l'effet du mod ne se produit pas du tout. Cela prouve que votre fonction fd et fe sont mutuellement inverses. Je prouve aussi ici que ma fonction fe (x) est une bijection, et cela signifie qu'il s'agit d'un seul à un 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 côtés à l'exposant d, j'ai x1 ed modulo N est le même que le x2 ed modulo N. Cela signifie essentiellement que x1 est égal à x2, parce que x1 ed modulo N, n'est rien que x1 et x2 ed modulo N n'est rien d'autre que x2. Donc ça veut dire, si je prends un mappage arbitraire x1, x2 à la même y, puis en gros je termine par montrer que x1 est égal à x2, et donc j'ai l'impression générale que ma fonction fe est une permutation ici. (Référez-vous à la diapositive: 10 :32) Maintenant, discuterons de l'hypothèse qui en découle, qui sera liée à l'hypothèse de la RSA, dont nous discuterons enfin. C'est ce qu'on appelle l'Assomption 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 recherche des principaux facteurs est effectivement une tâche difficile. Il s'agit d'un problème très connu et bien étudié qui a été étudié pendant plusieurs siècles. Et jusqu'à présent, nous n'avons pas d'algorithmes polytime efficaces pour factoriser un produit de deux nombres 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. Il sélectionne en gros deux nombres premiers aléatoires n-bit, disons p et q, et il y a des algorithmes bien connus pour choisir des nombres premiers aléatoires. Je ne vais pas entrer 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, la Hypothèse de Factoring, en ce qui concerne l'algorithme de GenModulus, est modélisée comme une expérience, que nous appelons "Factor Experiment", 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 trouver la factorisation correcte du module N, est délimitée par une fonction négligeable. Notez 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. Donc, il s'avère que Factoring Assumption, bien qu'il ressemble à une fonction One-Way candidate, c'est-à-dire que si je vous donne le produit de deux nombres premiers de grande taille arbitraire et que je vous mets au défi de venir avec la factorisation, alors ça ressemble à une Fonction One-Way candidate. Mais sur la base de cette fonction One-Way, nous ne pouvons pas obtenir directement un cryptosystème à clé publique. Donc, pour contourner cela, nous introduisons un problème connexe, 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 de 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 ramasser 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 choisit un exposant e tel 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 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 avez juste un module public 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. I insiste 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 de le faire. Le défi ici est de calculer la valeur de la racine de la partie aléatoire y 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 vous demandez comment choisir un élément aléatoire à partir de l'ensemble ZN* est possible en poly (n) temps, bien c'est possible, vous pouvez voir le livre de référence de Katz et Lindell où l'algorithme est donné de la façon de choisir des éléments aléatoires. Maintenant le défi pour l'adversaire est de découvrir la racine de cette ie aléatoire juste à partir de 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 la sortie de l'expérience est 1, si et seulement si, x est effectivement la racine de l'aléatoire y modulo N, à savoir si xe modulo 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'elle puisse trouver la bonne racine de la racine d'une y est délimitée par une probabilité négligeable. (Reportez-vous à la section Heure de la diapositive: 16 :23) Maintenant, laissez ’ essayer de comparer l'hypothèse RSA et la prise en charge de Factoring, car à un niveau élevé, ils peuvent ressembler à vous. Donc, sur votre gauche, vous avez l'expérience d'affacturage où le défi pour l'adversaire est de trouver les principaux facteurs du module public N. Sur la droite, vous avez l'expérience modérer le problème RSA où l'adversaire est maintenant donné quelques informations supplémentaires dans le cadre de son défi, à savoir, il est donné l'exposant public e et le aléatoire y de l'ensemble ZN*, et son but est de trouver la racine de la racine y modulo N. Il s'avère que nous pouvons prouver que si l'hypothèse RSA tient, alors Factoring Assumption détient aussi et ceci peut être prouvé par controltive, c'est-à-dire, si vous supposez que l'affacturage Est facile de calcul, cela signifie qu'il est possible pour un adversaire polytime de se présenter avec une factorisation principale 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 e est donné à vous, puis en exécutant l'algorithme Euclide étendu, vous pouvez vous-même calculer l'inverse multiplicatif de e, à savoir d, et une fois que vous calculez d, la racine de y n'est rien d'autre que yd modulo N. Cela signifie que cette implication est vraie. D'autre part, laissez ’ essayer de considérer la relation entre la prise en charge Factoring et RSA, en ce sens, pouvons-nous dire que si Factoring Assumption détient, alors l'hypothèse RSA est valable et nous n'avons pas de réponse à cela. Cela signifie que nous ne pouvons pas prouver que si l'hypothèse RSA ne tient pas et que l'hypothèse de Factoring ne tient pas. C'est un gros problème ouvert car il pourrait y avoir un moyen de résoudre efficacement le problème RSA sans tenir compte de votre module. Mais nous pouvons avoir une sorte de compromis et pour la plupart des nombreuses instanciations pratiques, il s'agit d'un clic commun, qui est utilisé pour rendre le processus de cryptage rapide. Maintenant, supposons que nous utilisons une instanciation de RSA, où nous avons défini e à être 3, et nous disons que nous sommes en train de considérer une application où les messages sous-jacents m ∈ ZN*, mais la grandeur de m est strictement inférieure à la racine du module N. Et si vous vous demandez que le type d'applications rencontre ce type de m, si plus tard on verra le cryptage RSA hybride. Ensuite, la taille du module que nous utilisons généralement est de taille 1024 bits, et le message que nous aimerions chiffrer avec le chiffrement RSA hybride sera approximativement une chaîne de bit aléatoire de 300 bits et nous allons définir e à être 3. Si c'est le cas, alors le texte de chiffrement sera m3 modulo N. Mais puisque ma magnitude de m est strictement inférieure à la racine de cube de m, moi ou m3 modulo N sera équivalent au cube entier et l'effet du mod N n'aura pas lieu du tout. Et si l'adversaire est conscient du fait que nous utilisons une application avec un texte de fond sous-jacent, il est de magnitude est strictement inférieur à la racine cubique du module N, alors il sera également conscient que le m sous-jacent, qui a été crypté. Son cube est en fait contenu dans le texte de chiffrement c, à savoir le cube entier non le cube modulo, et il est très facile de récupérer l'inconnu sous-jacent à partir de c en trouvant la racine de cube entier du texte de chiffrement c, qui peut être calculé en poly de la taille du module N de calcul. C'est donc notre première classe d'attaque. (Voir Diapositive Heure: 14 :14) Nous pouvons avoir beaucoup d'autres types d'attaques possibles sur le Cipher de RSA, alors imaginez pour le moment que nous étudions une application où le même message doit être chiffré et envoyé à plusieurs récepteurs. Imaginez si nous disons que nous avons 3 récepteurs, récepteur 1, 2 et 3 chacun a son propre module N1, N2 et N3 respectivement. Mais chacun d'eux utilise un même exposant public que 3, et bien sûr un autre exposant de déchiffrement d1, d2 et d3 où d1 est l'inverse multiplicatif de 3 modulo N1, d2 est l'inverse multiplicatif de 3 modulo N2, et ainsi de suite. Donc, la clé publique, qui est disponible dans le domaine public sont les clés publiques respectives des 3 récepteurs et imaginez que nous avons un expéditeur, qui a un message aléatoire m ∈ ZN1 *, ainsi que ZN2 *, ainsi que ZN3 * choisis au hasard et dit qu'il veut chiffrer et envoyer un même message aux 3 récepteurs. Ainsi, il calculera c1 qui sera le m3 modulo N1, c2 qui sera le m3 modulo N2, etc. Maintenant, supposons que ce modulo N1, N2 et N3, ils sont deux premiers par paires. Si ce n'est pas le cas par exemple, la GCD de Ni et Nj n'est pas 1, elles ne sont pas co-prime les unes aux autres. Cela signifie qu'il existe un facteur commun de Ni et de Nj, puis en utilisant ce facteur commun, il est facile de factoriser le module Ni ou Nj et dire, par exemple, si le Ni est factorisable, et puisque ei est aussi connu publiquement et si on connaît les facteurs de Ni ’, on peut calculer la valeur de i). Et une fois que nous savons i) et ei, nous pouvons calculer la valeur de di en quantité polynomiale de temps. Si di est calculable, tout chiffrement destiné au destinataire peut être déchiffré par l'adversaire. Donc, il est sûr de supposer pour le moment que la paire sage, tous les modules N1, N2 et N3, ils sont co-premiers l'un à l'autre. Maintenant, laissez-moi définir un module plus gros N*, qui est le produit de tous les trois modules ici, à savoir N1, N2 et N3, et puisque mon texte en clair sous-jacent, qui est l'expéditeur, a crypté ∈ ZN1 *, ainsi que ZN2 *, ainsi que ZN3 *. Cela signifie que m est strictement inférieur à N1, il est strictement inférieur à N2, il est strictement inférieur à N3. Cela signifie que le nombre entier de m3 sera strictement inférieur au module plus gros N* et maintenant ce que je peux faire est que mon module N1, N2, et N2, N3 et N1, N3 ils sont co-premiers entre eux. Je peux invoquer un très beau résultat de la théorie des nombres, que nous appelons le théorème Chinois Remainder, qui dit que si votre individu modulo N1, N2 et N3 ils sont co-premiers. Ensuite, il est possible de calculer la valeur entière en m3 en quantité polynomiale de temps, polynomial dans la taille des modules respectifs N1, N2 et N3, de sorte que le m3 récupéré satisfait fondamentalement le système des équations modulaires suivantes. Donc, on vous donne la valeur c1, qui est un entier de m3 modulo N1, où m3 n'est pas connu, et vous êtes donné c2, qui est le même m3 modulo N2 et vous avez la valeur de c3, qui est le même m3 modulo N3, et si vos N1, N2 et N3, le module respectif ils sont co-prime entre eux. Ensuite, ce que le Chinois Remainder Theorem dit, c'est qu'il est possible de récupérer ce m3 inconnu en quantité polynomiale de calcul. Ensuite, en appliquant le théorème de Remainder chinois, un adversaire qui écoute ces trois cipher texte c1, c2, c3, peut appliquer le théorème de Remainder chinois, et récupérer l'inconnu. Une fois que l'entier inconnu m3 est récupéré, il peut trouver le m exact. Donc, encore une fois, c'est une autre attaque, qui est possible sur le Cipher de la plaine RSA même si nous supposons qu'un message de l'expéditeur, le message m ∈ ZN* set. Il s'avère qu'il pourrait y avoir plusieurs autres attaques possibles, qui peuvent être lancées sur le processus de cryptage de la RSA. (Voir la diapositive: 18 :48) Donc, cela nous amène au concept de ce que nous appelons le cryptosystème à clé publique RSA, et fondamentalement l'idée générale ici est que, nous avons déjà vu que le processus de chiffrement de RSA est un processus de chiffrement déterministe. Il n'y a pas de caractère aléatoire interne et s'il n'y a pas de caractère aléatoire interne, nous ne pourrons jamais espérer atteindre la sécurité de l'ACP. Donc, l'idée derrière le processus de chiffrement RSA pajouté est que nous essayons d'ajouter des chaînes de bits aléatoires aux bits de texte en clair, que nous voulons chiffrer et convertir tout en un élément de groupe dans le jeu ZN*, et ensuite nous appliquons la fonction RSA pour le chiffrement. D'autre part, la fin du déchiffrement, nous allons couper les chaînes de bits aléatoires, que nous avons ajoutées aux chaînes de bits avant le chiffrement et qui seront alors le texte en clair récupéré.