Вопросы по использованию PRF для построения PRG

Question

Пусть F - безопасная псевдослучайная функция со 128-битным ключом и длиной блока 256 бит. Какие из следующих функций G являются безопасными псевдослучайными генераторами? (Выбрать все, что подходит.)

А. $G(x)=F_x(0...0)$, где $x$ это $128$-битовый ввод.

Б. $G(x)=F_x(0...0)|| F_x(0...0)$, где $x$ это $128$-битовый ввод.

С. $G(x)=F_x(0...0)||F_x(1...1)$, где $x$ это $128$-битовый ввод.

Д. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, где $x$ это $256$-битовый ввод.

Ответ, который дал наш учитель: $A,D$. Но я не понимаю. И почему C ошибается?

Answer 1

Мы не отвечаем напрямую на вопросы домашнего задания, но дадим подсказки.

Предполагается, что злоумышленник имеет контроль над всеми несекретными входами. Ключ секретный, блок нет. В этом ответе есть хорошее определение PRG: простыми словами PRG - это функция, которая принимает секретную входную начальную битовую строку фиксированной длины и выводит более длинную битовую цепочку, которую нельзя отличить от случайной битовой цепочки с немалой вероятностью.

А. $G(x)=F_{x}(0...0)$, где x - 128-битный ключ ввода.

Контролирует ли злоумышленник какие-либо входы? Может ли злоумышленник отличить выходные данные от случайных функций с немалой вероятностью (т. Е. Есть ли какие-либо наблюдаемые закономерности в выходных данных)? Выходной сигнал длиннее входа?

Единственная входная переменная - это секретный ключ. Никаких дополнительных шаблонов в вывод не добавляется. Как долго на выходе?

Б. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, где x - 128-битный ключ ввода.

Те же вопросы.

Единственная входная переменная - это секретный ключ. На выходе некоторая последовательность повторяется дважды. Как долго на выходе?

С. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, где x - 128-битный ключ ввода.

Те же вопросы.

Единственная входная переменная - это секретный ключ. Есть ли на выходе дополнительные шаблоны? Как долго на выходе?

Д. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, где x - это 256-битный блок входных данных.

Те же вопросы.

Единственная входная переменная - это общедоступный блок данных. Есть ли на выходе дополнительные шаблоны? Как долго на выходе?

Отсутствует вариант, продолжающий шаблон: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, где x - публичный 256-битный блок данных.

Если вы можете ответить на AD, E должно быть тривиальным.