El cuerpo de 256 elementos: la aritmética de los bytes en AES

Hasta la lección 8 hemos seguido a DES: una red de Feistel de 16 rondas cuya clave de 56 bits se quedó corta. Empezamos ahora la segunda mitad del relato, la de su sucesor, AES. Antes de ver cómo es AES por dentro, hay que aprender un idioma que DES no necesitaba: AES no trata los bytes como simples cadenas de 8 bits, sino como números que se pueden sumar, multiplicar y dividir. En esta lección aprendes esa aritmética. Es la de un cuerpo de 256 elementos, el mismo que usan los códigos Reed-Solomon de los códigos QR, que quizá conozcas del curso de códigos. Eso sí, los QR lo construyen con otro polinomio ($x^8+x^4+x^3+x^2+1$), así que allí las tablas de multiplicar de los bytes son distintas.

La idea

Un byte tiene 256 valores posibles. Queremos sumar dos bytes y obtener otro byte, multiplicar dos bytes y obtener otro byte, y poder dividir entre cualquier byte distinto de cero, siempre sin salirnos de 8 bits.

Con los enteros usuales no sale. Si sumas $200 + 100$ te pasas de 255. Si haces la aritmética «del reloj» módulo 256, tampoco: $2 \cdot 128 = 256 \equiv 0$, y un producto de dos números no nulos que da cero rompe la división (el $2$ no tendría inverso). Lo que necesitamos es un cuerpo con 256 elementos. Existe porque $256 = 2^8$ es potencia de un primo, y se construye igual que $\mathbb{F}_4$ y $\mathbb{F}_8$ en la lección sobre cuerpos finitos del curso de códigos: con polinomios y un polinomio irreducible.

Repaso Si no has hecho el curso de códigos

Un cuerpo es un conjunto donde puedes sumar, restar, multiplicar y dividir entre todo lo que no sea cero, con las reglas de siempre. Los racionales y los reales lo son. Existen cuerpos con un número finito de elementos, y su tamaño es siempre una potencia de un primo. El de 2 elementos son los bits $\{0,1\}$, con $1+1=0$. Los de $2^m$ elementos se construyen con polinomios de coeficientes $0$ y $1$, tomando restos al dividir entre un polinomio irreducible (uno que no se puede escribir como producto de polinomios de menor grado), igual que $\mathbb{Z}_p$ toma restos al dividir entre un primo $p$.

Un byte es un polinomio

Un byte $b_7b_6\dots b_1b_0$ se identifica con el polinomio

$$b_7x^7 + b_6x^6 + \dots + b_1x + b_0, \qquad b_i \in \{0,1\}.$$

Hay $2^8 = 256$ polinomios de grado como máximo 7 con coeficientes $0$ y $1$, uno por byte. Por ejemplo, $\texttt{57}$ en binario es $01010111$, que es el polinomio $x^6+x^4+x^2+x+1$. Y $\texttt{83}$ es $10000011$, es decir, $x^7+x+1$. Recuerda que escribimos los bytes en hexadecimal, así: $\texttt{57}$, $\texttt{83}$. A partir de aquí escribimos el hexadecimal en minúsculas, como hace FIPS 197: $\texttt{d4}$ y $\texttt{D4}$ son el mismo byte. El byte $\texttt{01}$ es el polinomio $1$ y el byte $\texttt{02}$ es el polinomio $x$.

Sumar es hacer XOR

Los coeficientes se suman módulo 2. Sumar dos polinomios es sumar coeficiente a coeficiente, sin llevadas: eso es exactamente el XOR bit a bit. Así que

$$\texttt{57} + \texttt{83} = \texttt{57} \oplus \texttt{83} = \texttt{d4}.$$

Compruébalo en binario: $01010111 \oplus 10000011 = 11010100$, que es $\texttt{d4}$. Como $1+1=0$, cada byte es su propio opuesto, así que restar es lo mismo que sumar. Esa es la operación más barata de todas, y AES la usa continuamente (la lección siguiente la llama AddRoundKey).

Multiplicar: módulo un polinomio irreducible

Multiplicar dos polinomios de grado hasta 7 da uno de grado hasta 14, que ya no cabe en un byte. Se arregla tomando el resto al dividir entre un polinomio irreducible de grado 8. AES usa

$$m(x) = x^8 + x^4 + x^3 + x + 1,$$

es decir, $100011011$ en binario, o $\texttt{11b}$ en hexadecimal. Que sea irreducible es lo que hace que sea un cuerpo (más abajo vemos por qué importa). El cuerpo resultante es

$$\mathbb{F}_{2^8} = \mathbb{F}_2[x]/(x^8+x^4+x^3+x+1).$$

En la práctica la regla de reducción es una sola: en el cuerpo, $m(x) = 0$, o sea

$$x^8 = x^4 + x^3 + x + 1 = \texttt{1b}.$$

Cada vez que aparezca un $x^8$, lo cambias por $\texttt{1b}$ (esto es un XOR con $00011011$).

xtime: multiplicar por $x$

