Hispanopedia Wiki
Articulo de referencia

Cifrado de Feistel

En criptografía , el cifrado Feistel (también conocido como cifrado de bloques Luby-Rackoff ) es una estructura simétrica utilizada en la construcción de cifrados de bloques , q...

Hispanopedia WikiContenido en espanolLectura gratuita

En criptografía , el cifrado Feistel (también conocido como cifrado de bloques Luby-Rackoff ) es una estructura simétrica utilizada en la construcción de cifrados de bloques , que recibe su nombre del físico y criptógrafo alemán Horst Feistel , quien realizó investigaciones pioneras mientras trabajaba para IBM ; también se le conoce comúnmente como red Feistel . Un gran número de cifrados de bloques utilizan este esquema, incluyendo el Estándar de Cifrado de Datos de EE. UU., el GOST soviético/ruso (también conocido como Magma) y los más recientes cifrados Blowfish y Twofish . 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 cifrados de bloques simétricos modernos se basan en redes Feistel. Estas redes 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 prestigio cuando el gobierno federal de EE. UU. adoptó el DES (un cifrado basado en Lucifer, con modificaciones realizadas por la NSA ) en 1976. Al igual que otros componentes del DES, la naturaleza iterativa de la construcción Feistel facilita la implementación del criptosistema en hardware (especialmente 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 mediante XOR con la otra mitad de los datos. 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 (redes SP), 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 invertible en sí misma. La función de ronda puede hacerse arbitrariamente compleja, ya que no necesita diseñarse para ser invertible. [ 2 ] : 465 [ 3 ] : 347 Además, las operaciones de cifrado y descifrado son muy similares, incluso idénticas en algunos casos, requiriendo solo una inversión del esquema de claves . Por lo tanto, el tamaño del código o circuito necesario para implementar dicho cifrado se reduce prácticamente a la mitad. A diferencia de las redes SP, las redes Feistel tampoco dependen de una caja de sustitución que podría provocar problemas de sincronización en las implementaciones de software.  

Trabajo teórico

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

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

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

Detalles de construcción

DejarF{\displaystyle \mathrm {F} }sea ​​la función redonda y deje queK0,K1,…,Knorte{\displaystyle K_{0},K_{1},\ldots ,K_{n}}sean las subclaves para las rondas0,1,…,norte{\displaystyle 0,1,\ldots ,n}respectivamente.

Entonces, el funcionamiento básico es el siguiente:

Divida el bloque de texto plano en dos partes iguales: (L0{\displaystyle L_{0}},R0{\displaystyle R_{0}}).

Por cada rondai=0,1,…,norte{\displaystyle i=0,1,\dots ,n}, calcular

Li+1=Ri,{\displaystyle L_{i+1}=R_{i},}
Ri+1=Li⊕F(Ri,Ki),{\displaystyle R_{i+1}=L_{i}\oplus \mathrm {F} (R_{i},K_{i}),}

dónde⊕{\displaystyle \oplus }significa XOR . Entonces el texto cifrado es(Rnorte+1,Lnorte+1){\displaystyle (R_{n+1},L_{n+1})}.

Descifrado de un texto cifrado(Rnorte+1,Lnorte+1){\displaystyle (R_{n+1},L_{n+1})}se logra mediante el cálculo dei=norte,norte−1,…,0{\displaystyle i=n,n-1,\ldots ,0}

Ri=Li+1,{\displaystyle R_{i}=L_{i+1},}
Li=Ri+1⊕F⁡(Li+1,Ki).{\displaystyle L_{i}=R_{i+1}\oplus \operatorname {F} (L_{i+1},K_{i}).}

Entonces(L0,R0){\displaystyle (L_{0},R_{0})}es el texto plano de nuevo.

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

Cifrado Feistel desequilibrado

Los cifrados Feistel desequilibrados utilizan una estructura modificada dondeL0{\displaystyle L_{0}}yR0{\displaystyle R_{0}}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 desequilibrado propietario para realizar la autenticación de desafío-respuesta . [ 8 ]

El algoritmo Thorp shuffle es un caso extremo de cifrado Feistel desequilibrado en el que un lado es un solo bit. Este cifrado ofrece una seguridad demostrable superior a la de un cifrado Feistel equilibrado, pero requiere más rondas. [ 9 ]

Existen redes Feistel de tipo 1, tipo 2 y tipo 3, donde la función Feistel tiene un cuarto del tamaño del bloque, pero opera un número variable de veces dentro de una ronda. [ 10 ]

Otros usos

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

Se puede utilizar un algoritmo de Feistel generalizado para crear permutaciones fuertes en dominios pequeños cuyo tamaño no sea una potencia de dos (véase el cifrado que preserva el formato ). [ 9 ]

Redes Feistel como componente de diseño

Independientemente de si el cifrado completo es un cifrado Feistel o no, las redes tipo Feistel pueden utilizarse como 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 bloques no Feistel que utiliza una función MIX tipo Feistel.

Lista de cifrados 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  ed.). 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.), Avances en criptología - CRYPTO 2003 (PDF) , Lecture Notes in Computer Science, vol. 2729, pp. 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 con seguridad demostrable y que no dependen de hipótesis no probadas». Avances en criptología — Actas de CRYPTO' 89. Notas de clase en ciencias de la computación. 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 por software . Notas de clase en informática. Vol. 1039. págs. 121–144 . doi : 10.1007/3-540-60865-6_49 . ISBN   978-3-540-60865-3Consultado 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 con capacidad criptográfica" (PDF) . Actas del Simposio de Seguridad de USENIX . Consultado el 21 de noviembre de 2017 .
  9. 1 2 Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). "Cómo cifrar mensajes en un dominio pequeño". Avances en criptología - CRYPTO 2009 (PDF) . Notas de clase en ciencias de la computación. Vol. 5677. págs. 286–302 . doi : 10.1007/978-3-642-03356-8_17 . ISBN   978-3-642-03355-1Consultado el 21 de noviembre de 2017 .
  10. ↑ Hoang, Viet; Rogaway, Philip. "Sobre redes Feistel generalizadas" (PDF) . IACR . Consultado el 6 de febrero de 2026 .