Autor
Cualquiera que tenga el mínimo interés en sistemas de cifrado de clave pública/privada, como PGP, se habrá preguntado alguna vez que por qué son necesarios números primos muy grandes, o que cuantas parejas de claves salen de dos de esos números primos, o que como será el sistema
para que lo que se cifra con una clave se descifre solo con la otra, o que por qué es tan dificil obtener la clave privada a partir de la pública, etc.
Si alguno además se ha preocupado de leer lo que hay publicado por ahí, y no es matemático, supongo que lo habrá dado por imposible con tanto phi, numeros primos relativos, modulos, etc.
El propósito de este artículo es explicar como va esto de la manera más fácil posible, empezando desde cero y pasito a pasito.
Así veremos que no es tan difícil como parece.
Artimética modular:
Aunque el nombre asuste, es bien sencillo. Supongamos que nos ponemos a sumar o restar horas, en un reloj de esfera de 12 horas, nada de digitales. Si son las 8 y le sumamos 6 horas, nos quedan las 2. O sea, cuando pasamos de 12 empezamos por el 1.
Pues eso es aritmética modular. En este caso sería módulo 12.
Así podemos decir que 8 + 6 mod 12 = 2
La única diferencia es que en la aritmética modular incluimos el cero. Entonces en nuestro caso del reloj los números que existirían serían del 0 al 11. No habría por ejemplo el 12, porque "daría la vuelta" y pasaría a ser cero, o el 13 que pasaría a ser 1. Solo existen esos números.
Ahora en módulo 7. Nuestro universo de números sería {0,1,2,3,4,5,6}.
Si hiceramos 3*5, en los número reales sería 15, pero en módulo 7 serían 2 vueltas (7+7) y uno mas. O sea, 3*5 mod 7 = 1.
Como vemos, en realidad lo que hacemos para calcular el módulo es dividir 15 entre 7 y quedarnos con el resto, que es 1.
De esta misma forma, si dividimos 64 entre 7, nos sigue quedando que el resto es 1 (lo único que hemos hecho es "darle mas vueltas" al reloj), así que podemos decir que 64 = k*7 + 1. K nos da igual porque es el número de vueltas que le vamos a dar al reloj.
De forma genérica, si un número a (el 64) mod n (el 7) = resto (el 1), a = k*n + resto.
Bien, ahora vamos a fijarnos en este mismo ejemplo. Vemos que en mod 7, 3*5 = 1. Al igual que con los números reales, si dos números se multiplican y dan 1, es que son inversos (5 * 1/5 = 1).
Así podemos decir que 3 y 5 son inversos en módulo 7.
Hasta aquí claro? Es fácil verdad?
Seguimos,
Hay una propiedad, que os la teneis que creer, que dice que un número a tiene inversa módulo n, si no existe ningún número (excepto 1) menor que a y menor que n que los divida de forma exacta.
Esto es a lo que se llama primos relativos. 8 y 5 serían primos relativos, porque no hay ningún número que los divida, aunque 8 no sea primo. Su máximo común divisor es 1.
En el ejemplo del módulo 7, vemos que todos los números (el cero no cuenta) tienen que tener inversa, porque 7 es primo absoluto y no va a existir ningún número que lo divida.
* La inversa del 1 es el 1: 1 * 1 = 1 que dividido entre 7 es igual a cero y resto 1, (1*1 mod 7 =1)
* La inversa del 2 es el 4: 2 * 4 = 8 que dividido entre 7 es igual a 1 y de resto 0, (2*4 mod 7 = 1)
etc...
Esto también es fácil no?
Vale, vamos a entrar ahora con el temido número phi.
El número phi nos dice la cantidad de números que tienen inversa para un módulo.
Me explico, en nuestro caso, vemos que en el módulo 7 todo su conjunto de números, menos el cero, tienen inversa, porque 7 es un número primo y nos lo dice la propiedad anterior. O sea, hay 6 números (del 1 al 6) que tienen inversa, y si phi(7) nos dice la cantidad de números que tienen inversa, queda que phi(7) = 6.
De forma genérica, si n es un número primo, phi(n) = n - 1. (El menos 1 es porque no contamos con cero).
Por la misma razón, si n está formado por la multiplicación de dos números primos, n = p * q, entonces phi(n) = (p-1) * (q-1).
Generación de claves.
Ahora entramos ya en el meollo del artículo.
Para la generación de las claves pública y privadas, vamos a basarnos en phi(n).
Ahora creeros el por qué se hace esto, que luego lo entendereis.
Lo que hacemos es coger dos números primos muy muy grandes, que serán el p y q de antes, y multiplicarlos para calcular n.
Vale, ya tenemos n, lo dejamos apartado a un lado.
Calculamos el phi(n) que es (p-1)*(q-1).
Vale ya tenemos por otro lado phi(n).
Y ahora escogemos las claves.
La clave pública será un número aleatorio que sea primo relativo con phi(n). Esto es para que tenga inversa, recordad que si no hay ningún número menor que los divida es que tiene inversa. A ese númerro le llamamos e y la clave pública será la pareja (e,n).
A la inversa le llamamos d, y será la clave privada.
En este momento tenemos un número e, que sale de phi(n), un número d, que sale de phi(n) y el módulo n. Como ahora veremos, con e y n podemos cifrar y con d y n podemos descifrar, con lo que podemos tirar phi(n) a la basura.
Así que tiramos phi(n), que es el generador de nuestras claves.
Si alguien quisiera generar nuestra clave privada de nuevo, tendría que recuperar phi(n), no?
Y aquí está una de las cosas que siempre oimos, lo de la imposibilidad de factorizar.
El que quiera recuperar phi(n) para sacar la clave privada calculando la inversa de la pública, solo conoce n, no conoce p ni q. Así que tendría que empezar a dividir n entre números primos gigantes para adivinar p y q y luego poder hacer el (p-1)*(q-1) que es phi(n).
Y aquí hay dos dificultades, una es que ir dividiendo requiere muchos recursos, y otra es que saber si el número por el que divide es primo, por lo que la factorización de n (que así se llama a encontrar p y q) se vuelve un problema intratable.
Cifrar y descifrar.
1- Para cifrar, lo único que hacemos es elevar lo que queremos cifrar a e (el exponente de la clave pública).
2- Para descifrar es un poco más complicado.
Como hemos visto, las claves vienen calculadas en módulo phi(n), y nada tienen que ver a priori con n, son dos "segmentos" de números distintos.
Entonces como lo hacemos?
Hay una propiedad que dice que si multiplicamos un número a (distinto de cero) por si mismo phi(n) veces, o sea, a^phi(n), el resultado nos da 1 en módulo n.
En el ejemplo del módulo 7, donde phi(7) = 6, si multiplicamos por ejemplo el 2 por si mismo 6 veces (2^6) nos da 64 que como vimos 64 mod 7 = 1.
En esta propiedad es la que se basa todo el algoritmo RSA.
Vamos a calcular m^e (cifrar m) y luego elevarlo a d (descifralo) para ver si nos sigue quedando m.
Lo hacemos paso a paso.
* Elevar m a e y luego a d (m^(e^d)) es lo mismo que hacer m^(e*d). se multiplican los exponentes.
* D y e vienen de phi(n), y son inversas, o sea que d*e mod phi(n) = 1
* Según vimos al principio, d*e mod phi(n) = 1 es lo mismo que decir que d*e = k*phi(n) + 1.
* Resumiendo, tenemos que elevar m a phi(n), el resultado elevarlo a k y todo ello multiplicarlo luego por m otra vez. Recordad que es m elevado a k*phi(n) + 1, si aplicamos las reglas de la matemática normal podemos hacer (m^phi(n))^k * (m^1).
* Y hasta aquí hemos llegado en principio, como podemos ver, tenemos en medio a phi(n), el cual desconocemos porque lo hemos tirado al generar las claves, y sin conocerlo no podremos seguir, y no vamos a factorizar n claro. Pero entonces hacemos caso de la última propiedad, que nos permite poner phi(n) en factor de n.
* Si elevamos m a phi(n) nos da que m mod n = 1. Por lo cual sustituimos en la anterior fórmula y nos quedaría (1^k)(m^1) = m
Con lo que vemos como podemos descifrar mediante claves generadas por un módulo (phi(n)) usando otro módulo distinto, n.
Ejemplo real.
- Por un lado tenemos que n = 5 * 11.
- Y por otro lado tenemos que phi(n) = 4 * 10 = 40
- Elegimos e=7 que es primo relativo con 40.
- Calculamos su inversa módulo 40, que es 23. 7*23 = 161 = 1 mod 40. Tenemos que d = 23
Tenemos que la clave pública es (55, 7) y la privada (55, 23).
Si queremos cifrar el número 2, bastará con calcular 2^7 = 128 = 18 mod 55.
Si queremos descifrar, elevamos 18 a 23 módulo 55 y nos da 2.
Bueno, esto es todo.
Si lo leeis por encima os parecera dificil, pero si le dedicais algo de tiempo vereis lo sencillo que es.
Tened en cuenta que probablemente no haya otro documento donde se explique tan "lento", y si lo hay yo no lo he encontrado después de buscar mucho tiempo. Además estoy seguro de que muy poca gente lo entiende de forma tan clara a como aquí está espuesto, y eso es un privilegio del que ahora disponeis, así que aprovechadlo, porque es mi último artículo de criptografía en el foro.
Salu2
Postead vuestras dudas aquí, y poco a poco lo iremos acalrando más si cabe.
|
 |
Bienvenido(a), Visitante. Por favor Ingresar o Registrarse ¿Perdiste tu email de activación?. |
En línea
).
.
