1.27: El esquema RSA
- Page ID
- 117421
En este capítulo discutimos las bases del esquema RSA. Este es uno de los ejemplos más importantes de un esquema criptográfico de clave pública. En pocas palabras, en un sistema criptográfico de clave pública, la información (llamada la “clave pública”) es proporcionada al mundo por una persona o compañía (llamemos a la persona “Bob”) que quiera recibir mensajes. Cualquier persona en el mundo, incluida una persona a la que llamaremos “Alice”, puede enviar mensajes a Bob de manera segura disfrazándolos o cifrando los mensajes antes de enviarlos. Una vez que Bob recibe los mensajes cifrados de Alice, usa información privada que solo él conoce para descifrar los mensajes, o cambiarlos de nuevo a su estado original antes del descifrado. Lo importante es que los mensajes que Alice envía a Bob estén encriptados de tal manera que aunque estos mensajes fueran interceptados por un tercero (llámala “Eva” \(^{1}\)), serían ilegibles aunque Eve supiera la información que Bob hizo pública que Alice utilizaba para cifrar los mensajes.
Es decir, para que un esquema criptográfico de clave pública sea exitoso, todos deberían poder seguir las instrucciones de Bob para que se le envíen los mensajes cifrados, pero solo Bob debería saber descifrar esos mensajes una vez que están cifrados. De inmediato surge una gran pregunta: ¿esto es posible? Si Eve supiera cómo se cifraban los mensajes, ¿no debería ser capaz de averiguar cómo “deshacer” el cifrado y leer los mensajes de Alice que le fueron enviados a Bob?
Un gran paso adelante en la criptografía de clave pública ocurrió en 1977 cuando R. Rivest, A. Shamir y L. Adelman (anoten sus últimas iniciales) descubrieron y desarrollaron una técnica teórica de números para cifrar la información de tal manera que el cifrado no se podía deshacer a menos que el destinatario tuviera información secreta, o potencia de cómputos y mucho tiempo. \(^{2}\)
Juguemos el papel de Alice para ver cómo funciona el esquema RSA. En RSA Bob comienza haciendo públicos dos enteros\(m\) y\(e\), llamados el módulo y exponente de cifrado, respectivamente. En nuestro papel de Alice, tomamos un mensaje que deseamos enviarle a Bob y lo convertimos a un entero en el conjunto\(Z_m = \{0,1,2,\dots, m-1 \}\) donde\(m\) está el módulo de Bob (\(m\)suele ser un número muy grande, demasiado grande para que cualquiera factorifique rápidamente).
Habiendo escrito nuestro mensaje pretendido a Bob como un entero (denotemos este entero por\(x\)), ciframos nuestro mensaje subiendo\(x\) al poder\(e\) y reduciéndolo módulo\(m\). En símbolos, ciframos nuestro mensaje calculando\[M = x^e \bmod m.\nonumber \] El número\(M\) resultante de este cálculo es nuestro mensaje cifrado; es\(M\), en lugar de\(x\), que le enviamos a Bob.
Se le invita a pensar en cómo una eavesdropper Eve, viendo el mensaje encriptado\(M=x^e \bmod m\) y sabiendo\(m\) y\(e\) pero no\(x\), pudo determinar qué\(x\) era. Probablemente llegarás a la conclusión de que no es una tarea fácil, sobre todo si\(m\) es muy grande.
Ahora en el esquema RSA Bob recibe nuestro mensaje cifrado\(M\) y necesita descifrarlo para ver cuál\(x\) era nuestro mensaje original. Por suerte, Bob (y solo Bob) conoce un entero especial\(d\) llamado el exponente de cifrado, que tiene la propiedad de que\[M^d \bmod m = x.\nonumber \] Bob simplemente levanta el mensaje encriptado\(M\) hacer el exponente de descifrado\(d\), lo reduce modulo \(m\), y\(x\) aparece el mensaje original sin cifrar.
Veamos un ejemplo (usando un módulo y exponente de cifrado mucho más pequeños que los que se usarían en la práctica).
Supongamos que Bob usa módulo\(m=57\) y\(e=25\); los publica en línea para que cualquier persona en el mundo pueda usar esta información para cifrar los mensajes que planean enviarle. Alice quiere comunicarle el número\(x = 23\) a Bob, pero no quiere que Eve sepa cuál es su mensaje. Alice cifra el mensaje computando\[M = x^e \bmod m = 23^{25}\bmod {57};\nonumber \] para hacerlo podría usar el método binario de la Sección 1.26 —encuentra eso\(25 = 16 + 8 + 1\), y\[\begin{aligned} 23^1 &\equiv 23 \pmod{57};\\ 23^2 &\equiv 16 \pmod{57};\\ 23^4 &\equiv 28 \pmod{57};\\ 23^8 &\equiv 43 \pmod{57};\\ 23^{16} &\equiv 25 \pmod{57}, \end{aligned}\] así\[23^{25} = 23^{16}23^{8}23^1 \equiv 25\cdot 43 \cdot 23 \equiv 44 \pmod{57}.\nonumber \] Así\(M=44\), y Alice envía el mensaje cifrado\(44\) a Bob.
Ahora Eve intercepta el mensaje 44 y sabe que tiene que igualar\(x^{25} \bmod{57}\), pero Eve no puede determinar\(x\) directamente (podría simplemente experimentar elevando números adivinados a la potencia 25 y reduciendo módulo\(57\) hasta que encuentre uno que produzca 44, pero este proceso tardaría más de lo que Eve tiene paciencia).
Bob, en cambio, recibe el mensaje 44 y lo eleva a su exponente de descifrado\(d\); aquí\(d=13\), pero nadie lo sabe sino Bob. Él computa\[44^{13} \bmod 57 = 44^{8}44^{4}44^{1} \bmod{57} = (16 \cdot 4 \cdot 44) \bmod{57} = 23\nonumber \] y ve que Alice le envió el mensaje 23.
Hay mucho que se puede decir sobre la implementación del esquema RSA de manera que sea más eficiente computacionalmente y más seguro. Nuestro propósito aquí, sin embargo, es dar la base teórica numérica del esquema básico.
Para explicar por qué funciona RSA, requeriremos dos funciones:\[E:Z_m \to Z_m \qquad \mbox{(E for }encipher\text{)}\nonumber \] y\[D:Z_m \to Z_m \qquad \mbox{(D for }decipher\text{)}.\nonumber \] Para poder usar\(D\) para descifrar lo que\(E\) ha cifrado necesitamos tener\(D(E(x)) = x\) para todos\(x \in Z_m\).
Ahora como se describió anteriormente, usaremos\[E(x)=x^e\bmod m \quad \text{and} \quad D\left(M\right)=M^d\bmod m.\nonumber \]
Para ver por qué\(E\) y\(D\) son elegidos de esta manera, y para sugerir cómo Bob puede decidir para qué usar\(m\), primero probamos un lema:
Dejar\(p\) y\(q\) ser cualesquiera dos primos distintos y dejar\(m=pq\). Let\(e\) y\(d\) ser cualesquiera dos enteros positivos que son inversos el uno del otro módulo\(\phi(m)\). Entonces\[\left(x^e\right)^d = x^{ed}\equiv x\pmod m\nonumber \] para todos\(x\).
Prueba
Por Teorema 1.15.4,\(\phi(m)=(p-1)(q-1)\). Ya\(ed\equiv 1 \pmod {\phi(m)}\) que tenemos\(ed-1=k\phi(m)=k(p-1)(q-1)\) para algunos\(k\). Nota\(k>0\) a menos que\(ed=1\) en cuyo caso el teorema sea obvio. Entonces tenemos\[\label{eq: lem28.1} ed=k\phi(m)+1=k(p-1)(q-1)+1\] para algunos\(k>0\).
Ahora por el Pequeño Teorema de Fermat, si\(\gcd(x,p)=1\) tenemos\(x^{p-1}\equiv 1\pmod p\) y elevando ambos lados de la congruencia al poder\((q-1)k\) obtenemos:\[x^{(p-1)(q-1)k}\equiv 1\pmod p\nonumber \] y multiplicando ambos lados por\(x\) tenemos Es\[x^{(p-1)(q-1)k+1}\equiv x\pmod p\nonumber \] decir, por ecuación\(\eqref{eq: lem28.1}\),\[x^{ed}\equiv x\pmod p.\nonumber \] Ahora probamos esta última afirmación cuando\(\gcd(x,p)=1\), pero si\(\gcd(x,p)=p\), la misma conclusión es cierta, desde entonces\(x\equiv 0\pmod p\). De ahí\(x^{ed}\equiv x\pmod p\) que se mantenga en todos los casos. Un argumento similar prueba que para todos\(x\),\[x^{ed}\equiv x\pmod q.\nonumber \] Así que por el Ejercicio 1.17.11, ya que\(\gcd(p,q)=1\) y\(m=pq\), tenemos\[x^{ed}\equiv x\pmod m\nonumber \] para todos\(x\).
La congruencia en la sentencia de este lema se puede reescribir como\(D(E(x)) = x\) para todos\(x\), es decir, que la función de descifrado\(D\), tal y como la hemos definido, logra deshacer la función de cifrado\(E\) si las siguientes declaraciones son verdaderas:
- El módulo\(m\) es el producto de dos primos distintos\(p\) y\(q\).
- El exponente de descifrado\(d\) es el inverso del exponente de cifrado\(e\) en\(Z_{\phi(m)}\). De ahí\(d\) y\(e\) son relativamente primos para\(\phi(m)\).
En el ejemplo anterior, antes de que Alice enviara a Bob algún mensaje, Bob había creado el módulo\(m\) eligiendo dos primos\(p=3\) y\(q=19\) y dejando\(m = pq\). Dado que\(d\) y\(e\) necesitaba ser inversas el uno del otro módulo\(\phi(m)\), Bob encontró\[\phi(m) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1) = (3-1)(19-1) = 36.\nonumber \] Por lo tanto,\(e\) debe ser un número que sea relativamente primo a\(36\); Bob eligió\(e=25\) y computó \(25^*\)ser\(13\), lo que le dijo\(d\).
Ahora Bob había hecho todo este trabajo preliminar en privado. Cuando estaba listo, no compartió nada de esta información con el mundo excepto el módulo\(m\) y el exponente de cifrado\(e\). Aún así,\(m\) y\(e\) son las únicas cosas que Alice (o cualquier otra persona) necesita para enviar a Bob mensajes cifrados.
Ataques al esquema criptográfico RSA
Desde su descubrimiento a finales de la década de 1970, se han hecho muchos intentos para atacar el esquema de RSA, o en otras palabras, encontrar formas para que una Eve espiadora tome un mensaje cifrado\(M\) y determine cuál\(x\) era el mensaje original sin conocer el exponente de descifrado \(d\)antes de tiempo. Aunque aquí no vamos a decir mucho sobre estos, alentaremos al lector interesado a que haga un poco de investigación bibliotecaria; hay muchos artículos que describen tales ataques. \(^{3}\)
En la práctica, cada paso de la preparación de Bob debe llevarse a cabo con cuidado para prevenir contra los ataques que Eve pueda llevar a cabo. Por ejemplo, si el módulo de Bob\(m\) es demasiado pequeño, entonces Eve podría ser capaz de factorizarlo y deducir qué primos\(p\) y\(q\) fueron utilizados para formarlo; a partir de ahí\(\phi(m)\) es fácil de calcular y así es\(d\), ya que Eva sabe qué \(e\)es. De ahí que los primos de Bob\(p\) y ambos\(q\) deben ser muy grandes, quizás de 100 dígitos de largo cada uno, por lo que\(m\) tiene 200 dígitos y es probable que ningún algoritmo tropiece con una factorización de\(m\) en un período de tiempo razonable.
Otros ataques bastante inteligentes son posibles si, por ejemplo, se sabe que múltiples individuos usan el mismo módulo\(m\), o si el exponente de descifrado de Bob es muy pequeño en comparación con\(m\). Estos ataques suelen utilizar la potencia informática para probar un número asombroso de casos posibles, pero si no\(p,q,d,e\) se eligen con cuidado, el número de casos a verificar es lo suficientemente pequeño como para que Eve\(d\) pueda determinar de alguna manera el exponente de cifrado, y todo el tráfico cifrado destinado a Bob puede ser leído por Eve tan pronto como sea interceptado.
Dado que se\(d\) puede determinar desde\(m\) y\(e\) si se\(m\) puede factorizar en\(p\) y\(q\), y dado que una forma de mejorar la seguridad del cifrado es asegurándose\(m\) es lo suficientemente grande como para que la factorización sea poco probable, se sugiere una pregunta sin respuesta:
¿Existe un algoritmo rápido para factorizar enteros grandes?
Un algoritmo verdaderamente rápido para la factorización tendría implicaciones importantes para la criptografía y la seguridad de los datos. Es interesante (¡y un poco aleccionador!) reflexionar sobre la idea de que las respuestas a preguntas teóricas de números abstractos tienen el potencial de afectar el bienestar de los humanos en todo el mundo.
Ejercicios
Supongamos que planea usar RSA para permitir que las personas le envíen mensajes cifrados. Su uso de RSA emplea módulo\(m=pq\), exponente\(e\) de cifrado y exponente de descifrado\(d\).
- ¿Cuál de los siguientes datos deben hacerse públicos a las personas que quieran enviarle mensajes? \[p \qquad d \qquad m \qquad q \qquad e \qquad \phi(m)\nonumber \]
- Para cada una de las piezas de información de la parte (a) que no deben hacerse públicas, explique en detalle cómo una persona que descubre esta información podría leer los mensajes cifrados.
- Usando módulo\(m=851\) y exponente de cifrado\(e = 7\), encripte el mensaje\(28\).
- El exponente de descifrado para\(e=7\) es\(d=679\). Demuestre que descifrar su respuesta a la parte (a) produce el mensaje original (es decir,\(28\)). Puede ayudar saber eso\(679 = 512 + 128 + 32 + 4 + 2 + 1\).
Un mensaje ha sido previamente encriptado\(100\) usando módulo\(m=851\) y un exponente de cifrado adecuado. Si sabemos que el exponente de descifrado es\(97\), entonces ¿cuál es el mensaje original?
- Supongamos que deseamos llevar a cabo RSA utilizando\(m = 35\). ¿Qué números en\(\{1,2,3,4,5,6,7,8,9,10\}\) podrían usarse con éxito como exponentes de cifrado?
- Para cada exponente potencial de cifrado que encuentre en la parte (a), determine el exponente de descifrado correspondiente.
En los dos ejercicios siguientes, utilice la siguiente tabla para convertir letras a números antes del cifrado o después del descifrado.
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
Usando módulo\(m=391\) y exponente de cifrado\(3\), y la tabla anterior, ¿cuáles son los números cifrados resultantes producidos a partir del mensaje original 'NUMBER'?
Supongamos que un individuo quiere usar módulo\(m=55\) y exponente de cifrado\(3\). Esta es una mala elección, ya que permitirá fácilmente que se rompa el cifrado. Demostremos esto:
- ¿Cuál sería el exponente de descifrado? (Explica cómo llegaste a tu respuesta.)
- Supongamos que interceptó un mensaje que estaba encriptado usando este módulo y exponente de cifrado, y el mensaje cifrado dice\[51 \quad 8 \quad 25 \quad 31.\nonumber \] ¿Cuál era el mensaje antes del cifrado? Utilice la tabla anterior para reconocer el mensaje de precifrado como una palabra.
¿Es posible elegir un módulo\(m\) y un exponente de cifrado\(e\) tal que el exponente de descifrado\(d\) sea igual\(e\)? Si no, explica por qué no. Si es así, proporcionar un ejemplo de tal\(m\) y\(e\).
Notas al pie
[1] Para “espías” - o tal vez “malvado”.
[2] Una copia de su artículo “Un método para obtener firmas digitales y criptosistemas de clave pública” puede descargarse de
http://citeseer.nj.nec.com/rivest78method.html.
[3] Una encuesta bien conocida es “Veinte años de ataques al criptosistema RSA” de Dan Boneh de la Universidad de Stanford, disponible en línea en https://crypto.stanford.edu/ dabo/papers/RSA-survey.pdf.