[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección7.2Criptografía de Clave Pública

Si se usan criptosistemas tradicionales, cualquiera que sea capaz de encriptar un mensaje, también tendrá información suficiente para decriptar un mensaje interceptado. En 1976, W. Diffie y M. Hellman propusieron la criptografía de clave pública, que está basada en la observación de que los procesos de encriptación y decriptación no necesitan tener la misma clave. Esto quita el requerimiento de que la clave de encriptación sea secreta. La función encriptadora \(f\) debe ser relativamente fácil de calcular, pero \(f^{-1}\) tiene que ser muy difícil de calcular sin alguna información adicional, de manera que alguien que conozca la clave de encriptación, no pueda descubrir la clave de decriptación sin pasar por cálculos prohibitivamente difíciles. Es interesante notar que hasta la fecha para ningún método propuesto se ha demostrado que es “unidireccional;” es decir, para ningún criptosistema de clave pública existente, se ha demostrado que sea computacionalmente prohibitivo descifrar el mensaje con el solo conocimiento de la clave de encriptación.

SubsecciónEl Criptosistema RSA

El Criptosistema RSA introducido por R. Rivest, A. Shamir, y L. Adleman en 1978, se basa en la dificultad de factorizar número grandes. Si bien no es difícil encontrar dos primos aleatorios grandes y multiplicarlos, factorizar un número de 150 dígitos que sea el producto de dos primos grandes requería de 100 millones de computadores operando 10 millones de instrucciones por segundo durante 50 millones de años con los mejores algoritmos conocidos a principios de la década de 1990. Si bien los algoritmos se han mejorado, factorizar un producto de dos primos grandes sigue siendo computacionalmente prohibitivo.

El Criptosistema RSA funciona como sigue. Supongamos que escogemos al azar dos números primos \(p\) y \(q\) de 150 dígitos cada uno. Después calculamos su producto \(n= pq\) y también calculamos \(\phi(n) = m = (p - 1)(q-1)\text{,}\) donde \(\phi\) es la función \(\phi\) de Euler. Ahora comenzamos a elegir enteros aleatorios \(E\) hasta que encontremos uno que sea relativamente primo con \(m\text{;}\) es decir, elegimos \(E\) tal que \(\gcd(E, m) = 1\text{.}\) Usando el algoritmo de Euclides, podemos encontrar un número \(D\) tal que \(DE \equiv 1 \pmod{m}\text{.}\) Los números \(n\) y \(E\) ahora se hacen públicos.

Supongamos que la persona B (Bob) desea enviar a la persona A (Alice) un mensaje a través de un canal abierto (público). Como \(E\) y \(n\) son conocidos para todo el mundo, cualquiera puede encriptar mensajes. Bob primero convierte su mensaje en una cadena numérica de acuerdo a algún procedimiento, digamos \(\text{A} = 00, \text{B} = 02, \ldots, \text{Z}= 25\text{.}\) Si es necesario, descompondrá su mensaje de manera que cada pedazo sea un entero positivo menor a \(n\text{.}\) Supongamos que \(x\) es uno de estos pedazos. Bob forma el número \(y = x^E \mod n\) y envía \(y\) a Alice. Para que Alice recupere \(x\text{,}\) ella solo necesita calcular \(x = y^D \bmod n\text{.}\) Solo Alice conoce \(D\text{.}\)

Ejemplo7.5

Antes de explorar la teoría tras el criptosistema RSA o intentar usar enteros grandes, usaremos algunos enteros pequeños simplemente para ver que el sistema realmente funciona. Supongamos que el mensaje que deseamos enviar, una vez digitalizado es 25. Sean \(p = 23\) y \(q = 29\text{.}\) Entonces

\begin{equation*} n = pq = 667 \end{equation*}

y

\begin{equation*} \phi(n) = m = (p - 1)(q - 1) = 616. \end{equation*}

Podemos elegir \(E = 487\text{,}\) pues \(\gcd(616, 487) = 1\text{.}\) El mensaje codificado lo calculamos como

\begin{equation*} 25^{487} \bmod 667 = 169. \end{equation*}

Este cálculo se puede realizar de forma razonable usando el método de los cuadrados repetidos descrito en el Capítulo 4. Usando el algoritmo de Euclides, determinamos que \(191 E = 1 + 151 m\text{;}\) por lo tanto, la clave de decriptación es \((n, D) = ( 667, 191)\text{.}\) Podemos recuperar el mensaje original calculando

\begin{equation*} 169^{191} \bmod 667 = 25. \end{equation*}

Examinemos ahora por qué funciona el criptosistema RSA. Sabemos que \(DE \equiv 1 \pmod{ m}\text{;}\) luego, existe \(k\) tal que

\begin{equation*} DE = km + 1 = k \phi(n) + 1. \end{equation*}

Debemos considerar dos casos. En el primer caso supongamos que \(\gcd(x, n) = 1\text{.}\) Entonces, por el Teorema 6.18,

\begin{equation*} y^D = (x^E)^D = x^{DE} = x^{km + 1} = (x^{\phi(n)})^k x = (1)^k x = x \bmod n. \end{equation*}

De esta manera vemos que Alice recupera el mensaje original \(x\) cuando calcula \(y^D \bmod n\text{.}\)

Para el otro caso, supongamos que \(\gcd(x, n) \neq 1\text{.}\) Como \(n = pq\) y \(x \lt n\text{,}\) sabemos que \(x\) es un múltiplo de \(p\) o un múltiplo de \(q\text{,}\) pero no ambos. Describiremos solo la primera posibilidad, pues la otra es completamente similar. Entonces existe un entero \(r\text{,}\) con \(r \lt q\) y \(x = rp\text{.}\) Notemos que tenemos \(\gcd(x, q) = 1\) y que \(m=\phi(n)=(p - 1)(q - 1)=\phi(p)\phi(q)\text{.}\) Entonces, usando el Teorema 6.18, pero ahora mód \(q\text{,}\)

\begin{equation*} x^{km} = x^{k\phi(p)\phi(q)} = (x^{\phi(q)})^{k\phi(p)} = (1)^{k\phi(p)} = 1 \bmod q. \end{equation*}

Existe un entero \(t\) tal que \(x^{km}=1 + tq\text{.}\) Luego, Alice también recupera el mensaje en este caso,

\begin{equation*} y^D = x^{km + 1} = x^{km} x = (1 + tq) x = x + tq(rp) = x + trn = x \bmod n. \end{equation*}

Podemos preguntarnos ahora como uno intentaría violar el criptosistema RSA. Para encontrar \(D\) dados \(n\) y \(E\text{,}\) necesitamos factorizar \(n\) y encontrar \(D\) usando el algoritmo de Euclides. Si supiéramos que \(667 = 23 \cdot 29\) en el Ejemplo 7.5, podríamos recuperar \(D\text{.}\)

SubsecciónVerificación del Mensaje

Hay un problema de verificación de mensajes en los criptosistemas de clave pública. Como la clave codificadora es de público conocimiento, cualquiera tiene la capacidad de enviar un mensaje codificado. Si Alice recibe un mensaje de Bob, a ella le gustaría poder verificar que realmente fue Bob quien envió el mensaje. Supongamos que la clave encriptadora de Bob es \((n', E')\) y su clave decriptadora es \((n', D')\text{.}\) Además, supongamos que la clave encriptadora de Alice es \((n, E)\) y que su clave decriptadora es \((n, D)\text{.}\) Como las claves encriptadoras son de conocimiento público, ambos pueden intercambiar mensajes cuando lo deseen. Bob quiere poder asegurarle a Alice que el mensaje que le está enviando es auténtico. Antes de enviar el mensaje \(x\) a Alice, Bob decripta \(x\) con su propia clave secreta:

\begin{equation*} x' = x ^{D'} \bmod n'. \end{equation*}

