Will all the key pairs that ssh-keygengenerates be unique (not taking collision into account at this point)?
Sì, ogni coppia di chiavi sarà unica, con ben oltre il 99,9999% di probabilità. Ciò è in gran parte dovuto alla dimensione dello spazio chiave e alla qualità del CSPRNG utilizzato (vedi sotto).
If yes, how does ssh-keygen assure that all key pairs that different people generate at different times are unique and do not end up being the same?
Non fornisce tali assicurazioni, ma è comunque garantito che sia comunque unico. Questo perché il sistema operativo utilizza un algoritmo CSPRNG (Generatore di numeri pseudo-casuali di numeri crittografati) di alta qualità che è molto più affidabile (il che significa, più imprevedibile) rispetto al PRNG immediato che si ottiene con la maggior parte delle lingue.
If no, on what factors does the uniqueness of a key pair depend? Other than key length space, and PRNG.
L'unicità proviene da CSPRNG , non da un PRNG "regolare". La differenza è la scelta di entropia.
Un PRNG prende semplicemente un seme (di solito "0" se un programmatore è pigro, o qualche misura arbitraria, come da time ()), rimescola i bit ogni volta che qualcosa chiede bit, quindi fa più mischiare. Solo "sembra" essere casuale finché non si osserva l'output per un certo periodo di tempo, a quel punto è possibile determinare (a) quale seme è stato utilizzato, e (b) il prossimo numero infinito di uscite che saranno osservate da quel particolare PRNG.
Un CSPRNG, al contrario, costruisce l'entropia più a lungo funziona. Lo fa prendendo letture periodiche da più dispositivi e applicando alcune astrazioni piuttosto complicate ai dati in arrivo per generare un pool di bit "casuali". Questo significa che se stai caricando un assaggio di Linux quando carichi questa risposta, le probabilità sono che alcuni bit di questa risposta ora fluttuano nel tuo entropy pool (fino a quando non vengono utilizzati, in ogni caso).
Logicamente, naturalmente, questi bit sono casuali nel senso che i computer non hanno effettivamente la capacità di fare cose "casuali" (seguono sempre con precisione le istruzioni date loro), ma sono comunque casuali nel senso che nessun algoritmo generico ideato da un uomo o da una macchina può sperare di determinare i numeri di entropia originali, che vengono costantemente reintegrati quando vengono generati numeri casuali.
Poiché i computer spesso ricevono diversi tipi di input dalla rete, dai dischi e così via in ordine abbastanza imprevedibile (a causa della latenza, tentativi, altre caratteristiche fisiche dell'hardware), sarebbe impossibile sincronizzare perfettamente due sistemi con il punto in cui anche il CSPRNG sarebbe sincronizzato. Allo stesso modo, sarebbe impossibile prevedere l'output di un CSPRNG a meno che non si stia effettuando il debug del kernel, e l'atto stesso di farlo, o il tentativo di riportare lo stato corrente, altererebbe lo stato di CSPRNG.
Naturalmente, la documentazione ufficiale è abbastanza chiara su questo: è tutto teorico, in quanto non abbiamo modo di dimostrare che nessuna chiave verrà mai generata due volte. Tuttavia, le probabilità sono così incredibilmente impilate da non trovare mai una chiave casuale che fosse un duplicato, tanto vale dire che è davvero impossibile.