Un campo finito, a veces también llamado campo de Galois, es un conjunto con un número finito de elementos. A grandes rasgos, un campo de Galois es un conjunto finito de elementos en los que podemos sumar, restar, multiplicar e invertir. Antes de introducir la definición de un campo, primero se necesita el concepto de una estructura algebraica más simple, un grupo.

Grupo

Un grupo es un conjunto de elementos G junto con una operación ∘ que combina dos elementos de G. Un grupo tiene las siguientes propiedades:

1. La operación de grupo ∘ es cerrada. Es decir, para todo a, b, ∈ G, sostiene que a ∘ b = c ∈ G.
2. La operación de grupo es asociativa. Es decir, a ∘ (b ∘ c) = (a ∘ b) ∘ c para todo a, b, c ∈ G.
3. Existe un elemento 1 ∈ G, llamado elemento neutro (o elemento de identidad), tal que a ∘ 1 = 1 ∘ a = a para todo a ∈ G.
4. Para cada a ∈ G existe un elemento a^-1 ∈ G, llamado inverso de a, tal que a ∘ a^-1 = a^-1 ∘ a = 1.
5. Un grupo G es conmutativo si, además, a ∘ b = b ∘ a para todo a, b ∈ G.

Para tener las cuatro operaciones aritméticas básicas (es decir, suma, resta, multiplicación, división) en una estructura, necesitamos un conjunto que contenga un grupo aditivo y un grupo multiplicativo. Esto es lo que llamamos un campo.

Campo

Un campo F es un conjunto de elementos con las siguientes propiedades:

1. Todos los elementos de F forman un grupo aditivo con la operación de grupo "+" Y el elemento neutro 0.
2. Todos los elementos de F excepto 0 forman un grupo multiplicativo con la operación de grupo x y el elemento neutro 1.
3. Cuando las dos operaciones del grupo están mezcladas, la ley de distributividad se mantiene, es decir, para todos a, b, c ∈ F: a (b + c) = (ab) + (ac).

Por ejemplo. El conjunto E de números reales es un campo con el elemento neutro 0 para el grupo aditivo y el elemento neutro 1 para el grupo multiplicativo. Cada número real a tiene un inverso aditivo, llamado -a, y cada elemento no nulo a tiene un inverso multiplicativo 1/a.

En la criptografía, casi siempre se está interesado ​​en campos con un número finito de elementos, que llamamos campos finitos o campos de Galois. El número de elementos en el campo se denomina orden o cardinalidad del campo. Es de importancia fundamental el siguiente teorema:

Un campo con orden m sólo existe si m es una potencia prima, es decir, m = pⁿ, para algún número entero positivo n y entero primo p. p es llamado característica del campo finito.

Este teorema implica que existen, por ejemplo, campos finitos con 11 elementos, o con 81 elementos (desde 81 = 3⁴) o con 256 elementos (ya que 256 = 2⁸, y 2 es un primo). Sin embargo, no hay campo finito con 12 elementos desde 12 = 2² · 3, y 12 no es, por lo tanto, una potencia prima.

Campos primos

Los ejemplos más intuitivos de campos finitos son campos de orden primo, es decir, campos con n = 1. Los elementos del campo GF(p) pueden ser representados por enteros 0, 1, ... , p-1. Las dos operaciones del campo son la adición entera modular y la multiplicación entera módulo p.

Sea p un primo. El anillo entero Z_p se denomina GF(p) y se denomina campo primo, o como campo Galois con un número primo de elementos. Todos los elementos no nulos de GF(p) tienen un inverso. La aritmética en GF(p) se hace módulo p

Para hacer la aritmética en un campo primo, se deben seguir las reglas para los anillos enteros: La adición y la multiplicación se hacen módulo p, el aditivo inverso de cualquier elemento a está dado por a + (-a) = 0 mod p, y el inverso multiplicativo de cualquier elemento no nulo a se define como a · a^-1 = 1.

Por ejemplo. Consideramos el campo finito GF(5) = {0, 1, 2, 3, 4}. Las tablas a continuación describen cómo sumar y multiplicar dos elementos cualquiera, así como el inverso aditivo y multiplicativo de los elementos del campo. Utilizando estas tablas, podemos realizar todos los cálculos en este campo sin utilizar explícitamente la reducción modular.

Tablas de las operaciones aritméticas para GF(5)

Un campo primo muy importante es GF(2), que es el campo finito más pequeño que existe. Ahora veamos las tablas de multiplicación y suma para el campo. Ejemplo. Consideremos el campo finito pequeño GF(2) = {0,1}. La aritmética se hace simplemente módulo 2, produciendo las siguientes tablas aritméticas:

Tablas de suma y multiplicación para GF(2)

Campos de extensión GF(2^m)

En AES el campo finito contiene 256 elementos y se denomina GF(2⁸). Este campo fue elegido porque cada uno de los elementos de campo puede ser representado por un byte. Para las transformaciones S-Box y MixColumn, AES trata cada byte como un elemento del campo GF(2⁸) y manipula los datos realizando la aritmética en este campo finito.

En el campo GF(2⁸), que se utiliza en AES, cada elemento A ∈ GF(2⁸) se representa así:

Observe que hay exactamente 256 = 2⁸ tales polinomios. El conjunto de estos 256 polinomios es el campo finito GF(2⁸). También es importante observar que cada polinomio puede ser simplemente almacenado en forma digital como un vector de 8 bits A = (a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀). En particular, no tenemos que almacenar los factores x⁷, x⁶, etc. Está claro que de las posiciones de los bits, a que potencia xⁱ pertenece cada coeficiente.

Referencias

1. Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.