SageMath y la paradoja RSA: precisión, velocidad y seguridad

Inicio » Software » SageMath y la paradoja RSA: precisión, velocidad y seguridad

Cuando se busca entender la llamada paradoja de RSA en SageMath, casi siempre se tropieza con dos ideas que parecen chocar: por un lado, es muy sencillo multiplicar dos primos gigantes, y por otro, es endiabladamente duro recuperar esos primos a partir de su producto. En este artículo aterrizamos esa tensión aparente y la conectamos con las ventajas prácticas de SageMath frente a un Python “vanilla”, tanto en precisión matemática como en rendimiento y herramientas de alto nivel.

Además de profundizar en la implementación de RSA con SageMath, explicaremos por qué SageMath no es “solo Python con extras”, sino una plataforma matemática completa que integra bibliotecas de primer nivel (FLINT, GMP, entre otras), ofrece tipos numéricos exactos, y resuelve operaciones algebraicas y de teoría de números con enorme naturalidad. También veremos ejemplos reales, desde aritmética modular y factorizaciones hasta generación de primos de 1024 bits, y cerraremos con una visión honesta sobre la seguridad de RSA-1024 ante GNFS y el horizonte cuántico.

Qué es SageMath y en qué se diferencia realmente de Python

Aunque ambos comparten sintaxis y espíritu, SageMath integra un ecosistema de software matemático de código abierto y lo presenta con una interfaz unificada en Python: GAP (teoría de grupos), PARI/GP (geometría aritmética), Maxima (cálculo simbólico), Singular (álgebra conmutativa) y más. La magia está en que todo esto se usa de forma coherente, sin que el usuario tenga que aprender la sintaxis de cada paquete por separado.

Un detalle aparentemente trivial ilustra muy bien la diferencia de filosofía: en Python 3, 1/3 es un flotante aproximado, mientras que en SageMath 1/3 es un racional exacto; si multiplicas 1/3 por 3, en Python obtienes 0.9999999999999999 por las limitaciones binarias del punto flotante, mientras que en SageMath el resultado es exactamente 1. Esta fidelidad a la estructura matemática evita sorpresas en álgebra simbólica y teoría de números.

También cambian los tipos: en Python, type(1/3) es float; en SageMath, 1/3 es Rational. Por su parte, 0.3333333333333333 se considera un número real aproximado (RealLiteral) en SageMath, dejando claro que se trata de una aproximación. Y ojo a los operadores: en Python el símbolo ^ es XOR a nivel de bits; en SageMath ^ es exponenciación, y x se interpreta como variable simbólica incluso si no la has definido antes.

Todo esto se traduce en que SageMath extiende Python con tipos nativos matemáticos, conserva exactitud siempre que puede y se comporta como un entorno pensado para la investigación y la docencia en matemáticas, no solo como un lenguaje multipropósito.

Funciones matemáticas nativas útiles en criptografía

En tareas criptográficas y de teoría de números, SageMath ofrece funciones listas para usar. Por ejemplo, Mod(a, b) calcula restos incluso con enteros enormes; is_prime comprueba primalidad de forma fiable; y factor descompone enteros grandes cuando es factible. Un ejemplo clásico es factorizar 1000000016000000063 en dos primos: 1000000007 y 1000000009, mientras que gcd y lcm confirman propiedades como la coprimalidad (gcd=1) y que el mcm devuelve el compuesto original.

También destaca QQbar, el “campo” de números algebraicos: QQbar(sqrt(2)) devuelve un objeto algebraico exacto, cuya representación decimal puede mostrarse con un signo de interrogación final para indicar que lo que ves en pantalla es una aproximación (por ejemplo, 1.414213562373095?). En Python estándar necesitarías combinar librerías como SymPy, math o mpmath para cubrir este espectro.

Rendimiento: por qué SageMath acelera los enteros gigantes

Más allá de la comodidad, SageMath es muy rápido con enteros de precisión arbitraria porque se apoya en bibliotecas de bajo nivel optimizadas: FLINT (para álgebra y teoría de números, escrita en C) y GMP (aritmética multiprecisión). En contraposición, Python “de fábrica” depende de int y librerías generales no pensadas específicamente para cargas de teoría de números propias de la criptografía.

Una prueba sencilla consiste en multiplicar dos potencias gigantes en Python y en SageMath, midiendo tiempos. En Python podrías tener algo como:

import time
t0 = time.time()
a = 2**10000000
b = 3**10000000
c = a * b
print("Wall time:", time.time() - t0, "seconds")

Mientras que en SageMath el programa equivalente usa walltime y el operador ^ para exponentes: el mismo cálculo tarda muchísimo menos, y la diferencia se agranda según crecen los tamaños.

