Ilustración y Teoría del RSA¶
Motivación¶
Nos ocuparemos ahora con entender un sistema criptográfico más extenso. Vimos en la sección de Diffie-Hellman el comportamiento de un sistema de intercambio de claves cuyo proposito es establecer un canal de comunicación con cifrado simétrico. Para evaluar la efectividad de este método usamos cifrados escogidos de forma arbitraria, así como sesiones para las llaves efimeras de un único mensaje. Estas decisiones no son características de Diffie-Hellman ya que es un sistema que contempla solo el primer requisito para establecer comunicación. Introduciremos el RSA. Nombrado así por los tres investigadores que publicaron su hallazgo en 1977, el RSA es un sistema criptográfico que, así como el Diffie-Hellman, contempla una fase de generación y distribución de llaves, pero también contempla métodos de encripción y descifrado específicos del protocolo.
Primeros conceptos¶
Recordemos que el objetivo de el Diffie-Hellman es el de permitirle a dos partes compartir una misma clave privada con la que cifrar y descifrar mensajes de forma simétrica. El RSA, por otro lado, es un sistema criptográfico asimétrico. Esto quiere decir que el proces de encriptar y desencriptar un mensaje se hace con una llave pública y su complemento privado. Un mensaje encriptado con una llave pública solo puede ser descifrado por su contraparte privada. En la primer página del Diffie-Hellman exploramos distintas formas en las que este par de llaves puede ser utilizado para autenticar el remitente de un mensaje, o para asegurar que solo el destinatario pueda leer el contenido de un mensaje.
Idea general¶
En el caso de la criptografía simétrica, debe establecerse una clave única para cada canal de comunicación. Si, volviendo a nuestro ejemplo ilustrativo del Diffie-Hellman, muchas otras personas quisieran comunicarse con Alice con cifrado simétrico, esta tendría que establecer una llave secreta con cada uno de estos. Un acercamiento a la criptografía asimétrica más rudimentario no es muy distinto, ya que un destinatario de un mensaje tiene una llave pública única con la que debería encriptarse su mensaje para que este pueda descifrarlo con su clave privada. En este caso la cantidad de llaves que Alice debe manejar en función de destinatario es mínima. Alice tan solo contempla su clave pública, con la que todos pueden encriptar un mensaje destinado a ella, y su clave privada, con la que descifrará todo mensaje destinado a ella. Una analogía común es aquella de el candado y la llave, donde si Alice quiere recibir un mensaje de Bob, le puede prestar una caja con un candado sin llave. Bob empaca su mensaje y lo sella con el candado y despacha la caja para donde Alice. Alice, propietaria de la llave, abre el candado y lee el mensaje de Bob. Es evidente que el candado es el equivalente a una llave pública la llave del candado su complemento privado.
Teoría¶
Los aspectos teóricos que están detrás del sistema RSA son varios resultados de teoría de números que se explican a continuación.
Definición: La función \(\varphi:\mathbb{Z}^+\longrightarrow\mathbb{N}\) denominada \(\varphi\) de Euler, se define para un número \(n\) entero positivo de la siguiente forma:
es decir, \(\varphi\left (n\right )\) indica la cantidad de primos relativos menores o iguales a \(n\).
Esta función está presente en varios resultados importantes de la teoría de números y algunas de sus propiedades se usan en la implementación del RSA. En primer lugar, de su definición es claro que \(\varphi(p)=p-1 \) si \(p\) es un primo. Por otro lado, un resultado muy útil y no tan obvio de ésta función es que es multiplicativa. Esto quiere decir que para cualesquiera dos números \(m\) y \(n\) primos relativos se tiene \(\varphi(mn)=\varphi(m)\varphi(n)\). Existen distintas formas de demostrar este hecho, como por ejemplo usando técnicas de teoría de números como la inversión de Möbius. Otra forma más avanzada de demostrar esta propiedad es que es un corolario del teorema chino de los residuos de la teoría de anillos (Esto puede verse en la página 265 de la tercera edición del libro de álgebra Abstracta de Dummit y Foote). Finalmente, es importante el siguiente teorema:
Teorema de Euler-Fermat:
Sean \(a\) y \(n\) enteros positivos, primos relativos, entonces se tiene la congruencia \(n^{\varphi(a)} \equiv 1 \mod a\).
Demostración: Sea \(A\) el conjunto canónico de residuos módulo \( a \) (es decir el conjunto de los primos relativos menores o iguales de \( a \)), entonces por definición \(A\) tiene \(\varphi(a)\) elementos. Considere el conjunto \(B=\lbrace xn \mid x\in A\rbrace \). Como \(a\) y \(n\) son coprimos, \(B\) es un conjunto reducido de residuos módulo \(a\). Si \(u\) es el producto de todos los elementos de \(A\) y \(v\) el producto de todos los elementos de \(B\), entonces \( un^{\varphi(a)}=v \) y \(\ v\equiv u \mod a\), entonces \( un^{\varphi(a)}\equiv u \mod a \) y como \(u\) es primo relativo con \(a\), pues es producto de primos relativos con \(a\) , entonces tenemos \(n^{\varphi(a))} \equiv 1 \mod a\). \(\blacksquare\)
Este teorema es una generalización del pequeño teorema de Fermat, pues este último se obtiene tomando \(a\) primo.
Ahora veamos cómo se aplican estos resultados al RSA. Digamos que un banco quiere recibir una información confidencial de un cliente. El banco primero elije dos primos muy grandes \(P\) y \(Q\) y el primer número de la clave pública sería \(N=P\cdot Q\). Ahora que el banco conoce \(P\) y \(Q\) le es posible calcular fácilmente \(\varphi(N)\), pues \(\varphi(N)= \varphi(Q\cdot P)=\varphi(Q)\cdot\varphi(P)=(Q-1)(P-1)\). Luego, el banco escoge un \(e\) que tenga inverso multiplicativo \(d\) módulo \(\varphi(N)\). En la práctica, escoger un \(e\) menor que \(\varphi(N)\) con inverso multiplicativo es enteramente posible ya que los primos que tomó el banco son lo suficientemente grandes como para que \(\varphi(N)\) tenga varios primos relativos menores, es decir, para que \(\varphi(\varphi(N))\geqslant1\). Un método para calcular el inverso multiplicativo \(d\) de \(e\) es calcular \(e^{(\varphi(\varphi(N)))-1}\) módulo \(\varphi(N)\) por el teorema de Euler-Fermat. Este número \(d\) es lo que correspondería a la “clave privada” del banco, el cual es casi imposible de descifrar porque para hacerlo sería necesario conocer los primos \(P\) y \(Q\) que factorizan a \(N\), para así calcular \(\varphi(N)\) (tarea que para \(N\)’s muy grandes es casi imposible). Así, el banco finalmente publica el par de números \((N,e)\) que vendrían a ser lo que se denomina la “clave pública” del banco.
Digamos ahora que el cliente recopila la información que le quiere enviar al banco y la codifica en un mensaje \(M\) (aquí el sistema de codificación debe ser tal que no admita mensajes iguales a \(P\), \(Q\) ni mayores que \(N\)). Luego, para enviar este mensaje de manera secreta debe encriptarlo con la “clave pública” del banco, a saber, el par \((N,e)\). Así, el mensaje encriptado del cliente sería \(C= M^{e} \) módulo \( N \) y una vez hecha esta operación lo publica para que el banco pueda acceder a él.
El banco es el único que conoce \(d\), su “clave privada”, y entonces puede usarla para descifrar el mensaje encriptado \(C\) del cliente. Para esto, calcula \( C^{d}\) módulo \( N\). Esto funciona por el Teorema Euler-Fermat, pues \(M\) y \(N\) son primos relativos porque \(M\) es distinto a \( P \), \( Q \) y \( N\), y como \( e\cdot d\equiv 1 \mod \varphi(N) \), existe un entero \( k \) tal que \( e\cdot d=\varphi(N)k+1 \) y por lo tanto se tiene
El teorema Euler-Fermat se usa en el paso \( M(M^{\varphi(N)})^k \equiv M1^k\). De esta manera, el banco logra recobrar el mensaje completo del cliente. Aquí se evidencia la importancia de que \(M\) sea menor o igual a \(N\), pues de lo contrario cuando el banco calcula \(C^d\) (mod \(N\)) obtendría \(M\) (mod \(N\)), el cual es distinto al mensaje original del cliente \(M\) dado que \(M>N\).