Dadas las diversas longitudes de los pares de claves RSA (1024, 2048, 4096), ¿cuáles son las probabilidades de que dos usuarios hayan generado exactamente la misma clave privada?
Dadas las diversas longitudes de los pares de claves RSA (1024, 2048, 4096), ¿cuáles son las probabilidades de que dos usuarios hayan generado exactamente la misma clave privada?
Primero, lo que importa es no tener dos claves privadas idénticas, si alguno de los números primos es el mismo en el módulo (que es parte de la clave pública ), es fácil de recuperar rápidamente La clave privada completa.
( Aparte - Breve RSA primer : en RSA para una clave privada de n bits, la clave pública se compone de un exponente, típicamente e = 65537 y un módulo, N, que es el producto de dos números primos de n / 2 bits. La clave privada consiste en el exponente privado d (calculado por d = e -1 mod (p-1) (q-1) que se encuentra de manera eficiente utilizando el algoritmo euclidiano extendido) y el módulo, N. El par público permite el cifrado de un mensaje, m, en un texto cifrado, c, mediante exponenciación modular: c = m e mod N, y el privado la tecla permite el descifrado mediante m = c d mod N. Todo esto funciona debido a una parte fundamental de la teoría de los números: el teorema de Euler y cómo calcular totients).
Si dos módulos comparten un factor, entonces puedes tomar el mayor divisor común de los dos módulos de manera eficiente (usando el algoritmo de Euclides) y encontrar el factor compartido. Dejemos que los dos módulos compartan un factor primo q, por lo que N 1 = p 1 q y N 2 = p 2 q, luego gcd (N 1 , N 2 ) = q. Con el factor primo encontrado, es trivial encontrar el otro factor primo (p 1 = N 1 / q) y recrear el exponente privado. Un estudio 2012 examinó 4.7 millones de módulos RSA distintos y encontró factores compartidos en 12720 de ellos (es decir, 0.3% de las 4,7 millones de claves RSA rastreadas desde la web se rompen de su análisis). (El documento también encontró otros problemas con RSA en la práctica, como las claves compartidas utilizadas en entidades aparentemente diferentes).
Ahora, elegir números primos idénticos es una probabilidad extremadamente baja si su máquina tiene una gran cantidad de entropía inicial y no hay fallas en la generación de números aleatorios. Ambas suposiciones no siempre son ciertas; vea las claves de problemas de Debian OpenSSL de 2006-2008 y tenga en cuenta que muchas personas crean claves para Sistemas en máquinas nuevas (virtuales) que no han tenido tiempo suficiente para establecer una gran cantidad de entropía.
Aproximadamente, la fuerza de una clave de 1024 bits se basa en la elección de los dos números primos de 512 bits que comprenden el módulo. Según el teorema del número primo, hay aproximadamente (2 512 / ln 2 512 - 2 511 / ln 2 511 ) ~ 10 151 números primos de 512 bits distintos. A partir de la paradoja del cumpleaños, deberías esperar una colisión de un número primo que aparezca más de una vez con aproximadamente un 50% de probabilidad, luego de generar sqrt (10 151 ) ~ 10 75 Números primos distintos. Es decir, si algún gobierno generara mil millones de números primos de 512 bits por segundo por computadora y usara mil millones de computadoras y funcionara durante mil millones de años, solo habrían generado alrededor de 10 números primos 34 , y el la probabilidad de una colisión con alguna clave externa sería esencialmente cero, la misma posibilidad que jugar al powerball exactamente 10 veces en semanas consecutivas y comprar exactamente un boleto y ganar el premio mayor cada vez sin hacer trampa. (No hay una posibilidad significativa de una colisión principal única hasta que se generan casi 10 números primos).
.40 = 100000000000000000000000000000000000000
Sin embargo, como lo muestra el documento de 2012, esto no es cierto en el mundo real ya que las claves RSA son generadas por métodos defectuosos en la práctica a una tasa de al menos 0.3%.
Lea otras preguntas en las etiquetas rsa