Aritmética de campos finitos - Finite field arithmetic

En matemáticas , la aritmética de campo finito es aritmética en un campo finito (un campo que contiene un número finito de elementos ) contrariamente a la aritmética en un campo con un número infinito de elementos, como el campo de números racionales .

Hay infinitos campos finitos diferentes. Su número de elementos es necesariamente de la forma p n donde p es un número primo y n es un número entero positivo , y dos campos finitos del mismo tamaño son isomorfos . El primo p se denomina característica del campo y el entero positivo n se denomina dimensión del campo sobre su campo primo .

Los campos finitos se utilizan en una variedad de aplicaciones, incluida la teoría de codificación clásica en códigos de bloques lineales como los códigos BCH y la corrección de errores Reed-Solomon , en algoritmos de criptografía como el algoritmo de cifrado Rijndael ( AES ), en la programación de torneos y en el diseño de experimentos .

Representación polinomial efectiva

El campo finito con p n elementos se denota GF ( p n ) y también se llama campo de Galois , en honor al fundador de la teoría de campos finitos, Évariste Galois . GF ( p ), donde p es un número primo, es simplemente el anillo de números enteros módulo p . Es decir, se pueden realizar operaciones (suma, resta, multiplicación) utilizando la operación habitual con números enteros, seguida de un módulo de reducción p . Por ejemplo, en GF (5), 4 + 3 = 7 se reduce a 2 módulo 5. La división es una multiplicación por el módulo inverso p , que puede calcularse utilizando el algoritmo euclidiano extendido .

Un caso particular es GF (2), donde además es exclusiva OR (XOR) y la multiplicación es Y . Dado que el único elemento invertible es 1, la división es la función de identidad .

Los elementos de GF ( p n ) pueden representarse como polinomios de grado estrictamente menor que n sobre GF ( p ). A continuación, las operaciones se realizan en el módulo R, donde R es un polinomio irreducible de grado n sobre GF ( p ), por ejemplo, utilizando la división polinomial larga . La suma de dos polinomios P y Q se realiza como de costumbre; la multiplicación se puede hacer de la siguiente manera: calcule W = PQ como de costumbre, luego calcule el resto módulo R (existen mejores formas de hacer esto).

Hay otras representaciones de los elementos de GF ( p n ), algunas son isomorfas a la representación polinomial anterior y otras que se ven bastante diferentes (por ejemplo, usando matrices).

Cuando el primo es 2, es convencional expresar elementos de GF ( p n ) como números binarios , con cada término en un polinomio representado por un bit en la expresión binaria del elemento correspondiente. Las llaves ("{" y "}") o delimitadores similares se agregan comúnmente a los números binarios, o sus equivalentes hexadecimales, para indicar que el valor es un elemento de un campo. Por ejemplo, las siguientes son representaciones equivalentes del mismo valor en un campo finito característico 2:

Polinomio x 6 + x 4 + x + 1
Binario {01010011}
Hexadecimal {53}

Polinomios primitivos

Hay muchos polinomios irreducibles (a veces llamados polinomios reductores ) que pueden usarse para generar un campo finito, pero no todos dan lugar a la misma representación del campo.

Un polinomio mónico irreducible de grado n que tiene coeficientes en el campo finito GF ( q ), donde q = p t para algún primo p y un entero positivo t , se llama polinomio primitivo si todas sus raíces son elementos primitivos de GF ( q n ). En la representación polinomial del campo finito, esto implica que x es un elemento primitivo. Hay al menos un polinomio irreducible para el cual x es un elemento primitivo. En otras palabras, para un polinomio primitivo, las potencias de x generan todos los valores distintos de cero en el campo.

En los siguientes ejemplos, es mejor no utilizar la representación polinomial, ya que el significado de x cambia entre los ejemplos. El polinomio mónico irreducible x 8 + x 4 + x 3 + x + 1 sobre GF (2) no es primitivo. Sea λ una raíz de este polinomio (en la representación polinomial sería x ), es decir, λ 8 + λ 4 + λ 3 + λ + 1 = 0 . Ahora λ 51 = 1 , entonces λ no es un elemento primitivo de GF (2 8 ) y genera un subgrupo multiplicativo de orden 51. Considere el elemento de campo λ + 1 (en la representación polinomial esto sería x + 1). Ahora (λ + 1) 8 + (λ + 1) 4 + (λ + 1) 3 + (λ + 1) 2 + 1 = λ 8 + λ 4 + λ 3 + λ + 1 = 0 . Como todas las raíces de este polinomio primitivo son elementos primitivos, λ + 1 es un elemento primitivo de GF (2 8 ) ( (λ + 1) 255 = 1 y ninguna potencia menor lo hace). GF (2 8 ) tiene 128 generadores (ver Número de elementos primitivos ). Tener x como generador de un campo finito es beneficioso para muchas operaciones matemáticas computacionales.

