Bloque S (ciencias de la computación)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de marzo de 2015; las comprobaciones requieren 30 ediciones .

S-box (o bloque de sustitución , ing.  s-box de substitution-box ): una función en el código del programa o un sistema de hardware que toma n bits en la entrada , los convierte de acuerdo con un cierto algoritmo y devuelve m bits en el salida n y m no son necesariamente iguales [1] .

Las cajas S se utilizan en cifrados de bloque .

En electrónica, puede aplicar directamente el circuito que se muestra en la figura . En programación se crean tablas de sustitución ( tablas de sustitución, tablas de sustitución). Ambos enfoques son equivalentes, es decir, los datos cifrados en una computadora se pueden descifrar en un dispositivo electrónico y viceversa.

Un S-box se llama perfecto ( perfect s-box ) [2] si los valores de los bits de salida se calculan mediante la función doblada en función de los valores de los bits de entrada y cualquier combinación lineal de bits de salida es un función doblada de los bits de entrada.  

Implementación de software

La implementación del software del s-block funciona de la siguiente manera:

La tabla utilizada se denomina "tabla de reemplazo" o "tabla de sustitución". La mesa puede:

Por ejemplo, se utiliza una tabla fija para el cifrado DES (algoritmo), mientras que para los cifrados Blowfish y Twofish , la tabla se crea en función de la clave.

Ejemplo [3] . Considere trabajar con la tabla del quinto bloque s ( ) del cifrado DES . El quinto s-box toma 6 bits ( ) como entrada y  devuelve 4 bits (  ) como salida . Numeramos los bits de entrada de izquierda a derecha del 1 al 6. La tabla de sustitución tiene la siguiente forma:

S5 _ Valores de los bits 2, 3, 4 y 5 en la entrada
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Valores de los bits 1 y 6 en la entrada 00 0010 1100 0100 0001 0111 1010 1011 0110 1000 0101 0011 1111 1101 0000 1110 1001
01 1110 1011 0010 1100 0100 0111 1101 0001 0101 0000 1111 1010 0011 1001 1000 0110
diez 0100 0010 0001 1011 1010 1101 0111 1000 1111 1001 1100 0101 0110 0011 0000 1110
once 1011 1000 1100 0111 0001 1110 0010 1101 0110 1111 0000 1001 1010 0100 0101 0011

Deje que los bits de entrada " 0 1101 1 ". Encontremos los bits de salida .

Implementación de hardware

La implementación de hardware del bloque s (ver Fig. ) consta de los siguientes dispositivos:

Un decodificador  es un dispositivo que convierte una señal binaria de n bits en una señal base de un bit .

Por ejemplo, para el s-box que se muestra en la figura , el decodificador convierte una señal de tres bits ( ) en una de ocho bits ( ).

Sistema de conmutación  : conexiones internas que realizan intercambio de bits . Si m=n , el número de conexiones es . Cada bit de entrada se asigna a un bit de salida ubicado en el mismo bit o en un bit diferente . Si el número de entradas ny salidas m no es igual, cada salida del decodificador puede tener cero, una, dos o más conexiones. Lo mismo es cierto para las entradas del codificador.

Para el bloque S que se muestra en la figura , el número de conexiones es .

Un codificador  es un dispositivo que convierte una señal de un binario de un solo bita un binario de n bits .

Para el bloque s que se muestra en la figura , se puede compilar la siguiente tabla de sustitución (tabla de sustitución).

0 una 2 3 cuatro 5 6 7
Valor de entrada del decodificador 000 2 = 0 10 001 2 =1 10 010 2 =2 10 011 2 =3 10 100 2 = 4 10 101 2 = 5 10 110 2 =6 10 111 2 =7 10
El número de la salida del decodificador (según la figura ) en la que el valor se establece en 1 (en otras salidas el valor se establece en 0) 0 una 2 3 cuatro 5 6 7
El número de la entrada del codificador (según la figura ) en la que el valor se establece en 1 (en otras entradas el valor se establece en 0) 3 0 una cuatro 6 7 2 5
El valor a la salida del codificador. 011 2 =3 10 000 2 = 0 10 001 2 =1 10 100 2 = 4 10 110 2 =6 10 111 2 =7 10 010 2 =2 10 101 2 = 5 10

ejemplo _ Deje que el número 110 2 se alimente a las entradas del codificador que se muestra en la figura (ver figura ). Dado que la representación decimal del número binario 110 2 es 6 10 , la salida 6 del codificador tendrá el valor 1 y las otras salidas tendrán el valor 0 (ver figura ). Con la ayuda de un sistema de interruptores, el valor 1 se transferirá a la segunda entrada del decodificador (intercambio de bits). Dado que la representación binaria del número decimal 2 10 es 010 2 , las salidas del decodificador serán el número 010 2 (ver figura ).

Aplicación

Los S-boxes se utilizan en cifrados de bloque cuando se realiza el cifrado simétrico para ocultar la relación estadística entre el texto sin formato y el texto cifrado .

El análisis de un bloque s de n bits para n grande es extremadamente difícil, pero es muy difícil implementar dicho bloque en la práctica, ya que el número de conexiones posibles es grande ( ). En la práctica, el "bloque de sustitución" se utiliza como elemento de sistemas más complejos.

Las cajas S se utilizan en los siguientes cifrados:

Seguridad

Al diseñar un s-box, se debe prestar especial atención a la compilación de una "tabla de sustitución". Durante muchos años, los investigadores han estado buscando marcadores (vulnerabilidades conocidas solo por los creadores) en las tablas de sustitución de los ocho bloques s del cifrado DES . Los autores de DES contaron [4] sobre lo que se guiaron al compilar tablas de sustitución. Los resultados del criptoanálisis diferencial del cifrado DES mostraron que los números en las tablas de sustitución se eligieron cuidadosamente para aumentar la resistencia de DES a ciertos tipos de ataques. Biham y Shamir encontraron que incluso pequeños cambios en las tablas pueden debilitar significativamente DES [5] .

Notas

  1. ↑ Chandrasekaran, J. et al. Un enfoque basado en el caos para mejorar la no linealidad en el diseño s-box de criptosistemas de clave simétrica // Avances en redes y comunicaciones: primera conferencia internacional sobre informática y tecnología de la información, CCSIT 2011, Bangalore , India , 2 al 4 de enero de 2011 . Actas, parte 2. - Springer, 2011. - P. 516. - ISBN 978-3-642-17877-1 .
  2. ↑ RFC 4086 . Sección 5.3 "Uso de s‑boxes para mezclar"
  3. ↑ Buchmann Johannes A. 5. DES // Introducción a la criptografía. — Corre. 2. impresión.. - Nueva York, NY [ua]: Springer, 2001. - P. 119-120. — ISBN 0-387-95034-6 .
  4. ↑ Calderero, Don El estándar de cifrado de datos (DES) y su fortaleza frente a los ataques  //  IBM Journal of Research and Development : diario. - 1994. - vol. 38 , núm. 3 . - P. 243-250 . -doi : 10.1147 / rd.383.0243 .
  5. ↑ "Modificaciones de S-Box y su efecto en sistemas de cifrado similares a DES" de Gargiulo. Archivado el 20 de mayo de 2012 en Wayback Machine . S. 9.

Literatura

Véase también

Enlaces