t0 = walltime()
a = 2^10000000
b = 3^10000000
c = a * b
print("Wall time:", walltime(t0), "seconds")

En pruebas de referencia, se ha visto una ventaja en el orden de x16 para estos cálculos, y al aumentar la magnitud de los exponentes el margen suele crecer. La ganancia procede de implementaciones especializadas en C y ensamblador que SageMath aprovecha de forma transparente.

RSA bajo la lupa con SageMath

RSA se basa en una idea elegante: cada usuario publica una clave para cifrar y guarda en secreto otra para descifrar. La clave pública incluye n = p × q (producto de dos primos grandes) y un exponente público e; la clave privada contiene el exponente d que es el inverso modular de e respecto de φ(n). Cualquiera puede cifrar con la clave pública, pero solo quien conoce d puede recuperar el mensaje.

En la práctica, los primos de RSA se sitúan típicamente entre 1024 y 2048 bits por primo (aproximadamente 309 y 617 dígitos decimales por primo, respectivamente). El módulo n resultante en un esquema con primos de 1024 bits ronda los 2048 bits, es decir, en torno a 617 dígitos decimales. Calcular n es trivial con los primos en la mano; factorizar n después, en cambio, es lo difícil.

La “paradoja” de RSA: grande por fuera, sencillo por dentro

Desde fuera parece paradójico que un mensaje pequeño, como el número 68, se convierta en un cifrado enorme del tamaño de n. Pero no hay truco: RSA opera en el anillo de enteros módulo n, así que c = m^e mod n “vive” en ese espacio y puede ocupar todo su rango de valores. La aparente desproporción es el precio de la seguridad: se usa un “caja fuerte” gigante (n) para garantizar que el problema inverso, factorizar n, sea inviable.

Esto también explica por qué RSA no se usa para grandes volúmenes de datos: es costoso computacionalmente. Lo habitual es utilizar RSA para encapsular una clave simétrica corta y, a partir de ahí, cifrar a alta velocidad con AES u otro algoritmo simétrico moderno.

Generación de primos de 1024 bits en SageMath

Con SageMath, el proceso es directo. La función random_prime permite escoger un primo aleatorio dentro de un intervalo. Si queremos un primo de exactamente 1024 bits, fijamos el límite inferior en 2^1023 y el superior en 2^1024 − 1. Un ejemplo canónico:

p = random_prime(2^1024 - 1, 2^1023)
print("1024-bit prime (in decimal):")
print(p)
print("\nNumber of decimal digits:", len(str(p)))

Al ejecutar el procedimiento dos veces obtenemos p y q. La rutina de primalidad y la aritmética de enteros grandes se benefician de GMP y FLINT, lo que hace viable generar primos muy grandes con fiabilidad y buen rendimiento.

Implementación mínima de RSA en SageMath

Una vez tenemos p y q, implementamos RSA en pocos pasos. El esqueleto minimalista en SageMath podría ser:

n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = inverse_mod(e, phi)
m = 68
c = power_mod(m, e, n)
descifrado = power_mod(c, d, n)
print("Original:", m)
print("Cifrado:", c)
print("Descifrado:", descifrado)

La lógica es la habitual: n y e forman la clave pública; φ(n) sirve para hallar d mediante inverso modular; ciframos con c = m^e mod n y recuperamos con m = c^d mod n. En el ejemplo, m = 68 coincide con el código ASCII de la letra D, aunque en práctica se usan codificaciones y rellenos seguros.

Es normal que el cifrado c sea un entero con centenares de dígitos, porque está representado módulo n. De nuevo: el tamaño del “contenedor” es lo que proporciona la seguridad frente a la factorización.

Seguridad práctica de RSA-1024, GNFS y horizonte cuántico

Con los medios clásicos actuales, el mejor algoritmo público para factorizar n de tamaño RSA-1024 es el General Number Field Sieve (GNFS). Incluso con enormes granjas de cómputo, factorizar un módulo de 1024 bits exigiría escalas de tiempo que superan el siglo, lo que se considera impracticable en escenarios comunes.

La amenaza real a medio plazo está en la computación cuántica: un equipo cuántico grande y tolerante a fallos podría ejecutar el algoritmo de Shor para factorizar eficientemente n. A día de hoy no existe esa máquina con la escala requerida, así que se trata de un riesgo futuro. Por prudencia, se recomiendan tamaños de 2048 o 3072 bits y valorar algoritmos resistentes a cuántica para proteger información con horizonte temporal largo.

Fundamentos con Sage: divisores, congruencias y la función φ

