El sistema criptográfico de llave pública RSA

La criptologíaes el estudio de los sistemasllamados  criptográficoso criptosistemas, para las comunicaciones seguras. En un sistema criptográfico, el remitente transforma el mensaje antes de trasmitirlo, con la esperanza de que sólo los receptores autorizados puedan reconstruir el mensaje original (es decir, el mensaje antes de transformarlo). Se dice que el remitente envía un mensaje cifrado o encriptado, en tanto que el receptor descifra o desencripta el mensaje. Si el sistema criptográfico es seguro, las personas no autorizadas no podrán descubrir la técnica para encriptar, de manera que si leen el mensaje cifrado, no podrán descifrarlo. Los sistemas criptográficos son importantes para las grandes organizaciones (por ejemplo, el gobierno y la milicia), los negocios basados en Internet y los individuos. Por ejemplo, si se envía el número de una tarjeta de crédito por Internet, es importante que sólo el receptor al que se dirige pueda leerlo. En esta sección, se presentan algunos algoritmos que apoyan la seguridad de las comunicaciones. En uno de los sistemas más antiguos y sencillos, tanto el remitente como el receptor tienen una clave que define un carácter sustituto para cada carácter potencial que se pueda enviar. Más aún, el remitente y el receptor no revelan la clave. Se dice que estas claves son privadas.

Si una llave se define como el carácter: ABCDEFGHIJKLMNOPQRSTUVWXYZ se sustituye por: EIJFUAXVHWP GSRKOBTQYDMLZNC El mensaje ENVÍA DINERO sería cifrado como ARMWIEUWRATK. El mensaje cifrado UWRATKEARMWIUK se descifraría como DINERO ENVIADO.

Los sistemas sencillos como el del ejemplo 5.4.1 se pueden penetrar o averiguar con facilidad ya que ciertas letras (como E en inglés) y combinaciones de letras (como ER en inglés) aparecen con más frecuencia que otras. Otro problema con las llaves privadas en general es que deben enviarse por un medio seguro al remitente y el receptor antes de que se envíe el mensaje. El resto de esta sección se dedica al sistema criptográfico RSA de llave pública, llamado así en honor de sus inventores, Ronald L. Rivest, Adi Shamir y Leonard M. Adleman, que se piensa que es seguro. En el sistema RSA, cada participante hace pública una llave de ciframiento y oculta la llave de desciframiento. Para enviar un mensaje, basta con buscar la llave de ciframiento en la tabla pública distribuida. El receptor descifra el mensaje usando la llave de desciframiento oculta. En el sistema RSA, los mensajes se representan como números. Por ejemplo, cada carácter se representa como un número. Si un espacio en blanco se representa como 1, A como 2, B como 3, etcétera. El mensaje ENV A DINERO se representaría como 6, 15, 23 10, 2, 1, 5, 10, 15, 6, 19, 16. Si se desea, los enteros se pueden combinar en un solo entero

061523100201051015061916

(observe que se agregaron ceros a la izquierda para todos los números de un dígito).

se describe cómo trabaja un sistema RSA, se presenta un ejemplo concreto y se analiza por qué funciona. Cada receptor potencial elige dos primos p y q y calcula z=pq. Puesto que la seguridad del sistema RSA se basa en la incapacidad de otros de conocer el valor de z para descubrir los números p y q, es común que p y q se elijan de manera que cada uno tenga 100 o más dígitos. Después el receptor potencial calcula φ=(p – 1)(q – 1) y elige un entero n tal que el mcd(n, φ) =1. En la práctica, n suele ser primo. El par z, n se hace público. Por último, el receptor potencial calcula el número único s, 0 < s <φ, que satisface ns mod φ = 1. (Una manera eficiente de calcular s se da en la sección 5.3).

 El número s se guarda en secreto y se usa para descifrar los mensajes. Para enviar el entero a, 0 ≤a≤z – 1, al propietario de la llave pública z, n, el remitente calcula c=an mod z y envía c. (El algoritmo 5.2.19 proporciona una manera eficiente de calcular an mod z). Para descifrar el mensaje, el receptor calcula cs mod z, que se puede demostrar que es igual a a.

Suponga que se elige p=23, q=31 y n=29. Entonces z=pq=713 y φ =(p – 1)(q – 1) = 660. Ahora s = 569 ya que ns mod φ = 29·569 mod 660 =16501 mod 660 =1. El par z, n=713, 29 se hace público. Para trasmitir a=572 al dueño de la llave pública 713, 29, el remitente calcula c=a n mod z = 57929 mod 713 = 113. El receptor calcula cs mod z = 113569 mod 713 = 572 para poder descifrar el mensaje.

El resultado principal que hace que funcione el ciframiento y desciframiento es que an mod z=a para todo 0 ≤a < z y u mod φ =1 (vea la demostración en [Cormen: Teorema 31.36, p. 885]). Usando este resultado y el Teorema 5.2.17, se demuestra que el desciframiento produce el resultado correcto. Como ns mod φ =1,

