Cifrado de Feistel - Feistel cipher

En criptografía , un cifrado Feistel (también conocido como Luby-Rackoff cifrado de bloques ) es una estructura simétrica utilizada en la construcción de sistemas de cifrado en bloque , llamado así por el alemán -nacido físico y criptógrafo Horst Feistel que no investigación pionera, mientras trabajaba para IBM (EE.UU.) ; también se conoce comúnmente como red Feistel . Una gran proporción de cifrados en bloque utiliza el esquema, incluido el Estándar de cifrado de datos de EE. UU . , El GOST soviético / ruso y los cifrados Blowfish y Twofish más recientes . En un cifrado de Feistel, el cifrado y el descifrado son operaciones muy similares, y ambas consisten en ejecutar iterativamente una función llamada "función redonda" un número fijo de veces.

Historia

Muchos cifrados de bloques simétricos modernos se basan en redes de Feistel. Las redes Feistel se vieron por primera vez comercialmente en el cifrado Lucifer de IBM , diseñado por Horst Feistel y Don Coppersmith en 1973. Las redes Feistel ganaron respetabilidad cuando el gobierno federal de Estados Unidos adoptó el DES (un cifrado basado en Lucifer, con cambios realizados por la NSA ) en 1976. Como otros componentes del DES, la naturaleza iterativa de la construcción de Feistel facilita la implementación del criptosistema en el hardware (particularmente en el hardware disponible en el momento del diseño del DES).

Diseño

Una red Feistel usa una función redonda , una función que toma dos entradas, un bloque de datos y una subclave, y devuelve una salida del mismo tamaño que el bloque de datos. En cada ronda, la función de ronda se ejecuta en la mitad de los datos que se van a cifrar y su salida se XOR con la otra mitad de los datos. Esto se repite un número fijo de veces y el resultado final son los datos cifrados. Una ventaja importante de las redes Feistel en comparación con otros diseños de cifrado, como las redes de sustitución-permutación, es que se garantiza que toda la operación es invertible (es decir, los datos cifrados se pueden descifrar), incluso si la función redonda no es invertible en sí misma. La función redonda se puede complicar arbitrariamente, ya que no es necesario diseñarla para que sea invertible. Además, las operaciones de cifrado y descifrado son muy similares, incluso idénticas en algunos casos, y solo requieren una inversión del programa de claves . Por lo tanto, el tamaño del código o de los circuitos necesarios para implementar dicho cifrado se reduce casi a la mitad.

Trabajo teórico

Los criptógrafos han analizado ampliamente la estructura y las propiedades de los cifrados de Feistel .

Michael Luby y Charles Rackoff analizaron la construcción de cifrado Feistel, y demostraron que si la función de ronda es un criptográficamente seguro función pseudoaleatoria , con K i utiliza como la semilla, a continuación, 3 rondas son suficientes para hacer que el cifrado de bloques una permutación pseudoaleatoria , mientras que 4 rondas son suficientes para convertirlo en una permutación pseudoaleatoria "fuerte" (lo que significa que sigue siendo pseudoaleatorio incluso para un adversario que obtiene acceso de oráculo a su permutación inversa). Debido a este resultado muy importante de Luby y Rackoff, los cifrados de Feistel a veces se denominan cifrados de bloque de Luby-Rackoff.

El trabajo teórico posterior ha generalizado algo la construcción y ha dado límites más precisos para la seguridad.

Detalles de construcción

Diagrama de cifrado de Feistel en.svg

Sea la función de ronda y las sub-teclas para las rondas respectivamente.

Entonces la operación básica es la siguiente:

Divida el bloque de texto sin formato en dos partes iguales, ( , )

Para cada ronda , calcule

Donde significa XOR . Entonces el texto cifrado es .

El descifrado de un texto cifrado se logra calculando

Entonces es el texto sin formato de nuevo.

El diagrama ilustra tanto el cifrado como el descifrado. Tenga en cuenta la inversión del orden de las subclaves para el descifrado; esta es la única diferencia entre cifrado y descifrado.

Cifrado de Feistel desequilibrado

Los cifrados de Feistel desequilibrados utilizan una estructura modificada donde y no tienen la misma longitud. El cifrado Skipjack es un ejemplo de dicho cifrado. El transpondedor de firma digital de Texas Instruments usa un cifrado Feistel no balanceado patentado para realizar la autenticación de desafío-respuesta .

El shuffle de Thorp es un caso extremo de un cifrado Feistel desequilibrado en el que un lado es un solo bit. Esto tiene una mejor seguridad demostrable que un cifrado Feistel equilibrado, pero requiere más rondas.

Otros usos

La construcción de Feistel también se utiliza en algoritmos criptográficos distintos de los cifrados en bloque. Por ejemplo, el esquema de relleno de cifrado asimétrico óptimo (OAEP) utiliza una red Feistel simple para aleatorizar los textos cifrados en ciertos esquemas de cifrado de clave asimétrica .

Se puede usar un algoritmo de Feistel generalizado para crear fuertes permutaciones en dominios pequeños de tamaño no una potencia de dos (ver cifrado que preserva el formato ).

Redes Feistel como componente de diseño

Ya sea que el cifrado completo sea un cifrado de Feistel o no, las redes similares a Feistel se pueden utilizar como un componente del diseño de un cifrado. Por ejemplo, MISTY1 es un cifrado Feistel que usa una red Feistel de tres rondas en su función redonda, Skipjack es un cifrado Feistel modificado que usa una red Feistel en su permutación G, y Threefish (parte de Skein ) es un cifrado en bloque que no es Feistel que utiliza una función MIX similar a Feistel.

Lista de cifrados de Feistel

Feistel o Feistel modificado:

Feistel generalizado:

Ver también

Referencias