Adición y sustracción

La suma y la resta se realizan sumando o restando dos de estos polinomios juntos y reduciendo el resultado al módulo de la característica.

En un campo finito con característica 2, módulo de suma 2, módulo de resta 2 y XOR son idénticos. Por lo tanto,

Polinomio ( x 6 + x 4 + x + 1) + ( x 7 + x 6 + x 3 + x ) = x 7 + x 4 + x 3 + 1
Binario {01010011} + {11001010} = {10011001}
Hexadecimal {53} + {CA} = {99}

Bajo la adición regular de polinomios, la suma contendría un término 2 x 6 . Este término se convierte en 0 x 6 y se elimina cuando la respuesta se reduce en módulo 2.

Aquí hay una tabla con la suma algebraica normal y la suma característica de 2 campos finitos de unos pocos polinomios:

p 1 p 2 p 1 + p 2 bajo ...
K [x] GF (2 n )
x 3 + x + 1 x 3 + x 2 2 x 3 + x 2 + x + 1 x 2 + x + 1
x 4 + x 2 x 6 + x 2 x 6 + x 4 + 2 x 2 x 6 + x 4
x + 1 x 2 + 1 x 2 + x + 2 x 2 + x
x 3 + x x 2 + 1 x 3 + x 2 + x + 1 x 3 + x 2 + x + 1
x 2 + x x 2 + x 2 x 2 + 2 x 0

En aplicaciones informáticas, las operaciones se simplifican para campos finitos de característica 2, también llamados campos GF (2 n ) Galois , lo que hace que estos campos sean opciones especialmente populares para las aplicaciones.

Multiplicación

La multiplicación en un campo finito es un módulo de multiplicación, un polinomio reductor irreducible que se utiliza para definir el campo finito. (Es decir, es una multiplicación seguida de una división usando el polinomio reductor como divisor; el resto es el producto). El símbolo "•" se puede usar para denotar la multiplicación en un campo finito.

Campo finito de Rijndael (AES)

Rijndael (estandarizado como AES) utiliza el campo finito característico 2 con 256 elementos, que también se puede llamar el campo de Galois GF (2 8 ). Emplea el siguiente polinomio reductor para la multiplicación:

x 8 + x 4 + x 3 + x + 1.

Por ejemplo, {53} • {CA} = {01} en el campo de Rijndael porque

( x 6 + x 4 + x + 1) ( x 7 + x 6 + x 3 + x )
= ( x 13 + x 12 + x 9 + x 7 ) + ( x 11 + x 10 + x 7 + x 5 ) + ( x 8 + x 7 + x 4 + x 2 ) + ( x 7 + x 6 + x 3 + x )
= x 13 + x 12 + x 9 + x 11 + x 10 + x 5 + x 8 + x 4 + x 2 + x 6 + x 3 + x
= x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x 2 + x

y

x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x 2 + x mod x 8 + x 4 + x 3 + x 1 + 1
= (11111101111110 mod 100011011)
= {3F7E mod 11B} = {01}
= 1 (decimal)

Esto último se puede demostrar mediante la división larga (que se muestra usando notación binaria, ya que se adapta bien a la tarea. Observe que en el ejemplo se aplica OR exclusivo y no resta aritmética, como se podría usar en la división larga de la escuela primaria):

                        
          11111101111110 (mod) 100011011
         ^100011011     
          01110000011110
          ^100011011    
           0110110101110
           ^100011011   
            010101110110
            ^100011011  
             00100011010
              ^100011011  
               000000001

(Los elementos {53} y {CA} son inversos multiplicativos entre sí, ya que su producto es 1 ).

La multiplicación en este campo finito particular también se puede hacer usando una versión modificada del " algoritmo del campesino ". Cada polinomio se representa utilizando la misma notación binaria anterior. Ocho bits son suficientes porque solo los grados 0 a 7 son posibles en los términos de cada polinomio (reducido).

Este algoritmo utiliza tres variables (en el sentido de la programación informática), cada una con una representación de ocho bits. una y b se inicializan con los multiplicandos; p acumula el producto y debe inicializarse a 0.

