Matemáticas, Criptografía y otras hierbas

¿Cuánto es $1+1$ ? Le preguntamos esto a alguien de primero básico y nos dirá que 2. Si me preguntas a mí, yo te respondería que depende.

Nuestra intuición nos dice que si comenzamos a sumar $1+1+1+1+\dots+1$ tantas veces como se nos ocurra, el resultado será un número cada vez mayor. Esa misma intuición también estalla si vemos escrito $1+1=0.$

Enteros módulo $n$

¿Qué pasa cuando este número representa, por ejemplo, las horas del reloj? Si a las 21:00 horas le sumas 4 horas, la respuesta será la 01:00 am. Esto ocurre porque estamos en un sistema de numeración distinto, que solo considera 24 números entre 0 y 23; luego, si sumo dos de ellos, esperaría que el resultado siguiera ahí. ¿Cómo podemos justificar que $21+4=1?$ Para formalizar este concepto matemáticamente, definimos lo siguiente:

Sean $a,b$ y $n$ números enteros, con $n\geq 1$. Decimos que $a$ es congruente a $b$ módulo n y lo denotamos por:

si $b$ es el resto de dividir $a$ por $n$.¹

Por ejemplo, $28\equiv 3 \pmod 5$ (basta dividir 28 en 5 y ver cuánto «sobra»).

En este conjunto podemos hacer todas las «operaciones básicas» que realizamos en los enteros, y al resultado obtenido aplicarle reducción modular. Por ejemplo:

Con esta notación, podemos escribir entonces que $21+4\equiv 1\pmod {24}$ sin ambigüedad. El concepto de congruencias fue introducido por el matemático alemán Carl Friedrich Gauss en su obra Disquisitiones Arithmeticae (1801) cuando tenía 24 años.

La teoría de congruencias se refiere a la «aritmética de los residuos». Gauss lo definió inicialmente de esta manera:

«Si dos enteros $a$ y $b$ están a distancias múltiplo de n,diremos que $a$ y $b$ son congruentes».

Cuando consideramos a los números enteros dotados de sus operaciones, escribimos formalmente $(\mathbb{Z},+,\cdot)$ y diremos que es un anillo.

Aquí podemos hacer de todo, salvo «dividir» (aunque esta operación en lo formal no existe). Si ahora nos movemos a congruencias módulo $n$, usaremos esta notación: $(\mathbb{Z}_n,+,\cdot)$.

Vamos un poco más allá con las operaciones. Cuando $n$ es un número primo, escribiremos $p$ . En $\mathbb{Z}_p$ se puede dividir, es decir, para todo elemento $k\in\mathbb{Z}_p$, distinto de cero, existe un cierto $\widetilde{k}\in \mathbb{Z}_p$ tal que $k\cdot\widetilde{k}\equiv 1\pmod p$. Cuando esto pasa, decimos que el conjunto con sus operaciones es un cuerpo. De hecho, $\mathbb{Z}_p$ es un cuerpo finito, pues tiene finitos elementos. Usaremos la notación $\mathbb{F}_p$ para este conjunto. Para las demostraciones y otras propiedades de esos conjuntos, ver Burton ².

Cuerpos Finitos

¿Son todos los cuerpos finitos como $\mathbb{Z}_p$ para algún $p$ primo?

Hay más cuerpos finitos que $\mathbb{Z}_p$, pero todos tienen una estructura similar.

Afirmación importante: Todo cuerpo finito tiene $p^n$ elementos, para algún $p$ primo y $n\geq 1.$Veamos cómo construirlos.

Supongamos $n=2.$ Consideramos un polinomio mónico e irreducible ³ $f(x)=x^2+f_1x+f_0$, con $f_1,f_0\in\mathbb{F}_p$. Al ser irreducible, no tiene raíces en $\mathbb{F}_p.$ Construimos el siguiente conjunto:

donde $\alpha$ verifica que$f(\alpha)=0$. Si asumimos que $p$ está fijo, es posible contar a mano cuántos elementos hay en $\mathbb{F}_p(\alpha)$. Hay exactamente $p^2$ elementos, que es la cantidad de combinaciones que se pueden hacer. ¡Lo más interesante es que este conjunto es un cuerpo!

Se puede demostrar que si cambiamos el polinomio $f(x)$ (y por ende $\alpha$), el cuerpo $\mathbb{F}_p(\beta)$ que obtenemos es el mismo desde el punto de vista del álgebra (son isomorfos⁴).

