Solución:
La generación de una clave RSA requiere encontrar dos números primos aleatorios grandes que satisfagan ciertos criterios. Encontrar tales números primos es esencialmente una cuestión de elegir números aleatorios y luego verificar si son primos o no mediante la realización de ciertas pruebas. El teorema de los números primos nos dice que a medida que los números primos se hacen más grandes, también se vuelven más raros, por lo que debe generar más números aleatorios para encontrar uno que sea primo. La verificación para determinar si el número es primo también toma más tiempo para números más grandes.
Todos los factores anteriores contribuyen al aumento del tiempo que lleva generar claves más grandes, sin embargo, aparte de esto, parece que esta biblioteca no es particularmente rápida. Usando OpenSSL en una PC razonablemente moderna, puedo generar una clave de 2048 bits en ~ 1 segundo y una clave de 4096 bits en <10 segundos, por lo que sus tiempos de 10 segundos y 3-5 minutos parecen excesivos. Si el rendimiento es un problema, le sugiero que pruebe con una biblioteca diferente, con el entendimiento de alguna ¡la biblioteca va a ser más lenta para generar claves grandes que las más pequeñas!
Un poco tarde para una respuesta, pero como las otras respuestas son puramente heurísticas, aquí algunos antecedentes sobre por qué lleva tanto más tiempo:
La parte más lenta de la generación de una clave RSA suele ser la prueba de Fermat, que debe ejecutarse para cada candidato principal x y consiste en verificar si 2 ^ {x-1} = 1 módulo x (usar 2 se puede hacer más rápido que usar otras bases). Entonces, ¿cómo depende el tiempo necesario para las pruebas de Fermat de la longitud de bits de x?
-
El tiempo de ejecución para la multiplicación es aproximadamente cuadrático en las longitudes de bits de los factores, por lo que duplicar la longitud cuadriplica el tiempo (eso es para la multiplicación escolar; si usa Karatsuba, entonces se trata de triplicar el tiempo; para métodos de multiplicación más sofísticos, el bit- longitudes de RSA son demasiado cortas).
-
El tiempo de ejecución de una exponenciación modular es lineal en la longitud de bits del exponente.
-
La probabilidad de que un número aleatorio de n bits sea primo es 1: log (2 ^ n), donde log es el logaritmo natural, es decir, es 1: (n * log (2)).
Entonces, duplicar la longitud de bits le da un factor de 4 de (1) y dos veces un factor de 2 de (2) y (3) para el tiempo de ejecución de la generación de clave RSA, por lo que en total el tiempo de ejecución para las pruebas de Fermat. sube por un factor de 16 (o 12 usando Karatsuba).
Como hay otras partes de la generación de claves cuyos tiempos de ejecución no aumentan tan rápido, un factor de alrededor de 10, como se indica en la respuesta de Iridium, es razonable.