Perguntas sobre o uso de PRF para construir PRG
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
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.