He estado investigando las desventajas de usar RSA para el cifrado, y una que he encontrado repetidamente es que el descifrado RSA es lento, pero no he visto una explicación de por qué esto es así. ¿Alguien puede explicar por qué esto sería?
El descifrado RSA es lento en comparación con el cifrado, ya que d el exponente privado es necesariamente grande, mientras que (con el uso adecuado de RSA) no hay razón para que el exponente público no pueda ser pequeño como 65537 (o incluso 3). / p>
El cifrado RSA genera el texto cifrado mediante m^e mod N , donde (N, e) son su clave pública y el descifrado funciona a través de c^d mod N donde (N, d) es la clave privada que se calcula de manera eficiente cuando se conocen p y q los primos grandes.
Aquí hay un ejemplo de una clave que acabo de generar. Para mantener el ejemplo más simple, solo usé RSA de 256 bits (débil), en realidad debería usar al menos RSA de 2048 bits en este caso, en cuyo caso p, q, N yd tendrán ocho veces el número de digitos (Mientras tanto, e permanecerá 65537 incluso con RSA de 2048 bits.)
p = 255972651020913583852708738755558492779
q = 315961372360286283221530569994994089667
N = 80877470103268491690225776687889776985485516372419877405296906209811698014593
e = 65537
d = 62101042930507606982857645825838676738862341745400679479964616076341592694761
Puede verificar que se cumplan las condiciones de RSA, p y q son primos, N == p*q , y e*d % ((p-1)*(q-1)) == 1 (esta última condición es la que permite que el desencriptado RSA funcione a través de Teorema de Euler ). También puede probar que el cifrado funciona: para un mensaje m = 12345678901234567890, a continuación, es c = m^e mod N y luego c = 37526865766319703630750491158429044860161927049301804846356525193422406944367 será c^d mod N (sin enlace de wolframalpha - entrada demasiado larga para la versión gratuita). Aquí hay un cuaderno de ipython que muestra todos los pasos : la nota en python 12345678901234567890 es la sintaxis de pow(x, y, N) .
A partir de esto, parece bastante obvio que el tiempo para calcular x^y mod N será un cálculo mucho más rápido que m^e mod N . Para el cifrado, la exponenciación por 65537 mediante cuadratura repetida requerirá cuadratura y tomar el módulo 16 veces con una multiplicación adicional como m 65537 = m * m 2 16 (sus 16 cuadrados como x 2 n = (x 2 ) 2 n-1 ). Para el descifrado con RSA-256, la exponenciación de d requerirá cuadrar 256 veces y aproximadamente 128 (el número de 1s en d en binario excluyendo las primeras 1) otras multiplicaciones con RSA-256 y para cada cuadrícula también debe calcular el módulo de N. Cabe señalar que estas multiplicaciones de módulo de números grandes no son una operación de tiempo constante sino que dependen de la longitud de bits de los números. Tenga en cuenta que si elige c^d mod N para que sea pequeño como d , entonces su clave privada podría ser forzada de manera bruta (cifre un mensaje usando la clave pública y luego intente cada pequeño valor de d hasta que se descifre correctamente). Incluso si d es demasiado grande para la fuerza bruta de esta manera trivial, los ataques en d pequeña (que significa d < N 1/4 / 3), entonces hay ataques más sofisticados que permitirán que un atacante descubra el exponente privado.
(Y sí, ignoré algunos hechos de RSA del mundo real. Puede usar el teorema del resto chino usando p y q como parte de la clave privada para acelerar el descifrado. Además, no usa RSA en el mensaje real, es necesario utilizar un relleno seguro (OAEP) y luego cifrar solo una clave simétrica aleatoria que luego se usa para cifrar el mensaje real).
RSA implica realizar cálculos con números muy grandes, en particular, descifrar es calcular un gran número con una gran potencia. Hay algunos accesos directos si conoce los factores de la clave privada, pero sigue siendo lento.
Los sistemas criptográficos clásicos (es decir, simétricos) funcionan principalmente repitiendo operaciones de bit muy simples (que pueden paralizarse bastante bien) mucho, pero al final hacen mucho menos trabajo.
La forma recomendada de usar RSA es seleccionar una clave simétrica al azar, cifrando que con RSA, cifrar el mensaje con esa clave aleatoria, adjuntarla cifrada y enviar ambas a la vez. Claramente, entonces es crítico tener un generador de números aleatorios criptográficamente sólido ...
Primero, debe pensar qué significa "el desencriptado RSA es lento". ¿Lento comparado con qué? Como resultado, el cifrado RSA es lento en el sentido de que nos parece que vale la pena buscar alternativas.
El descifrado RSA es más lento que el no usar ningún cifrado. Obviamente, la ventaja de utilizar el cifrado es que puede mantener la confidencialidad de los datos, por lo que a veces la lentitud es un precio que vale la pena pagar.
El descifrado RSA es más lento que el descifrado AES. Más generalmente, para un nivel equivalente de seguridad (es decir, qué tan difícil sería romper el cifrado por fuerza bruta), la criptografía asimétrica es significativamente más lenta que la criptografía simétrica. Que yo sepa, no hay una razón matemática fundamental por la que esto sea así, es solo que los algoritmos conocidos tienen esta propiedad. La criptografía asimétrica se puede usar de forma simétrica (compartiendo claves privadas), por lo tanto, o la criptografía asimétrica es tan rápida como la criptografía simétrica.
Debido a que el cifrado y descifrado RSA es lento, generalmente se usa como parte de cryptosystems híbridos . Para cifrar un mensaje, en lugar de utilizar el par de claves RSA para cifrarlo y descifrarlo, generamos una clave simétrica única (generalmente una clave AES), ciframos la clave simétrica con RSA y ciframos el mensaje con AES. De esta manera, RSA solo se utiliza para cifrar un solo bloque de unos pocos cientos de bits.
El cifrado RSA suele ser más lento que los esquemas de cifrado basados en curvas elípticas , para un nivel de seguridad igual (que requiere claves más pequeñas) con ECC). ECC es más nuevo que RSA y poco a poco se está adoptando más.
Una observación lateral: el descifrado RSA es más lento que el cifrado, como se usa normalmente. La operación costosa del descifrado RSA es una exponenciación: C = P ^ d (mod n). La operación de cifrado correspondiente es muy similar: P = C ^ e (mod n). La diferencia de velocidad proviene del hecho de que podemos, y lo hacemos, elegir el exponente público e para que el cálculo sea más rápido. La exponencia requiere una multiplicación por cada bit del exponente, y otra multiplicación por cada bit que se establece en 1. El exponente privado d tiene que ser aleatorio para que no se pueda adivinar, mientras que e puede ser pequeño (3 y 2 16 +1 son las opciones más comunes).
Lea otras preguntas en las etiquetas cryptography rsa asymmetric