Fragen zur Verwendung von PRF zur Erstellung von PRG
Sei F eine sichere Pseudozufallsfunktion mit 128-Bit-Schlüssel und 256-Bit-Blocklänge. Welche der folgenden Funktionen G sind sichere Pseudozufallsgeneratoren? (Wählen Sie alle zutreffenden.)
EIN. $G(x)=F_x(0...0)$, wo $x$ ist ein $128$-bit Eingabe.
B. B. $G(x)=F_x(0...0)|| F_x(0...0)$, wo $x$ ist ein $128$-bit Eingabe.
C. $G(x)=F_x(0...0)||F_x(1...1)$, wo $x$ ist ein $128$-bit Eingabe.
D. D. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, wo $x$ ist ein $256$-bit Eingabe.
Die Antwort unseres Lehrers ist $A,D$. Aber ich verstehe nicht. Und warum ist C falsch?
Antworten
Wir beantworten Hausaufgabenfragen nicht direkt, geben aber Hinweise.
Es wird angenommen, dass ein Angreifer die Kontrolle über alle nicht geheimen Eingaben hat. Der Schlüssel ist geheim, der Block nicht. Diese Antwort hat eine gute Definition eines PRG: In einfachen Worten ist ein PRG eine Funktion, die einen geheimen Eingabe-Seed-Bitstring fester Länge verwendet und einen längeren Bitstring ausgibt, der nicht mit nicht zu vernachlässigender Wahrscheinlichkeit von einem zufälligen Bitstring unterschieden werden kann.
EIN. $G(x)=F_{x}(0...0)$Dabei ist x ein 128-Bit-Eingabeschlüssel.
Kontrolliert der Angreifer einen der Eingänge? Kann der Angreifer die Ausgabe mit nicht zu vernachlässigender Wahrscheinlichkeit von der einer Zufallsfunktion unterscheiden (dh gibt es beobachtbare Muster in der Ausgabe)? Ist der Ausgang länger als der Eingang?
Die einzige Eingabevariable ist ein geheimer Schlüssel. Der Ausgabe werden keine zusätzlichen Muster hinzugefügt. Wie lang ist die Ausgabe?
B. B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$Dabei ist x ein 128-Bit-Eingabeschlüssel.
Gleiche Fragen.
Die einzige Eingabevariable ist ein geheimer Schlüssel. Die Ausgabe wiederholt eine Sequenz zweimal. Wie lang ist die Ausgabe?
C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$Dabei ist x ein 128-Bit-Eingabeschlüssel.
Gleiche Fragen.
Die einzige Eingabevariable ist ein geheimer Schlüssel. Hat die Ausgabe zusätzliche Muster? Wie lang ist die Ausgabe?
D. D. $G(x)=F_{0...0}(x)||F_{1...1}(x)$Dabei ist x ein 256-Bit-Eingangsdatenblock.
Gleiche Fragen.
Die einzige Eingabevariable ist ein öffentlicher Datenblock. Hat die Ausgabe zusätzliche Muster? Wie lang ist die Ausgabe?
Es fehlt eine Option, die das Muster fortsetzt: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$Dabei ist x ein öffentlicher 256-Bit-Datenblock.
Wenn Sie die AD beantworten können, sollte E trivial sein.