Questions sur l'utilisation de PRF pour construire PRG
Soit F une fonction pseudo-aléatoire sécurisée avec une clé de 128 bits et une longueur de bloc de 256 bits. Quelles sont les fonctions suivantes G sont des générateurs pseudo-aléatoires sécurisés? (Sélectionnez tout ce qui s'y rapporte.)
UNE. $G(x)=F_x(0...0)$, où $x$ est un $128$entrée -bit.
B. $G(x)=F_x(0...0)|| F_x(0...0)$, où $x$ est un $128$entrée -bit.
C. $G(x)=F_x(0...0)||F_x(1...1)$, où $x$ est un $128$entrée -bit.
RÉ. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, où $x$ est un $256$entrée -bit.
La réponse que notre professeur a donnée est $A,D$. Mais je ne comprends pas. Et pourquoi C a tort?
Réponses
Nous ne répondons pas directement aux questions de devoirs, mais donnerons des indices.
Un attaquant est supposé avoir le contrôle de toutes les entrées non secrètes. La clé est secrète, le bloc ne l'est pas. Cette réponse a une bonne définition d'un PRG: en termes simples, un PRG est une fonction qui prend une chaîne de bits d'entrée secrète de longueur fixe, et produit une chaîne de bits plus longue qui ne peut être distinguée d'une chaîne de bits aléatoire avec une probabilité non négligeable.
UNE. $G(x)=F_{x}(0...0)$, où x est une clé d'entrée de 128 bits.
L'attaquant contrôle-t-il l'une des entrées? L'attaquant peut-il distinguer la sortie de celle d'une fonction aléatoire avec une probabilité non négligeable (c.-à-d. Y a-t-il des modèles observables dans la sortie)? La sortie est-elle plus longue que l'entrée?
La seule variable d'entrée est une clé secrète. Aucun modèle supplémentaire n'est ajouté à la sortie. Combien de temps dure la sortie?
B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, où x est une clé d'entrée de 128 bits.
Mêmes questions.
La seule variable d'entrée est une clé secrète. La sortie répète une séquence deux fois. Combien de temps dure la sortie?
C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, où x est une clé d'entrée de 128 bits.
Mêmes questions.
La seule variable d'entrée est une clé secrète. La sortie a-t-elle des modèles supplémentaires? Combien de temps dure la sortie?
RÉ. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, où x est un bloc de données d'entrée de 256 bits.
Mêmes questions.
La seule variable d'entrée est un bloc de données public. La sortie a-t-elle des modèles supplémentaires? Combien de temps dure la sortie?
Il y a une option manquante qui continue le modèle: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, où x est un bloc de données public de 256 bits.
Si vous pouvez répondre à l'AD, E devrait être trivial.