cryptography - pais - ¿Cuántos números primos hay(disponibles para encriptación RSA)?
numeros primos (3)
A medida que sale nueva investigación, la respuesta a su pregunta se vuelve más interesante. En un artículo reciente "Secreto Forward Imperfecto: Cómo falla Diffie-Hellman en la práctica" por David Adrian y todos encontraron @ https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf visitado el 16/10/2015 los investigadores Demuestre que, aunque probablemente haya un número suficiente de números primos disponibles para la clave de 1024 bits de RSA, existen grupos de claves dentro de todo el conjunto que es más probable que se usen debido a la implementación.
Estimamos que incluso en el caso de 1024 bits, los cálculos son plausibles dados los recursos del estado nación. Millones de servidores utilizan una pequeña cantidad de grupos fijos o estandarizados; realizar una precomputación para un único grupo de 1024 bits permitiría la escucha pasiva en el 18% de los sitios HTTPS populares, y un segundo grupo permitiría el descifrado del tráfico al 66% de las VPN IPsec y al 26% de los servidores SSH. Una lectura atenta de las filtraciones publicadas de la NSA muestra que los ataques de la agencia contra las VPN son consistentes con haber logrado dicho rompimiento. Llegamos a la conclusión de que pasar a métodos de intercambio de claves más fuertes debería ser una prioridad para la comunidad de Internet.
La investigación también muestra un error en TLS que podría permitir a un atacante hombre-en-medio degradar el cifrado a 512 bits.
Entonces, en respuesta a su pregunta, probablemente haya una cantidad suficiente de números primos en el cifrado RSA en papel, pero en la práctica existe un problema de seguridad si se esconde de un estado nación.
¿Me equivoco al pensar que la seguridad del cifrado RSA, en general, está limitada por la cantidad de números primos conocidos?
Para crackear (o crear) una clave privada, uno tiene que combinar el par correcto de números primos.
¿Es imposible publicar una lista de todos los números primos en el rango utilizado por RSA? ¿O es esa lista lo suficientemente grande como para que este ataque de fuerza bruta sea improbable? ¿No habría números primos "comúnmente usados"?
Los números primos que se utilizarán en RSA no son solo grandes. Tiene que ser de 10 dígitos o puede ser de 100 dígitos. A lo que me refiero no está en billones o trillones sino en algo más allá de lo que es difícil de expresar o incluso imaginar.
Entonces, para responder a la pregunta, no se pueden conocer esos números primos.
RSA no selecciona de una lista de números primos conocidos: genera un número muy grande y luego aplica un algoritmo para encontrar un número cercano que casi seguramente es primo. Vea esta útil descripción de la gran generación principal ):
La forma estándar de generar números primos grandes es tomar un número aleatorio preseleccionado de la longitud deseada, aplicar una prueba de Fermat (mejor con la base 2, ya que se puede optimizar para la velocidad) y luego aplicar una determinada cantidad de pruebas de Miller-Rabin (dependiendo de la duración y la tasa de error permitida, como 2-100) para obtener un número que es muy probablemente un número primo.
(Podría preguntar por qué, en ese caso, no estamos usando este enfoque cuando tratamos de encontrar números primos más grandes. La respuesta es que el primo más grande conocido tiene más de 17 millones de dígitos , mucho más allá incluso de los números muy grandes que típicamente se usan en criptografía).
En cuanto a si las colisiones son posibles, los tamaños de clave modernos (dependiendo de la seguridad que desee) van de 1024 a 4096, lo que significa que los números primos varían de 512 a 2048 bits. Eso significa que sus números primos están en el orden de 2 ^ 512: más de 150 dígitos de longitud.
Podemos estimar muy aproximadamente la densidad de primos utilizando 1 / ln(n) (ver here ). Eso significa que entre estos 10^150 números, hay aproximadamente 10^150/ln(10^150) primos, lo que da como resultado 2.8x10^147 números primos para elegir, ¡ciertamente más de lo que cabría en cualquier lista!
Entonces sí, el número de primos en ese rango es asombrosamente enorme, y las colisiones son efectivamente imposibles. (Incluso si generó un trillón de números primos posibles, formando un septillón de combinaciones, la posibilidad de que dos de ellos sean el mismo número primo sería 10^-123 ).