En esta entrada nos enfocaremos en el algoritmo RSA y su funcionamiento, no en los elementos que conforman y dan seguridad a una infraestructura de llave pública.
Desde tiempos remotos el hombre ha tenido necesidad de enviar mensajes de forma tal que si el mensajero era interceptado la información que portaba no corriera el peligro de caer en manos del enemigo. Uno de los primeros métodos documentados es el cifrado César, utilizado por los romanos, que consistía en un sistema de sustitución.
Hasta la segunda mitad del siglo XX, solo estaban disponibles los sistemas simétricos, donde se utiliza la misma clave para cifrar y descifrar los mensajes. Las dos partes que se comunican han de ponerse de acuerdo de antemano sobre la clave a usar. Una vez que ambas partes tienen acceso a esta clave, el remitente cifra un mensaje usando la clave, lo envía al destinatario, y este lo descifra con la misma clave. Algunos ejemplos de algoritmos simétricos modernos son: DES, 3DES, RC5, AES, Blowfish e IDEA.
Aunque estos algoritmos son extremadamente robustos y eficientes desde el punto de vista computacional, presentan un inconveniente crucial, la distribución de claves.
Pongamos por ejemplo un ministerio de relaciones exteriores, que tiene necesidad de enviar mensajes cifrados a sus representaciones en más de 100 países. Necesariamente, estos mensajes deberán enviarse mediante canales no seguros, ya que difícilmente puedan costear la instalación de una fibra óptica entre las representaciones.
Cada sede deberá tener su propia clave, o conjunto de claves, las que deben llegar a dicho lugar, garantizando que no fueron interceptadas (lo que puede llegar a ser difícil). La situación se complica exponencialmente si existe la necesidad de que las representaciones se comuniquen entre ellas, requiriendo la generación de una clave entre cada par.
Para ilustrar el problema, imaginemos que necesitamos generar todas las claves necesarias para la comunicación de 100 sedes, de manera que puedan comunicarse entre ellas y que la divulgación de una clave no afecte al resto. El número de claves a generar se calcula a partir de la fórmula n(n-1)/2, dando un total de 4950 claves.
La criptografía asimétrica soluciona el problema anterior, requiriendo solamente un par de claves, una privada y otra pública para cada usuario del sistema.
Según el profesor Andrew S. Tanenbaum, cualquier escrito sobre criptografía que se precie, deberá utilizar como emisor y receptor imaginarios a Alice y Bob, por lo que en honor a la tradición los utilizaremos como ejemplo.
 |