La seguridad del sistema RSA para cifrar se basa principalmente en el hecho de que, hasta ahora, no se cuenta con un algoritmo eficiente para factorizar enteros; es decir, no se conoce un algoritmo para factorizar enteros de d dígitos en tiempo polinomial, O(dk). Entonces, si se seleccionan primos p y q suficientemente grandes, es impráctico calcular la factorización z=pq. Si una persona que intercepta un mensaje pudiera encontrar la factorización, podría descifrar el mensaje igual que el receptor autorizado.

 Hasta ahora, no se conoce un método práctico para factorizar enteros con 200 dígitos o más, de manera que si p y q se eligen cada uno con 100 dígitos o más, pq tendrá alrededor de 200 dígitos o más, lo que parece lograr que el sistema RSA sea seguro. La primera descripción del sistema criptográfico RSA se encuentra en la columna de Matin Gardner, en el número de febrero de 1977 de Scientific American (vea [Gardner, 1977]).

 Incluyó en esta columna un mensaje encriptado usando la clave z, n, donde z era el producto de primos con 64 y 65 dígitos, y n=9007, además de una oferta de $100 a la primera persona que descifrara el código. Cuando se escribió el artículo, se estimaba que tomaría 40 mil billones de años factorizar z. De hecho, en abril de 1994, Arjen Lenstra, Paul Leyland, Michaek Graff y Derek Atkins, con la ayuda de 600 voluntarios de 25 países, usando más de 1600 computadoras, factorizaron z (vea [Taubes]).

El trabajo se coordinó por Internet. Otra manera posible de interceptar y descifrar un mensaje sería tomar la raíz n de c mod z, donde c es el valor cifrado. Como c=an mod z, la raíz n de c mod z daría a, el valor descifrado. De nuevo, no se conoce un algoritmo con tiempo polinomial para calcular las raíces n mod z. También es concebible que un mensaje se pueda descifrar por algún me

cs mod z =(an mod z)s mod z =(an)s mod z =ans mod z =a.

dio diferente a la factorización de enteros o la obtención de las raíces n mod z. Por ejemplo, a mediados de los 90, Paul Kocher propuso una manera de penetrar en el RSA con base en el tiempo que toma descifrar un mensaje (vea [English]). La idea es que llaves secretas diferentes requieren tiempos diferentes para descifrar los mensajes y, al usar esta información de tiempos, una persona no autorizada quizá sea capaz de descubrir la llave secreta y descifrar el mensaje. Para frustrar estos ataques, quienes están a cargo del RSA han tomado medidas para alterar el tiempo observado para descifrar los mensajes

El resultado principal que hace que funcione el ciframiento y desciframiento es que an mod z=a para todo 0 ≤a < z y u mod φ =1 (vea la demostración en [Cormen: Teorema 31.36, p. 885]). Usando este resultado y el Teorema 5.2.17, se demuestra que el desciframiento produce el resultado correcto. Como ns mod φ =1,

La seguridad del sistema RSA para cifrar se basa principalmente en el hecho de que, hasta ahora, no se cuenta con un algoritmo eficiente para factorizar enteros; es decir, no se conoce un algoritmo para factorizar enteros de d dígitos en tiempo polinomial, O(dk). Entonces, si se seleccionan primos p y q suficientemente grandes, es impráctico calcular la factorización z=pq. Si una persona que intercepta un mensaje pudiera encontrar la factorización, podría descifrar el mensaje igual que el receptor autorizado.

 Hasta ahora, no se conoce un método práctico para factorizar enteros con 200 dígitos o más, de manera que si p y q se eligen cada uno con 100 dígitos o más, pq tendrá alrededor de 200 dígitos o más, lo que parece lograr que el sistema RSA sea seguro. La primera descripción del sistema criptográfico RSA se encuentra en la columna de Matin Gardner, en el número de febrero de 1977 de Scientific American (vea [Gardner, 1977]).

 Incluyó en esta columna un mensaje encriptado usando la clave z, n, donde z era el producto de primos con 64 y 65 dígitos, y n=9007, además de una oferta de $100 a la primera persona que descifrara el código. Cuando se escribió el artículo, se estimaba que tomaría 40 mil billones de años factorizar z. De hecho, en abril de 1994, Arjen Lenstra, Paul Leyland, Michaek Graff y Derek Atkins, con la ayuda de 600 voluntarios de 25 países, usando más de 1600 computadoras, factorizaron z (vea [Taubes]).

El trabajo se coordinó por Internet. Otra manera posible de interceptar y descifrar un mensaje sería tomar la raíz n de c mod z, donde c es el valor cifrado. Como c=an mod z, la raíz n de c mod z daría a, el valor descifrado. De nuevo, no se conoce un algoritmo con tiempo polinomial para calcular las raíces n mod z. También es concebible que un mensaje se pueda descifrar por algún mecs mod z =(an mod z)s mod z =(an)s mod z =ans mod z =a.

dio diferente a la factorización de enteros o la obtención de las raíces n mod z.

Por ejemplo, a mediados de los 90, Paul Kocher propuso una manera de penetrar en el RSA con base en el tiempo que toma descifrar un mensaje (vea [English]). La idea es que llaves secretas diferentes requieren tiempos diferentes para descifrar los mensajes y, al usar esta información de tiempos, una persona no autorizada quizá sea capaz de descubrir la llave secreta y descifrar el mensaje. Para frustrar estos ataques, quienes están a cargo del RSA han tomado medidas para alterar el tiempo observado para descifrar los mensajes.