Cualquiera puede transformar \(x'\) de vuelta a \(x\) encriptando, pero solo Bob tiene la habilidad de formar \(x'\text{.}\) Ahora Bob encripta \(x'\) con la clave pública de Alice formando

\begin{equation*} y' = {x'}^E \bmod n, \end{equation*}

un mensaje que solo Alice puede decriptar. Alice decripta el mensaje y luego encripta el resultado con la clave de encriptación de Bob para leer el mensaje original, un mensaje que solo puede haber sido enviado por Bob.

SubsecciónNota Histórica

La idea de encriptar mensajes secretos se remonta a la Antiguedad. Como sabemos, Julio César usaba un código de desplazamiento simple para enviar y recibir mensajes. Sin embargo, el estudio formal de la codificación y decodificación de mensajes probablemente comenzó con los árabes en el siglo XV. En los siglos XV y XVI, matemáticos como Alberti y Viete descubrieron que los criptosistemas monoalfabéticos no ofrecían ninguna seguridad real. En el siglo XIX, F. W. Kasiski estableció métodos para violar sistemas en los que una letra del texto encriptado puede representar más de una letra del texto claro, si la misma clave era usada varias veces. Este descubrimiento llevó al uso de criptosistemas con claves que se usaban solo una vez. La Criptografía obtuvo fundamentos matemáticos firmes con los trabajos de gente como W. Friedman y L. Hill a comienzos del siglo XX.

