Loading
Notes d'étude
Study Reminders
Support
Text Version

Limitations de la sécurité parfaite

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 Professeur de développement de carrière Professeur Institut international de technologie de l'information-Conférence Bengaluru-05 Limitations de la sécurité parfaite Bonjour tout le monde, bienvenue à la conférence 5. (Reportez-vous à la page Heure de la diapositive: 00:30) Le plan pour cette conférence est le suivant: nous allons voir un candidat pour un cryptage parfaitement sécurisé, que nous appelons comme un seul bloc de temps et nous allons voir les limitations qui sont imposées par tout schéma de cryptage parfaitement sécurisé. (Reportez-vous à l'heure de la diapositive: 00 :44) Ainsi, le processus de chiffrement d'un bloc de temps, qui est également appelé Vernam cipher, est très simple. Ici, l'espace de texte en clair, l'espace clé et un espace de texte de chiffrement sont des chaînes de bits de type l, où l est un paramètre système qui est publiquement connu de l'expéditeur, du récepteur et de toute personne qui utilise ce système. L'algorithme de génération de clé va générer une clé uniformément aléatoire. Donc, étant donné que l'espace clé est défini comme des chaînes de bits, l'algorithme de génération de clé va générer une clé de l bit uniformément aléatoire. L'algorithme de chiffrement est le suivant. Donc il faut un texte clair qui va être une chaîne de l bit et la clé k générée par l'algorithme de génération de clé, qui est aussi une chaîne de l bit. Et le texte chiffré est une chaîne de caractères l, où le texte chiffré n'est rien d'autre que la XOR des caractères de texte en clair et les caractères clés bit par bit. Et comme vous pouvez voir qu'il s'agit d'un algorithme déterministe, il n'y a pas de caractère aléatoire interne dans le cadre de cet algorithme de chiffrement. Cela signifie que si vous chiffrez le même message à l'aide de la même clé, vous obtiendrez le même texte. L'algorithme de déchiffrement n'est qu'une opération inverse de l'algorithme de chiffrement dans le sens où il faut un algorithme de chiffrement qui va être une chaîne de l bit et la clé k qui sera aussi une chaîne de l bit. Et pour récupérer le message, l'algorithme de décryptage exécute simplement la XOR du texte de chiffrement avec la clé k bit par bit. Donc juste pour rappeler, ce qui est exactement une opération XOR, donc l'opération XOR fonctionne avec 2 bits à la fois et la sortie est définie comme suit si les deux bits sont identiques, alors la sortie va être 0. Alors que si les bits sont différents, et que la sortie va être 1, c'est ce qui est l'opération XOR, non. (Voir Diapositive Heure: 02:30) Donc, dans un certain sens, vous pouvez imaginer que cet algorithme de chiffrement fait le masquage du message avec la clé, pas vrai. Ainsi, l'opération XOR a pour effet de masquer le message bit par bit avec les bits de la clé. Alors que l'opération de décryptage comme vous pouvez l'imaginer, elle a le fonctionnement inverse du masquage, c'est-à-dire de ne pas masquer l'effet de la clé du texte chiffré par bit. Donc, l'important ici est que puisque l'opération XOR est une sorte de réversible ici, vous pouvez masquer le message à l'aide de la clé en effectuant l'opération XOR. Et pour obtenir l'effet d'un démasquage, vous avez juste à XOR la clé du texte chiffré pour récupérer votre message. Donc, maintenant, prouvons que ce Vernam cipher ou un bloc de temps est en effet parfaitement sécurisé. Et nous pouvons prouver sa parfaite sécurité selon l'une des 3 définitions que nous avons vues lors de la dernière conférence. Je vais donc prouver que Vernam cipher est en effet parfaitement sécurisé sur l'espace de message des chaînes de bits. Et pour cela, je vais utiliser la première définition alternative du secret parfait que nous avons discutée lors de la dernière conférence. À savoir, je vais prouver que la distribution du texte chiffré est indépendante du texte en clair sous-jacent dans n'importe quelle instance de Vernam cipher. Pour cela, nous considérons une distribution de probabilité arbitraire par rapport à l'espace en clair, et une paire arbitraire de messages m0, m1 appartenant à l'espace de texte en clair selon cette distribution de probabilité qui a une probabilité non nulle d'occurrence. Et nous choisissons aussi un chiffon arbitraire, qui a une probabilité non nulle d'occurrence. Ce que je vais prouver, c'est que pour n'importe quel m0 et m1 que nous avons choisi ici arbitrairement et pour n'importe quel texte de chiffrement que nous avons choisi arbitrairement ici, la probabilité que m0 est chiffrée en c, et la probabilité que m1 dans crypté est c, sont identiques, ce qui démontrera que Vernam cipher est parfaitement sécurisé. Alors, maintenant, essayons d'abord de calculer la probabilité conditionnelle que si votre texte en clair est m0, quelle est la probabilité que le code de chiffrement de Vernam produise le texte de chiffrement à c, à droite. Donc la probabilité que le texte en clair m0 va produire le texte de chiffrement, c, est la même que la probabilité que la clé qui est utilisée pour le chiffrement est cette chaîne, à savoir la clé est XOR de m0 et c. Et quelle est la probabilité que la clé obtenue en exécutant l'algorithme de génération de clé soit en effet la XOR de m0 et c. Eh bien, c'est 1/2l. Parce que, selon la syntaxe de notre algorithme de génération de clé, l'algorithme de génération de clé est sortie pour générer une clé uniformément aléatoire. Donc la probabilité que la clé uniformément aléatoire qui est obtenue par l'algorithme de génération de clé satisfait effectivement la valeur XOR de m0 et c est 1/2l. De la même manière, la probabilité que le message m1 soit chiffré dans le texte de chiffrement, c, est identique à la valeur de clé utilisée pour le chiffrement est la XOR de m1 et c. Et encore une fois, puisque mon algorithme de génération de clé va générer des clés aléatoires uniformes, la probabilité que ma clé soit XOR de m1 et c est 1/2l. Donc, puisque ces deux probabilités sont égales après avoir vu un algorithme de chiffrement, qui va être une chaîne de l bit, l'adversaire ne peut pas déterminer s'il s'agit d'un chiffrement de m0, ou s'il s'agit d'un chiffrement de m1. Et donc l'adversaire sera complètement indéporel. Et c'est pourquoi ce cryptage répond à la définition du secret parfait. Nous avons donc maintenant un système de cryptage des candidats, qui est parfaitement sécurisé. (Référez-vous à la diapositive: 06 :17) Alors maintenant, vous vous demandez peut-être que si nous avons un système de cryptage des candidats, qui est parfaitement sécurisé, pourquoi ne pouvons-nous pas nous permettre de l'utiliser dans la pratique. Nous allons donc maintenant voir certaines des limitations qui sont imposées par le système de remplissage unique. La première limitation imposée ici est que la clé doit être aussi large que le texte en clair parce que la taille de la clé est l, ainsi que la taille du texte en clair est aussi l, à droite. Cela signifie que si vous voulez chiffrer un fichier de 1 Go, cela signifie que si l'expéditeur veut chiffrer un fichier de 1 Go, il doit s'entendre sur une clé qui est également de taille 1 Go, ce qui semble très peu pratique car dans la pratique, nous visons le processus de cryptage, où nous pouvons utiliser une petite clé de taille pour chiffrer de longs messages. C'est donc la première restriction imposée par Vernam cipher. La seconde limitation imposée ici est que vous ne pouvez pas réutiliser la même clé pour le chiffrement de plusieurs messages. Cela signifie que chaque instance du chiffrement a besoin d'une nouvelle clé. Je souligne ici que lorsque je dis ici que vous ne pouvez pas réutiliser la clé, je ne veux pas dire que vous ne pouvez pas réutiliser la clé dans l'instance suivante, ce que je veux dire ici, c'est que dans chaque cas, vous devez de nouveau s'exécuter dans une instance indépendante ou une nouvelle instance de l'algorithme de génération de clé. C'est bien si la clé que vous allez obtenir lors de l'appel suivant de l'algorithme de génération de clé est identique à celle que vous avez obtenue lors de l'appel précédent. Ce qui est important ici, c'est que ces deux appels de la génération clé vont générer des sorties indépendantes. Donc, du point de vue de l'adversaire ou de l'attaquant qui intercepte le texte chiffré, il ne serait pas en sachant que les clés qui ont été utilisées, qu'elles soient identiques ou qu'elles soient différentes. Du point de vue de l'attaquant, ce sont des clés indépendantes. Donc la deuxième restriction, qui est imposée ici, c'est que vous ne pouvez pas conserver la même clé et continuer à chiffrer plusieurs messages à l'aide de la même clé. Par exemple, imaginez un scénario dans lequel l'expéditeur va utiliser ou conserver la même clé k pour le chiffrement de 2 messages m0 et m1 différents dans l'ordre. Cela signifie qu'il a utilisé une clé k pour le chiffrement d'un premier message m0 a communiqué le texte de chiffrement. Et supposons qu'elle conserve à nouveau la même valeur de clé au lieu d'exécuter à nouveau l'algorithme de génération de clé. Et il réutilise la même clé k pour le chiffrement d'un message suivant m1, et encore une fois, le texte de chiffrement est communiqué sur le canal. Et supposons que l'adversaire est conscient de ce fait que la même clé a été conservée et utilisée par l'expéditeur pour chiffrer deux messages m0 et m1. Donc maintenant ce qu'un attaquant peut faire, c'est ce qui suit. Comme il a intercepté le texte de chiffrement c0, ainsi qu'il a intercepté le texte de chiffrement c1 et il connaît la relation entre les messages m0 et k, m1 et k, et c0, c1. Namely, il sait que c0 est la XOR de m0 et k et il sait que c1 est la XOR de m1 et k. S'il exécute la XOR de c0 et c1, l'effet de k va disparaître, car c'est ce qui est la propriété de l'opération XOR. Parce que k sera XORed avec k lui-même, ce qui vous donnera 0. En conséquence, en effectuant la XOR de c0 et c1, l'adversaire va obtenir la XOR de m0 et m1. Donc maintenant vous vous demandez peut-être combien d'informations sont réellement révélées en apprenant la XOR de m0 et m1. Et il s'avère qu'il s'agit d'une quantité importante d'informations. Cela signifie que nous ne pouvons pas revendiquer le secret parfait pour ce type de processus de cryptage où le même k est maintenant conservé pour le chiffrement de plusieurs messages. (Référez-vous à la diapositive: 09 :48) Donc voici ce que le lauréat du prix Turing, le légendaire informaticien Michael Rabin, a à dire à propos d'un bloc de temps, il dit que vous ne devriez jamais réutiliser un bloc de temps, c'est comme un papier toilette, parce que si vous le réutilisez, les choses peuvent être désordonnées, de droite, de sorte que vous ne devriez jamais réutiliser la clé. Pour chaque instance de l'extrusion de temps unique Vernam, vous devez exécuter un algorithme de génération de clé et obtenir une nouvelle clé pour le chiffrement de vos prochains messages. (Référez-vous à la diapositive: 10:14) Voici donc les 2 restrictions imposées par Vernam cipher. Maintenant, une question naturelle est de savoir si ces 2 restrictions ne s'appliquent qu'à un seul bloc de temps ou à Vernam cipher, ou sont ces 2 restrictions inhérentes à tout code de chiffrement parfaitement sécurisé. Ce que nous allons maintenant prouver, c'est que ces deux restrictions sont inhérentes à tout code de chiffrement parfaitement sécurisé, pour n'importe quelle clé de chiffrement parfaitement sécurisée devrait être aussi large que le texte en clair. Et nous prouverons également que tout code de chiffrement parfaitement sécurisé, chaque instance du chiffrement a besoin d'une nouvelle clé. (Référez-vous à la diapositive: 10:49) Alors, laissez-nous d'abord prouver la première limitation. Donc le théorème ici, est d'imaginer que vous êtes donné un chiffrement parfaitement sécurisé. Il ne s'agit peut-être pas d'un seul bloc de temps, il peut s'agir d'un code de chiffrement parfaitement sécurisé. Le théorème dit que si le schéma est parfaitement sécurisé, alors l'espace clé doit être aussi grand que l'espace de message, non. Donc, voici la preuve, la preuve va être en contradiction. Alors au contraire, imaginez que même si mon schéma est parfaitement sécurisé, mon espace clé est moins que mon espace de message. Cela signifie que le nombre de clés candidates est inférieur au nombre de candidats en clair. Et pour la démonstration ici est un exemple, je suppose que mon espace de texte de l'usine candidate est composé de 3 textes en clair et que mon espace candidat est composé de 2 clés possibles. Alors maintenant, vous considérez la distribution de probabilité uniforme sur l'espace de message, cela signifie que vous considérez un scénario où l'expéditeur aurait pu chiffrer n'importe lequel de ces 3 messages possibles avec une probabilité égale. Et vous considérez un texte chiffré dont la probabilité d'occurrence est différente de zéro. Alors maintenant, permettez-moi de définir le set M (c) qui est l'ensemble de tous les déchiffrement valides du texte de chiffrement c, à savoir M (c) se composent de tout le texte brut à partir de l'espace de texte en clair, que je peux obtenir en déchiffant le texte de chiffrement c sous différentes clés candidates de l'espace clé, à droite. Donc, encore une fois dans cet exemple particulier, si j'essaie de déchiffrer le texte de chiffrement c, j'ai 2 clés possibles. Lors du déchiffrement du texte par k1, je vais obtenir un message et le déchiffrer c par la deuxième clé k2 Je vais obtenir un second message qui signifie ce que je peux dire que la cardinalité de l'ensemble M (c) est bornée par la cardinalité de l'espace clé car c'est le nombre maximum de déchiffrement que vous pouvez obtenir en déchiffant le texte de chiffrement c ici, et puisque dans le cadre de mon hypothèse, la cardinalité de l'espace de clé est inférieure à la cardinalité de l'espace de message, ce que j'ai obtenu ici est que la cardinalité de M (c) est strictement inférieure à la cardinalité de l'espace clé qui est inférieur à la cardinalité du message Espace. Ce que cela signifie ici, c'est qu'il existe au moins un message de l'espace message, un espace de texte en clair, qui ne peut jamais conduire au texte chiffré c qui signifie pour déchiffrer le texte du code de chiffrement, je n'obtiens jamais le texte en clair. Encore une fois dans cet exemple spécifique, vous pouvez voir que le décryptage de c ne peut jamais vous donner de m3. Et c'est une violation de l'état de secret parfait parce que le secret parfait dit que si vous avez une distribution de probabilité uniforme sur l'espace de texte normal, alors pour chaque texte de chiffrement c qui se produit avec une probabilité non nulle, il devrait être un chiffrement potentiel de tous les messages candidats avec des probabilités égales ou en d'autres sens si je vois les définitions originales du secret parfait, ce que nous sommes arrivés ici est le fait que nous avons au moins un message est m, où la probabilité d'occurrence du m est non nulle, mais la probabilité conditionnelle que m est cryptée dans le texte de chiffrement c est 0. Cela signifie que ces 2 probabilités ne sont pas les mêmes. C'est donc une violation du secret parfait. Donc, cela signifie que nous avons prouvé que dans tout schéma de cryptage parfaitement sécurisé, l'espace clé doit être aussi grand que l'espace de message. (Référez-vous à la diapositive: 14 :20) Maintenant, quelle est l'implication de ce théorème. Imaginez votre espace clé est l'ensemble de toutes les chaînes possibles de longueur x. Cela signifie que mon processus de chiffrement prend en charge le chiffrement des chaînes de bits. Cela signifie que la cardinalité de l'espace clé n'est rien d'autre que 2x. Et de la même façon, imaginez que mon processus de chiffrement supporte l'espace de texte en clair de chaînes de bits qui signifie que le texte en clair doit être des chaînes de bits et, par conséquent, la cardinalité de mon espace de message est 2y. Maintenant, comme pour ce théorème est mon schéma est parfaitement sécurisé j'ai besoin de la cardinalité de l'espace clé pour être aussi large que la cardinalité de l'espace message, c'est-à-dire que 2x devrait être supérieur à 2y. Et comme conséquence de cela, j'ai le fait que x devrait être supérieur à y, c'est-à-dire que la longueur de la clé doit être aussi grande que le texte en clair. C'est la première limitation de tout code de chiffrement parfaitement sécurisé, à savoir que la clé doit être aussi large que le texte en clair. (Référez-vous à la diapositive: 15 :24) Maintenant, prouverons la seconde limitation de tout code de chiffrement parfaitement sécurisé. Et je ne vais pas le prouver de façon rigoureuse et formelle, je vais vous donner un détail de haut niveau de la preuve ici. Donc le théorème des états qui imaginent que vous avez un chiffrement parfaitement sécurisé au-dessus de l'espace de texte en clair m et de l'espace clé k, puis chaque instance du processus de chiffrement de ce chiffrement doit exiger une clé indépendante pour être générée par l'algorithme de génération de clé. Cela signifie que vous ne pouvez pas conserver la même clé pour le chiffrement de plusieurs messages. Encore une fois, essayons de vous prouver que vous utilisez une contradiction. Imaginez un scénario où l'expéditeur conserve la même clé k pour le chiffrement de 2 messages m1 et m2 en séquence, à droite. Ainsi, il a chiffré le message m1 de production de texte chiffré c1 communiqué sur le canal, et ensuite il doit utiliser la même clé k pour chiffrer un second message dans la séquence. Et encore une fois le texte chiffré est communiqué sur le canal. Et l'adversaire a intercepté à la fois le texte chiffré et l'adversaire est conscient du fait que la même clé inconnue k a été conservée et utilisée pour chiffrer les messages m1 aussi bien que m2. Ce que nous allons prouver, c'est que si quelque chose de ce genre s'est produit, alors vous ne pourrez jamais obtenir le secret parfait, pas vrai. Alors imaginez 2 séquences différentes de texte en clair. La première séquence est lorsque le premier message est m1 et que le second message est également m1 et dans la deuxième séquence m ’, les séquences de messages sont m1 et m2, où m1 et m2 sont différents. Et imaginez que l'adversaire a intercepté un texte chiffré composé de 2 séquences de texte de chiffrement où le premier texte de chiffrement est c1 et le second texte de chiffrement c2, à droite. Ainsi, conformément à l'exigence de secret parfait, si l'adversaire a obtenu une séquence de texte de chiffrement c1 et c2, et si l'adversaire a une information préalable que ces 2 séquences de messages, qui auraient pu être cryptés dans c1 c2 pourrait être m1, m1 ou m1, m2, alors l'exigence du secret parfait est qu'avec une probabilité égale la séquence de chiffrement c1, c2 doit être n'importe quel chiffrement de m1, m1, ainsi qu'il devrait être un chiffrage potentiel de m1, m2 à droite. Cela signifie que si je considère la probabilité de gauche ici, j'ai introduit ici 2 variables aléatoires c1 et c2 en caractères gras, ce qui indique la valeur de la première séquence de texte de chiffrement et la deuxième séquence de texte de chiffrement. Et de la même façon, j'ai introduit 2 variables aléatoires, boldface m1 et boldface m2, pour noter le premier texte en clair du candidat et le deuxième texte en clair du candidat. Donc, ma prétention ici est que la probabilité que la probabilité de la main gauche et la probabilité de la main droite ne soient jamais identiques, ce qui est une violation du secret parfait. Pictorialement l'exigence du secret parfait devrait être qu'il importe peu que la première séquence de message m1, m1 soit chiffrée ou si la deuxième séquence de message m1, m2 est chiffrée à l'aide de la clé selon votre processus de cryptage avec la même probabilité qu'elle devrait vous conduire à la séquence de texte c1, c2, si à tous vos processus de cryptage parfaitement sécurisé. Mais si c'est le cas, cela signifie imaginer un scénario où en effet la séquence de message m1, m1 et une séquence de message m1, m2, les deux mènent à une séquence de texte de chiffrement c1, c2 avec une probabilité égale sous la même et la clé k, alors cela signifie une erreur de déchiffrement. Parce que cela signifie que si vous déchiffrez le texte de chiffrement c2 pour utiliser la clé k, alors il devrait vous ramener au texte en clair m1 ainsi qu'il devrait vous ramener à la surface de texte en m2, ce qui signifie qu'il y a une erreur d'exactitude dans votre processus de chiffrement. Cela signifie qu'il y a une erreur de déchiffrement dans votre processus de chiffrement, ce qui est une violation du fait que votre processus de chiffrement est sécurisé, car l'une des exigences de tout chiffrement sécurisé est l'exigence de correction, ce qui exige que votre description soit sans ambiguïté, mais si nous sommes dans un scénario comme celui-ci, où la séquence de message m1 m1 et la séquence de message m1 m2 mènent à la même séquence de texte c1, c2. Alors cela signifie que si je décrypte juste la séquence de texhertext c2 elle pourrait me ramener à m1 aussi bien qu'elle pourrait me ramener à la m2. Cela signifie qu'il y a une ambiguïté dans le décryptage de mon processus de chiffrement d'origine lui-même, ce qui est une contradiction, cela prouve officieusement le théorème que chaque instance du processus de chiffrement devrait être exécutée d'une nouvelle instance de l'algorithme de génération de clé. Cela m'amène à la fin de cette conférence. Juste pour résumer. Dans cette conférence, nous avons discuté d'un candidat, un processus de cryptage parfaitement sécurisé, à savoir un bloc de temps ou Vernam cipher, et nous avons prouvé son secret parfait. Nous avons également vu les 2 restrictions imposées par un bloc de temps. Et nous avons soutenu que ces 2 restrictions, à savoir la taille de la clé étant aussi grande que le message et la clé fraîche pour chaque instance du chiffrement, sont inhérentes à tout processus de chiffrement parfaitement sécurisé. J'espère que vous avez apprécié cette conférence. Je vous remercie.