Perguntas sobre o uso de PRF para construir PRG

Dec 21 2020

Seja F uma função pseudo-aleatória segura com chave de 128 bits e comprimento de bloco de 256 bits. Quais são as seguintes funções G são geradores pseudo-aleatórios seguros? (Selecione tudo que se aplica.)

UMA. $G(x)=F_x(0...0)$, Onde $x$ é um $128$entrada de bits.

B. $G(x)=F_x(0...0)|| F_x(0...0)$, Onde $x$ é um $128$entrada de bits.

C. $G(x)=F_x(0...0)||F_x(1...1)$, Onde $x$ é um $128$entrada de bits.

D. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, Onde $x$ é um $256$entrada de bits.

A resposta que nosso professor deu é $A,D$. Mas eu não entendo. E por que C está errado?

Respostas

1 SAIPeregrinus Dec 23 2020 at 03:33

Não respondemos diretamente às perguntas do dever de casa, mas daremos dicas.

Presume-se que um invasor tenha controle sobre todas as entradas não secretas. A chave é secreta, o bloqueio não. Essa resposta tem uma boa definição de PRG: em termos simples, um PRG é uma função que recebe uma sequência de bits de semente de entrada secreta de comprimento fixo e produz uma sequência de bits mais longa que não pode ser distinguida de uma sequência de bits aleatória com probabilidade não desprezível.

UMA. $G(x)=F_{x}(0...0)$, onde x é uma chave de entrada de 128 bits.

O invasor controla alguma das entradas? O invasor consegue distinguir a saída daquela de uma função aleatória com probabilidade não desprezível (ou seja, há algum padrão observável na saída)? A saída é mais longa do que a entrada?

A única variável de entrada é uma chave secreta. Nenhum padrão extra é adicionado à saída. Qual é a duração da saída?

B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, onde x é uma chave de entrada de 128 bits.

Mesmas perguntas.

A única variável de entrada é uma chave secreta. A saída repete alguma sequência duas vezes. Qual é a duração da saída?

C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, onde x é uma chave de entrada de 128 bits.

Mesmas perguntas.

A única variável de entrada é uma chave secreta. A saída tem algum padrão extra? Qual é a duração da saída?

D. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, onde x é um bloco de dados de entrada de 256 bits.

Mesmas perguntas.

A única variável de entrada é um bloco de dados público. A saída tem algum padrão extra? Qual é a duração da saída?

Falta uma opção que dá continuidade ao padrão: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, onde x é um bloco de dados público de 256 bits.

Se você pode responder a DA, E deve ser trivial.