Multiplicar por $x$ desplaza todos los coeficientes un lugar a la izquierda. Si el byte no tiene el bit 7 activo, el resultado cabe en 8 bits y ya está. Si tiene el bit 7 activo, aparece un $x^8$, que se sustituye por $\texttt{1b}$. Esta operación se llama xtime:

• se desplaza el byte un bit a la izquierda (descartando el bit que sale);
• si el bit que salió era 1, se hace XOR con $\texttt{1b}$.

Multiplicar por $\texttt{02}$ es xtime. Y como cualquier byte es una suma de potencias de $x$, toda multiplicación se reduce a xtime repetidos y XOR. Para multiplicar $a \cdot b$: escribe $b$ como suma de potencias de $x$ (sus bits), calcula $a, \ xa, \ x^2a, \dots$ con xtime y suma (XOR) los que correspondan.

El inverso

Como $m(x)$ es irreducible, todo byte distinto de $\texttt{00}$ tiene un inverso: otro byte con el que el producto es $\texttt{01}$. La razón de una línea: si un byte $a \ne 0$ y un byte $b \ne 0$ dieran producto cero, $m(x)$ dividiría a $a(x)b(x)$, y un polinomio irreducible dividiendo a un producto divide a un factor, imposible porque $a$ y $b$ tienen grado menor que 8. Sin productos nulos entre no nulos, multiplicar por $a$ es una permutación de los 255 bytes no nulos, y alguno sale $\texttt{01}$.

Si el polinomio no fuera irreducible, se rompería. Lo veremos en el ejercicio 3.

No hay una fórmula sencilla para calcular el inverso a mano. Se puede hacer con el algoritmo de Euclides para polinomios, o por tanteo, o con una tabla de 256 entradas. Aquí nos basta con comprobar un inverso dado, multiplicando. En la lección 11 verás que la operación SubBytes de AES calcula el inverso de cada byte (con $\texttt{00} \mapsto \texttt{00}$, porque el cero no tiene inverso) y le aplica después una transformación sencilla.

Ejemplo resuelto

Producto $\texttt{57} \cdot \texttt{83}$. Primero, la lista de los xtime sucesivos de $\texttt{57}$ (es decir, $\texttt{57}\cdot x^j$):

$j$	0	1	2	3	4	5	6	7
$\texttt{57}\cdot x^j$	$\texttt{57}$	$\texttt{ae}$	$\texttt{47}$	$\texttt{8e}$	$\texttt{07}$	$\texttt{0e}$	$\texttt{1c}$	$\texttt{38}$

Veamos los pasos que tienen reducción. De $\texttt{57} = 01010111$ a $\texttt{ae} = 10101110$: el bit 7 era 0, solo desplazamos. De $\texttt{ae} = 10101110$ a $\texttt{47}$: desplazamos y queda $01011100 = \texttt{5c}$ con un bit que salió (un 1), así que $\texttt{5c} \oplus \texttt{1b} = \texttt{47}$. De $\texttt{47}$ a $\texttt{8e}$: solo desplazar. De $\texttt{8e} = 10001110$ a $\texttt{07}$: desplazamos y queda $00011100 = \texttt{1c}$, salió un 1, y $\texttt{1c} \oplus \texttt{1b} = \texttt{07}$. Los tres siguientes ($\texttt{0e}$, $\texttt{1c}$, $\texttt{38}$) son solo desplazamientos.

Ahora $\texttt{83} = 10000011 = x^7 + x + 1$, así que

$$\texttt{57}\cdot\texttt{83} = \texttt{57}\cdot x^7 \oplus \texttt{57}\cdot x \oplus \texttt{57}\cdot 1 = \texttt{38} \oplus \texttt{ae} \oplus \texttt{57}.$$

Cuenta: $\texttt{38} \oplus \texttt{ae} = \texttt{96}$ y $\texttt{96} \oplus \texttt{57} = \texttt{c1}$. Resultado:

$$\texttt{57}\cdot\texttt{83} = \texttt{c1}.$$

Es el ejemplo que da el propio estándar FIPS 197. Con la misma tabla, $\texttt{13} = x^4 + x + 1$ da $\texttt{57}\cdot\texttt{13} = \texttt{07} \oplus \texttt{ae} \oplus \texttt{57} = \texttt{fe}$.

Un inverso. Afirmamos que $\texttt{53}^{-1} = \texttt{ca}$. Lo comprobamos multiplicando. Primero los xtime de $\texttt{ca}$:

$j$	0	1	2	3	4	5	6
$\texttt{ca}\cdot x^j$	$\texttt{ca}$	$\texttt{8f}$	$\texttt{05}$	$\texttt{0a}$	$\texttt{14}$	$\texttt{28}$	$\texttt{50}$

Y $\texttt{53} = 01010011 = x^6 + x^4 + x + 1$. Entonces

$$\texttt{53}\cdot\texttt{ca} = \texttt{50} \oplus \texttt{14} \oplus \texttt{8f} \oplus \texttt{ca}.$$

