Pytania dotyczące wykorzystania PRF do budowy PRG

Question

Niech F będzie bezpieczną funkcją pseudolosową ze 128-bitowym kluczem i 256-bitową długością bloku. Które funkcje G są bezpiecznymi generatorami pseudolosowymi? (Wybierz wszystkie pasujące odpowiedzi).

ZA. $G(x)=F_x(0...0)$, gdzie $x$ jest $128$-bitowe wejście.

B. $G(x)=F_x(0...0)|| F_x(0...0)$, gdzie $x$ jest $128$-bitowe wejście.

DO. $G(x)=F_x(0...0)||F_x(1...1)$, gdzie $x$ jest $128$-bitowe wejście.

RE. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, gdzie $x$ jest $256$-bitowe wejście.

Odpowiedź, której udzielił nasz nauczyciel, brzmi $A,D$. Ale ja nie rozumiem. A dlaczego C się myli?

Answer 1

Nie odpowiadamy bezpośrednio na pytania dotyczące pracy domowej, ale dajemy wskazówki.

Zakłada się, że atakujący ma kontrolę nad wszystkimi niejawnymi danymi wejściowymi. Klucz jest tajny, blok nie. Ta odpowiedź ma dobrą definicję PRG: w prostych słowach PRG to funkcja, która pobiera tajny wejściowy łańcuch bitowy o stałej długości i generuje dłuższy ciąg bitów, którego nie można odróżnić od losowego ciągu bitów z prawdopodobieństwem nie do pominięcia.

ZA. $G(x)=F_{x}(0...0)$, gdzie x to 128-bitowy klucz wejściowy.

Czy atakujący kontroluje którekolwiek z wejść? Czy atakujący może odróżnić wynik od wyniku funkcji losowej z prawdopodobieństwem nie do pominięcia (tj. Czy na wyjściu są obserwowalne wzorce)? Czy dane wyjściowe są dłuższe niż wejściowe?

Jedyną zmienną wejściową jest tajny klucz. Żadne dodatkowe wzorce nie są dodawane do wyjścia. Jak długo trwa wyjście?

B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, gdzie x to 128-bitowy klucz wejściowy.

Te same pytania.

Jedyną zmienną wejściową jest tajny klucz. Dane wyjściowe powtarzają się dwukrotnie. Jak długo trwa wyjście?

DO. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, gdzie x to 128-bitowy klucz wejściowy.

Te same pytania.

Jedyną zmienną wejściową jest tajny klucz. Czy na wyjściu są jakieś dodatkowe wzory? Jak długo trwa wyjście?

RE. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, gdzie x to 256-bitowy blok danych wejściowych.

Te same pytania.

Jedyną zmienną wejściową jest publiczny blok danych. Czy na wyjściu są jakieś dodatkowe wzory? Jak długo trwa wyjście?

Brakuje opcji, która kontynuuje schemat: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, gdzie x jest publicznym 256-bitowym blokiem danych.

Jeśli możesz odpowiedzieć na reklamę, E powinno być trywialne.