El interés por transmitir un mensaje de forma que su significado quede oculto a los ojos de todo lector que no sea el destinatario es, posiblemente, tan antiguo como la propia escritura.
Hasta tiempos relativamente recientes, la clave de un emisor y de un receptor en todos los sistemas criptográficos concebibles tenían que ser iguales o cuanto menos simétricas; es decir, tenían que servir igualmente para encriptar y desencriptar. La clave era, pues, un secreto compartido entre emisor y receptor, y por tanto, el sistema criptográfico en cuestión era vulnerable, por así decirlo, por ambos lados.
Hoy en día, los algoritmos de encriptación empleados en la mayoría de las comunicaciones consisten en, al menos, dos claves: una privada, como era tradicional, y otra pública que conoce todo el mundo. Un emisor se hace con la clave pública del receptor a quien desea enviar el mensaje, y la emplea para encriptarlo. El receptor coge ahora su clave privada y la utiliza para descifrar el mensaje recibido. Ni el emisor ni el receptor han tenido que verse previamente para acordar ninguna de las claves implicadas, con lo que la seguridad del sistema se refuerza todavía más. Esta forma de encriptación absolutamente revolucionaria se conoce como de clave pública, y constituye la base de la seguridad de las redes globales de comunicación contemporáneas.
En la base del desarrollo de esta tecnología revolucionaria se encuentran las matemáticas. En efecto, la criptografía moderna descansa en dos pilares: la aritmética modular, por un lado, y la teoría de los números primos.
De forma sencilla, cuando trabajamos con la aritmética tradicional, lo hacemos en base 10, compuesta por 10 guarismos comprendidos del 0 al 9. La operación aritmética 3x5=15 se entiende perfectamente.
Supongamos que la base que utilizamos no es 10 sino 7. Los guarismos utilizados en este caso son los comprendidos entre el 0 y el 6 y la operación aritmética 3x5=21 en base 7.
Bien si lo que pretendemos es calcular el módulo 7 de 21 obtenemos 1. Esto es (kx7)+1 donde k en este caso es 2. Para el número 64 el módulo 7 también es 1 dado que 64=(kx7)+1 para k=9.
Del mismo modo que en aritmética decimal dos números son inversos cuando multiplicados entre sí el resultado es la unidad. Por poner un ejemplo 3x(1/3)=1, 3 y 1/3 son inversos, podemos decir que 3 y 5 son inversos en módulo 7.
Un número m tiene inverso en módulo n si no existe ningún número (excepto el 1) menor que n y menor que m que los divida de forma exacta. Esto es lo que se llama números primos relativos. Esto se puede demostrar fácilmente pero no es el objetivo de esta entrada.
Por ejemplo en módulo 7 todos los números (el cero no se tiene en consideración) deben tener inverso porque 7 es primo absoluto y no hay ningún número que lo divida, así:
El inverso de 1 es 1 porque 1x1=1 que dividido por 7 es cero y resto 1 (1x1 mod 7=1)
El inverso de 2 es 4 porque 2x4=8 que dividido por 7 es uno y resto 1 (2x4 mod 7=1)
El inveros de 3 es 5 porque 3x5=15 que dividido por 7 es dos y resto 1 (3x5 mod 7=1)
Según Euler existe una función Phi(n) representa la cantidad de números que tienen inversa para un módulo n dado. En nuestro ejemplo Phi(7)=6 porque todos los números (sin tener en cuenta el 0) tienen inversa, 6 en total. Para n primo Phi(n)=n-1 y si n está formado por la multiplicación de dos primos pxq, Phi(n)=Phi(pxq)=(p-1)x(q-1).
Para encriptar un número tomamos dós primos muy grandes (p y q) y los multiplicamos entre sí para obtener n.
Calculamos Phi(n)=(p-1)x(q-1).
La clave pública será un número aleatorio que sea primo relativo de Phi(n) (esto es para que tenga inversa). Denominamos s a este número y la clave pública sera la dupla (s,n). A la inversa la llamamos t y esta será la clave privada.
En este momento tenemos un número s que sale de Phi(n), un número t que sale de Phi(n) y el módulo n. Como veremos a continuación con s y n podemos cifrar y con t y n podemos descifrar, por lo que podemos prescindir de Phi(n).
Si alguien quisiera conseguir nuestra clave privada debería descifrar Phi(n) y es aquí donde radica la dificultad de averiguar p-1 y q-1 mediante la factorización de números que deben ser primos y enormes. El problema se vuelve imposible incluso para los sistemas más potentes en la actualidad.
Bien, para cifrar elevamos a k el caracter en cuestión. Para descifrar debemos creernos la siguiente igualdad igualmente demostrable. M elevado a Phi(n)=1 en módulo n y es en esta propiedad en la que se basa todo el algoritmo RSA.
En el ejemplo anterior Phi(7)=6. Para el número 2, 2 elevado a 6 es 64 que como vimos es 1 en módulo 7.
Vamos a elevar m a s para cifrarlo y luego lo elevaremos a t para descifrarlo.
Elevar m a s y luego a t es lo mismo que elevar m a (sxt).
S y t se obtienen de Phi(n) y son inversos por lo que sxt mod Phi(n)=1.
Esto es lo mismo que decir que sxt=kxPhi(n)+1.
Por lo tanto m elevado a (sxt) =(m elevado k elevado a Phi(n)) x (m elevado a 1).
M elevado a Phi(n) = m mod n =1 por lo tanto tenemos (1 elevado a k) x (m elevado 1)=m.
Podemos descifrar con claves generadas por un módulo Phi(n) usando otro módulo distinto de n.
Veamos un ejemplo numérico:
Generamos un módulo compuesto por el producto de dos primos: n=5x11.
Calculamos Phi(n) como (5-1)x(11-1)=40.
Tomamos s=7 que es primo relativo con 40.
Calculamos su inversa módulo 40 que es 23. 7x23=161=1 módulo 40.
Tenemos que t=23.
Por lo tanto clave pública (55,7) y clave privada (55,23).
Cifrar el número 2 supone 2 elevado a 7 que es 128 = 18 mod 55.
Si queremos descifrar elevamos 18 a 23 módulo 55 = 2.
No hay comentarios:
Publicar un comentario