Agrupando, $\texttt{50} \oplus \texttt{14} = \texttt{44}$, $\texttt{8f} \oplus \texttt{ca} = \texttt{45}$ y $\texttt{44} \oplus \texttt{45} = \texttt{01}$. Efectivamente, el producto es $\texttt{01}$: $\texttt{ca}$ es el inverso de $\texttt{53}$, y se puede dividir por $\texttt{53}$ multiplicando por $\texttt{ca}$.

Ejercicios

Ejercicio 1

Calcula $\texttt{b3} \oplus \texttt{5e}$ y escribe el resultado como polinomio. Después calcula $\texttt{02}\cdot\texttt{b3}$, $\texttt{02}\cdot\texttt{80}$ y $\texttt{02}\cdot\texttt{c7}$.

Ver la solución

En binario, $\texttt{b3} = 10110011$ y $\texttt{5e} = 01011110$. Su XOR es $11101101 = \texttt{ed}$, que es el polinomio $x^7+x^6+x^5+x^3+x^2+1$.

Para $\texttt{02}\cdot\texttt{b3}$: $\texttt{b3} = 10110011$ tiene el bit 7 activo, así que desplazamos ($01100110 = \texttt{66}$) y hacemos XOR con $\texttt{1b}$: $\texttt{66}\oplus\texttt{1b} = \texttt{7d}$.

Para $\texttt{02}\cdot\texttt{80}$: $\texttt{80} = x^7$, así que $x\cdot x^7 = x^8 = \texttt{1b}$. Por el procedimiento: desplazar da $\texttt{00}$, y $\texttt{00}\oplus\texttt{1b} = \texttt{1b}$.

Para $\texttt{02}\cdot\texttt{c7}$: $\texttt{c7} = 11000111$, bit 7 activo; desplazado es $10001110 = \texttt{8e}$, y $\texttt{8e}\oplus\texttt{1b} = \texttt{95}$.

Ejercicio 2

Calcula $\texttt{03}\cdot\texttt{7a}$ (nota que $\texttt{03} = x+1$). Después comprueba que $\texttt{02}\cdot\texttt{8d} = \texttt{01}$, es decir, que $\texttt{8d}$ es el inverso de $\texttt{02}$.

Ver la solución

Como $\texttt{03} = x + 1$, tenemos $\texttt{03}\cdot a = (x\cdot a) \oplus a$. Para $a = \texttt{7a} = 01111010$: el bit 7 es 0, así que $\texttt{02}\cdot\texttt{7a}$ es solo el desplazamiento, $11110100 = \texttt{f4}$. Entonces $\texttt{03}\cdot\texttt{7a} = \texttt{f4}\oplus\texttt{7a} = \texttt{8e}$.

Para el inverso: $\texttt{8d} = 10001101$ tiene el bit 7 activo. Desplazado es $00011010 = \texttt{1a}$, y $\texttt{1a}\oplus\texttt{1b} = \texttt{01}$. Luego $\texttt{02}\cdot\texttt{8d} = \texttt{01}$ y $\texttt{02}^{-1} = \texttt{8d}$.

Ejercicio 3

Si en lugar de $x^8+x^4+x^3+x+1$ se tomara el polinomio $x^8+1$ (que en hexadecimal es $\texttt{101}$), ¿seguiría siendo un cuerpo? Demuestra que no, calculando $\texttt{03}\cdot\texttt{ff}$ con ese módulo.

Ver la solución

Se tiene $\texttt{03} = x+1$ y $\texttt{ff} = x^7+x^6+\dots+x+1$. Entonces

$$(x+1)(x^7+x^6+\dots+x+1) = x^8 + 1,$$

porque al multiplicar, todos los términos intermedios se cancelan por pares (módulo 2). Con módulo $x^8+1$ eso vale $0$. Dos bytes no nulos, $\texttt{03}$ y $\texttt{ff}$, con producto $\texttt{00}$: es lo mismo que pasaba con $2\cdot 128 \equiv 0$ módulo 256 al principio de la lección. Entonces $\texttt{03}$ no tiene inverso y no hay cuerpo. La causa es que $x^8+1 = (x+1)^8$ en $\mathbb{F}_2[x]$, que no es irreducible. Con el módulo bueno, $\texttt{03}\cdot\texttt{ff} = \texttt{1a}$, distinto de cero.

En resumen

• AES trata cada byte como un elemento del cuerpo $\mathbb{F}_{2^8} = \mathbb{F}_2[x]/(x^8+x^4+x^3+x+1)$: el byte $b_7\dots b_0$ es el polinomio $b_7x^7+\dots+b_0$, y $\texttt{02}$ es $x$.
• Sumar es XOR, y restar es lo mismo.
• Multiplicar por $\texttt{02}$ es xtime: desplazar un bit y, si se sale un 1, hacer XOR con $\texttt{1b}$. Toda multiplicación se reduce a xtime y XOR; por ejemplo, $\texttt{57}\cdot\texttt{83} = \texttt{c1}$.
• Como el polinomio es irreducible, todo byte no nulo tiene inverso; por ejemplo, $\texttt{53}^{-1} = \texttt{ca}$.

Siguiente lección: AES visto desde arriba: bloques, rondas y estado