El período que siguió a la Primera Guerra Mundial vio el desarrollo de máquinas especializadas para la encriptación y decriptación de mensajes, y los matemáticos trabajaron muy activamente en criptografía durante la Segunda Guerra Mundial. Los esfuerzos por penetrar los criptosistemas de las naciones del Eje fueron organizados en Inglaterra y en los Estados Unidos por matemáticos notables como Alan Turing y A. A. Albert. Los Aliados obtuvieron una tremenda ventaja en la Segunda Guerra Mundial al romper los sistemas de encriptación producidos por la máquina Enigma de Alemania y los cifrados Púrpura de Japón.

Hacia 1970, el interés en la criptografía comercial comenzó a solidificarse. Había una necesidad creciente de proteger transacciones bancarias, datos informáticos y correo electrónico. A comienzos de los 70, IBM desarrolló e implementó LUZIFER, el precursor de estándar de encriptación de datos del National Bureau of Standards de Estados Unidos.

El concepto de un criptosistema de clave pública, debido a Diffie y Hellman, es muy reciente (1976). Su desarrollo fue continuado por Rivest, Shamir, y Adleman con el criptosistema RSA (1978). No se sabe qué tan seguros son estos criptosistemas. El criptosistema de la mochila de decisión, desarrollado por Merkle y Hellman, ya fue roto. Es aún una pregunta abierta si el sistema RSA puede o no ser roto. En 1991, los Laboratorios RSA publicaron una lista de semiprimos (números que tienen exactamente dos factores primos) con un premio en dinero para quien pudiera factorizarlos (http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm). Si bien el desafío terminó en 2007, muchos de estos números aún no han sido factorizados.

Ha habido bastante controversia en relación a la investigación de criptosistemas, la criptografía en sí. En 1929, cuando Henry Stimson, Secretario de Estado de Herbert Hoover, disolvió la Cámara Negra (la división de criptografía del Departamento de Estado) con la justificación ética de que “los caballeros no leen la correspondencia de otros.” Durante las últimas dos décadas del siglo XX, la Agencia Nacional de Seguridad (NSA) quería mantener en secreto la información sobre criptografía, mientras la comunidad científica peleó por el derecho de publicar la ciencia básica relacionada. Actualmente, la investigación en criptografía matemática y la teoría de números computacional es muy activa, y los matemáticos tienen la libertad de publicar sus resultados en estas áreas.