RSA
Utiliza la exponenciación modular para cifrar y descifrar y basa su seguridad en la complejidad del problema
de la factorización de enteros grandes.
En febrero de 1978 Ron Rivest, Adi Shamir y Leonard Adleman, proponen un sistema de
cifra que llevará las iniciales de sus apellidos y el algoritmo se patenta como RSA.
RSA basa su fortaleza en la dificultad computacional de factorizar un número compuesto
muy grande, producto de dos primos grandes, y encontrar por tanto tales factores primos.
Ambos problemas tienen una complejidad algorítmica similar y son inabordables para la
capacidad mundial de cómputo en nuestros días cuando se trata de valores por encima de
miles de bits.
LA SEGURIDAD DEL ALGORITMO RSA
La seguridad del algoritmo RSA se basa en la dificultad computacional que conlleva
encontrar los dos factores primos de un número compuesto muy grande, resultado del
producto de éstos, donde sus primos también son números grandes. Esto es lo que
matemáticamente se conoce como el problema de la factorización entera, uno de los
problemas denominados No Polinomiales o de tipo NP, muy usados en la criptografía.
Se trata de un problema que en un sentido el cálculo es muy fácil y rápido (por
ejemplo multiplicar dos números primos) pero que en sentido contrario (por ejemplo,
encontrar esos dos factores conocido el producto) se vuelve computacionalmente
intratable a medida que la entrada es cada vez mayor. Es decir, requiere de unos
recursos informáticos excesivos y, por tanto, de un tiempo de cálculo exorbitante.
Ejemplo
Hagamos una sencilla prueba que nos permita comprender este tipo de problema.
Si te propongo que multipliques estos primos de uno, dos, tres y cuatro dígitos, no te será muy complicado
hacer esos cálculos. Eso sí, deberías usar papel y lápiz, no una calculadora:
2 x 5 = ______; 31 x 53 = ______; 401 x 599 = ______; 3.911 x 8.009 = ______
Encontrarás que los productos son:
2 x 5 = 10; 31 x 53 = 1.643; 401 x 599 = 240.199; 3.911 x 8.009 = 31.323.199.
En los dos últimos casos has tenido que trabajar bastante más porque la entrada ha aumentado de tamaño.
Sin embargo, ahora te pido que encuentres ‐otra vez sin calculadora‐ cuáles son los dos primos que dan
como producto los siguientes números compuestos de dos, cuatro, seis y ocho dígitos:
21 = p x q = ____; 2.183 = p x q = ____; 245.809 = p x q = ____; 1.379.087 = p x q= ____
verás que no lo tienes tan fácil ya en el segundo número porque lo primero que se nos ocurre
1
es hacer la Criba de Eratóstenes (ver enlace), preguntando si el número es divisible por 2, 3, 5,
7, 11, ...etc., y eso conlleva una gran cantidad de operaciones, y obviamente también tiempo.
Resultado
21 = 3 x 7 2.183 = 37 x 59 245.809 = 409 x 601 31.379.087 = 3.917 x 8.011
Aunque no sea matemáticamente exacto, se podría aceptar que la primera operación
es lineal en el sentido de que la cantidad de operaciones a realizar es directamente
proporcional al tamaño de los dos operandos; en cambio, la segunda operación es de tipo
exponencial de manera que, por ejemplo, aumentando al doble el tamaño de la entrada,
el número de cálculos a realizar no aumenta al doble sino mucho más, reflejándose esto
en una curva de tipo exponencial del tiempo de cálculo en función del tamaño de la
entrada.
En el caso de RSA y ya en el año 2012, los valores mínimos de esos dos primos debe ser
de 512 bits (unos 155 dígitos) en certificados digitales X.509 y, por tanto, su producto es
un número de 1.024 bits (unos 310 dígitos), siendo su factorización un problema
actualmente intratable.
Pasos
1. Cada usuario elige 2 números primos grandes p, q (p y q no se hacen públicos)
2. Se calcula n = pq
3. Los valores p y q no se hacen públicos.
4. Cada usuario calcula (n) = (p-1)(q-1).
5. Cada usuario elige un numero e de forma que 1 < e< (n) y que cumpla con la condición: MCD [e,
(n)] = 1.
6. Cada usuario calcula d = inv [d,(n)].
7. Se hace público n y e (ambos forman la clave publica).
8. Se guarda en secreto la clave d (que junto a n forman la clave privada).
Recuerda que hacer públicos los valores de e y n, no pone en peligro la clave privada d
puesto que para calcular d = inv [e, Φ(n)] hace falta conocer la trampa (p - 1)(q - 1), es
decir los primos p y q, y ya hemos visto que si estos primos son mayores que 500 bits
esta tarea es computacionalmente imposible a fecha actual.
Para encriptar se usa:
e
C=M mod n
Para desencriptar
d
M =C mod n