stringtranslate.com

Cifrado de Feistel

En criptografía , un cifrado Feistel (también conocido como cifrado de bloque Luby-Rackoff ) es una estructura simétrica utilizada en la construcción de cifrados de bloque , llamada así por el físico y criptógrafo alemán Horst Feistel , quien realizó una investigación pionera mientras trabajaba para IBM ; también se lo conoce comúnmente como red Feistel . Una gran cantidad de cifrados de bloque utilizan 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 Feistel, el cifrado y el descifrado son operaciones muy similares, y ambas consisten en ejecutar iterativamente una función llamada " función de ronda " un número fijo de veces.

Historia

Muchos de los cifrados de bloques simétricos modernos se basan en redes 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 los EE. UU. adoptó el DES (un cifrado basado en Lucifer, con cambios realizados por la NSA ) en 1976. Al igual que otros componentes del DES, la naturaleza iterativa de la construcción de Feistel hace que la implementación del criptosistema en hardware sea más sencilla (particularmente en el hardware disponible en el momento del diseño del DES).

Diseño

Una red Feistel utiliza una función de ronda , 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. [1] 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 combina con la otra mitad de los datos mediante la operación XOR. Esto se repite un número fijo de veces y la salida 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 sea invertible (es decir, los datos cifrados se pueden descifrar), incluso si la función de ronda no es en sí misma invertible. La función de ronda se puede complicar arbitrariamente, ya que no necesita estar diseñada para ser invertible. [2] : 465  [3] : 347  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 circuito necesario para implementar un cifrado de este tipo se reduce casi a la mitad. A diferencia de las redes de sustitución-permutación, las redes de Feistel tampoco dependen de una caja de sustitución que podría causar canales secundarios de temporización en las implementaciones de software.

Trabajo teórico

La estructura y las propiedades de los cifrados Feistel han sido ampliamente analizadas por los criptógrafos .

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

Trabajos teóricos posteriores han generalizado un poco la construcción y han proporcionado límites más precisos para la seguridad. [5] [6]

Detalles de construcción

Sea la función de ronda y sean las subclaves para las rondas respectivamente.

Entonces el funcionamiento básico es el siguiente:

Divida el bloque de texto simple en dos partes iguales: ( , ).

Para cada ronda , calcule

donde significa XOR . Entonces el texto cifrado es .

El descifrado de un texto cifrado se logra mediante el cálculo de

Luego está el texto simple nuevamente.

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

Cifrado de Feistel desequilibrado

Los cifrados Feistel no balanceados utilizan una estructura modificada donde y no tienen la misma longitud. [7] El cifrado Skipjack es un ejemplo de este tipo de cifrado. El transpondedor de firma digital de Texas Instruments utiliza un cifrado Feistel no balanceado patentado para realizar la autenticación de desafío-respuesta . [8]

El barajado de Thorp es un caso extremo de un cifrado Feistel desequilibrado en el que un lado es un solo bit. Este método ofrece una seguridad demostrable mejor que un cifrado Feistel equilibrado, pero requiere más rondas. [9]

Otros usos

La construcción Feistel también se utiliza en algoritmos criptográficos distintos de los cifrados por bloques. 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 utilizar un algoritmo Feistel generalizado para crear permutaciones fuertes en dominios pequeños de tamaño no mayor que una potencia de dos (véase cifrado con preservación de formato ). [9]

Las redes Feistel como componente de diseño

Independientemente de si todo el cifrado es un cifrado 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 utiliza una red Feistel de tres rondas en su función de ronda, Skipjack es un cifrado Feistel modificado que utiliza una red Feistel en su permutación G, y Threefish (parte de Skein ) es un cifrado de bloque no Feistel que utiliza una función MIX similar a Feistel.

Lista de cifras de Feistel

Feistel o Feistel modificado:

Feistel generalizado:

Véase también

Referencias

  1. ^ Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. (2001). Manual de criptografía aplicada (quinta edición). Taylor & Francis. pág. 251. ISBN 978-0849385230.
  2. ^ Schneier, Bruce (1996). Criptografía aplicada . Nueva York: John Wiley & Sons. ISBN 0-471-12845-7.
  3. ^ Stinson, Douglas R. (1995). Criptografía: teoría y práctica . Boca Raton: CRC Press. ISBN 0-8493-8521-0.
  4. ^ Luby, Michael; Rackoff, Charles (abril de 1988), "Cómo construir permutaciones pseudoaleatorias a partir de funciones pseudoaleatorias", SIAM Journal on Computing , 17 (2): 373–386, doi :10.1137/0217022, ISSN  0097-5397.
  5. ^ Patarin, Jacques (octubre de 2003), Boneh, Dan (ed.), Advances in Cryptology - CRYPTO 2003 (PDF) , Lecture Notes in Computer Science, vol. 2729, págs. 513-529, doi :10.1007/b11817, ISBN 978-3-540-40674-7, S2CID  20273458 , consultado el 27 de julio de 2009
  6. ^ Zheng, Yuliang; Matsumoto, Tsutomu; Imai, Hideki (20 de agosto de 1989). "Sobre la construcción de cifrados de bloques que sean demostrablemente seguros y que no dependan de ninguna hipótesis no demostrada". Avances en criptología — Actas de CRYPTO' 89. Apuntes de clase en informática. Vol. 435. págs. 461–480. doi :10.1007/0-387-34805-0_42. ISBN 978-0-387-97317-3.
  7. ^ Schneier, Bruce; Kelsey, John (21 de febrero de 1996). "Redes Feistel desequilibradas y diseño de cifrado por bloques". Cifrado rápido de software. Apuntes de clase en informática. Vol. 1039. págs. 121–144. doi :10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. Recuperado el 21 de noviembre de 2017 .
  8. ^ Bono, Stephen; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael (5 de agosto de 2005). "Análisis de seguridad de un dispositivo RFID habilitado criptográficamente" (PDF) . Actas del Simposio de seguridad de USENIX . Consultado el 21 de noviembre de 2017 .
  9. ^ ab Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). "Cómo cifrar mensajes en un dominio pequeño". Avances en criptología - CRYPTO 2009 (PDF) . Apuntes de clase en informática. Vol. 5677. págs. 286–302. doi :10.1007/978-3-642-03356-8_17. ISBN 978-3-642-03355-1. Recuperado el 21 de noviembre de 2017 .