7.2: Criptografía de Clave Pública

Si se utilizan criptosistemas tradicionales, cualquiera que sepa lo suficiente para codificar un mensaje también sabrá lo suficiente como para decodificar un mensaje interceptado. En 1976, W. Diffie y M. Hellman propusieron la criptografía de clave pública, la cual se basa en la observación de que los procedimientos de cifrado y descifrado no necesitan tener la misma clave. Esto elimina el requisito de que la clave de codificación se mantenga en secreto. La función de codificación\(f\) debe ser relativamente fácil de calcular, pero\(f^{-1}\) debe ser extremadamente difícil de calcular sin alguna información adicional, de modo que alguien que solo conozca la clave de cifrado no pueda encontrar la clave de descifrado sin un cálculo prohibitivo. Es interesante señalar que hasta la fecha, no se ha propuesto ningún sistema que se haya demostrado que sea “unidireccional”; es decir, para cualquier criptosistema de clave pública existente, nunca se ha demostrado que sea computacionalmente prohibitivo decodificar mensajes con solo conocimiento de la clave de codificación.

El criptosistema RSA

El criptosistema RSA introducido por R. Rivest, A. Shamir y L. Adleman en 1978, se basa en la dificultad de factorizar grandes números. Aunque no es una tarea difícil encontrar dos primos aleatorios grandes y multiplicarlos juntos, factorizar un número de 150 dígitos que es producto de dos primos grandes tomaría 100 millones de computadoras operando a 10 millones de instrucciones por segundo alrededor de 50 millones de años bajo los algoritmos más rápidos disponibles en el principios de los noventa. Aunque los algoritmos han mejorado, factorizar un número que es producto de dos primos grandes sigue siendo computacionalmente prohibitivo.

El criptosistema RSA funciona de la siguiente manera. Supongamos que elegimos dos números primos aleatorios de 150 dígitos\(p\) y\(q\text{.}\) Next, calculamos el producto\(n= pq\) y también calculamos\(\phi(n) = m = (p - 1)(q-1)\text{,}\) dónde\(\phi\) está la\(\phi\) función Euler. Ahora empezamos a elegir enteros aleatorios\(E\) hasta que encontremos uno que sea relativamente primo a\(m\text{;}\) eso es, elegimos\(E\) tal que\(\gcd(E, m) = 1\text{.}\) Usando el algoritmo euclidiano, podemos encontrar un número\(D\) tal que\(DE \equiv 1 \pmod{m}\text{.}\) Los números\(n\) y ahora\(E\) se hacen públicos.

Supongamos que ahora esa persona B (Bob) desea enviar a la persona A (Alice) un mensaje por una línea pública. Desde\(E\) y\(n\) son conocidos por todos, cualquiera puede codificar mensajes. Bob primero digitaliza el mensaje según algún esquema, digamos\(\text{A} = 00, \text{B} = 02, \ldots, \text{Z}= 25\text{.}\) Si es necesario, romperá el mensaje en pedazos de tal manera que cada pieza sea un entero positivo menor que\(n\text{.}\) Supongamos que\(x\) es una de las piezas. Bob forma el número\(y = x^E \mod n\) y envía\(y\) a Alice. Para que Alice se recupere solo\(x\text{,}\) necesita cómputos\(x = y^D \bmod n\text{.}\) Solo Alice sabe\(D\text{.}\)

Ejemplo\(7.5\)

Antes de explorar la teoría detrás del criptosistema RSA o intentar usar enteros grandes, usaremos algunos enteros pequeños solo para ver que el sistema efectivamente funciona. Supongamos que deseamos enviar algún mensaje, que cuando se digitaliza es\(25\text{.}\) Let\(p = 23\) y\(q = 29\text{.}\)

Solución

Entonces

\[ n = pq = 667 \nonumber \]

y

\[ \phi(n) = m = (p - 1)(q - 1) = 616\text{.} \nonumber \]

Podemos dejar\(E = 487\text{,}\) ya que\(\gcd(616, 487) = 1\text{.}\) el mensaje codificado se calcula para ser

\[ 25^{487} \bmod 667 = 169\text{.} \nonumber \]

Este cálculo puede realizarse razonablemente utilizando el método de cuadrados repetidos como se describe en el Capítulo 4. Usando el algoritmo euclidiano, determinamos que\(191 E = 1 + 151 m\text{;}\) por lo tanto, la clave de descifrado es\((n, D) = ( 667, 191)\text{.}\) Podemos recuperar el mensaje original calculando

\[ 169^{191} \bmod 667 = 25\text{.} \nonumber \]

Ahora examinemos por qué funciona el criptosistema RSA. Sabemos que de\(DE \equiv 1 \pmod{ m}\text{;}\) ahí, existe\(k\) tal que

\[ DE = km + 1 = k \phi(n) + 1\text{.} \nonumber \]

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

\[ y^D = (x^E)^D = x^{DE} = x^{km + 1} = (x^{\phi(n)})^k x = (1)^k x = x \bmod n\text{.} \nonumber \]

Así vemos que Alice recupera el mensaje original\(x\) cuando computa\(y^D \bmod n\text{.}\)