| Alice y Bob |
Bob quiere enviar un mensaje cifrado a Alice. Bob busca, en Internet por ejemplo, la clave pública de Alice y la utiliza para cifrar el mensaje, aquí surgen las confusiones, pues la pública es para cifrar. En este punto, Bob tiene un mensaje cifrado, que envía, y Alice es la única en todo el mundo que lo puede leer, ya que solo puede descifrarse con la clave privada de ella. Dicha clave debe protegerse y no revelarse.
RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente.
Estamos acostumbrados a escuchar que la computación cambia vertiginosamente y no es posible seguir el ritmo, y sin embargo, aquí estamos, tratando un algoritmo elaborado hace 42 años que es el estándar de la industria.
Los autores del RSA, en su artículo “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” definen su funcionamiento como:
Dada una clave pública de cifrado (e,n), siendo e y n un par de enteros positivos, se representa el mensaje como un entero entre 0 y n-1, los mensajes grandes se dividen en bloques de este tipo. Se cifra el mensaje elevándolo a la potencia e módulo n. El mensaje cifrado es el resto de la división Me dividido entre n.
C = E(M) = Me (mod n)
Para descifrar el texto, se eleva a otra potencia d, de nuevo módulo n.
D(C) = Cd (mod n)
La clave de cifrado es el par de enteros positivos (e,n) y la de descifrado es (d,n). Se hace pública la clave para cifrar (e,n) y solo puede ser descifrado mediante la clave (d,n), la cual se debe proteger.
Las claves de cifrado y descifrado se calculan de la siguiente manera:
n = p . q
siendo p y q dos números primos grandes (en el orden de las 200 cifras) de longitud similar.
Se escoge d de manera que sea un entero grande y primo relativo de (p – 1) . (q – 1), de manera que se satisfaga:
mcd(d,(p – 1) . (q – 1)) = 1
El entero e es finalmente calculado de p, q y d que sea el multiplicador modular inverso de d, módulo (p – 1) . (q – 1), teniendo:
e . d = 1 (mod (p – 1) . (q – 1))
Las funciones de cifrado y descifrado son permutaciones inversas, propiedad utilizada en la firma digital.
Factorizar n permitiría a un criptoanalista “romper” el cifrado, estos factores le posibilitaría conocer los elementos que componen las claves. Afortunadamente, factorizar un número es un problema más complejo que determinar si es primo o compuesto.
Ejemplo práctico (tomado de Wikipedia):
| p = 61 | 1º nº primo privado |
| q = 53 | 2º nº primo privado |
| n = p·q = 3233 | producto p×q |
| e = 17 | exponente público |
| d = 2753 | exponente privado |
La clave pública es (e,n), la privada es (d,n). Donde m es el mensaje a cifrar, la función de cifrado es:
encryp(m) = me (mod n) = m17 (mod 3233)
La función de descifrado para un mensaje c sería:
decrypt(c) = cd (mod n) = c2753 (mod 3233)
Dado el mensaje en claro 123, se calcula:
encryp(123) = 12317 (mod 3233) = 855
El mensaje cifrado sería 855, para descifrarlo aplicaríamos la función de descifrado:
decrypt(855) = 8552753 (mod 3233) = 123
La fuerza del algoritmo radica en que no existen métodos eficientes para factorizar enteros grandes en factores primos, es decir, aunque es posible romper el cifrado, el tiempo necesario lo hace inviable. Por ejemplo, si n tiene 256 bits o menos, puede ser factorizado en una computadora personal en unas horas. Con una clave de 512 bits, son necesarias cientos de computadoras.
En la actualidad está desaconsejado utilizar 1024 bits, se recomienda utilizar valores de n de 2048 bits o mayores.
La fuerza del algoritmo radica en la generación de claves, a raíz de esto, la Agencia de Seguridad Nacional de los Estados Unidos (NSA) ha buscado la manera de burlar su seguridad, debilitando el mecanismo de generación de claves, de manera que le fuera posible romper los cifrados. Los documentos filtrados por Edward Snowden revelaron las acciones llevadas a cabo para debilitar el algoritmo. Enlace.
RSA es mucho más lento que DES y otros criptosistemas simétricos, por lo que generalmente es utilizado para transmitir las claves de estos últimos y luego la comunicación continúa utilizando el cifrado más rápido.
En el caso de la firma digital, se busca garantizar la integridad, autenticidad y no repudio de documentos electrónicos. RSA es uno de los algoritmos más utilizados con este fin.
Pasos para firmar:
- Se calcula una función resumen (hash) del documento y se representa como un entero o bloques de enteros.
- Se utiliza la clave privada (sí, la privada, lo contrario del caso para cifrar) para calcular una firma.
- Se envía el mensaje original junto a la firma generada.
Verificación del documento:
- Se recibe el documento y la firma.
- Se calcula la función resumen del documento recibido.
- Utilizando la llave pública del emisor, se cifra la firma recibida, obteniendo un hash.
- Se compara el hash calculado con el obtenido al cifrar la firma, si son iguales, el documento no se ha modificado y fue generado por el dueño de la clave. En el caso que no sean iguales, se desecha el documento como no válido.
Esto funciona ya que las operaciones de cifrado y descifrado para RSA son permutaciones inversas, algo parecido a lo que ocurre con la suma y la resta, la división y multiplicación, etc..
RSA será seguro mientras no exista un método eficiente para factorizar enteros grandes en primos. Aunque se incremente la potencia de cómputo disponible para romper las claves actuales, solo es necesario aumentar la longitud de dichas claves para mantenerlo seguro. Se ha planteado que con el arribo de la computación cuántica este tipo de problemas sería fácil de solucionar, pero no se espera que esto ocurra en un tiempo corto.
Comentarios
Publicar un comentario