En los pasos de generación de claves RSA, ¿qué sucede si dos entidades seleccionan un factor común para generar n (es decir, p*q1=n1 y p*q2=n2 ) que resulta en gcd(n1,n2) <> 1 ?
Esto llevará a un problema en el que todos pueden calcular el p y q , rompiendo así este esquema de cifrado:
gcd(n1,n2)=p
n1/p gives q1
n2/p gives q2
¿Cómo garantiza RSA que esto no suceda?
La protección se llama "suerte". La probabilidad de que ocurra un evento de este tipo es lo suficientemente baja como para que se pueda descuidar. Siempre que las claves RSA se generen correctamente.
En 2012, algunos investigadores realizaron un estudio interesante en el que recolectaron 11.5 millones de claves RSA disponibles públicamente ( por ejemplo, claves de certificados de servidor SSL). Descubrieron que algunas claves estaban ampliamente duplicadas (mi propio muestreo encontró lo mismo: aparentemente hay ADSL o módems de cable ampliamente implementados que alojan un servidor SSL, todos con el mismo par de claves pública / privada). También encontraron, y eso es lo que corresponde a su pregunta, que el hecho de compartir el factor entre distintas claves RSA era raro pero no desconocido. Esto demuestra el uso de un PRNG pobremente poblado.
De hecho, cualquier generación práctica de pares de claves RSA producirá primos aleatorios ejecutando un PRNG sembrado con cierta "aleatoriedad inicial" . Si esa semilla aleatoria inicial no tiene suficiente entropía, entonces el número de primos posibles que este generador puede producir es bajo. Por ejemplo, si la semilla tiene 40 bits de entropía, entonces es suficiente generar un millón de claves RSA para obtener una colisión (dos de estas claves utilizan un factor primo común). Más generalmente, si la semilla tiene bits de entropía n , todos deberían estar seguros siempre y cuando se generen menos de 2 n / 2 RSA . El PRNG adecuado apuntará a n = 128 o más.Si bien no hay necesidad de temer tal resultado con las claves RSA correctamente generadas, este hecho demuestra que una siembra de PRNG adecuada no es fácil y, lo que es más importante, es muy difícil determinar si un proceso de siembra dado es adecuado o no. Algunos sistemas integrados y máquinas virtuales corren mayor riesgo de no tener suficiente entropía "física" para trabajar.
Lea otras preguntas en las etiquetas public-key-infrastructure encryption rsa