Un Método para Obtener Firmas Digitales y Criptosistemas de Clave Pública
R.L. Rivest, A. Shamir, y L. Adleman (documento original) ResumenSe presenta un método de encriptación con la propiedad novedosa de que revelar públicamente una clave de encriptación no revela la clave de desencriptación correspondiente. Esto tiene dos consecuencias importantes:
Un mensaje se encripta representándolo como un número \(M\), elevando \(M\) a una potencia especificada públicamente \(e\), y luego tomando el resto cuando el resultado se divide por el producto especificado públicamente, \(n\), de dos números primos grandes secretos \(p\) y \(q\). La desencriptación es similar; solo se usa una potencia diferente, secreta, \(d\), donde \(e \cdot d \equiv 1 \ (\text{mod} \ (p-1) \cdot (q-1))\). La seguridad del sistema se basa en parte en la dificultad de factorizar el divisor publicado, \(n\). Palabras clave: firmas digitales, criptosistemas de clave pública, privacidad, autenticación, seguridad, factorización, número primo, correo electrónico, transferencia electrónica de mensajes, criptografía. I IntroducciónLa era del "correo electrónico" puede estar sobre nosotros; debemos asegurarnos de que dos propiedades importantes del sistema actual de "correo en papel" se preserven: (a) los mensajes son privados, y (b) los mensajes pueden ser firmados. Demostramos en este documento cómo construir estas capacidades en un sistema de correo electrónico. En el corazón de nuestra propuesta hay un nuevo método de encriptación. Este método proporciona una implementación de un "criptosistema de clave pública", un concepto elegante inventado por Diffie y Hellman. Su artículo motivó nuestra investigación, ya que presentaron el concepto pero no una implementación práctica de dicho sistema. Los lectores familiarizados con su trabajo pueden pasar directamente a la Sección V para una descripción de nuestro método. II Criptosistemas de Clave PúblicaEn un "criptosistema de clave pública" cada usuario coloca en un archivo público un procedimiento de encriptación \(E\). Es decir, el archivo público es un directorio que da el procedimiento de encriptación de cada usuario. El usuario mantiene en secreto los detalles de su procedimiento de desencriptación correspondiente \(D\). Estos procedimientos tienen las siguientes cuatro propiedades:
Un procedimiento de encriptación (o desencriptación) típicamente consiste en un método general y una clave de encriptación. El método general, bajo el control de la clave, cifra un mensaje \(M\) para obtener la forma cifrada del mensaje, llamada el "cifrado" \(C\). Todos pueden usar el mismo método general; la seguridad de un procedimiento dado dependerá de la seguridad de la clave. Revelar un algoritmo de encriptación entonces significa revelar la clave. Cuando el usuario revela \(E\), revela un método muy ineficiente de calcular \(D(C)\): probar todos los mensajes posibles \(M\) hasta encontrar uno tal que \(E(M) = C\). Si se cumple la propiedad (c), el número de tales mensajes a probar será tan grande que este enfoque es impráctico. Una función \(E\) que satisface (a)-(c) es una "función trampa de un solo sentido"; si también satisface (d) es una "permutación trampa de un solo sentido". Diffie y Hellman introdujeron el concepto de funciones trampa de un solo sentido pero no presentaron ejemplos. Estas funciones se llaman "de un solo sentido" porque son fáciles de calcular en una dirección pero (aparentemente) muy difíciles de calcular en la otra. Se llaman funciones "trampa" porque las funciones inversas son en realidad fáciles de calcular una vez que se conoce cierta información privada "trampa". Una función trampa de un solo sentido que también satisface (d) debe ser una permutación: cada mensaje es el cifrado de algún otro mensaje y cada cifrado es en sí mismo un mensaje permisible. (La mapeo es "uno a uno" y "sobre"). La propiedad (d) solo es necesaria para implementar "firmas". El lector está animado a leer el excelente artículo de Diffie y Hellman para obtener más información, para la elaboración del concepto de un criptosistema de clave pública, y para una discusión de otros problemas en el área de la criptografía. Las formas en que un criptosistema de clave pública puede garantizar la privacidad y habilitar "firmas" (descritas en las Secciones III y IV a continuación) también se deben a Diffie y Hellman. Para nuestros escenarios, suponemos que A y B (también conocidos como Alicia y Bob) son dos usuarios de un criptosistema de clave pública. Distinguiremos sus procedimientos de encriptación y desencriptación con subíndices: \(E_A\), \(D_A\), \(E_B\), \(D_B\). III PrivacidadLa encriptación es el medio estándar para hacer privada una comunicación. El remitente cifra cada mensaje antes de transmitirlo al receptor. El receptor (pero ninguna persona no autorizada) conoce la función de desencriptación apropiada para aplicar al mensaje recibido y obtener el mensaje original. Un espía que escucha el mensaje transmitido solo escucha "basura" (el cifrado) que no tiene sentido para él, ya que no sabe cómo descifrarlo. El gran volumen de información personal y sensible actualmente almacenada en bancos de datos informatizados y transmitida por líneas telefónicas hace que la encriptación sea cada vez más importante. En reconocimiento del hecho de que se necesitan técnicas de encriptación eficientes y de alta calidad pero son escasas, la Oficina Nacional de Normas ha adoptado recientemente un "Estándar de Encriptación de Datos" desarrollado en IBM. El nuevo estándar no tiene la propiedad (c), necesaria para implementar un criptosistema de clave pública. Todos los métodos de encriptación clásicos (incluido el estándar de la NBS) sufren del "problema de distribución de claves". El problema es que antes de que pueda comenzar una comunicación privada, es necesario realizar otra transacción privada para distribuir las claves de encriptación y desencriptación correspondientes al remitente y al receptor, respectivamente. Típicamente, se usa un mensajero privado para llevar una clave del remitente al receptor. Tal práctica no es factible si un sistema de correo electrónico debe ser rápido y económico. Un criptosistema de clave pública no necesita mensajeros privados; las claves se pueden distribuir a través del canal de comunicaciones inseguro. ¿Cómo puede Bob enviar un mensaje privado \(M\) a Alicia en un criptosistema de clave pública? Primero, recupera \(E_A\) del archivo público. Luego le envía el mensaje cifrado \(E_A(M)\). Alicia descifra el mensaje calculando \(D_A(E_A(M)) = M\). Por la propiedad (c) del criptosistema de clave pública, solo ella puede descifrar \(E_A(M)\). Ella puede cifrar una respuesta privada con \(E_B\), también disponible en el archivo público. Observe que no se necesitan transacciones privadas entre Alicia y Bob para establecer una comunicación privada. El único "preparativo" requerido es que cada usuario que desee recibir comunicaciones privadas debe colocar su algoritmo de cifrado en el archivo público. Dos usuarios también pueden establecer comunicación privada a través de un canal de comunicaciones inseguro sin consultar un archivo público. Cada usuario envía su clave de encriptación al otro. Posteriormente, todos los mensajes se cifran con la clave de encriptación del destinatario, como en el sistema de clave pública. Un intruso que escucha en el canal no puede descifrar ningún mensaje, ya que no es posible derivar las claves de desencriptación de las claves de encriptación. (Suponemos que el intruso no puede modificar o insertar mensajes en el canal). Ralph Merkle ha desarrollado otra solución a este problema. Un criptosistema de clave pública puede usarse para "arrancar" un esquema de encriptación estándar como el método NBS. Una vez establecidas las comunicaciones seguras, el primer mensaje transmitido puede ser una clave para usar en el esquema NBS para codificar todos los mensajes siguientes. Esto puede ser deseable si la encriptación con nuestro método es más lenta que con el esquema estándar. (El esquema NBS probablemente sea algo más rápido si se utilizan dispositivos de encriptación por hardware de propósito especial; nuestro esquema puede ser más rápido en una computadora de propósito general, ya que las operaciones aritméticas de precisión múltiple son más simples de implementar que las manipulaciones de bits complicadas). IV FirmasSi los sistemas de correo electrónico deben reemplazar el sistema de correo en papel existente para transacciones comerciales, debe ser posible "firmar" un mensaje electrónico. El destinatario de un mensaje firmado tiene prueba de que el mensaje se originó en el remitente. Esta cualidad es más fuerte que la mera autenticación (donde el destinatario puede verificar que el mensaje proviene del remitente); el destinatario puede convencer a un "juez" de que el firmante envió el mensaje. Para hacerlo, debe convencer al juez de que él no falsificó el mensaje firmado él mismo. En un problema de autenticación, el destinatario no se preocupa por esta posibilidad, ya que solo quiere satisfacerse de que el mensaje proviene del remitente. Una firma electrónica debe depender del mensaje, así como del firmante. De lo contrario, el destinatario podría modificar el mensaje antes de mostrar el par mensaje-firma a un juez. O podría adjuntar la firma a cualquier mensaje, ya que es imposible detectar el "cortar y pegar" electrónico. Para implementar firmas, el criptosistema de clave pública debe implementarse con permutaciones trampa de un solo sentido (es decir, tener la propiedad (d)), ya que el algoritmo de desencriptación se aplicará a mensajes no cifrados. ¿Cómo puede el usuario Bob enviar a Alicia un mensaje "firmado" \(M\) en un criptosistema de clave pública? Primero calcula su "firma" \(S\) para el mensaje \(M\) usando \(D_B\): \[ S = D_B(M) \] (Descifrar un mensaje no cifrado "tiene sentido" por la propiedad (d) de un criptosistema de clave pública: cada mensaje es el cifrado de algún otro mensaje). Luego cifra \(S\) usando \(E_A\) (para privacidad) y envía el resultado \(E_A(S)\) a Alicia. No necesita enviar \(M\) también; se puede calcular a partir de \(S\). Alicia primero descifra el cifrado con \(D_A\) para obtener \(S\). Ella sabe quién es el presunto remitente de la firma (en este caso, Bob); esto se puede dar si es necesario en texto claro adjunto a \(S\). Luego extrae el mensaje con el procedimiento de encriptación del remitente, en este caso \(E_B\) (disponible en el archivo público): \[ M = E_B(S) \] Ahora posee un par mensaje-firma (\(M, S\)) con propiedades similares a las de un documento firmado en papel. Bob no puede negar posteriormente haber enviado este mensaje a Alicia, ya que nadie más podría haber creado \(S = D_B(M)\). Alicia puede convencer a un "juez" de que \(E_B(S) = M\), por lo que tiene prueba de que Bob firmó el documento. Claramente, Alicia no puede modificar \(M\) a una versión diferente \(M'\), ya que entonces tendría que crear la firma correspondiente \(S' = D_B(M')\) también. Por lo tanto, Alicia ha recibido un mensaje "firmado" por Bob, que puede "probar" que él envió, pero que no puede modificar. (Ni puede falsificar su firma para cualquier otro mensaje). Un sistema de cheques electrónicos podría basarse en un sistema de firmas como el anterior. Es fácil imaginar un dispositivo de encriptación en su terminal doméstico que le permita firmar cheques que se envían por correo electrónico al destinatario. Solo sería necesario incluir un número de cheque único en cada cheque para que, incluso si el destinatario copia el cheque, el banco solo honre la primera versión que vea. Otra posibilidad surge si los dispositivos de encriptación pueden ser lo suficientemente rápidos: será posible tener una conversación telefónica en la que cada palabra hablada sea firmada por el dispositivo de encriptación antes de la transmisión. Cuando se utiliza la encriptación para firmas como se indicó anteriormente, es importante que el dispositivo de encriptación no esté "conectado" entre el terminal (o computadora) y el canal de comunicaciones, ya que un mensaje puede tener que ser cifrado sucesivamente con varias claves. Quizás sea más natural ver el dispositivo de encriptación como una "subrutina de hardware" que se puede ejecutar según sea necesario. Hemos asumido anteriormente que cada usuario puede acceder siempre al archivo público de forma confiable. En una "red informática" esto podría ser difícil; un "intruso" podría falsificar mensajes que pretenden ser del archivo público. El usuario querría asegurarse de que realmente obtiene el procedimiento de encriptación de su corresponsal deseado y no, digamos, el procedimiento de encriptación del intruso. Este peligro desaparece si el archivo público "firma" cada mensaje que envía a un usuario. El usuario puede verificar la firma con el algoritmo de encriptación del archivo público \(E_{PF}\). El problema de "buscar" \(E_{PF}\) en el archivo público se evita al dar a cada usuario una descripción de \(E_{PF}\) cuando se inscribe (en persona) para unirse al criptosistema de clave pública y depositar su procedimiento de encriptación público. Luego, almacena esta descripción en lugar de buscarla de nuevo. La necesidad de un mensajero entre cada par de usuarios se ha reemplazado por el requisito de una reunión segura entre cada usuario y el administrador del archivo público cuando el usuario se une al sistema. Otra solución es dar a cada usuario, cuando se inscribe, un libro (como una guía telefónica) que contenga todas las claves de encriptación de los usuarios en el sistema. V Nuestros Métodos de Encriptación y DesencriptaciónPara cifrar un mensaje \(M\) con nuestro método, utilizando una clave de encriptación pública \((e, n)\), proceda de la siguiente manera. (Aquí \(e\) y \(n\) son un par de enteros positivos). Primero, represente el mensaje como un entero entre 0 y \(n-1\). (Divida un mensaje largo en una serie de bloques y represente cada bloque como tal entero). Use cualquier representación estándar. El propósito aquí no es cifrar el mensaje, sino solo ponerlo en la forma numérica necesaria para la encriptación. Luego, cifre el mensaje elevándolo a la potencia \(e\) y tomando el módulo \(n\). Es decir, el resultado (el cifrado \(C\)) es el resto cuando \(M^e\) se divide por \(n\). Para descifrar el cifrado, elévelo a otra potencia \(d\), nuevamente módulo \(n\). Los algoritmos de encriptación y desencriptación \(E\) y \(D\) son así: \[ C \equiv E(M) \equiv M^e \ (\text{mod} \ n), \text{ para un mensaje } M \] \[ D(C) \equiv C^d \ (\text{mod} \ n), \text{ para un cifrado } C \] Note que la encriptación no aumenta el tamaño de un mensaje; tanto el mensaje como el cifrado son enteros en el rango de 0 a \(n-1\). La clave de encriptación es así el par de enteros positivos \((e, n)\). Del mismo modo, la clave de desencriptación es el par de enteros positivos \((d, n)\). Cada usuario hace pública su clave de encriptación y mantiene privada la clave de desencriptación correspondiente. (Estos enteros deben estar propiamente subscritos como en \(n_A, e_A,\) y \(d_A\), ya que cada usuario tiene su propio conjunto. Sin embargo, solo consideraremos un conjunto típico y omitiremos los subíndices). ¿Cómo debe elegir sus claves de encriptación y desencriptación, si desea usar nuestro método? Primero, calcule \(n\) como el producto de dos primos \(p\) y \(q\): \[ n = p \cdot q \] Estos primos son muy grandes y "aleatorios". Aunque hará público \(n\), los factores \(p\) y \(q\) estarán efectivamente ocultos para todos los demás debido a la enorme dificultad de factorizar \(n\). Esto también oculta la forma en que se puede derivar \(d\) de \(e\). Luego elija el entero \(d\) como un número grande y aleatorio que sea relativamente primo a \((p-1) \cdot (q-1)\). Es decir, verifique que \(d\) satisfaga: \[ \text{mcd}(d, (p-1) \cdot (q-1)) = 1 \] ("mcd" significa "máximo común divisor"). El entero \(e\) finalmente se calcula a partir de \(p\), \(q\) y \(d\) como el "inverso multiplicativo" de \(d\), módulo \((p-1) \cdot (q-1)\). Así tenemos \[ e \cdot d \equiv 1 \ (\text{mod} \ (p-1) \cdot (q-1)) \] En la siguiente sección probamos que esto garantiza que (1) y (2) se cumplen, es decir, que \(E\) y \(D\) son permutaciones inversas. La Sección VII muestra cómo se pueden hacer eficientemente cada una de las operaciones anteriores. El método mencionado anteriormente no debe confundirse con la técnica de "exponenciación" presentada por Diffie y Hellman para resolver el problema de distribución de claves. Su técnica permite a dos usuarios determinar una clave en común para ser utilizada en un sistema criptográfico normal. No se basa en una permutación trampa de un solo sentido. Pohlig y Hellman estudian un esquema relacionado con el nuestro, donde la exponenciación se realiza módulo un número primo. VI Las Matemáticas SubyacentesDemostramos la corrección del algoritmo de desencriptación usando una identidad de Euler y Fermat: para cualquier entero (mensaje) \(M\) que sea relativamente primo a \(n\), \[ M^{\varphi(n)} \equiv 1 \ (\text{mod} \ n) \] Aquí \(\varphi(n)\) es la función totient de Euler que da el número de enteros positivos menores que \(n\) que son relativamente primos a \(n\). Para números primos \(p\), \[ \varphi(p) = p-1 \] En nuestro caso, tenemos por propiedades elementales de la función totient: \[ \varphi(n) = \varphi(p) \cdot \varphi(q) \] \[ = (p-1) \cdot (q-1) \] \[ = n - (p + q) + 1 \] Como \(d\) es relativamente primo a \(\varphi(n)\), tiene un inverso multiplicativo \(e\) en el anillo de enteros módulo \(\varphi(n)\): \[ e \cdot d \equiv 1 \ (\text{mod} \ \varphi(n)) \] Ahora probamos que las ecuaciones (1) y (2) se cumplen (es decir, que la desencriptación funciona correctamente si \(e\) y \(d\) se eligen como se indicó anteriormente). Ahora \[ D(E(M)) \equiv (E(M))^d \equiv (M^e)^d \ (\text{mod} \ n) = M^{e \cdot d} \ (\text{mod} \ n) \] \[ E(D(M)) \equiv (D(M))^e \equiv (M^d)^e \ (\text{mod} \ n) = M^{e \cdot d} \ (\text{mod} \ n) \] y \[ M^{e \cdot d} \equiv M^{k \cdot \varphi(n) + 1} \ (\text{mod} \ n) \ (\text{para algún entero } k). \] De (3) vemos que para todo \(M\) tal que \(p\) no divide a \(M\) \[ M^{p-1} \equiv 1 \ (\text{mod} \ p) \] y como \((p-1)\) divide a \(\varphi(n)\) \[ M^{k \cdot \varphi(n) + 1} \equiv M \ (\text{mod} \ p) \] Esto es trivialmente cierto cuando \(M \equiv 0 \ (\text{mod} \ p)\), por lo que esta igualdad se cumple realmente para todo \(M\). Argumentando de manera similar para \(q\) obtenemos \[ M^{k \cdot \varphi(n) + 1} \equiv M \ (\text{mod} \ q) \] Juntas, estas dos últimas ecuaciones implican que para todo \(M\), \[ M^{e \cdot d} \equiv M^{k \cdot \varphi(n) + 1} \equiv M \ (\text{mod} \ n) \] Esto implica (1) y (2) para todo \(M\), \(0 \leq M < n\). Por lo tanto, \(E\) y \(D\) son permutaciones inversas. (Agradecemos a Rich Schroeppel por sugerir la versión mejorada anterior de la prueba anterior de los autores). VII AlgoritmosPara mostrar que nuestro método es práctico, describimos un algoritmo eficiente para cada operación requerida. A Cómo Cifrar y Descifrar EficientementeCalcular \(M^e \ (\text{mod} \ n)\) requiere como máximo \(2 \cdot \log_2(e)\) multiplicaciones y \(2 \cdot \log_2(e)\) divisiones usando el siguiente procedimiento (la desencriptación se puede realizar de manera similar usando \(d\) en lugar de \(e\)):
Este procedimiento se llama "exponenciación por cuadrado repetido y multiplicación". Este procedimiento es la mitad de bueno que el mejor; se conocen procedimientos más eficientes. Knuth estudia este problema en detalle. El hecho de que el cifrado y el descifrado sean idénticos conduce a una implementación simple. (Toda la operación se puede implementar en unos pocos chips de circuito integrado de propósito especial). Una computadora de alta velocidad puede cifrar un mensaje de 200 dígitos \(M\) en unos pocos segundos; el hardware de propósito especial sería mucho más rápido. El tiempo de encriptación por bloque aumenta no más rápido que el cubo del número de dígitos en \(n\). B Cómo Encontrar Números Primos GrandesCada usuario debe (privadamente) elegir dos números grandes y aleatorios \(p\) y \(q\) para crear sus propias claves de encriptación y desencriptación. Estos números deben ser grandes para que no sea factible computacionalmente para nadie factorizar \(n = p \cdot q\). (Recuerde que \(n\), pero no \(p\) o \(q\), estará en el archivo público). Recomendamos usar números primos de 100 dígitos (decimales) \(p\) y \(q\), de modo que \(n\) tenga 200 dígitos. Para encontrar un número primo "aleatorio" de 100 dígitos, genere números aleatorios (impares) de 100 dígitos hasta encontrar un número primo. Según el teorema de los números primos, se probarán aproximadamente 115 números antes de encontrar un número primo. Para probar la primalidad de un número grande \(b\), recomendamos el elegante algoritmo "probabilístico" de Solovay y Strassen. Elige un número aleatorio \(a\) de una distribución uniforme en \(\{1, \ldots, b-1\}\), y prueba si \[ \text{mcd}(a, b) = 1 \text{ y } J(a, b) = a^{(b-1)/2} \ (\text{mod} \ b), \] donde \(J(a, b)\) es el símbolo de Jacobi. Si \(b\) es primo, esto siempre se cumple. Si \(b\) es compuesto, esto será falso con una probabilidad de al menos 1/2. Si se cumple para 100 valores aleatorios de \(a\), entonces \(b\) es casi seguramente primo; hay una probabilidad (negligible) de una en \(2^{100}\) de que \(b\) sea compuesto. Incluso si se usara accidentalmente un compuesto en nuestro sistema, el receptor probablemente lo detectaría al notar que la desencriptación no funcionó correctamente. Cuando \(b\) es impar, \(a \leq b\), y \(\text{mcd}(a, b) = 1\), el símbolo de Jacobi \(J(a, b)\) tiene un valor en \(\{-1, 1\}\) y se puede calcular eficientemente mediante el programa: \[ J(a, b) = \text{if } a = 1 \text{ then } 1 \text{ else if } a \text{ es par entonces } J(a/2, b) \cdot (-1)^{(b^2-1)/8} \text{ else } J(b \ (\text{mod} \ a), a) \cdot (-1)^{(a-1) \cdot (b-1)/4} \] (Las computaciones de \(J(a, b)\) y \(\text{mcd}(a, b)\) también se pueden combinar bien). Note que este algoritmo no prueba la primalidad de un número tratando de factorizarlo. Otros procedimientos eficientes para probar la primalidad de un número grande se dan en. Para obtener protección adicional contra algoritmos de factorización sofisticados, \(p\) y \(q\) deben diferir en longitud por unos pocos dígitos, tanto \((p-1)\) como \((q-1)\) deben contener factores primos grandes, y \(\text{mcd}(p-1, q-1)\) debe ser pequeño. Esta última condición es fácil de verificar. Para encontrar un número primo \(p\) tal que \((p-1)\) tenga un factor primo grande, genere un número primo grande \(u\) al azar, luego deje que \(p\) sea el primer primo en la secuencia \(i \cdot u + 1\), para \(i = 2, 4, 6, \ldots\). (Esto no debería tomar mucho tiempo). Se proporciona seguridad adicional asegurándose de que \((u-1)\) también tenga un factor primo grande. Una computadora de alta velocidad puede determinar en varios segundos si un número de 100 dígitos es primo, y puede encontrar el primer primo después de un punto dado en uno o dos minutos. Otro enfoque para encontrar números primos grandes es tomar un número de factorización conocida, sumarle uno y probar el resultado para primalidad. Si se encuentra un primo \(p\), es posible probar que realmente es primo usando la factorización de \(p-1\). Omitimos una discusión de esto, ya que el método probabilístico es adecuado. C Cómo Elegir \(d\)Es muy fácil elegir un número \(d\) que sea relativamente primo a \(\varphi(n)\). Por ejemplo, cualquier número primo mayor que \(\max(p, q)\) servirá. Es importante que \(d\) se elija de un conjunto lo suficientemente grande como para que un criptoanalista no pueda encontrarlo mediante una búsqueda directa. D Cómo Calcular \(e\) a partir de \(d\) y \(\varphi(n)\)Para calcular \(e\), use la siguiente variación del algoritmo de Euclides para calcular el máximo común divisor de \(\varphi(n)\) y \(d\). Calcule \(\text{mcd}(\varphi(n), d)\) calculando una serie \(x_0, x_1, x_2, \ldots\), donde \(x_0 \equiv \varphi(n), x_1 = d\), y \(x_{i+1} \equiv x_{i-1} \ (\text{mod} \ x_i)\), hasta que se encuentre un \(x_k\) igual a 0. Luego \(\text{mcd}(x_0, x_1) = x_{k-1}\). Calcule para cada \(x_i\) números \(a_i\) y \(b_i\) tales que \(x_i = a_i \cdot x_0 + b_i \cdot x_1\). Si \(x_{k-1} = 1\), entonces \(b_{k-1}\) es el inverso multiplicativo de \(x_1 \ (\text{mod} \ x_0)\). Dado que \(k\) será menor que \(2 \log_2(n)\), este cálculo es muy rápido. Si \(e\) resulta ser menor que \(\log_2(n)\), comience de nuevo eligiendo otro valor de \(d\). Esto garantiza que cada mensaje cifrado (excepto \(M = 0\) o \(M = 1\)) sufra algún "desbordamiento" (reducción módulo \(n\)). VIII Un Pequeño EjemploConsidere el caso \(p = 47\), \(q = 59\), \(n = p \cdot q = 47 \cdot 59 = 2773\), y \(d = 157\). Entonces \(\varphi(2773) = 46 \cdot 58 = 2668\), y \(e\) se puede calcular como sigue: \[ x_0 = 2668, a_0 = 1, b_0 = 0, \] \[ x_1 = 157, a_1 = 0, b_1 = 1, \] \[ x_2 = 156, a_2 = 1, b_2 = -16 \ (\text{dado que } 2668 = 157 \cdot 16 + 156), \] \[ x_3 = 1, a_3 = -1, b_3 = 17 \ (\text{dado que } 157 = 1 \cdot 156 + 1). \] Por lo tanto, \(e = 17\), el inverso multiplicativo (mod 2668) de \(d = 157\). Con \(n = 2773\) podemos codificar dos letras por bloque, sustituyendo un número de dos dígitos por cada letra: espacio en blanco = 00, A = 01, B = 02, ..., Z = 26. Así, el mensaje ITS ALL GREEK TO ME (Julio César, I, ii, 288, parafraseado) se codifica: 0920 1900 0112 1200 0718 0505 1100 2015 0013 0500 Como \(e = 10001\) en binario, el primer bloque (\(M = 920\)) se cifra: \[ M^{17} = (((((1)^2 \cdot M)^2)^2)^2)^2 \cdot M = 948 \ (\text{mod} \ 2773). \] Todo el mensaje se cifra como: 0948 2342 1084 1444 2663 2390 0778 0774 0219 1655. El lector puede comprobar que la desencriptación funciona: \(948^{157} \equiv 920 \ (\text{mod} \ 2773)\), etc.
Simulación RSA
IX Seguridad del Método: Enfoques CriptoanalíticosDado que no existen técnicas para probar que un esquema de encriptación es seguro, la única prueba disponible es ver si alguien puede pensar en una forma de romperlo. El estándar de la NBS fue "certificado" de esta manera; diecisiete años-hombre en IBM se gastaron infructuosamente tratando de romper ese esquema. Una vez que un método ha resistido un ataque concertado de esta manera, puede considerarse seguro para fines prácticos. (En realidad, existe cierta controversia sobre la seguridad del método de la NBS). Mostramos en las siguientes secciones que todos los enfoques obvios para romper nuestro sistema son al menos tan difíciles como factorizar \(n\). Si bien la factorización de números grandes no es probadamente difícil, es un problema bien conocido que ha sido trabajado durante los últimos trescientos años por muchos matemáticos famosos. Fermat y Legendre desarrollaron algoritmos de factorización; algunos de los algoritmos más eficientes de hoy en día se basan en el trabajo de Legendre. Como veremos en la siguiente sección, sin embargo, nadie ha encontrado aún un algoritmo que pueda factorizar un número de 200 dígitos en un tiempo razonable. Concluimos que nuestro sistema ya ha sido parcialmente "certificado" por estos esfuerzos anteriores para encontrar algoritmos de factorización eficientes. En las siguientes secciones consideramos formas en que un criptoanalista podría intentar determinar la clave de desencriptación secreta a partir de la clave de encriptación revelada públicamente. No consideramos formas de proteger la clave de desencriptación contra el robo; los métodos de seguridad física habituales deberían ser suficientes. (Por ejemplo, el dispositivo de encriptación podría ser un dispositivo separado que también podría usarse para generar las claves de encriptación y desencriptación, de modo que la clave de desencriptación nunca se imprima (incluso para su propietario) sino que solo se use para descifrar mensajes. El dispositivo podría borrar la clave de desencriptación si se manipula). A Factorizar \(n\)Factorizar \(n\) permitiría a un criptoanalista enemigo "romper" nuestro método. Los factores de \(n\) le permiten calcular \(\varphi(n)\) y así \(d\). Afortunadamente, factorizar un número parece ser mucho más difícil que determinar si es primo o compuesto. Existe una gran cantidad de algoritmos de factorización. Knuth presenta una excelente presentación de muchos de ellos. Pollard presenta un algoritmo que factoriza un número \(n\) en tiempo \(O(n^{1/4})\). El algoritmo de factorización más rápido conocido por los autores es de Richard Schroeppel (no publicado); puede factorizar \(n\) en aproximadamente \[ \exp\left( \sqrt{\ln(n) \cdot \ln(\ln(n))} \right) = n^{\sqrt{\ln(\ln(n))/\ln(n)}} = (\ln(n))^{\sqrt{\ln(n)/\ln(\ln(n))}} \] pasos (aquí ln denota la función logaritmo natural). La Tabla 1 muestra el número de operaciones necesarias para factorizar \(n\) con el método de Schroeppel, y el tiempo requerido si cada operación utiliza un microsegundo, para varias longitudes del número \(n\) (en dígitos decimales).
Recomendamos que \(n\) tenga alrededor de 200 dígitos de longitud. Se pueden usar longitudes más largas o más cortas dependiendo de la importancia relativa de la velocidad de encriptación y la seguridad en la aplicación en cuestión. Un \(n\) de 80 dígitos proporciona una seguridad moderada contra un ataque utilizando la tecnología actual; usar 200 dígitos proporciona un margen de seguridad contra desarrollos futuros. Esta flexibilidad para elegir una longitud de clave (y así un nivel de seguridad) para adecuarse a una aplicación particular es una característica que no se encuentra en muchos de los esquemas de encriptación anteriores (como el esquema de la NBS). B Calcular \(\varphi(n)\) Sin Factorizar \(n\)Si un criptoanalista pudiera calcular \(\varphi(n)\), podría romper el sistema calculando \(d\) como el inverso multiplicativo de \(e\) módulo \(\varphi(n)\) (usando el procedimiento de la Sección VII D). Argumentamos que este enfoque no es más fácil que factorizar \(n\) ya que permite al criptoanalista factorizar \(n\) fácilmente usando \(\varphi(n)\). Este enfoque para factorizar \(n\) no ha resultado ser práctico. ¿Cómo se puede factorizar \(n\) usando \(\varphi(n)\)? Primero, \((p + q)\) se obtiene de \(n\) y \(\varphi(n) = n - (p + q) + 1\). Luego, \((p - q)\) es la raíz cuadrada de \((p + q)^2 - 4n\). Finalmente, \(q\) es la mitad de la diferencia de \((p + q)\) y \((p - q)\). Por lo tanto, romper nuestro sistema calculando \(\varphi(n)\) no es más fácil que romper nuestro sistema factorizando \(n\). (Por esto, \(n\) debe ser compuesto; \(\varphi(n)\) es trivial de calcular si \(n\) es primo). C Determinar \(d\) Sin Factorizar \(n\) o Calcular \(\varphi(n)\)Por supuesto, \(d\) debe elegirse de un conjunto lo suficientemente grande como para que una búsqueda directa sea inviable. Argumentamos que calcular \(d\) no es más fácil para un criptoanalista que factorizar \(n\), ya que una vez que \(d\) se conoce, \(n\) podría factorizarse fácilmente. Este enfoque para factorizar tampoco ha resultado ser fructífero. Conocer \(d\) permite factorizar \(n\) de la siguiente manera. Una vez que un criptoanalista conoce \(d\), puede calcular \(e \cdot d - 1\), que es un múltiplo de \(\varphi(n)\). Miller ha demostrado que \(n\) se puede factorizar usando cualquier múltiplo de \(\varphi(n)\). Por lo tanto, si \(n\) es grande, un criptoanalista no debería poder determinar \(d\) más fácilmente que factorizar \(n\). Un criptoanalista puede esperar encontrar un \(d'\) que sea equivalente al \(d\) que posee en secreto un usuario del criptosistema de clave pública. Si tales valores \(d'\) fueran comunes, entonces una búsqueda por fuerza bruta podría romper el sistema. Sin embargo, todos esos \(d'\) difieren por el mínimo común múltiplo de \((p-1)\) y \((q-1)\), y encontrar uno permite factorizar \(n\). (En (3) y (5), \(\varphi(n)\) se puede reemplazar por \(\text{mcm}(p-1, q-1)\)). Por lo tanto, encontrar cualquier \(d'\) es tan difícil como factorizar \(n\). D Calcular \(D\) de Alguna Otra ManeraAunque este problema de "calcular raíces \(e\)-ésimas módulo \(n\) sin factorizar \(n\)" no es un problema difícil bien conocido como la factorización, nos sentimos razonablemente seguros de que es intratable computacionalmente. Puede ser posible probar que cualquier método general de romper nuestro esquema produce un algoritmo de factorización eficiente. Esto establecería que cualquier forma de romper nuestro esquema debe ser tan difícil como factorizar. Sin embargo, no hemos podido probar esta conjetura. Nuestro método debe certificarse haciendo que la conjetura anterior de intratabilidad resista un intento concertado de refutarla. Se desafía al lector a encontrar una forma de "romper" nuestro método. X Evitar el "Rebloqueo" al Cifrar un Mensaje FirmadoEs posible que un mensaje firmado tenga que ser "rebloqueado" para encriptarse, ya que la firma \(n\) puede ser mayor que la encriptación \(n\) (cada usuario tiene su propio \(n\)). Esto se puede evitar de la siguiente manera. Se elige un valor umbral \(h\) (digamos \(h = 10^{199}\)) para el criptosistema de clave pública. Cada usuario mantiene dos pares públicos \((e, n)\), uno para el cifrado y otro para la verificación de firmas, donde cada firma \(n\) es menor que \(h\), y cada encriptación \(n\) es mayor que \(h\). El rebloqueo para cifrar un mensaje firmado es entonces innecesario; el mensaje se bloquea según la firma \(n\) del transmisor. Otra solución usa una técnica dada en. Cada usuario tiene un solo par \((e, n)\) donde \(n\) está entre \(h\) y \(2h\), donde \(h\) es un umbral como el anterior. Un mensaje se codifica como un número menor que \(h\) y se cifra como antes, excepto que si el cifrado es mayor que \(h\), se vuelve a cifrar repetidamente hasta que sea menor que \(h\). De manera similar, para descifrar, el cifrado se descifra repetidamente para obtener un valor menor que \(h\). Si \(n\) está cerca de \(h\), el recifrado será poco frecuente. (El bucle infinito no es posible, ya que en el peor de los casos un mensaje se cifra como a sí mismo). XI ConclusionesHemos propuesto un método para implementar un criptosistema de clave pública cuya seguridad se basa en parte en la dificultad de factorizar números grandes. Si la seguridad de nuestro método resulta ser adecuada, permite establecer comunicaciones seguras sin el uso de mensajeros para llevar claves, y también permite "firmar" documentos digitalizados. La seguridad de este sistema debe examinarse con más detalle. En particular, se debe examinar muy de cerca la dificultad de factorizar números grandes. Se insta al lector a encontrar una forma de "romper" el sistema. Una vez que el método haya resistido todos los ataques durante un tiempo suficiente, se podrá usar con una cantidad razonable de confianza. Nuestra función de encriptación es el único candidato para una "permutación trampa de un solo sentido" conocida por los autores. Podría ser deseable encontrar otros ejemplos, para proporcionar implementaciones alternativas en caso de que la seguridad de nuestro sistema resulte algún día inadecuada. Seguramente también hay muchas nuevas aplicaciones por descubrir para estas funciones. Agradecimientos: Agradecemos a Martin Hellman, Richard Schroeppel, Abraham Lempel y Roger Needham por discusiones útiles, y a Wendy Glasser por su ayuda en la preparación del manuscrito inicial. Xerox PARC proporcionó apoyo y algunas maravillosas instalaciones de edición de texto para preparar el manuscrito final. Recibido el 4 de abril de 1977; revisado el 1 de septiembre de 1977. Referencias
|