Suponte que cojes un número (m) y lo elevas a otro número (e):
me == c mod n (n es primo)
c es el resultado de esa operacion. A partir de c, como obtienes m?? pues veamos:
sabemos que (me)d == m(e*d) vale, pues a partir de esto, si encontramos un d tal que e*d==1 mod n ya tenemos la forma de desencriptar: cd == (me)d == m(e*d) == m1 == m mod n o sea, elevamos c a d y obtenemos m... y d y e son dos números tal que e*d==1 mod n, pero no tienen por que ser iguales. Si m fuera un trozo de un mensaje que queremos encriptar, el mensaje encriptado obtenido (c) se consigue usando una clave (e) distinta de la clave que necesitamos para recuperar el mensaje original (d).
Así que en este caso, m serian los datos a enviar, {e,n} la clave pública, {d,n} la clave privada, y c lo que envias por internet a tu amigo, o sea, el mensaje encriptado! :-) Como ves, d y e no son iguales! Así que aunque tu amigo te envie e y alguien lo vea, no pasa nada, porque no podrá obtener m a partir de tener c, e y n... necesita d! :-) y como calculamos d?? pues... en este caso es fácil: e*d == 1, o sea, d == 1/e, es decir, d == 1*(e-1) == e-1 si podemos calcular el inverso de e ya tenemos d... y el inverso de d se puede calcular fácilmente porque n es primo! :-) vaya... pero... yo sólo he necesitado n y e para calcularlo... así que... cualquiera lo puede calcular! :-(
Eso no es lo que yo queria... Parece que cualquiera que pueda ver e podrá calcular d y entonces podrá descifrar mi mensaje c! :-( Eso no es lo que dije antes, verdad?? Dije que teniendo e no se tenia que poder calcular d... Así que todo lo que hemos hecho no sirve para nada?? Deberiamos tratar de arreglar un poco esto para que no sea tan fácil calcular d a partir de e! Y cómo hacemos para que sea más difícil el cálculo de d?? pues... haciendo que n no sea primo... :-) Hagamos que n sea realmente el producto de dos números primos p y q, y que nadie más que la persona que ha de recibir el mesaje conozca p y q... a partir de n sólo se puede encontrar p y q si factorizas, pero factorizar es un problema también muy difícil del que luego hablaré un poco. Ahora veamos cómo queda modificado el algoritmo que teníamos si n deja de ser primo:
como n no es primo, ya no es cierto que f(n)=n-1, y en su lugar, lo que se cumple es que f(n)=(p-1)*(q-1), así que suponiendo que c==me, hemos de conseguir un d tal que cd==m, o sea, que (me)d==m, o lo que es lo mismo, que m(e*d)==m, o sea, que e*d==f(n)+1 Y como obtenemos d?? pues fácil, e*d==1 mod f(n), así que d==1/e==e-1 mod f(n), y para calcular d ahora necesitamos pode calcular f(n)=(p-1)*(q-1), o sea, necesitamos conocer p y q, cosa que sólo conoce el receptor, ya que aunque n=p*q nadie es capaz de factorizar un número muy grande en sus dos factores, y si no te lo crees, intenta factorizar este pequeño n de sólo 20 cifras, y obtener sus dos factores p y q... ;-)
66024717357306257987
Por cierto, el hecho de que se use un n producto de sólo dos números primos es porque cuantos más factores tenga n, más fácil es de factorizar. Me explico, si n=p*q se sabe que o bien p o bien q estará por debajo de sqrt(n) (o sea, raíz cuadrada de n), en cambio si n=p*q*r lo que se sabe es que alguno de los tres factores está por debajo la raiz cúbica de n, que es un número aún menor que sqrt(n). Así que para factorizar n basta con probar a dividirlo por números más pequeños que ese límite que se conoce. Y el límite preferible es sqrt(n), que es mayor que la raiz cúbica y, por tanto, obliga a hacer más pruebas para factorizar n. Es por eso que se usa un n compuesto únicamente de dos factores primos p y q.
Otra cuestión respecto a los números primos escogidos para generar n es que han de estar muy separados, o sea, que (p-q) sea un número grande ya que sino existen ataques que permiten factorizar n. También es importante que p-1 y q-1 sean números que tengan ambos por lo menos un factor primo muy grande ya que, en caso contrario, también es muy sencillo factorizar n.
Un algoritmo que se basa en todo eso: RSA RSA es uno de estos algoritmos de clave pública que se basan en lo que os he explicado en el apartado anterior. Su funcionamiento es muy simple:
Se eligen 2 números primos, llamemosles p y q. Se calcula n=p*q. Se escoge un número e en el rango [2..n-1] que cumpla ciertas cosas. Para que el inverso de e sea difícil de calcular, e no puede valer 1 (el inverso de 1 es 1) ni tampoco puede ser múltiplo de (p-1)*(q-1), ya que calcularemos d como e-1 en el mundo "módulo (p-1)*(q-1)", y si e es múltipo de (p-1)*(q-1) tendriamos que e==0 en ese mundo, así que no podríamos calcular su inverso! :-( [dime un número que multiplicado por 0 de 1 en el mundo módulo (p-1)*(q-1), o lo que es lo mismo, dime cuanto vale 1/0 en ese mundo...].
Ahora se calcula d == e-1 mod ((p-1)*(q-1)). Como os dije antes, hay un teorema que permite calcular esta d sin problemas, sólo que necesitamos conocer p y q. La clave pública es {n,e} y la privada es {p,q,d} Así que tú le pides a tu amigo, al que quieres enviar datos, su clave pública, y él te envia {n,e} a tí... Tú ahora, codificas tu mensaje como una tira de números entre 0 y n-1 y a cada número m le aplicas c = me mod n y envias cada uno de esos números c después de aplicarles la operación. Ahora tu amigo recibe cada número y hace m = cd mod p*q (o sea, mod n ya que n=p*q) y obtiene los números originales entre 0 y n-1 que son en realidad tu mensaje desencriptado.
Supongamos que en este proceso alguien captura lo que circula por la red, o sea, {n,e} y c. Qué puede hacer?? :-? Pues realmente nada: Necesita d para poder desencriptar los datos c, y para calcular d necesita tener e y saber los 2 factores en los que se descompone n. O sino, puede intentar calcular m como la raiz e-ésima de c módulo n, pero eso también es un problema muy difícil. Así que, este sistema, en qué basa su seguridad?? pues en 2 cosas:
Si tienes n que es producto de dos primos p y q, has de factorizar para poder obtener p y q, y factorizar es un proceso muy lento (has de ir provando a hacer divisiones y mirar si te da 0 de resto o no), así que si n es lo bastante grande, necesitarás millones de años y el ordenador más potente del mundo para encontrar los dos factores p y q. Calcular la raiz e-ésima de c para obtener m en el mundo "módulo n" es algo también muy difícil, y sólo se saben calcular raices de una forma fácil si conoces la factorización de n o si n es primo.
Pues bien, este algoritmo que os he explicado es el RSA. Es un algoritmo que está patentado en USA (o sea, que para implementarlo y usarlo has de pagar derechos), pero que es libre en el resto del mundo, es decir, que si no vives en USA puedes usarlo sin problemas. Este algoritmo se lo inventaron tres señores cuyos apellidos eran Rivest, Shamir y Adleman, así que le pusieron de nombre las iniciales de sus apellidos: RSA. Como veis, eran muy poco originales! :-)