En general, podemos decir lo siguiente: si $f(x)=x^n+f_{n-1}x^{n-1}+\dots+f_1x+f_0$, con $f_i\in\mathbb{F}_p$ es un polinomio irreducible y $\beta$ verifica que $f(\beta)=0$, entonces

es un cuerpo de $p^n$ elementos. Dada la unicidad de la que hablamos antes, denotamos por $\mathbb{F}_{p^n}$ a este cuerpo.

Cuerpos Finitos en Criptografía

No se puede comprender casi ningún protocolo criptográfico sin entender antes la aritmética de cuerpos finitos.

Cifrado del César: Este es uno de los ejemplos más clásicos (y lo vimos en el post anterior!) Julio César enviaba mensajes a sus generales desplazando las letras del alfabeto. Si asignamos un número a cada letra :

podemos usar la aritmética módulo 27 (considerando la Ñ). Para cifrar una letra $x$ con una clave secreta $k$ (el número de desplazamientos), simplemente sumamos:

Para descifrar, hacemos la operación inversa. Probablemente los romanos usaron aritmética modular sin saberlo.

Cuerpos binarios y el protocolo AES: Uno de los principales cifrados simétricos utilizados hoy es AES (Advanced Encryption Standard). La unidad básica de procesamiento es el byte (8 bits). Cada byte puede identificarse con un elemento en el cuerpo finito de 256 elementos: $\mathbb{F}_{2^8}$ (también denotado como Galois Field $GF(2^8)$).

Aritmética en el cuerpo finito $\mathbb{F}_{2^8}$

Matemáticamente, el cuerpo finito $\mathbb{F}_{2^8}$ se construye de tal forma que los bytes no se tratan como números, sino como vectores. Los elementos de este cuerpo se representan mediante una base polinómica

donde cada byte $b = (b_7, b_6, \dots, b_0)$ se asocia biunívocamente con el polinomio:

Las operaciones binarias fundamentales se definen de la siguiente manera:

Adición

La adición de dos elementos $a(x), b(x) \in\mathbb{F}_{2^8}$ es la suma usual de polinomios con coeficientes en $\mathbb{F}_2$ (aritmética módulo 2):

Dado que en $\mathbb{F}_2$ la suma es equivalente a la operación lógica $\texttt{XOR}$ (1+1=0), la adición es una operación bastante rápida en un procesador.

Multiplicación

La multiplicación, denotada por $a(x) \cdot b(x)$, se define como el producto algebraico de los polinomios, al que después se reduce módulo un polinomio irreducible fijo:

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

Esta reducción modular es la que garantiza que el resultado se mantenga dentro del cuerpo, es decir, con un grado estrictamente menor a 8. Para profundizar, ver el libro ⁵

Para ilustrar esto, sean dos elementos del cuerpo definidos por:

La suma $a(x) + b(x)$ se realiza sumando los coeficientes de las potencias correspondientes módulo 2:

Observe que los términos $x\,\, y\,\, 1$ se cancelan mutuamente ($x+x=0\,\, y \,\,1+1=0$).

Para el producto, consideremos multiplicar $a(x)$ por un nuevo polinomio. $c(x) = x^4 + x + 1.$Utilizando la propiedad distributiva en el anillo:

Calculamos los términos individuales aplicando la reducción módulo $m(x)$ cuando el grado es mayor o igual a 8.

Finalmente, sumamos estos resultados parciales (módulo 2):

Los términos constantes 1+1 se anulan, al igual que otros pares internos. Este polinomio resultante corresponde a la escritura binaria $11111110$.

Veremos en otros posts que, además de los cuerpos binarios, en criptografía se utilizan cuerpos finitos $\mathbb{F}_p$ con $p$ siendo primos de 256 bits (por ejemplo, $p=2^{256}-189$). Ciertamente estos cuerpos tienen finitos elementos, ¡pero no pocos!

View this post on Instagram

1. Otra forma de definirlo es que $n \mid a-b.$ ↩︎
2. Burton, David M. Elementary Number Theory. 6th ed., McGraw-Hill, 2007 ↩︎
3. Un polinomio irreducible (sobre un cuerpo) no se puede factorizar como producto de otros de menor grado. Esto implica. Ser mónico significa que el coeficiente del término de mayor grado es 1. ↩︎
4. Que dos estructuras sean isomorfas significa que existe una función biyectiva entre ambas que preserva su estructura, en este caso, sus operaciones. En matemáticas usualmente tratamos a los objetos isomorfos como iguales, en cierto sentido. ↩︎
5. Smart, N. P. Cryptography Made Simple. Springer International Publishing (2016) ↩︎