¿Serán únicos todos los pares de claves que ssh-keygeng genera (no teniendo en cuenta la colisión en este punto)?
Sí, cada par de claves será único, con una probabilidad muy superior al 99.99999%. Esto se debe en gran medida al tamaño del espacio clave y la calidad del CSPRNG que se utiliza (ver más abajo).
En caso afirmativo, ¿cómo asegura ssh-keygen que todos los pares de claves que diferentes personas generan en diferentes momentos son únicos y no terminan siendo los mismos?
No ofrece tales garantías, pero de todos modos se garantiza que es único. Esto se debe a que el sistema operativo utiliza un algoritmo CSPRNG de alta calidad (Generador de números pseudoaleatorios criptográficamente seguros) que es mucho más confiable (es decir, más impredecible) que el PRNG listo para usar que se obtiene con la mayoría de los idiomas.
Si no, ¿de qué factores depende la singularidad de un par de claves? Aparte del espacio de longitud de clave, y PRNG.
La singularidad proviene de la CSPRNG , no un PRNG "regular". La diferencia es la elección de la entropía.
Un PRNG simplemente toma un valor de inicialización (generalmente "0" si un programador es perezoso, o alguna medida arbitraria, como la del tiempo ()), baraja los bits cada vez que algo pide bits y luego hace más barajadas. Solo "aparece" para ser aleatorio hasta que observe la salida durante un cierto período de tiempo, momento en el que puede determinar (a) qué semilla se usó, y (b) el siguiente número infinito de salidas que se observarán desde ese particular PRNG.
Un CSPRNG, por el contrario, genera entropía cuanto más se ejecuta. Para ello, toma lecturas periódicas de varios dispositivos y aplica algunas abstracciones bastante complicadas a los datos entrantes para generar un conjunto de bits "aleatorios". Esto significa que si está ejecutando una versión de Linux cuando cargó esta respuesta, es probable que algunos bits de esta respuesta estén ahora flotando en su grupo de entropía (hasta que se utilicen, al menos).
Lógicamente, por supuesto, estos bits son aleatorios en el sentido de que las computadoras realmente no tienen la capacidad de hacer cosas "aleatorias" (siempre siguen con precisión las instrucciones que se les dan), pero sin embargo son aleatorias en el sentido de que ningún algoritmo genérico ideado por un hombre o una máquina puede esperar determinar los números de entropía originales, que se repone constantemente a medida que se generan números aleatorios.
Dado que las computadoras a menudo reciben diferentes tipos de entrada de la red, discos, etc. en un orden bastante impredecible (debido a la latencia, los reintentos y otras características físicas del hardware), sería imposible que dos sistemas estuvieran perfectamente sincronizados con el punto donde el CSPRNG también estaría sincronizado. De manera similar, sería imposible predecir la salida de un CSPRNG a menos que literalmente estuviera depurando el kernel, y el simple hecho de hacerlo, o intentar informar el estado actual, alteraría el estado del CSPRNG.
Por supuesto, la documentación oficial es bastante clara al respecto: todo es teórico, ya que no tenemos forma de demostrar que nunca se generará una clave dos veces. Sin embargo, las probabilidades están tan increíblemente en contra de encontrar una clave aleatoria que fuera un duplicado que bien podría decirse que es realmente imposible.