Al comienzo y al final del algoritmo, y al comienzo y al final de cada iteración, este invariante es verdadero: a b + p es el producto. Obviamente, esto es cierto cuando se inicia el algoritmo. Cuando el algoritmo termina, una o b será cero por lo que p contendrá el producto.

  • Ejecute el siguiente ciclo ocho veces (una vez por bit). Está bien que parar cuando una o b es cero antes de una iteración:
    1. Si se establece el bit más a la derecha de b , O exclusivo el producto p por el valor de a . Esta es la suma de polinomios.
    2. Mueva b un bit a la derecha, descartando el bit más a la derecha y haciendo que el bit más a la izquierda tenga un valor de cero. Esto divide el polinomio por x , descartando el término x 0 .
    3. Realice un seguimiento de si el bit más a la izquierda de a está establecido en uno y llame a este valor de acarreo .
    4. Mueva un bit a la izquierda, descartando el bit más a la izquierda y haciendo que el nuevo bit más a la derecha sea cero. Esto multiplica el polinomio por x , pero aún debemos tener en cuenta el acarreo que representa el coeficiente de x 7 .
    5. Si acarreo tenía un valor de uno, exclusiva o una con el número hexadecimal 0x1b(00011011 en binario). 0x1bcorresponde al polinomio irreducible con el término alto eliminado. Conceptualmente, el término alto del polinomio irreducible y acarreo suman módulo 2 a 0.
  • p ahora tiene el producto

Este algoritmo generaliza fácilmente a la multiplicación sobre otros campos de la característica 2, el cambio de las longitudes de un , b , y p y el valor 0x1bapropiadamente.

Multiplicación inversa

Consulte también el algoritmo de inversión Itoh-Tsujii .

El inverso multiplicativo para un elemento a de un campo finito se puede calcular de diferentes formas:

  • Multiplicando a por cada número en el campo hasta que el producto sea uno. Esta es una búsqueda de fuerza bruta .
  • Dado que los elementos distintos de cero de GF ( p n ) forman un grupo finito con respecto a la multiplicación, a p n −1 = 1 (para a ≠ 0 ), por lo tanto, la inversa de a es a p n −2 .
  • Utilizando el algoritmo euclidiano extendido .
  • Haciendo tablas de logaritmo y exponenciación para el campo finito, restando el logaritmo de p n −1 y exponencializando el resultado.
  • Haciendo una tabla inversa multiplicativa modular para el campo finito y haciendo una búsqueda.
  • Mapeando a un campo compuesto donde la inversión es más simple y mapeando hacia atrás.
  • Construyendo un número entero especial (en el caso de un campo finito de orden primo) o un polinomio especial (en el caso de un campo finito de orden no primo) y dividiéndolo por a .

Trucos de implementación

Tablas basadas en generadores

Al desarrollar algoritmos para el cálculo de campo de Galois en campos pequeños de Galois, un enfoque común de optimización del rendimiento es encontrar un generador gy usar la identidad:

para implementar la multiplicación como una secuencia de búsquedas en tablas para las funciones log g ( a ) y g y y una operación de suma de enteros. Esto explota la propiedad de que todo campo finito contiene generadores. En el ejemplo del campo de Rijndael, el polinomio x + 1 (o {03}) es uno de esos generadores. Una condición necesaria pero no suficiente para que un polinomio sea un generador es que sea irreductible .

Una aplicación deberá prueba para el caso especial de una o b es cero, ya que el producto, también será cero.

Esta misma estrategia se puede utilizar para determinar el inverso multiplicativo con la identidad:

Aquí, el orden del generador, | g |, es el número de elementos distintos de cero del campo. En el caso de GF (2 8 ) esto es 2 8 - 1 = 255 . Es decir, para el ejemplo de Rijndael: (x + 1) 255 = 1 . Entonces esto se puede realizar con dos tablas de búsqueda y una resta de números enteros. El uso de esta idea para exponenciación también obtiene beneficios:

Esto requiere dos búsquedas en la tabla, una multiplicación de enteros y una operación de módulo de enteros. De nuevo, se debe realizar una prueba para el caso especial a = 0.

Sin embargo, en las implementaciones criptográficas, se debe tener cuidado con tales implementaciones ya que la arquitectura de caché de muchos microprocesadores conduce a una sincronización variable para el acceso a la memoria. Esto puede conducir a implementaciones que son vulnerables a un ataque de tiempo .

Multiplicar sin llevar

