OMAC: multiplicación en un campo finito: ¿cómo puedo calcular el polinomio correcto?

5

De El modo de operación EAX :

  

Explicamos la notación utilizada en la definición de OMAC. El valor de iL (línea 40: i un entero en {2, 4} y L ∈ {0, 1} n ) es la cadena de n bits que se obtiene al multiplicar L por la n- cadena de bits que representa el número i. La multiplicación se realiza en el campo fi nito GF (2 n ) usando un polinomio canónico para representar puntos de campo. El polinomio canónico que seleccionamos es el primer polinomio lexicográficamente entre los polinomios irreducibles de grado n que tienen un número mínimo de coeficientes distintos de cero. Para n = 128, el polinomio indicado es x 128 + x 7 + x 2 + x + 1. En ese caso, 2L = L & lt ; < 1 si el primer bit de L es 0 y 2L = (L < < 1) ⊕ 0 120 10000111 de lo contrario, donde L < < 1 significa el desplazamiento a la izquierda de L en una posición (el primer bit desaparece y un cero entra en el último bit). El valor de 4L es simplemente 2 (2L). Advertimos que para evitar ataques de canal lateral, se debe implementar la operación de duplicación en forma constante.

Básicamente, se me acaba de dar que el polinomio a usar en la multiplicación finita para n = 128 es x 128 + x 7 + x 2 + x + 1. Quiero que mi implementación sea abstracta, ya que no depende de los detalles del código cifrado que se está utilizando. Para permitir que el tamaño de bloque n sea cualquier número en lugar de codificación 128 o algunos otros, ¿cómo puedo hacer que mi software calcule el polinomio correcto?

    
pregunta jnm2 22.06.2011 - 02:33
fuente

2 respuestas

3

@ D.W. Da la respuesta importante y correcta, por supuesto. No vuelva a implementar su propia biblioteca criptográfica (o, al menos, hágalo para aprender y por diversión, pero no confíe en ello).

Ahora, para los detalles, el texto que cita en realidad proporciona todos los detalles que se necesitan, aunque de una manera matemática bastante concisa. La oración importante es esta:

  

El polinomio canónico que seleccionamos es el primer polinomio lexicográficamente entre los polinomios irreductibles de grado n que tienen un número mínimo de coeficientes distintos de cero.

Cuando calcula con polinomios binarios módulo a polinomio P de grado n , obtiene un campo finito (denotado GF (2 n ) ) solo si P es irreducible .

Hay 2n polinomios binarios de grado n ; todos se pueden escribir como:

P = p 0 + p 1 X + p 2 X 2 + .. . + p n-1 X n-1 + X n

donde cada pi es 0 o 1. Tenga en cuenta que para los polinomios binarios, calculamos todos los valores en GF (2) , así que la suma es XOR y la multiplicación es AND.

Para implementaciones más rápidas, lo preferimos cuando el número de pi distinto de cero es mínimo; también es mejor si los pi que no son cero son para valores pequeños de i . Es fácil ver que, para que P sea irreducible, p0 debe ser igual a 1, y debe haber un número impar de pi distinto a cero para i entre 1 y n-1 . Como dice la especificación de EAX, probamos todos los polinomios hasta que alcanzamos uno que es irreductible; comenzamos con los polinomios con solo un pi distinto de cero (hay n-1 de ellos) y, si ninguno es irreductible , luego probamos los polinomios con tres valores pi distintos de cero (hay (n-1) (n-2) (n-3) / 6 de ellos). Y comenzamos con aquellos donde pi son para los valores más bajos posibles i , es decir, comenzamos en 1 + X + X 2+X3+Xn .

Entonces, todo lo que tendría que hacer sería enumerar los polinomios binarios de grado n , con el número mínimo de coeficientes distintos de cero, en orden lexicográfico, y probarlos para determinar su irreductibilidad. Para esa prueba, consulte el Manual de criptografía aplicada , capítulo 4, sección 4.5.1.

    
respondido por el Thomas Pornin 16.09.2012 - 01:03
fuente
5

No. Para la mayoría de las personas, no hay razón para implementar su propia biblioteca criptográfica. Obtenga una biblioteca criptográfica existente con una implementación de CMAC (también conocida como AES-OMAC1) y use ese código. Implementarlo usted mismo es propenso a errores (con el riesgo de problemas de seguridad) y, a menudo, pierde las optimizaciones de rendimiento que se encuentran en las bibliotecas estándar. Para la mayoría de los propósitos, no hay razón para implementarlo usted mismo, y hay pocas razones para usar un cifrado que no sea AES, o en particular, un cifrado de bloque con algo más que un tamaño de bloque de 128 bits.

    
respondido por el D.W. 22.06.2011 - 04:25
fuente

Lea otras preguntas en las etiquetas