En el mundo real, se crean millones de claves PGP cada día, ¿cuál es la probabilidad (probabilidad) de crear dos claves idénticas? ¿En diferentes lugares, por diferentes personas?
Si asumimos que su generador de números aleatorios no está completamente bloqueado, entonces
¿Cuál es la posibilidad de que dos claves PGP sean exactamente idénticas?
se puede responder con aproximadamente algo elevado al poder del infinito negativo. O en otras palabras: no va a suceder.
Podemos resolver esto asumiendo que una clave pública PGP "promedio" usa una RSA módulo . Debido a que al menos el primer bit del módulo debe ser siempre 1, la longitud efectiva del módulo es un bit más corta. (La discusión técnica y matemática exacta detrás de esto es un poco más complicada, pero esto debería ser lo suficientemente bueno por ahora).
No sé qué tan comunes son los semiprimos (productos de dos números primos) en ese rango, pero seamos generosos y pongamos la probabilidad de que cualquier número aleatorio en ese rango sea un semiprime en 10 ^ -10. 10 ^ -10 es aproximadamente 2 ^ -33. Esta es la proporción de números naturales en el rango deseado a los módulos de RSA válidos reales en ese rango.
Por lo tanto, el efecto combinado es reducir efectivamente el número de módulos posibles en unos 34 bits en comparación con si solo tuviéramos que elegir un número de longitud suficiente al azar. (Debido a la magnitud de estos números, las fracciones decimales simplemente no son relevantes aquí).
Por lo tanto, pasamos de 2 ^ 2048 a 2 ^ 2014 (o más o menos) posibles módulos RSA.
Digamos que diez millones de claves se generan cada día. Esto es probablemente en el lado alto, pero nuevamente, estamos jugando generosamente. Nuevamente, eso es alrededor de 2 ^ 33 teclas. Digamos también que estamos haciendo esto durante 100 años, y solo nos importa si salen dos llaves para tener los mismos módulos (no necesitamos almacenarlos, ni compararlos entre sí, o cualquier otra cosa así, porque todo eso agrega una sobrecarga a nuestro proceso que habitualmente se ignora en la teoría criptográfica). 2 ^ 33 * 365 (días) * 100 (años) ~ 2 ^ 48. Hemos afeitado 48 bits adicionales efectivos, llegando a 2 ^ 1966. Incluso si asumimos billones de claves por día, eso solo se afeita en tres órdenes de magnitud adicionales (correspondientes a 30 bits) o menos.
Concluimos que la probabilidad de más de 100 años y suponiendo que correctamente generamos diez millones de claves por día, lo que lleva a que se generen dos claves al azar para tener el mismo módulo, por lo que se obtiene aproximadamente 2 ^ -1966 o 10 ^ -592. El número 2 ^ -1966 se puede comparar con ese para el año 2040, apenas podríamos contar hasta 2 ^ 138 en diez años . Es un largo camino hacia la curva exponencial de 2 ^ 138 a 2 ^ 1966, y aún tendríamos que hacer algo con cada número contado (como, por ejemplo, generar una clave RSA).
Incluso solo almacenando todos los módulos RSA de 2048 bits, suponiendo que la relación 10 ^ -10 mencionada anteriormente, tomaría aproximadamente 2 ^ 2015 * 2048/8 ~ 10 ^ 609 bytes (10 ^ 610 bits ) de almacenamiento. Si de alguna manera pudiéramos encontrar una manera de almacenar un bit por barión en todo el soobservable universo y acceda a todo ese almacenamiento de forma instantánea , entonces necesitaríamos solo un miserable de 10 ^ 530 universos para hacer esto.
Si no desea tomar la ruta fácil , entonces, por más difícil que sea, factorizando el módulo va a sea mucho, mucho más fácil que confiar en la posibilidad aleatoria de darle una clave duplicada. Y además del criptoanálisis de manguera de goma, factorizar en lugar de pura coincidencia aleatoria es la amenaza de la que debe preocuparse. Las cifras varían entre las diferentes estimaciones, pero en la actualidad, se estima que el RSA de 2048 bits proporciona unos 100-130 bits de seguridad (2 ^ 100 ~ 2 ^ 130 factor de trabajo) contra métodos conocidos de ataque, que por el momento es suficiente a menos que su modelo de amenaza incluya esfuerzos a largo plazo por parte de adversarios altamente financiados, en cuyo caso es posible que desee ir con un módulo de 3072-4096 bits (4096 bits RSA que proporcionan alrededor de 110-140 bits de seguridad, dependiendo de a quién le pregunte).
La respuesta aceptada es probablemente cierta, pero creo que merece más atención desde un punto de vista diferente.
Toda la seguridad del sistema depende del hecho de que el programa Debe ser capaz de generar todos y cada uno de estos 2 ** 254. números con más o menos probabilidad igual.
(El número específico aquí está "desactualizado", la parte relevante es que una generación de clave segura requiere una distribución uniforme).
Como seguimiento, es interesante aprender más sobre ataques con generadores de números aleatorios .
Y luego está esta pregunta: ¿Ejemplo de un backdoor enviado a un proyecto de código abierto?
Y finalmente en el blog de CloudFlare: Cómo la NSA (puede tener) poner una puerta trasera en la criptografía de RSA: Un manual técnico :
- Un error en un generador de números aleatorios permitió a las personas secuestrar a Hacker Cuentas de noticias.
- Se permite un generador de números aleatorios roto en Android atacantes para secuestrar miles de dólares en bitcoins.
- El La versión de OpenSSL en la distribución Debian tenía un número aleatorio Problema del generador que podría permitir a los atacantes adivinar claves privadas. creado en estos sistemas
Combinando lo anterior no es improbable que algunas organizaciones puedan, de hecho, tener la capacidad de generar una clave idéntica a una clave generada antes en otro lugar por otra persona. Es difícil poner un número en esta oportunidad, pero seguramente es más alto que "aproximadamente algo elevado al poder del infinito negativo".
Lea otras preguntas en las etiquetas pgp