Preguntas sobre el uso de PRF para construir PRG
Sea F una función pseudoaleatoria segura con una clave de 128 bits y una longitud de bloque de 256 bits. ¿Cuáles son las siguientes funciones G son generadores pseudoaleatorios seguros? (Seleccione todas las que correspondan.)
A. $G(x)=F_x(0...0)$, dónde $x$ es un $128$-Bit de entrada.
SEGUNDO. $G(x)=F_x(0...0)|| F_x(0...0)$, dónde $x$ es un $128$-Bit de entrada.
C. $G(x)=F_x(0...0)||F_x(1...1)$, dónde $x$ es un $128$-Bit de entrada.
RE. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, dónde $x$ es un $256$-Bit de entrada.
La respuesta que dio nuestro maestro es $A,D$. Pero no lo entiendo. ¿Y por qué C está mal?
Respuestas
No respondemos directamente a las preguntas sobre la tarea, pero damos pistas.
Se supone que un atacante tiene control sobre todas las entradas no secretas. La clave es secreta, el bloqueo no. Esta respuesta tiene una buena definición de PRG: en términos simples, un PRG es una función que toma una cadena de bits de semilla de entrada secreta de longitud fija y genera una cadena de bits más larga que no se puede distinguir de una cadena de bits aleatoria con una probabilidad no despreciable.
A. $G(x)=F_{x}(0...0)$, donde x es una clave de entrada de 128 bits.
¿El atacante controla alguna de las entradas? ¿Puede el atacante distinguir la salida de la de una función aleatoria con una probabilidad no despreciable (es decir, hay patrones observables en la salida)? ¿Es la salida más larga que la entrada?
La única variable de entrada es una clave secreta. No se agregan patrones adicionales a la salida. ¿Cuánto dura la salida?
SEGUNDO. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, donde x es una clave de entrada de 128 bits.
Las mismas preguntas.
La única variable de entrada es una clave secreta. La salida repite alguna secuencia dos veces. ¿Cuánto dura la salida?
C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, donde x es una clave de entrada de 128 bits.
Las mismas preguntas.
La única variable de entrada es una clave secreta. ¿Tiene la salida algún patrón adicional? ¿Cuánto dura la salida?
RE. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, donde x es un bloque de datos de entrada de 256 bits.
Las mismas preguntas.
La única variable de entrada es un bloque de datos público. ¿Tiene la salida algún patrón adicional? ¿Cuánto dura la salida?
Falta una opción que continúa el patrón: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, donde x es un bloque de datos público de 256 bits.
Si puede responder al AD, E debería ser trivial.