Tema 3
La criptografía moderna no depende solo de buenas ideas de ocultamiento, sino de estructuras matemáticas que permiten construir algoritmos eficientes, verificables y difíciles de atacar. Este tema presenta los conceptos mínimos que sostienen buena parte de la criptografía simétrica y asimétrica.
Cuando se estudia criptografía por primera vez, es común pensar que la seguridad depende principalmente de algoritmos y claves. Eso es cierto, pero detrás de esos algoritmos hay herramientas matemáticas muy concretas. La aritmética modular, los números primos, los inversos y la exponenciación modular aparecen una y otra vez porque permiten construir operaciones fáciles de ejecutar en un sentido y difíciles de revertir sin cierta información adicional.
La buena noticia es que no hace falta dominar matemáticas avanzadas para entender los fundamentos. Lo importante es captar las ideas operativas: cómo se comportan los números en ciertos sistemas, por qué algunas operaciones son sencillas de calcular pero difíciles de deshacer y cómo esas propiedades se convierten en seguridad práctica.
La aritmética modular consiste en operar con números considerando solo el resto de una división por un valor fijo llamado módulo. Cuando decimos "a mod n", nos referimos al resto que queda al dividir a por n.
Por ejemplo:
Este tipo de aritmética aparece en situaciones cotidianas como el reloj. Si son las 10 y avanzan 5 horas, no obtenemos 15 como hora visible, sino 3. En ese caso estamos trabajando módulo 12.
Dos números son congruentes módulo n si dejan el mismo resto al dividirlos por n. Se escribe:
a ≡ b (mod n)
Por ejemplo, 17 y 2 son congruentes módulo 5, porque ambos dejan resto 2. También 23 ≡ 11 (mod 12), porque ambos dejan resto 11 al dividirse por 12.
Esta notación es muy útil porque permite reemplazar números grandes por equivalentes más manejables sin cambiar el resultado dentro del sistema modular. Esa simplificación es esencial en cálculos criptográficos.
La suma, la resta y la multiplicación se comportan de forma muy natural en aritmética modular. Podemos operar normalmente y luego tomar el resultado módulo n.
| Operación | Ejemplo | Resultado |
|---|---|---|
| Suma | (8 + 9) mod 7 | 17 mod 7 = 3 |
| Resta | (4 - 9) mod 7 | -5 mod 7 = 2 |
| Multiplicación | (6 x 5) mod 7 | 30 mod 7 = 2 |
Estas propiedades hacen que la aritmética modular sea muy adecuada para implementaciones digitales. Es predecible, eficiente y compatible con operaciones repetidas sobre enteros grandes.
En aritmética modular, dividir no es tan directo como sumar o multiplicar. En lugar de dividir, lo que normalmente hacemos es multiplicar por un inverso modular, si ese inverso existe.
Por ejemplo, en aritmética real dividir por 3 equivale a multiplicar por 1/3. En aritmética modular, "dividir por 3 módulo n" equivale a buscar un número que, multiplicado por 3, dé 1 módulo n. Ese número es el inverso modular de 3.
No todos los números tienen inverso modular para cualquier módulo. Esa condición depende de una relación muy importante: el máximo común divisor.
El máximo común divisor, abreviado como MCD, es el mayor número que divide exactamente a dos enteros. Por ejemplo:
Cuando el MCD entre dos números es 1, decimos que son coprimos o primos entre sí. Esta propiedad es crucial porque un número a tiene inverso módulo n solo si MCD(a, n) = 1.
En otras palabras, la coprimalidad determina si ciertas operaciones criptográficas pueden realizarse de manera válida.
Un número primo es un entero mayor que 1 que solo es divisible por 1 y por sí mismo. Ejemplos: 2, 3, 5, 7, 11, 13, 17, 19.
Los números primos son centrales en criptografía porque permiten construir estructuras algebraicas con propiedades muy útiles. Muchos algoritmos asimétricos, como RSA o Diffie-Hellman, dependen de operaciones realizadas sobre módulos que involucran primos grandes.
Su importancia no está solo en ser "números especiales", sino en que la factorización y ciertas relaciones multiplicativas alrededor de ellos generan problemas difíciles para un atacante.
Los números primos aparecen porque facilitan ciertas propiedades matemáticas y, al mismo tiempo, permiten construir esquemas basados en dificultades computacionales. Por ejemplo:
Multiplicar dos números grandes es fácil para una computadora. En cambio, si solo conocemos el producto y queremos recuperar los factores primos originales, el problema puede volverse muy costoso. Esa asimetría es una de las bases de RSA.
Por ejemplo, si alguien nos dice que 15 es el producto de 3 y 5, no hay dificultad. Pero cuando el número tiene cientos o miles de bits, encontrar los factores deja de ser una tarea trivial. Esa diferencia entre operación directa y operación inversa es una idea recurrente en criptografía moderna.
El inverso modular de un número a módulo n es otro número b tal que:
a x b ≡ 1 (mod n)
Por ejemplo, el inverso de 3 módulo 7 es 5, porque:
3 x 5 = 15 ≡ 1 (mod 7)
Esto significa que 5 "deshace" a 3 dentro del sistema módulo 7. Los inversos modulares son fundamentales en RSA, en operaciones con claves y en muchos algoritmos donde hay que resolver ecuaciones dentro de un módulo.
Un número a tiene inverso módulo n si y solo si MCD(a, n) = 1. Si el número y el módulo comparten un divisor mayor que 1, entonces no existe inverso.
| Caso | MCD | ¿Tiene inverso? |
|---|---|---|
| 3 módulo 7 | 1 | Sí |
| 4 módulo 7 | 1 | Sí |
| 6 módulo 9 | 3 | No |
| 8 módulo 15 | 1 | Sí |
Para calcular el MCD de dos números se usa el algoritmo de Euclides, una técnica muy antigua y extremadamente eficiente. El algoritmo de Euclides extendido, además, permite encontrar coeficientes que expresan ese MCD como combinación lineal de los números originales.
Eso es importante porque, cuando el MCD es 1, esos coeficientes nos permiten hallar el inverso modular. Por eso el algoritmo de Euclides extendido es una herramienta práctica en muchas implementaciones criptográficas.
Una operación muy común en criptografía es elevar un número a una potencia enorme y luego tomar el resultado módulo n. Por ejemplo:
713 mod 11
Si intentáramos calcular primero la potencia completa, obtendríamos números gigantes. En la práctica, lo correcto es reducir módulo n en pasos intermedios. Eso evita crecimiento explosivo y hace viable el cálculo.
La exponenciación modular consiste justamente en calcular potencias grandes dentro de un módulo de forma eficiente. Esta operación está en el corazón de RSA, Diffie-Hellman y muchos otros esquemas.
La razón de su relevancia es doble:
La técnica habitual para implementarla es la exponenciación rápida por cuadrados sucesivos, que aprovecha la representación binaria del exponente.
Supongamos que queremos calcular 38 mod 5.
Podemos hacerlo así:
El resultado final es 1. Lo importante no es el número en sí, sino el método: vamos reduciendo en cada paso para mantener el cálculo pequeño y controlado.
Uno de los resultados más útiles en este tema es el pequeño teorema de Fermat. Dice que si p es primo y a no es múltiplo de p, entonces:
ap-1 ≡ 1 (mod p)
Este resultado tiene aplicaciones directas en simplificación de potencias, construcción de algoritmos y pruebas relacionadas con primalidad. También ayuda a entender por qué ciertos sistemas funcionan correctamente cuando se apoyan en módulos primos.
La función phi de Euler, escrita como φ(n), indica cuántos enteros positivos menores o iguales que n son coprimos con n. Es una función central en teoría de números y especialmente importante en RSA.
Por ejemplo:
Si p es primo, entonces φ(p) = p - 1. Y si p y q son primos distintos, entonces:
φ(pq) = (p - 1)(q - 1)
Esta fórmula es una pieza esencial en la generación de claves RSA.
Hasta aquí puede parecer que estamos viendo solo teoría de números, pero cada una de estas ideas tiene una aplicación concreta:
Los conceptos matemáticos de este tema no son un complemento decorativo: son el soporte real de la criptografía moderna. Entenderlos permite dejar de ver los algoritmos como cajas negras y empezar a comprender por qué funcionan, qué los hace seguros y qué condiciones necesitan para ser implementados correctamente.
En el próximo tema estudiaremos la generación de aleatoriedad, la entropía y los números pseudoaleatorios criptográficamente seguros, que son otro pilar indispensable para producir claves robustas y esquemas confiables.