Caja S Rijndael - Rijndael S-box

El S-box de Rijndael es un cuadro de sustitución ( tabla de búsqueda ) que se utiliza en el cifrado de Rijndael, en el que se basa el algoritmo criptográfico Advanced Encryption Standard (AES) .

Adelante S-box

El S-box asigna una entrada de 8 bits, c , a una salida de 8 bits, s = S ( c ) . Tanto la entrada como la salida se interpretan como polinomios sobre GF (2) . Primero, la entrada se asigna a su inverso multiplicativo en GF (2 ⁸ ) = GF (2) [ x ] / ( x ⁸ + x ⁴ + x ³ + x + 1) , el campo finito de Rijndael . El cero, como identidad, se asigna a sí mismo. Esta transformación se conoce como Nyberg S-box en honor a su inventora Kaisa Nyberg . Luego, el inverso multiplicativo se transforma utilizando la siguiente transformación afín :

${\ Displaystyle {\ begin {bmatrix} s_ {0} \\ s_ {1} \\ s_ {2} \\ s_ {3} \\ s_ {4} \\ s_ {5} \\ s_ {6} \ \ s_ {7} \ end {bmatrix}} = {\ begin {bmatrix} 1 y 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 y 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 y 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 y 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 y 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 y 0 y 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 y 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \ end {bmatrix}} {\ begin { bmatrix} b_ {0} \\ b_ {1} \\ b_ {2} \\ b_ {3} \\ b_ {4} \\ b_ {5} \\ b_ {6} \\ b_ {7} \ end {bmatrix}} + {\ begin {bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \ end {bmatrix}}}$

donde [ s ₇ ,…, s ₀ ] es la salida de la caja S y [ b ₇ ,…, b ₀ ] es el inverso multiplicativo como vector.

Esta transformación afín es la suma de múltiples rotaciones del byte como vector, donde la suma es la operación XOR:

${\ Displaystyle s = b \ oplus (b \ lll 1) \ oplus (b \ lll 2) \ oplus (b \ lll 3) \ oplus (b \ lll 4) \ oplus 63_ {16}}$

donde b representa el inverso multiplicativo, es el operador XOR bit a bit , es un desplazamiento circular a bit a la izquierda y la constante 63 ₁₆ = 01100011 ₂ se da en hexadecimal . ${\ Displaystyle \ oplus}$${\ Displaystyle \ lll}$

Una formulación equivalente de la transformación afín es

${\ Displaystyle s_ {i} = b_ {i} \ oplus b _ {(i + 4) \ operatorname {mod} 8} \ oplus b _ {(i + 5) \ operatorname {mod} 8} \ oplus b _ {(i +6) \ operatorname {mod} 8} \ oplus b _ {(i + 7) \ operatorname {mod} 8} \ oplus c_ {i}}$

donde s , b , y c son 8 matrices de bits, c es 01100011 ₂ , y los subíndices indican una referencia al bit indexada.

Otro equivalente es:

${\ Displaystyle s = \ left (b \ times 31_ {10} \ mod {257_ {10}} \ right) \ oplus 99_ {10}}$

donde es la multiplicación de polinomios de y se toma como matrices de bits. ${\ Displaystyle \ times}$${\ Displaystyle b}$${\ Displaystyle 31_ {10}}$

Caja S inversa

La caja S inversa es simplemente la caja S que se ejecuta en reversa. Por ejemplo, la caja S inversa de b8 ₁₆ es 9a ₁₆ . Se calcula calculando primero la transformación inversa afín del valor de entrada, seguida de la inversa multiplicativa. La transformación afín inversa es la siguiente:

${\ Displaystyle {\ begin {bmatrix} b_ {0} \\ b_ {1} \\ b_ {2} \\ b_ {3} \\ b_ {4} \\ b_ {5} \\ b_ {6} \ \ b_ {7} \ end {bmatrix}} = {\ begin {bmatrix} 0 & 0 & 1 y 0 y 0 y 1 y 0 y 1 \\ 1 y 0 y 0 y 1 y 0 y 0 y 1 y 0 \\ 0 & 1 y 0 y 0 y 1 y 0 y 0 y 1 \\ 1 y 0 y 1 y 0 y 0 y 1 y 0 y 0 \\ 0 & 1 y 0 y 1 y 0 y 0 y 1 y 0 \\ 0 & 0 & 1 y 0 y 1 y 0 y 0 y 1 \\ 1 y 0 y 0 y 1 y 0 y 1 y 0 y 0 \\ 0 & 1 y 0 y 0 y 1 y 0 y 1 y 0 \ end {bmatrix}} {\ begin { bmatrix} s_ {0} \\ s_ {1} \\ s_ {2} \\ s_ {3} \\ s_ {4} \\ s_ {5} \\ s_ {6} \\ s_ {7} \ end {bmatrix}} + {\ begin {bmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \ end {bmatrix}}}$

La transformación afín inversa también representa la suma de múltiples rotaciones del byte como un vector, donde la suma es la operación XOR:

${\ Displaystyle b = (s \ lll 1) \ oplus (s \ lll 3) \ oplus (s \ lll 6) \ oplus 5_ {16}}$

donde es el operador XOR bit a bit , es un desplazamiento circular a bit a la izquierda , y la constante 5 ₁₆ = 00000101 ₂ se da en hexadecimal .${\ Displaystyle \ oplus}$${\ Displaystyle \ lll}$

Criterio de diseño

El S-box de Rijndael fue diseñado específicamente para ser resistente al criptoanálisis diferencial y lineal . Esto se hizo minimizando la correlación entre las transformaciones lineales de los bits de entrada / salida y, al mismo tiempo, minimizando la probabilidad de propagación de la diferencia.

La caja S de Rijndael se puede reemplazar en el cifrado de Rijndael, lo que derrota la sospecha de una puerta trasera incorporada en el cifrado que explota una caja S estática. Los autores afirman que la estructura de cifrado de Rijndael debería proporcionar suficiente resistencia contra el criptoanálisis lineal y diferencial si se utiliza una caja S con propiedades de propagación de correlación / diferencia "promedio".

Implementación de ejemplo en lenguaje C

El siguiente código C calcula la caja S:

#include <stdint.h>

#define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))

void initialize_aes_sbox(uint8_t sbox[256]) {
	uint8_t p = 1, q = 1;
	
	/* loop invariant: p * q == 1 in the Galois field */
	do {
		/* multiply p by 3 */
		p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);

		/* divide q by 3 (equals multiplication by 0xf6) */
		q ^= q << 1;
		q ^= q << 2;
		q ^= q << 4;
		q ^= q & 0x80 ? 0x09 : 0;

		/* compute the affine transformation */
		uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);

		sbox[p] = xformed ^ 0x63;
	} while (p != 1);

	/* 0 is a special case since it has no inverse */
	sbox[0] = 0x63;
}

Referencias