Para los campos binarios GF (2 ^ n ), la multiplicación de campos se puede implementar usando una multiplicación sin acarreo como el conjunto de instrucciones CLMUL , lo cual es bueno para n <= 64. Una multiplicación usa una multiplicación sin acarreo para producir un producto (hasta 2 n - 1 bits), otra multiplicación sin acarreo de un inverso precalculado del polinomio de campo para producir un cociente = ⌊ producto / (polinomio de campo) ⌋, una multiplicación del cociente por el polinomio de campo, luego un xor: resultado = producto ⊕ ( (polinomio de campo) ⌊ producto / (polinomio de campo) ⌋). Los últimos 3 pasos (pclmulqdq, pclmulqdq, xor) se utilizan en el paso de reducción de Barrett para un cálculo rápido de CRC utilizando la instrucción X86 pclmulqdq.

Campo compuesto

Cuando k es un número compuesto , existirán isomorfismos desde un campo binario GF (2 k ) a un campo de extensión de uno de sus subcampos, es decir, GF ((2 m ) n ) donde k = m n . La utilización de uno de estos isomorfismos puede simplificar las consideraciones matemáticas ya que el grado de extensión es menor con la compensación de que los elementos ahora están representados en un subcampo más grande. Para reducir el recuento de puertas para las implementaciones de hardware, el proceso puede involucrar múltiples anidamientos, como el mapeo de GF (2 8 ) a GF (((2 2 ) 2 ) 2 ). Existe una restricción de implementación, las operaciones en las dos representaciones deben ser compatibles, por lo que se necesita un uso explícito del isomorfismo. Más precisamente, el isomorfismo será denotado por map (), es una biyección que mapea un elemento de GF (2 k ) a GF ((2 m ) n ), satisfaciendo: map (a + b) = map (a) + mapa (b) y mapa (ab) = mapa (a) mapa (b), donde las operaciones del lado izquierdo ocurren en GF (2 k ) antes del mapeo y las operaciones del lado derecho ocurren en GF ((2 m ) n ) después del mapeo. El isomorfismo generalmente se implementa con una matriz de k filas por k bits, que se utiliza para realizar una multiplicación matricial sobre GF (2) de un elemento de GF (2 k ) tratado como una matriz de k filas por 1 bit. Defina α como un elemento primitivo de GF (2 k ) y β como un elemento primitivo de GF ((2 m ) n ). Entonces β j  = mapa (α j ) y α j  = mapa −1j ). Los valores de α y β determinan la matriz de mapeo y su inversa. Dado que las matemáticas reales se realizan en GF ((2 m ) n ), el polinomio reductor para GF ((2 m ) n ) suele ser primitivo y β = x en GF ((2 m ) n ). Para cumplir la restricción de compatibilidad para la suma y la multiplicación, se realiza una búsqueda para elegir cualquier elemento primitivo α de GF (2 k ) que cumpla la restricción. En el caso de que el polinomio reductor para GF (2 k ) sea primitivo, es posible un método de mapeo alternativo: los coeficientes de 1 bit del polinomio reductor para GF (2 k ) se interpretan como m elementos de bit 0 o 1 de GF (2 m ), y habrá m factores primitivos de grado n , cualquiera de los cuales puede usarse como polinomio reductor para GF ((2 m ) n ). El mapeo a un campo compuesto se puede generalizar para mapear GF ( p k ) a un campo compuesto como GF (( p m ) n ), para p un número primo mayor que 2, pero estos campos no se usan comúnmente en la práctica.

Ejemplos de programas

Ejemplo de programación en C

Aquí hay un código C que sumará y multiplicará números en el campo finito característico 2 de orden 28 , usado por ejemplo por el algoritmo de Rijndael o Reed-Solomon, usando el algoritmo de multiplicación campesina rusa :

/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the polynomial x^8 + x^4 + x^3 + x + 1 = 0
 * using the Russian Peasant Multiplication algorithm
 * (the other way being to do carry-less multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* the product of the multiplication */
	while (a && b) {
            if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
                p ^= a; /* since we're in GF(2^m), addition is an XOR */

            if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
                a = (a << 1) ^ 0x11b; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
            else
                a <<= 1; /* equivalent to a*2 */
            b >>= 1; /* equivalent to b // 2 */
	}
	return p;
}

Este ejemplo tiene pérdidas de canal lateral de predicción de caché, temporización y ramificación , y no es adecuado para su uso en criptografía.

Ejemplo de programación D

Este programa D multiplicará números en el campo finito de Rijndael y generará una imagen PGM :

/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}

Este ejemplo no utiliza ninguna rama ni búsqueda de tablas para evitar canales laterales y, por lo tanto, es adecuado para su uso en criptografía.

Ver también

Referencias

Fuentes

enlaces externos