Un repaso rápido de teoría de números ayuda a usar Sage con criterio. El máximo común divisor gcd(a, b) es el mayor entero positivo que divide a ambos; si gcd(a, b) = 1 decimos que a y b son coprimos. Las congruencias capturan la idea de tener el mismo resto módulo n: a ≡ b (mod n) si n divide a − b. En Sage, mod y las clases Mod(a, n) facilitan estos cálculos cotidianos.

La función totiente de Euler, φ(n), cuenta cuántos enteros entre 1 y n son coprimos con n. En Sage la tienes como euler_phi(n). Por ejemplo, φ(20) devuelve 8 porque exactamente 8 números en ese rango son coprimos con 20. Estos conceptos son la base de RSA, ya que d se define como el inverso modular de e en Z/φ(n)Z.

Para cargar y ejecutar pequeños guiones puedes usar load con ficheros .sage, con la misma filosofía de los scripts Python. La convención de indentar con 4 espacios se mantiene como buena práctica, y en Sage también encontrarás el anillo de enteros ZZ y utilidades como ZZ.random_element(n), que devuelve un entero pseudoaleatorio uniforme en .

Cómo escoger e y calcular d con el algoritmo de Euclides extendido

En la práctica se utiliza e = 65537 por ser primo de Fermat razonablemente pequeño, eficiente y seguro en los usos estándar. Si quisieras elegir e al azar, bastaría con tomar un entero coprimo con φ(n) (gcd(e, φ(n)) = 1) y comprobarlo. Para obtener d, aplicas el algoritmo de Euclides extendido: xgcd(x, y) devuelve (g, s, t) con g = s x + t y; de ahí se deduce el inverso modular de e módulo φ(n).

Una vez hallado d, puedes verificar rápidamente que d × e ≡ 1 (mod φ(n)) con operaciones de módulo en Sage. Esta comprobación es valiosa porque garantiza que el descifrado invertirá el proceso de cifrado correctamente.

Modular exponentiation: por qué power_mod es la opción correcta

La exponenciación modular eficiente se hace con “repeated squaring” (exponenciación binaria). Calcular mod(m^e, n) de forma ingenua es una mala idea cuando e es grande: el número intermedio m^e puede resultar inabarcable en memoria. La función power_mod(m, e, n) combina cuadrados y multiplicaciones selectivas según los bits de e, trabajando todo el rato módulo n.

Si representas un mensaje como entero m (por ejemplo, codificando letras ASCII y concatenando), cifrar es c = power_mod(m, e, n) y descifrar es m = power_mod(c, d, n). Un ejemplo de libro obtiene un cifrado concreto, como 630913632577520058415521090, y al descifrar reaparece el entero original (por ejemplo, 72697676798779827668), que luego se puede volver a mapear a caracteres.

Ejemplos ilustrativos de primalidad, factorización y aritmética

Sage hace sencilla la demostración de ideas que en criptografía damos por sentadas. Puedes pedirle que confirme que 1000000000000000000000000000000000000037 es primo. O factorizar 1000000016000000063 en 1000000007 × 1000000009. Luego, gcd de esos dos primos es 1, y lcm devuelve el compuesto original, encajando con la teoría.

Este poder de cómputo simbólico y algorítmico no es solo “comodidad”; acorta el ciclo de prueba al diseñar o entender protocolos, facilita ejercicios docentes y permite prototipar experimentos con números realistas sin salir del cuaderno de trabajo.

Notas prácticas y avisos de seguridad al implementar RSA

Hay decisiones que conviene evitar en código con fines reales. Usar el tiempo del sistema como semilla para un generador pseudoaleatorio resulta predecible y débil, y por lo tanto inadecuado para generar claves. Igualmente, manejar claves demasiado pequeñas es temerario. En demos pedagógicas se ven claves cortas y hasta elecciones de p y q como primos de Mersenne, pero no deben emplearse fuera del aula.

En implementaciones “a mano”, algunas personas dividen el mensaje en bloques para que cada bloque sea menor que n, y reimplementan funciones en lugar de tirar de librerías. A efectos didácticos está bien, pero en producción se usan codificaciones y rellenos seguros (por ejemplo, OAEP) y generadores criptográficamente seguros, con tamaños de clave y parámetros alineados a las recomendaciones actuales.

Todo encaja: SageMath destaca por su fidelidad matemática (racionales exactos, tipos simbólicos), su ecosistema integrado (GAP, PARI/GP, Maxima, Singular) y su rendimiento gracias a FLINT y GMP; y RSA, pese a la “paradoja” de ver mensajes pequeños inflarse a tamaños gigantes, vive precisamente de ese espacio numérico, donde multiplicar es fácil pero factorizar el semiprimo n es impracticable con métodos clásicos, a la vez que se vigila el avance cuántico para ajustar tamaños y, si procede, migrar a esquemas poscuánticos.