Loading
Notes d'étude
Study Reminders
Support
Text Version

Instanciation pratique des GPR

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 CryptographyProf. Dr. Ashish Choudhury (Former) Infosys Foundation Chaire de développement de carrière ProfessorIndian Institute of Technology-BangaloreLecture-12Practical Instantiations of PRGHello tout le monde, bienvenue à la conférence 11. (Voir Diapositive Heure: 00 :30) Le plan de cette conférence est le suivant. Dans cette conférence, nous discuterons des instanciations pratiques de générateurs pseudo-aléatoires, à savoir nous allons voir la construction basée sur le registre de décalage linéaire et RC4 et nous discuterons des développements récents dans le domaine des instanciations pratiques de pseudo-générateur aléatoire. La raison pour laquelle nous appelons ces instanciations est qu'elles sont super rapides, comparées aux constructions de pseudo-générateurs pseudo-aléatoires dont nous avons discuté lors de la dernière conférence sur la base d'une fonction et d'une façon de permutation, mais malheureusement, pour ces instanciations pratiques de générateurs pseudo-aléatoires, nous n'avons pas de preuve mathématique qu'ils sont en effet des générateurs pseudo-aléatoires. Cela signifie que nous n'avons pas le théorème, ce qui prouve qu'il n'y a pas de distinction de temps polynomial qui puisse distinguer la sortie de ce générateur de nombres aléatoires de la sortie d'un vrai générateur de nombres aléatoires. C'est seulement parce que depuis la construction de ces instanciations pratiques de PRG que nous n'avons pas trouvé d'attaque appropriée ni de distinction convenable, nous croyons que ces constructions sont en sécurité, alors que pour les constructions sûres, basées sur une fonction et un prédicat dur que nous avons discuté lors de la dernière conférence, nous avons une preuve mathématique que En effet, dans la pratique, où que vous avez une construction cryptographique où vous voulez instancier un générateur pseudo-aléatoire, nous allons en fait pour ces instanciations pratiques. (Voir Diapositive Heure: 02 :08) Donc dans toutes les instanciations pratiques de générateurs pseudo-aléatoires, nous pouvons suivre l'abstraction suivante. Imaginez que vous vous êtes donné un générateur pseudo-aléatoire, qui étend une entrée de bits de l-bit à une sortie de? -bits. Nous pouvons supposer que le générateur pseudo-aléatoire consiste en une paire d'algorithmes, à savoir un algorithme d'initialisation et un algorithme GetNextBit. Et ce que ces algorithmes font essentiellement, c'est comme suivs.Donc, l'algorithme Init est en fait l'algorithme d'initialisation qui définit l'état initial de votre algorithme et c'est une fonction déterministe. Et ça prend la graine pour l'algorithme? Comme entrée et avec un vecteur d'initialisation facultatif, donc ce vecteur d'initialisation est facultatif. Il n'est pas nécessaire que chaque instanciation pratique d'un générateur pseudo-aléatoire prenne ce vecteur d'initialisation, cela dépend de la structure sous-jacente. Est donné en entrée, il est connu publiquement, et basé sur la semence et??? L'algorithme d'initialisation produit un état initial de l'algorithme que nous dénotent? ?0. A présent, l'algorithme GetNextBit effectue les opérations suivantes. It takes the current state of your algorithm or the PRG, which I denote by? ??, and it updates the state to? ?? + 1 and along with that it produces the next output bit of your algorithm?, right.So, if you want to generate a sequence of bits, what we do is we do the initialisation algorithm, get the initial state??? Et dire si vous êtes intéressé à obtenir une sortie de gros?-bits, en gros, nous invoquerons cet algorithme GetNextBit? Nombre de fois dans la séquence et dans chaque appel, l'état est mis à jour et les bits de sortie continuent à être générés un par un. Donc c'est l'abstraction que nous pouvons utiliser pour abstraire toute instrumentation pratique de générateur pseudo-aléatoire. (Voir la diapositive: 04 :03) Donc voyons, une instanciation pratique populaire de générateur pseudo-aléatoire, que nous utilisons dans le matériel. Et c'est ce qu'on appelle le registre de décalage linéaire ou LFSR. Ainsi, historiquement, il a été utilisé en tant que PRG. Et il est très rapide lorsqu'il est implémenté en matériel. Cependant, il n'est pas recommandé d'être utilisé pour les applications critiques, parce qu'il est très facile pour un adversaire de récupérer l'ensemble de la clé en ne voyant que peu de bits de sortie de la LFSR.So, une LFSR de degré? En gros consister en? Registres indiqués par? 0to??? − 1. Et avec ça, ça aura? Coefficients de rétroaction? 0à?? − 1, où les coefficients seront des valeurs booléennes. Ainsi, par exemple, nous avons ici une LFSR de degré 4 consistant en 4 registres, et les coefficients de rétroaction sont 0, 1, 0, 1. Donc, comment fonctionne un RPFT. En ce qui concerne l'état d'une LFSR, l'état n'est rien d'autre que les valeurs binaires qui sont stockées dans le registre individuel. Alors, si nous prenons cet exemple particulier, alors l'état de la LFSR n'est rien d'autre qu'une chaîne de 4 bits, à savoir les 4 bits stockés dans les registres? 3,? 2,? 1 et? 0 et la mise à jour de l'état se produit comme suit: après chaque cycle d'horloge, le bit qui est présent dans? 0est produit comme bit de sortie et le contenu de tous les registres est décalé à droite. En conséquence, qu'est-ce qui va se passer, c'est que le courant? 1 va devenir le suivant? 0. Le courant? 2 deviendra le suivant? 1 et ainsi de suite. Et en conséquence? 3 va devenir vide. Et la valeur actualisée du dernier registre, dans ce cas? 3, sera déterminée en prenant un XOR des sous-ensembles des bits de l'état actuel. Et les sous-ensembles des registres dont nous prenons XOR sont en fait déterminés par le coefficient de rétroaction. Donc encore dans cet exemple, puisque les coefficients de rétroaction sont 0, 1, 0, 1, cela signifie, après chaque cycle d'horloge une fois que nous faisons le changement de droite ici, la valeur de? 3, n'est rien, mais la XOR du courant? 2, et le courant? 0. Si vous prenez la XOR qui sera la valeur qui sera alimentée comme nouvelle valeur de? 3. C'est la raison pour laquelle le nom de la rétroaction linéaire s'enregistre. Dans chaque cycle d'horloge, nous décalons le contenu de tous les registres par un seul poste et c'est pourquoi le registre des postes. Et une rétroaction linéaire, parce que nous avons une boucle de rétroaction qui détermine la valeur du contenu de?? − 1, au cours du prochain cycle d'horloge. Et cette fonction de rétroaction est une fonction linéaire de l'ensemble actuel de registres. Donc par exemple, si vous prenez cette LFSR du degré 4, et supposons que l'état initial est 0011, puis après la première horloge, tout sera décalé par une position, et par conséquent, le bit 1 sera le premier bit de sortie et les commentaires qui seront dans le LFSR pour l'itération suivante seront 1, à savoir le XOR du bit 0 et 1 parce que vos coefficients de feedback sont 0, 1, 0, 1 et en conséquence l'état suivant du LFSR sera 1001.Again après le prochain cycle d'horloge, la valeur de bit 1 sera vidée de la sortie de test, qui sera la seconde Un bit de sortie de votre LFSR et les commentaires qui seront en cours seront 1 et, par conséquent, votre état sera mis à jour à 1100, et ainsi de suite. Donc, c'est comme ça qu'une RSS de degré? Fonctionne. (Référez-vous à la diapositive: 07 :49) Maintenant, nous devons nous demander si cette LFSR est sûre ou non, ce qui signifie que nous pouvons considérer que cette LFSR est un générateur pseudo-aléatoire. Et l'exigence d'un générateur pseudo-aléatoire est que si quelqu'un vous donne l'échantillon d'une LFSR, où vous n'avez pas l'état initial de l'algorithme parce que si on vous donne l'état initial du LFSR, alors vous pouvez calculer tous les bits de sortie du LFSR. Donc, imaginez que vous ne vous êtes pas donné l'état d'entrée du RPFT et que vous n'avez pas non plus donné les coefficients de rétroaction, mais que vous êtes donné le degré du RPFT, c'est-à-dire que vous connaissez le nombre de registres qui sont utilisés dans le RPFT. Il est alors possible pour l'attaquant de calculer ou de prédire les résultats de LFSR. Il s'avère que si nous avons un BSR de degré?, alors il peut avoir au plus 2? − 1 états non nulles. Et pourquoi nous sommes intéressés par les Etats non-nulles? Parce qu'une fois LFSR occupe l'état, où le contenu de tous les registres est 0, puis après qu'il importe peu combien de fois ou combien de cycles d'horloge nous exploitons le LFSR,tous les états suivants seront 0. Cela signifie qu'une fois que nous atteindrons un état tout à fait zéro, nous devrions cesser de produire les résultats du RPFT. Ce qui est intéressant, c'est quand nous nous concentrons sur les états non nulles du LFSR. Nous définissons le LFSR comme une LFSR de longueur maximale, si la séquence de sortie se répète après exactement 2? − 1 nombre d'états non nulles. Et de façon intéressante, il s'avère qu'il n'a pas d'importance avec l'état d'entrée que vous commencez avec, si vous commencez avec un état initial différent de zéro, alors il est toujours possible de définir les coefficients de rétroaction de façon à ce que votre RPFT devienne réellement une longueur maximale LFSR.Cela signifie qu'en commençant par cet état initial différent de zéro, vous pouvez passer par tous les 2? − 1 non-zéros, puis seule la séquence sera répétée. Alors imaginez pour le moment que vous avez une longueur maximale LFSR. Intuitivement, vous pourriez penser que toutes les chaînes de bits vont être produites avec une fréquence égale, alors est-ce que cela signifie que votre LFSR est un PRG sécurisé parce que si l'état de sortie va être répété après 2? − 1 nombre d'états, c'est-à-dire pour un attaquant, il doit attendre 2? − 1 nombre d'états, qui est une quantité exponentielle de quantité. Il ne peut donc pas distinguer la sortie du LFSR de la sortie d'un vrai générateur de nombres aléatoires. Cela pourrait être votre intuition sous-jacente à partir de laquelle vous pouvez déclarer votre SRFT sécurisée. Mais il s'avère que ce n'est pas le cas. Pour une LFSR de degré?, juste en observant le nombre de bits de sortie polynomiaux, (Référez-vous à la diapositive: 10 :26) un adversaire peut récupérer la clé entière et une fois qu'il récupère la clé entière, il peut prédire tous les bits de sortie futurs de la droite LFSR. Alors imaginez qu'on vous donne un RPT de degré?, où vous ne connaissez pas les coefficients de rétroaction et vous ne connaissez pas les états initiaux de LFSR et imaginez que l'adversaire a observé les 2 premiers? Les bits de sortie de la LFSR que je dénote? 1, …,? ?.Et l'état initial non-zéro de la LFSR est noté par la notation (?? − 1 (0), …,? 0 (0)). Donc, dans cette notation, dans le exposant, je mets 0 dans la parenthèse qui dénote le 0e état du LFSR, à savoir l'état initial, et qui est également inconnu pour l'agresseur, l'attaquant n'a vu que le premier 2? Bits de sortie. Nous supposons également que l'adversaire n'est pas au courant des coefficients de rétroaction ; du point de vue de l'adversaire, il pourrait s'agir d'un sous-ensemble de l'adversaire? Les registres qui sont en train de faire XORed pour décider de la rétroaction. Donc, les coefficients inconnus?? − 1to? 0 sont aussi l'attaquant. Il s'avère que l'adversaire sait que l'état initial de la LFSR n'est rien d'autre que le premier? Les bits de sortie qu'elle a vu parce que si vous voyez le fonctionnement de la LFSR, après chaque cycle d'horloge, le contenu de? 0est réellement sorti comme la sortie et après chaque cycle d'horloge, le nouveau contenu de? 0est en fait le contenu précédent de? 1, qui à son tour est en fait le précédent? 2 et ainsi de suite. Cela signifie que l'adversaire sait que le premier? Les bits de sortie de votre LFSR ne sont rien, mais votre état initial. C'est donc le premier élément d'information qui est maintenant disponible pour l'adversaire, qui est maintenant une quantité importante d'informations pour l'adversaire. Et il s'avère que les prochains bits de sortie, à savoir??? + 1to? 2?, donne en fait un système d'équations linéaires dans les inconnues dans les coefficients de rétroaction à l'adversaire. A savoir que l'adversaire sait que le? + 1 ?bit de sortie?? + 1 n'est rien, mais? 0?1? ?1?2? ????????? − 1 ??. De la même façon, le bit de sortie 2 ??h satisfait la relation? 2? =? 0????1?? + 1 …??? − 1 ?2? − 1. Donc l'adversaire a un système de? Des équations indépendantes dans? Variables. Et en les résolvant, il peut récupérer complètement les coefficients de rétroaction. Donc maintenant les deux clés ainsi que les coefficients de rétroaction sont connus de l'adversaire.Par conséquent, il peut entièrement déterminer tous les extrants subséquents de votre SRFT. C'est-à-dire juste en observant 2? Les bits de sortie de la LFSR, l'adversaire peut complètement briser cette LFSR. Et donc pas de moyen, c'est en fait un pseudo-générateur aléatoire. (Référez-vous à la diapositive: 13 :27) Donc, une méthode qui est utilisée pour préserver la sécurité de la LFSR est d'ajouter une sorte de non? linearité. Si vous voyez l'attaque, ou la stratégie, qui est utilisée par l'attaquant ici est d'explorer le système de l'équation linéaire, ou à savoir, l'attaquant utilise le fait que la rétroaction est en fait une fonction linéaire du sous-ensemble du registre. Donc une façon de contourner ceci est d'ajouter une sorte de non? linéarité dans le registre des retours de feedback. Et il y a plusieurs façons d'introduire la non-linéarité dans la construction d'un registre de décalage linéaire. La première méthode pour ajouter la non-linéarité est de faire en sorte que vos commentaires eux-mêmes soient non linéaires. A savoir, ce que nous supposons ici, c'est que le contenu du? ?hregister au cycle de l'horloge? + 1 sera le contenu de la? + 1 ?hregistre au cycle d'horloge?, cela signifie que tout est toujours décalé d'une position après chaque cycle d'horloge. Mais le contenu du dernier registre est maintenant une fonction non linéaire des registres actuels. Donc, dans la construction précédente dans le LFSR, la fonction? était en fait une fonction linéaire. Mais la proposition ici est qu'au lieu de s'assurer que la rétroaction est une fonction linéaire, le feedback va maintenant être une fonction non linéaire de l'ensemble de bits qui sont là dans le registre en cours. Donc, c'est une façon d'ajouter la non-linéarité qui est suivie dans les constructions modernes de générateurs pseudo-aléatoires basés sur des registres de décalage de feedback. L'autre façon d'ajouter la non-linéarité est d'ajouter la non-linéarité dans la sortie elle-même. Jusqu'à présent, nous discutons du cas où la production est en fait le contenu du courant? 0, où? 0est la valeur de? 1dans le cycle d'horloge précédent et ainsi de suite et chaque cycle d'horloge tout devient décalant d'une position. Mais je pourrais avoir une autre façon de déterminer la production, où la production est en fait une fonction non linéaire, et il y a 2 façons de déterminer les générateurs de combinaisons non linéaires. La variante est la suivante: nous utilisons toujours une seule LFSR, où tout se déplace d'une position et nous avons une rétroaction linéaire. Mais au lieu de simplement s'assurer que? 0est le bit de sortie, le bit de sortie s'avère être une fonction non linéaire des registres actuels. Et la variante deux est, au lieu d'utiliser une LFSR, nous aurons maintenant plusieurs LFSR, de préférence de différents degrés. Et le bit de sortie global du LFSR sera une fonction non linéaire compliquée de la sortie de chaque LFSR. Donc c'est la seconde variant.Donc, cela veut dire ajouter la non-linéarité vous avez 2 options, la non-linéarité dans le feedback et la non-linéarité dans la sortie, où la non-linéarité dans la sortie peut être réalisée de 2 manières. Il suffit d'utiliser 1 LFSR, la sortie étant une fonction non linéaire compliquée et l'option deux est d'utiliser plusieurs LFRS, la sortie étant une fonction non linéaire compliquée de la sortie de chaque LFSR. (Référez-vous à la diapositive: 16 :31) Et il s'avère que les constructions modernes de GPR basées sur le LFSR utilisent effectivement ces principes. Donc voici une construction candidate basée sur LFSR, qui s'appelle Trivium. Et c'est une instanciation très populaire de pseudo-générateur aléatoire. Si vous voyez de façon pictoriale, il s'agit en fait d'une combinaison de 3 registres de décalage de retour. Donc vous avez la première LFSR qui se compose de 93 registres, que nous dénotent comme le registre de retour d'information A. Alors vous avez le prochain LFSR, que nous dédèrons B constitué de 84 registres. Ensuite, nous avons les prochains registres de rétroaction C, constitués de 111 registres. Maintenant, la raison pour laquelle elle utilise 93, 84, 111 ne sont pas clairement connues ; elles sont le principe de conception utilisé par les concepteurs du trivium. Cependant, il y a certains principes bien connus qui sont utilisés pour sélectionner la valeur de FSR A, FSR B, FSR C, mais sinon en général il n'y a pas de lignes directrices fixes qui sont utilisées pour sélectionner la taille de FSR A, FSR B, FSR C comme ça. Et maintenant, vous voyez que chaque FSR a une sortie individuelle. Donc, si je considère la sortie de FSR A, donc, c'est essentiellement la XOR du registre le plus à droite, dans ce cas, le 93e registre et un autre registre du même FSR. Il s'agit donc de la première différence dans la construction de Trivium par rapport à la LFSR.régulière. Dans le LFSR régulier, la 93e sortie, le contenu du 93e registre sera considéré comme le bit de sortie après chaque cycle d'horloge. Mais maintenant après chaque cycle d'horloge, c'est le XOR du 93e registre et un 66 ?hregister dans le FSR A, qui sera considéré comme la sortie de la FSR A après les cycles d'horloge individuels. Et la même attente pour le FSR B ainsi que pour le FSR C. C'est la première façon d'ajouter la non-linéarité ici. Et la sortie globale du FSR est essentiellement la XOR de la sortie de la FSR A, FSR B, FSR C. Donc c'est la seconde façon d'ajouter la non-linéarité ici. En ce qui concerne la rétroaction, si vous voyez, par exemple, le FSR A ici, qu'est-ce qui se passe comme rétroaction? Donc la rétroaction n'est rien d'autre qu'une fonction de l'un des registres dans le même FSR et un sous-ensemble de registres du FSR au-dessus. Voici donc ce que je veux dire “ ci-dessus: comme je l'ai dit, la séquence des 93 premiers registres est la FSR A et le prochain registre 84 est FSR C. Vous pouvez imaginer cette construction comme une sorte de construction circulaire, où, au-dessus du FSR A, nous avons le FSR A et au-dessus du FSR C nous avons le FSR B. C'est ce que je veux dire par “ dans ce contexte. Et la rétroaction du FSR A est essentiellement un XOR de l'un des registres de la FSR A, avec certains des registres de la FSR C. De la même façon, la rétroaction du FSR B est une XOR de certains des registres de la FSR. Le registre du FSR B avec certains des registres de la FSR A, et de la même manière que la rétroaction pour le FSR C est un XOR de certains registres du FSR C avec certains des registres dans le FSR B. C'est ainsi que nous introduisons la non-linéarité. Donc, l'idée ici est de rendre cette construction compliquée, nous sommes en fait complètement en train de supprimer la linéarité qui était présente dans la construction originale du LFSR. Et c'est ainsi que le Trivium est conçu. Et ceci est considéré comme un PRG sécurisé car, après le développement de cette construction, nous n'avons pas eu d'attaque pratique. Cela signifie qu'aucun algorithme de temps polynomial n'a été rapporté, ce qui peut en fait prédire le résultat du trivium si l'état initial du trivium n'est pas connu de you.Donc, je ne vais pas entrer dans les détails complets de la construction, quels principes de conception sont utilisés, pourquoi les 3 FSR utilisés, leurs degrés sont construits comme ceci et ainsi de suite. Si vous voulez en savoir plus sur les détails de ces constructions, vous pouvez vous référer à n'importe laquelle des références que nous suivons dans ce cours. (Référez-vous à la diapositive: 20 :56) Nous allons maintenant envisager une autre instanciation populaire de pseudo-générateur aléatoire, à savoir RC4, qui est super rapide lorsqu'il est implémenté dans un logiciel. Et même si c'était des années de travail très populaires, plusieurs vulnérabilités ont été signalées récemment. Et c'est pourquoi il n'est plus recommandé d'être utilisé à des fins critiques. En fait, il a été utilisé comme une des normes dans WEP.Et après que les vulnérabilités aient été signalées dans le RC4, il n'est plus utilisé dans la norme. Alors, rappelez que toute instanciation pratique de pseudo-générateur aléatoire est constituée de 2 algorithmes, à savoir un algorithme d'initialisation et un algorithme de mise à jour de l'état. Et dans l'algorithme d'initialisation, l'état est initialisé et dans l'algorithme de mise à jour de l'état, l'état est mis à jour et les prochains bits de sortie générés. En ce qui concerne l'état de la RC4, l'état se compose essentiellement d'un tableau de 256 octets. Et tout au long de l'algorithme, il sera fait en sorte que ces 256 octets se composent en fait d'une permutation de l'ensemble 0 à 255. Cela signifie que chacune des valeurs de 0 à 255 se produira comme l'un des octets parmi ces 256 octets. Et c'est pourquoi il s'agit d'une permutation de l'ensemble 0 à 255.Maintenant, l'algorithme d'initialisation de ce RC4 est le suivant. L'algorithme d'initialisation crée une permutation pseudo-aléatoire dépendante clé de l'ensemble 0 à 255. Et avec ça, initialiser les pointeurs 2index? Et? Compris entre 0 et 255. C'est la façon dont l'initialisation se produit pour RC4, nous allons entrer dans les détails de l'initialisation très bientôt. Et une fois l'initialisation terminée, dans l'algorithme de mise à jour de l'état dans chaque itération les octets du?, qui sont en fait une permutation pseudo-aléatoire dépendante clé de l'ensemble de 0 à 255 sont mélangé, et après avoir mélangé l'un des octets est la sortie, c'est-à-dire la façon dont l'état est mis à jour (voir Diapositive Heure: 23 :02) Nous allons donc maintenant entrer dans les détails de l'algorithme d'initialisation. Donc la clé ou la graine pour l'algorithme RC4algorithme est fondamentalement une clé de 16 octets, ce qui va être une clé aléatoire de 16 octets. Donc on dénote itby? 0à? 15. Et la sortie va être une pseudo-permutation aléatoire de l'ensemble 0 à 255. Donc, ce sera le tableau?. Alors on initialise le tableau? Consistant en valeurs 0 à 255 dans sequence.Namely, le premier octet est défini sur 0. L'octet suivant est défini sur 1 et le dernier octet est la valeur 255. Il s'agit d'une permutation d'identité. Et maintenant nous avons à voir comment remanier le contenu de la grappe? En fonction de la valeur du tableau de clés?. Cela signifie, selon le contenu des principaux octets, que nous devons mélanger le contenu du tableau?, s'assurer qu'après le remaniement, la modification? Représente toujours une permutation de l'ensemble 0 à 255.Pour ce faire, nous répétons en fait les valeurs de la clé et assurez-vous que le tableau clé devient de la taille 255. Et cela se fait en effectuant l'opération,? [? ] =? [? Mod 16 ], cela signifie que nous prenons les 16 premiers octets, et répétons encore et encore, pour nous assurer que nous avons maintenant un tableau clé développé de taille 256. C'est ainsi que nous faisons l'expansion clé. Et puis nous avons défini le pointeur initial de l'index? pour être 0. Et une fois le pointeur? Est défini sur 0, pour les 256 itérations suivantes, nous faisons les opérations suivantes. Nous faisons le shuffling et pour faire le shuffling, nous changeons en fait la valeur de? Comme ceci: nous avons fixé? D'être la sommation du courant? Et le contenu actuel de l'octet? Et l'octet de clé? ?h. Namely,? =?? +? [? ] +? [? ]. Et une fois que nous aurons l'index mis à jour?, nous échangerons le contenu de? [? ] et? [? ]. C'est ainsi que nous faisons le shuffling. Donc, intuitivement ce que vous pouvez imaginer ici, c'est que dans chaque itération, l'index? Est incrémenté de 1. Et dans chaque itération l'index? Est mélangé au hasard, en fonction de l'octet des clés. Et une fois le pointeur? Est mis à jour, nous allons à cet emplacement dans le tableau? .Et permuter le contenu? [? ] avec le contenu de cet emplacement. C'est ainsi que nous générons une permutation pseudo-aléatoire dépendante de la clé?. Pourquoi il s'agit d'une permutation pseudo-aléatoire dépendante de la clé? Est parce que dans chaque itération, la valeur de? Dépend du contenu du tableau de clés. Ce ’ s comment la permutation résultante est une permutation dépendante de la clé. (Voir Heure de la diapositive: 26 :01) Une fois que l'état a été initialisé, nous allons à l'algorithme de mise à jour et de sortie de l'état. Donc, dans l'algorithme de mise à jour de l'état, dans chaque appel, le contenu actuel de l'? Va être mélangé et l'un des octets va être en sortie. Donc, la façon dont il est généré est la suivante: imaginons que nous avons le courant? Et le courant?, ce que nous faisons, c'est augmenter la valeur de?. Et ensuite on décide au hasard de la valeur de?, selon le contenu actuel de? Comme suit. Donc, la valeur de? Est mis à jour de façon pseudo-aléatoire par réglage:? (? +? [? ]) mod 256. Cela signifie tout ce qui est l'index actuel de?, à ce que nous ajoutons la valeur d'octet stockée à l'? ?hlocation de la grappe?, et pour s'assurer que nous faisons le bouclage, toutes les opérations sont faites modulaires 256. Donc, en faisant cette opération, on met à jour la valeur du compteur d'index? De façon pseudo-aléatoire. Et puis ce que nous faisons, nous échangerons le contenu de? ?hemplacement de tableau? Et? ?hemplacement de la grappe?. C'est ainsi que nous faisons la mise à jour de l'État. Pour déterminer la production, ce que nous faisons, c'est déterminer un nouvel indice, ce qui n'est rien d'autre que la sommation du contenu de l'? ?hemplacement de la grappe? Et l'emplacement de la grappe?, c'est-à-faire,? ? (? [? ] +? [? ]) mod 256. Et nous allons à cet endroit, c'est-à-dire l'? ?hlocation et quelle que soit la valeur de l'octet qui y est stockée, c'est-à-dire la valeur de l'octet que nous allons générer. (Référez-vous à la diapositive: 27 :46) Discutons maintenant de la sécurité de l'algorithme RC4. Donc si vous voyez le pseudocode de l'algorithme de mise à jour de l'état et l'algorithme d'initialisation, vous pouvez voir que nous ne faisons aucune opération compliquée. C'est pourquoi cet algorithme est super-rapide lorsque vous l'implémrez dans un logiciel. Et c'est pourquoi elle était très populaire. Puis les gens ont commencé à signaler les vulnérabilités dans la sécurité du RC4. Donc, nous voulons analyser ici si RC4 est un candidat pseudo-aléatoire générateur de nombres ou pas. Donc, si vous vous souvenez, dans chaque modification de la mise à jour de l'état, RC4 donne un octet. Nous devons donc comparer l'algorithme de générateur d'octets RC4 avec un véritable algorithme de générateur d'octets aléatoire. Un véritable algorithme de générateur d'octets aléatoire produira n'importe quel octet dans l'ensemble 0 à 255, uniformément aléatoire. Et le résultat attendu de la RC4 est que, dans chaque invocation de l'algorithme de mise à jour de l'état, l'octet de sortie peut être presque comme une valeur uniformément aléatoire de l'ensemble 0 à 255. Il s'avère que dans l'une des œuvres précédentes, Mantin et Shamir ont montré que même si nous supposons que l'initialisation de l'algorithme de la RC4 est une initialisation uniforme (cela signifie que cela ne dépend pas de l'algorithme de clé), si nous commençons à exécuter l'algorithme de mise à jour de l'état, alors le second octet de sortie RC4 est plus susceptible d'être 0 ce qui signifie, la probabilité que le second octet de sortie RC4is 0 soit 2256, comparé à 1256. Et cela peut être prouvé formellement. Donc, si vous voulez voir les détails formels exacts sur la façon dont cette probabilité est dérivée, vous pouvez vous référer à l'une des références que nous suivons. Donc, en supposant que c'est le cas, alors voici un RC4distinction très simple qui peut distinguer un octet d'échantillon généré par le générateur d'octets RC4, à partir d'un échantillon qui est généré par un générateur d'octets vraiment aléatoire. Donc imaginez que le distinguisher est donné un échantillon?, et il doit déterminer s'il est produit par le générateur d'octets RC4 ou par un générateur d'octets aléatoire. Donc ce que fait le distinguisher, puisqu'il connaît le résultat de Mantin et Shamir, il vérifie juste le second octet de?, et puis si le second octet de? S'avère être 0, puis il identifie l'échantillon? Est généré par le générateur d'octets RC4, sinon il étiquette l'échantillon? Pour être générée par une sortie vraiment aléatoire. Calculons maintenant l'avantage distinctif du distinguant que nous avons conçu. Si en effet l'échantillon? qui est une séquence d'octets est généré par le RC4 par générateur est donné au distinguisher, alors la probabilité qu'en effet le second octet est 0 est 2256. Donc, la probabilité que notre distinction soit faite quand un échantillon aléatoire généré par le générateur d'octets RC4 est libellé comme le résultat de RC4 est 2256. Alors que si la séquence d'octets est générée par un générateur d'octets vraiment aléatoire est donnée à l'élément de distinction, la probabilité que son second octet soit 0 est en fait 1 sur 256. Cela signifie que dans ce cas seulement, avec cette probabilité seulement, notre distinction finira par étiqueter une séquence aléatoire vraie d'octets pour être le résultat d'une RC4. Alors, quel est l'avantage de l'agresseur dans ce cas? La différence absolue est 1256, ce qui est une probabilité significative. Cela signifie que nous ne pouvons plus affirmer que la séquence d'octets générée par le générateur de bytegénérateurs RC4 est proche de la séquence d'octets, qu'un générateur d'octets vraiment aléatoire aurait produit et c'est pourquoi ce RC4 n'est plus considéré comme sécurisé. Pour conclure, dans cette conférence, nous avons vu à un niveau très élevé certaines des instanciations pratiques de pseudo-générateur aléatoire. Nous avons ensuite vu une construction basée sur le matériel, que nous appelons le registre de décalage linéaire. Le registre original des équipes de rétroaction linéaire n'est plus utilisé sous la forme proposée, car en observant le nombre polynomial d'extrants, un adversaire peut trouver l'état entier ainsi que les coefficients de rétroaction et, par conséquent, peut prédire tous les bits de sortie subséquents de LFSR. C'est la raison pour laquelle les instanciations modernes de générateurs pseudo-aléatoires basés sur le registre de décalage de retour introduisons une sorte de non-linéarité qui peut se faire de plusieurs manières, comme la non-linéarité sous forme de coefficients de rétroaction non linéaires, de bits de sortie non linéaires, etc. Nous avons aussi discuté d'une construction appelée Trivium, basée sur ce principe, et une seconde construction que nous avons vu est la construction de logiciels qui peut être implémentée dans le logiciel et c'est super? rapide, c'est-à-dire RC4. Malheureusement, nous avons aussi vu certaines vulnérabilités qui ont été signalées dans le RC4 à cause de laquelle il n'est plus recommandé d'être utilisé.