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 Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Technology-Bangalore Lecture – 52 RSA Signatures Bonjour tout le monde, bienvenue à cette conférence. Alors seulement pour récapitulation, lors de la dernière conférence, nous avons introduit des signatures numériques, nous avons vu leur définition formelle. (Référez-vous à l'heure de la diapositive: 00:40) Dans cette conférence, nous verrons une instanciation de signatures numériques basée sur la fonction RSA. Nous allons d'abord voir les signatures et les attaques de RSA qui peuvent être lancées sur des signatures RSA en clair. Ensuite, nous verrons une instanciation de signatures sécurisées basée sur la fonction RSA que nous appelons le hachage de domaine complet RSA. (Référez-vous à l'heure de la diapositive: 00:55)Donc, commençons par les signatures RSA. Et pour cela, permettez-moi de rappeler la RSA une façon de piéger la permutation de porte. Nous avons l'algorithme de génération de paramètres, qui génère d'abord les paramètres,,. Ici, le module est le produit de et, il pique et, où et sont inverses multiplicatifs l'un de l'autre. Et puis nous avons fixé le paramètre public à être, et le paramètre secret à être. Et notre fonction de direction avancée RSA est mod. Et notre fonction inverse est mod. Et nous avons prouvé que ces deux fonctions sont à l'inverse l'une de l'autre et nous considérons aussi qu'il s'agit d'une fonction à sens unique, où se trouve la porte de la trappe. Maintenant, la signature RSA simple que nous pouvons obtenir de cette RSA une façon de permutation de la porte est obtenue en visualisant ou en traitant cette fonction inverse comme la fonction de signature. Cela signifie que toute entité qui possède peut utiliser la fonction inverse pour calculer la signature, et utiliser la fonction de direction de l'avant pour être la fonction de vérification. Plus précisément, la signature RSA en clair sur l'espace de message Znier est obtenue comme suit. L'algorithme de génération de clés exécute l'algorithme Gen RSA pour obtenir les paramètres et maintenant, le paramètre public est défini comme clé de vérification, alors que les informations de la porte d'interruption, à savoir, sont définies comme clé de signature. Pour signer un message appartenant à Zions, nous calculons fondamentalement le mod, où sera disponible avec le signataire. Et pour vérifier un message, la paire signature (, ce que nous calculons en premier est la valeur de la fonction RSA sur le composant signature, c'est-à-dire que nous calculons mod et comparez-le avec le message reçu. (Voir Heure de la diapositive: 02:59)Si la comparaison passe, nous acceptons le message, à savoir la sortie 1, sinon la sortie est 0. Nous voulons maintenant analyser la sécurité de ce plan de signature RSA. Et on pourrait dire que l'argument intuitif suivant devrait prouver que le schéma de signature RSA est en effet impardonnable ou sécurisé. L'argument ici est que si je suis un adversaire et si je ne connais pas la valeur de la clé de signature, à savoir la valeur du secret. Et si mon but est de forger une signature sur un message, sur lequel je n'ai pas vu la signature dans le passé, alors pour forger une signature essentiellement, je dois calculer la valeur de (mod) mod, où je ne connais pas la valeur de. Et on peut dire que ce n'est rien d'autre qu'une instance du problème RSA. Mais si je suppose que mon problème RSA est difficile en ce qui concerne cette fonction de Gen RSA, je peux prétendre que ce schéma de signature RSA est sécurisé. Mais il s'avère que cet argument intuitif n'est pas correct. L'une des raisons est que l'hypothèse RSA ou RSA est difficile à résoudre, seulement si elle est choisie au hasard à partir de Zinsu. L'hypothèse RSA ne dit rien de la difficulté ou de la facilité à calculer (éventuellement) le mod, sans connaître le, pour toute appartenance à Znette. Le deuxième problème ici dans cet argument intuitif est que l'hypothèse RSA ne dit pas ou ne garantit rien au sujet d'un adversaire quant à la possibilité d'un mod (mod), étant donné que l'adversaire aurait pu voir la valeur de plusieurs mod pour tout son choix. Parce que souvenez-vous, lorsque nous considérons le jeu de forgeabilité pour le schéma de signature, l'adversaire est autorisé à voir une signature de plusieurs messages de son choix. Donc, si l'adversaire a envoyé un message, il aurait vu le mod de signature. Et il a peut-être vu la valeur du mod pour le nombre polynomial de messages. Et en voyant le nombre polynomial de valeurs de la forme mod, où est connu de l'adversaire, l'objectif de l'adversaire est de trouver une contrefaçon, c'est-à-dire, (mod) mod. Ainsi, l'hypothèse de RSA ne garantit pas à quel point il est difficile ou facile pour un adversaire de trouver le faux, étant donné qu'il a vu la signature, c'est-à-dire la sortie de la fonction RSA pour plusieurs mètres de son choix, dans le passé. (Référez-vous à l'heure de la diapositive: 05:41) En effet, il s'avère que pour cette signature RSA en clair, il existe plusieurs façons dont l'adversaire peut se présenter avec une contrefaçon. Alors, voyons une attaque très simple que nous appelons sans attaque de message. A partir du nom, il se peut qu'il n'y ait aucun message sur lequel l'adversaire produit la contrefaçon. Mais ce n'est pas le cas, il y a effectivement un message sur lequel l'adversaire produit la signature falsifiés. La raison pour laquelle il n'est pas appelé attaque de message sera claire pour vous bientôt. Donc l'idée derrière cette attaque est que pour forger une signature valide, l'adversaire n'a pas besoin de toujours travailler dans la direction de l'avant. Ce que je veux dire par là c'est que si nous considérons l'espace de message et l'espace de signature de cette signature RSA en clair, les deux sont le jeu Zions. Et la signature pour un messagecan est produite par informatique mod. Donc, si l'objectif de l'adversaire est de forger une signature sur un message, il doit calculer (en gros) le mod, c'est l'un des moyens par lesquels l'adversaire peut produire une signature et ce que j'appelle la signature produisant la signature en marchant dans la direction vers l'avant. Mais il s'avère que l'adversaire pourrait monter ou forger une signature en marchant dans le sens inverse. À savoir, ce qu'il peut faire, c'est qu'il peut d'abord choisir une signature aléatoire ou un élément de groupe aléatoire et le traiter comme une signature. Et puis il peut demander dans son esprit que ce qui pourrait être le message valide ou potentiel de l'espace de message, pour lequel la signature RSA aurait été le message de ramasseur. Et il est facile de voir qu'en choisissant une signature aléatoire, le message correspondant qui aurait produit la signature n'est rien, mais (mod) mod. Parce que si, en effet, mon application est (mod) mod, alors (cela signifie) constitue une signature RSA valide selon l'algorithme de vérification RSA. Et pour calculer, l'adversaire a tout à sa disposition. Namely, il a une valeur, il connaît la valeur de et il connaît la valeur de et donc il peut facilement calculer. Donc, fondamentalement ici, il est facile de voir qu'en marchant dans le sens inverse, l'adversaire pourrait arriver avec une contrefaçon valide, même sans aucun accès à l'oracle de signature. Il ne demande pas la signature de tout message de son choix ; il choisit simplement une signature et produit un message correspondant. Maintenant, la raison pour laquelle nous appelons ça comme une attaque sans message est ici la contrefaçon est produite en marchant dans la direction arriérée, l'adversaire ne dispose d'aucun message pour commencer avec pour lequel il veut générer un faux. Mais encore en ce qui concerne la définition de la contrefaçon, la façon dont l'adversaire a calculé (c'est-à-le-terme) est une contrefaçon valide. C'est une discussion différente que ce que l'adversaire a produit en marchant dans le sens rétrograde, c'est logique dans le contexte de la demande où le schéma de signature sous-jacent est utilisé. (Référez-vous à l'heure de la diapositive: 08:58)Maintenant, ce que nous allons faire maintenant, c'est que nous allons voir une attaque sérieuse où l'adversaire a maintenant un message concret et nous verrons comment en utilisant l'aide de l'oracle de signature, l'adversaire peut trouver le faux sur n'importe quel message du choix de l'adversaire contre cette simple signature RSA. Donc, encore une fois pour se rappeler dans l'attaque sans message, l'adversaire n'a aucun contrôle sur le message, qu'il a obtenu en marchant dans la direction arriérée. Mais un scénario d'attaque plus réaliste sera celui où l'adversaire a un message concret de son choix sur lequel il veut forger la signature du signataire. Alors, laissez-moi vous montrer une instanciation de l'attaque ici. Donc, selon l'expérience de falsification de signature, le challenger aurait lancé le défi à l'adversaire, à savoir la clé de vérification. Et dire que l'objectif de l'adversaire est de forger la signature sur le message. Ce qu'il fait est, il choisit 2 messages 1, 2 au hasard de l'ensemble ZdB, comme 1 ∙ 2 =. Et comment il peut choisir les 1 et 2? Eh bien, il peut d'abord choisir aléatoirement 1 dans le groupZique qui a besoin d'un temps polynomial. Et puis il peut définir 2 = 1 − 1, qui lui donnera le 2 requis, qui peut encore être calculé en quantité polynomiale de temps. Maintenant, ce que l'adversaire peut demander est, il peut demander l'accès à l'oracle de signature pour le message 1 et 2. Il demande au challenger de signer les messages 1 et 2. Donc, en gros, ce modèle de fait que dans le but réel de l'adversaire est de forger la signature du signataire, il influence maintenant le signataire sur le signataire pour signer les messages 1 et 2. Ainsi, selon les règles du jeu, le challenger signe les messages 1 et 2 et donne respectivement les signatures 1 et 2. Et maintenant que l'adversaire combine ces 2 signatures. À savoir, elle fixe la valeur de 1 ∙ 2 et elle soumet la contrefaçon (c'est-à-dire, le cas). Et ma prétention ici est que la probabilité que l'adversaire ici gagne le match est 1. C'est parce que 1 = (1) mod et 2 = (2) mod et donc le mod = (mod) mod, ce qui n'est rien d'autre que la signature RSA sur le message. Donc, maintenant vous avez une attaque concrète, en utilisant l'aide de l'oracle de signature, l'adversaire pourrait arriver avec une signature sur n'importe quel message de son choix, ce qui prouve que cette signature RSA n'est pas sécurisée. (Référez-vous à l'heure de la diapositive: 12:00) Alors, la question est maintenant de concevoir un schéma de signature sécurisé basé sur la fonction RSA? Et la réponse est oui, nous pouvons construire ce que nous appelons la signature de hachage de domaine complet RSA. Et à un niveau très élevé, cela pourrait ressembler à une instanciation du paradigme du hachage et des signes. Mais en fait, il ne s'agit pas d'une implémentation ou d'une instanciation à part entière du paradigme du hachage et des signes. L'idée ici est que nous voulons à nouveau transformer la chaîne de bits de message que nous voulons signer, avant de signer à l'aide de la fonction RSA. Donc, ce que nous faisons est l'espace de message réel que nous pouvons signer ici ou les autres messages que nous pouvons signer pourrait être une chaîne de bits arbitraire, nous les cartographions sur les éléments de Zions en appliquant une fonction de transformation, que j'appelle fonction, et puis le message transformé réel est signé à l'aide du schéma de signature RSA que nous avons discuté maintenant, le schéma de signature RSA non sécurisé. Ainsi, l'algorithme de génération de clé pour cette signature de hachage de domaine complet est le suivant: nous exécutons l'algorithme de Gen RSA, ensemble (pour être la clé de signature et (pour être la clé de vérification. Et nous faisons la fonction de transformation pour être publiquement connue, qui mappe des chaînes de bits de longueur arbitraire à des éléments de Zions. Et maintenant, pour calculer la signature sur le message, qui est une chaîne de bits de longueur arbitraire, ce que nous faisons est, nous calculons d'abord. C'est-à-dire que nous mappons la chaîne de bits à un élément de Zions, et ensuite nous calculons la valeur de la fonction inverse de RSA sur le, c'est-à-dire que nous calculons mod, c'est notre signature. La vérification se produit de façon canonique. A savoir si vous recevez (et si vous voulez le vérifier, ce que nous faisons d'abord, c'est que nous calculons ′ = mod. Et nous acceptons le message, si et seulement si ′ =, ce qui serait le cas si tout s'est passé de façon appropriée. C'est donc l'idée générale de ce hachage complet du domaine RSA. Maintenant, on peut se demander quelles sont les propriétés nécessaires que nous avons besoin de la transformation sous-jacente pour s'assurer que le système global est sécurisé. Je souligne ici que cette signature de hachage de domaine complet ne doit pas être considérée comme une instanciation du paradigme du hachage et des signes. Parce que pour la sécurité du paradigme du hachage et des signes, nous avons besoin que le schéma de signature de longueur fixe soit sécurisé. Mais le schéma de signature à longueur fixe, qui dans ce cas est la signature ordinaire RSA, nous l'avons déjà prouvé qu'il n'est pas sécurisé. Cependant, il s'avère que si nous faisons des suppositions appropriées pour cette fonction de transformation sous-jacente, alors cette façon générale d'écraser le message d'abord, puis de signer comme par l'insécurité ou la signature RSA, nous donne un schéma de signature sécurisé global. Alors, discutons de ce que sont exactement les propriétés de sécurité que nous avons besoin de la fonction de transformation? La liste des propriétés nécessaires est donc la suivante. Bien sûr, nous avons besoin que la fonction de transformation soit résistante aux collisions, c'est-à-dire qu'elle devrait être difficile sur le plan informatique pour un adversaire polytime ou un attaquant pour trouver une paire de messages (, par exemple). Parce que si c'est le cas, cela signifie que si l'adversaire pouvait trouver une telle paire de messages, alors il peut d'abord demander la signature sur le message et une signature sur le message sera exactement la même que la signature sur le message, donc il pourrait facilement arriver avec une contrefaçon. La deuxième exigence de la fonction de transformation est qu'elle doit éviter tout type de propriétés algébriques multiples ou multiplicatives que nous avions exploitées lors de l'attaque sur la signature RSA. Cela signifie qu'il ne devrait pas arriver que nous ayons un triplet de l'pour (1, 2) tel que 1) ∙ 2). Parce que s'il est possible pour un adversaire de trouver de tels triplets en quantité polynomiale de temps, alors ce que l'adversaire peut fondamentalement faire est, il peut demander la signature sur les messages 1 et 2 comme par ce hachage de domaine complet. Et étant donné cela, il peut facilement obtenir une signature sur le message, ce serait sa contrefaçon. Nous aimerions donc que cette transformation soit telle qu'elle ne devrait pas avoir de belles propriétés algébriques. Nous avons également besoin de la propriété de caractère unique à partir de cette fonction de transformation. En effet, nous avons besoin que, en raison d'un arbitraire de Zions, il soit difficile de trouver un message, tel que. Il s'agit de prévenir le type d'attaque sans message. Il s'avère que ces 3 propriétés sont nécessaires, mais nous ne savons pas si la liste est exhaustive ou non, si nous avons besoin d'une 4ème propriété, de la 5ème propriété, etc. Donc, nous sommes en quelque sorte coincés maintenant. Ce que nous pouvons faire, c'est que nous ne nous soucions pas de savoir si la liste est exhaustive ou non, si nous supposons que la fonction de transformation est modélisée comme un oracle aléatoire et si vous êtes dans le modèle d'oracle aléatoire, alors nous pouvons donner une preuve de sécurité complète pour cette signature de hachage de domaine complet. Donc, vous pouvez voir que si nous supposons que si vous êtes dans le modèle d'oracle aléatoire, alors certainement les 3 exigences que nous avons indiquées seront satisfaites. Et en plus, la preuve que le schéma de signature est sécurisé dans le modèle d'oracle aléatoire prend soin du fait qu'aucune autre attaque ne peut être lancée. Je ne vais donc pas entrer dans les détails formels de la preuve que ce schéma de signature est en effet sécurisé dans le modèle d'oracle aléatoire. Si vous êtes intéressé à voir la preuve formelle, vous pouvez vous référer au livre de Katz-Lindell ou au manuscrit de Boneh-Shoup. Cela m'amène à la fin de cette conférence.