Matemáticas, Criptografía y otras hierbas

Muchos de quienes investigamos en Teoría de Números llegamos a esta área atraídos por problemas relacionados con los números primos. A pesar de tener una definición muy sencilla, muchos de los problemas más difíciles en matemáticas se relacionan con ellos.

Decimos que un número $p>1$ es primo, si los únicos números que lo dividen en forma exacta son el 1 y $p$ . En otras palabras, la única forma de factorizar un primo es así: $p=p\cdot 1.$

¿Por qué son importantes? Son los átomos de la aritmética, por el siguiente resultado:

Teorema Fundamental de la Aritmética: Todo número natural $n>1$ se puede escribir de manera única como multiplicación de potencias de primos, es decir:

Esto quiere decir que todo número compuesto (es decir, que no es primo) se puede descomponer en primos.

Se sabe que existen infinitos primos. La primera demostración conocida de este hecho es de Euclides (300 a.C) , y puedes por ejemplo verla aquí: https://youtu.be/ctC33JAV4FI?si=L01PheB_d5Fqcgn_

Hasta aquí, pareciera que estos números han sido un objeto de estudio exclusivo del campo teórico, pero esto no es así.

Algoritmo RSA

En 1978, los investigadores en ciencias de la computación y matemáticas Ronald Rivest, Adi Shamir y Leonard Adleman desarrollaron el algoritmo RSA, el cual fue el primer protocolo de cifrado de clave pública.

Los algoritmos de clave pública requieren una clave pública conocida por todos y que será utilizada para cifrar mensajes, y una clave privada que solo conoce quien recibe y descifra los mensajes.

En el algoritmo RSA hay dos componentes matemáticas claves: nuestros queridos y misteriosos números primos, y aritmética modular (de la que hablé en el post anterior). Veamos como funciona:

Supongamos que Anita quiere enviar un mensaje a Beto por un canal inseguro sin que Oscar, que es un atacante, pueda conocer el contenido del mensaje.

Generación de Clave Pública

Beto construirá una clave pública de la siguiente forma: primero, elegirá dos números primos $p$ y q y calculará $N=pq$. Después elige un número $e$ que no tenga factores comunes con $(p-1) (q-1)$ (lo que es equivalente a que $m.c.d(e,(p-1)\cdot(q-1))=1$.) Beto hará público $(N,e)$, pero mantendrá secretos los primos $p$ y $q.$ Esta clave será conocida por todos

Generación de Clave Privada

Para elegir la clave privada, Beto selecciona un número $d$, que solo él conoce y que debe verificar lo siguiente: $ed\equiv 1 \pmod {(p-1)\cdot (q-1)}$ . Esto quiere decir, que $d$ es el inverso multiplicativo de $e$ en $\mathbb{Z}_{(p-1)\cdot/q-1)}$)

Algoritmo de Cifrado

Ahora es el momento en que Anita quiere comunicarse con Beto. Supongamos que el mensaje que va a enviar está codificado como un número $M$ que no será más grande que $N$. Utilizando la clave pública de Beto, Anita cifra su mensaje $M$ calculando $C\equiv M^e \pmod N$. $C$ será el mensaje cifrado.

Algoritmo de Descifrado

Para descifrar el mensaje, Beto calcula $C^d\pmod N$ lo cual, por propiedades matemáticas que veremos después, será exactamente el mensaje $M$ enviado por Anita.

¿Qué tan seguro es RSA? 

Si el atacante Oscar quiere descifrar el mensaje, requiere el valor de la clave privada $d$, es decir, necesita conocer los primos $p$ y $q$. Como conoce $N$, le bastaría poder factorizarlo. Parece un problema sencillo, pero si $N$ es grande (más de 100 dígitos), no existe un algoritmo que lo haga en un tiempo razonable. De hecho, ni siquiera existe una fórmula que permita conocer todos los números primos, por lo cual el problema de factorización se considera un problema difícil.

RSA utiliza hoy claves de 2048 bits, las que tienen 616 dígitos. Para factorizar $N$ se requerirían $2^{90}$ operaciones.

Por qué funciona RSA: algunos argumentos matemáticos

Si eliges no creer en que el proceso de cifrado y de descifrado sí funciona, quédate, que trataé de convencerte. Si eliges creer, puedes pasar al siguiente bloque.

Se define la función de $\phi$ de Euler en un valor $n$, con $n$ un número natural, de la siguiente manera:

es decir, cuenta cuántos números hay menores a $n$, que no tienen factores comunes con $n$. Por ejemplo: $\phi(8)=4$. No es muy difícil darse cuenta de que si $p$ es primo, entonces $\phi(p)=p-1.$

Otra propiedad interesante de esta función es que es multiplicativa, en el siguiente sentido:

Cuando Beto generó su clave privada, usó esta condición: $ed\equiv 1 \pmod {(p-1)\cdot (q-1)}.$Lo que garantiza que dado $e$, exista un número $d$ que cumpla lo anterior es que justamente que $m.c.d(e,(p-1)\cdot(q-1))=1.$

El siguiente teorema es el corazón de RSA:

Teorema: Si $ed\equiv1\pmod {\phi(N)}$, entonces $a^{ed}\equiv a\pmod n$, con $N=p\cdot q$, siendo $p$ y $q$ primos.

Para la demostración y otros detalles de RSA puedes ver el texto de Stinson-Paterson. ¹

Si observas, cambiando $a$ por el mensaje $M$ en el teorema, se obtiene la validez del protocolo.

De lo paper al mundo real

Si bien este método fue propuesto en el artículo «A method for obtaining digital signatures and public-key cryptosystems» (1978) ² no fue hasta los 90 que comenzó a utilizarse en el mundo real.

¿Cómo lograr que nuestros procesadores puedan ejecutar estos algoritmos matemáticos sin errores y de manera unificada ? Aquí entran los PKCS (Public-Key Cryptography Standards).

Los PKCS son un conjunto de especificaciones diseñadas por RSA Laboratories para asegurar que diferentes implementaciones de criptografía de clave pública sean compatibles entre sí y evitar fallos de seguridad.

En particular, PKCS#1 ³ entrega las definiciones básicas y parámetros con los que se sugiere utilizar RSA.

El NIST (National Institute of Standards and Technology) en el documento «NIST Special Publication 800-56B Revision 2″ ⁴ indica que para alcanzar 112 bits de seguridad, se requiere que $N$ tenga 2048 bits. Esto quiere decir, que cada primo debe tener algo así como 1024 bits. Que un algoritmo alcance $k$-bits de seguridad quiere decir que el mejor ataque que quiebra el sistema necesita aproximadamente $2^k$ operaciones.

En la actualidad, el algoritmo RSA se utiliza en cipher suites de TLS ⁵ , cifrado de correos electrónicos ⁶, VPN’s ⁷ y certificados de autoridad (CA).

View this post on Instagram

1. Stinson, D. R., & Paterson, M. B. (2018). Cryptography: Theory and Practice (4th ed.). CRC Press. ↩︎
2. R. L. Rivest, A. Shamir, and L. Adleman. 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 2 (Feb. 1978), 120–126. ↩︎
3. https://datatracker.ietf.org/doc/html/rfc3447 ↩︎
4. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf ↩︎
5. https://datatracker.ietf.org/doc/html/rfc5289 ↩︎
6. https://ieeexplore.ieee.org/document/9821831 ↩︎
7. https://ieeexplore.ieee.org/document/10467364 ↩︎