Para el otro caso, supongamos que\(\gcd(x, n) \neq 1\text{.}\)\(n = pq\) Since y\(x \lt n\text{,}\) sabemos\(x\) es un múltiplo de\(p\) o un múltiplo de\(q\text{,}\) pero no ambos. Describiremos la primera posibilidad solamente, ya que la segunda es totalmente similar. Hay entonces un entero\(r\text{,}\) con\(r \lt q\) y\(x = rp\text{.}\) Note que tenemos\(\gcd(x, q) = 1\) y que\(m=\phi(n)=(p - 1)(q - 1)=\phi(p)\phi(q)\text{.}\) Entonces, usando Teorema\(6.18\), pero ahora mod\(q\text{,}\)

\[ x^{km} = x^{k\phi(p)\phi(q)} = (x^{\phi(q)})^{k\phi(p)} = (1)^{k\phi(p)} = 1 \bmod q\text{.} \nonumber \]

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

\[ y^D = x^{km + 1} = x^{km} x = (1 + tq) x = x + tq(rp) = x + trn = x \bmod n\text{.} \nonumber \]

Ahora podemos preguntar cómo se iría para romper el criptosistema RSA. Para encontrar\(D\) dado\(n\) y simplemente\(E\text{,}\) necesitamos factorizar\(n\) y resolver\(D\) mediante el uso del algoritmo euclidiano. Si hubiéramos sabido que\(667 = 23 \cdot 29\) en Ejemplo\(7.5\), podríamos haber recuperado\(D\text{.}\)

Verificación de mensajes

Existe un problema de verificación de mensajes en criptosistemas de clave pública. Dado que la clave de codificación es de conocimiento público, cualquiera tiene la capacidad de enviar un mensaje codificado. Si Alice recibe un mensaje de Bob, le gustaría poder verificar que fue Bob quien realmente envió el mensaje. Supongamos que la clave de cifrado de Bob es\((n', E')\) y su clave de descifrado es\((n', D')\text{.}\) También, supongamos que la clave de cifrado de Alice es\((n, E)\) y su clave de descifrado es\((n, D)\text{.}\) Dado que las claves de cifrado son información pública, pueden intercambiar mensajes codificados a su conveniencia. Bob desea asegurarle a Alice que el mensaje que está enviando es auténtico. Antes de que Bob le envíe el mensaje\(x\) a Alice, descifra\(x\) con su propia clave:

\[ x' = x ^{D'} \bmod n'\text{.} \nonumber \]

Cualquiera puede\(x'\) volver a cambiar a\(x\) solo por cifrado, pero solo Bob tiene la capacidad de formar\(x'\text{.}\) Ahora Bob cifra\(x'\) con la clave de cifrado de Alice para formar

\[ y' = {x'}^E \bmod n\text{,} \nonumber \]

un mensaje que sólo Alice puede decodificar. Alice decodifica el mensaje y luego codifica el resultado con la clave de Bob para leer el mensaje original, un mensaje que solo pudo haber sido enviado por Bob.

Nota Histórica

El cifrado de mensajes secretos se remonta a la antigua Grecia y Roma. Como sabemos, Julio César utilizó un sencillo código de turno 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 1400. 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 romper cifrados en los que una letra de texto cifrado puede representar más de una letra de texto plano, si la misma clave se utilizó varias veces. Este descubrimiento llevó al uso de criptosistemas con claves que solo se utilizaron una sola vez. La criptografía fue colocada sobre bases matemáticas firmes por personas como W. Friedman y L. Hill a principios del siglo XX.

El período posterior a la Primera Guerra Mundial vio el desarrollo de máquinas de propósito especial para cifrar y descifrar mensajes, y los matemáticos fueron muy activos en la criptografía durante la Segunda Guerra Mundial. Los esfuerzos para penetrar en los criptosistemas de las naciones del Eje fueron organizados en Inglaterra y en Estados Unidos por matemáticos tan notables como Alan Turing y A. A. Albert. Los Aliados obtuvieron una tremenda ventaja en la Segunda Guerra Mundial al romper los cifrados producidos por la máquina Enigma alemana y los cifrados Purple japoneses.

Para la década de 1970, el interés por la criptografía comercial había comenzado a afianzarse. Había una creciente necesidad de proteger las transacciones bancarias, los datos informáticos y el correo electrónico. A principios de la década de 1970, IBM desarrolló e implementó LUZIFER, el precursor del Estándar de Cifrado de Datos (DES) de la Oficina Nacional de Normas.

El concepto de criptosistema de clave pública, debido a Diffie y Hellman, es muy reciente (1976). Fue desarrollado aún más por Rivest, Shamir y Adleman con el criptosistema RSA (1978). No se sabe cuán seguros son ninguno de estos sistemas. El criptosistema de mochila trampilla, desarrollado por Merkle y Hellman, se ha roto. Sigue siendo una cuestión abierta si se puede romper o no el sistema RSA. En 1991, RSA Laboratories publicó una lista de semiprimos (números con exactamente dos factores primos) con un premio en efectivo para quien fuera capaz de proporcionar una factorización (http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm). Aunque el reto terminó en 2007, muchos de estos números aún no han sido factorizados.

Hubo mucha controversia sobre la investigación en criptografía y criptografía misma. En 1929, cuando Henry Stimson, secretario de Estado bajo Herbert Hoover, desestimó la Cámara Negra (la división de criptografía del Departamento de Estado) con la base ética de que “los caballeros no leen el correo del otro”. Durante las dos últimas décadas del siglo XX, la Agencia Nacional de Seguridad quiso mantener en secreto la información sobre la criptografía, mientras que la comunidad académica luchó por el derecho a publicar investigaciones básicas. Actualmente, la investigación en criptografía matemática y teoría computacional de números es muy activa, y los matemáticos son libres de publicar sus resultados en estas áreas.