Qual è la possibilità che due chiavi PGP siano esattamente identiche?

Se supponiamo che il tuo generatore di numeri casuali non sia completamente borked, allora

what's the chance of two PGP keys being exactly identical?

si può rispondere con all'incirca qualcosa che si innalza al potere dell'infinito negativo. O in altre parole: non succederà.

Possiamo risolvere questo problema ipotizzando che una chiave pubblica PGP "media" usi un RSA a 2048 bit modulo. Perché almeno il primo bit del modulo deve essere sempre 1, la lunghezza del modulo effettivo è un po 'più breve. (L'esatta discussione tecnica e matematica alla base di questo è un po 'più complicata, ma per ora dovrebbe essere abbastanza buono.)

Non so come i semiprimi comuni (prodotti di due numeri primi) siano in quell'intervallo, ma cerchiamo di essere generosi e mettiamo la probabilità che qualsiasi numero casuale in quell'intervallo sia semipromo a 10 ^ -10. 10 ^ -10 è circa 2 ^ -33. Questo è il rapporto tra numeri naturali nell'intervallo desiderato per i moduli RSA validi effettivi in quell'intervallo.

Quindi, l'effetto combinato è quello di ridurre efficacemente il numero di moduli possibili di circa 34 bit rispetto a se dovessimo solo scegliere un numero di lunghezza sufficiente a caso. (A causa della grandezza di questi numeri, le frazioni decimali semplicemente non sono rilevanti qui.)

Quindi, passiamo da 2 ^ 2048 a 2 ^ 2014 (o giù di lì) possibili moduli RSA.

Diciamo che dieci milioni di chiavi vengono generate ogni giorno. Questo è probabilmente il lato alto, ma di nuovo, stiamo giocando generosi. Di nuovo, si tratta di 2 ^ 33 tasti. Diciamo anche che lo facciamo da 100 anni, e ci interessa solo se due chiavi escono per avere gli stessi moduli (non abbiamo bisogno di memorizzarli, o confrontarli tra loro, o qualsiasi altra cosa del genere, perché tutto ciò aggiunge un sovraccarico al nostro processo che è normalmente ignorato nella teoria crittografica). 2 ^ 33 * 365 (giorni) * 100 (anni) ~ 2 ^ 48. Abbiamo rasato un ulteriore 48 bit efficace, uscendo al 2 ^ 1966. Anche se assumiamo miliardi di chiavi al giorno, che si rade solo di altri tre ordini di grandezza (corrispondenti a 30 bit) o giù di lì.

Concludiamo che la probabilità di, più di 100 anni e supponendo che correttamente generi dieci milioni di chiavi al giorno, portando a due chiavi generate casualmente per avere lo stesso modulo quindi esce a circa 2 ^ -1966 o 10 ^ -592. Il numero 2 ^ -1966 può essere paragonato a quello entro l'anno 2040, potremmo riuscire a malapena a contare fino a 2 ^ 138 in dieci anni . È molto lungo la curva esponenziale da 2 ^ 138 a 2 ^ 1966, e dovremmo ancora fare qualcosa con ogni numero contato (come, ad esempio, generare una chiave RSA).

Anche solo memorizzare tutti i moduli RSA a 2048 bit, assumendo il rapporto 10 ^ -10 sopra menzionato, richiederebbero circa 2 ^ 2015 * 2048/8 ~ 10 ^ 609 byte (10 ^ 610 bit ) di stoccaggio. Se in qualche modo potessimo trovare un modo per archiviare un bit per barione nell'intero universo osservabile e accedi a tutto lo spazio di archiviazione istantaneamente , quindi avremmo bisogno di solo un misero circa 10 ^ 530 universi per farlo.

Se non vuoi prendere il percorso facile , allora anche così difficile, il factoring del modulo sta per essere molto, molto più facile che affidarsi alla casualità per darti una chiave duplicata. E oltre alla crittoanalisi dei tubi di gomma, il factoring piuttosto che la pura coincidenza casuale è la minaccia di cui devi preoccuparti. Le cifre variano a seconda delle stime diverse, ma al momento RSA a 2048 bit viene stimato per fornire circa 100-130 bit di sicurezza (2 ^ 100 ~ 2 ^ 130 fattore di lavoro) contro i noti metodi di attacco, che per il momento sono sufficienti a meno che il tuo modello di minaccia includa sforzi a lungo termine da parte di avversari altamente finanziati, nel qual caso potresti voler seguire un modulo di 3072-4096 bit (4096 bit RSA che forniscono circa 110-140 bit di sicurezza, a seconda di chi si chiede).

La risposta accettata è probabilmente vera, ma penso che meriti un po 'più di attenzione da un altro punto di vista.

1. Qui è una critica della generazione di chiavi PGP che vale la pena di leggere.

The whole security of the system depends on the fact that the program must be capable of generating each and every one of these 2**254 numbers with more-or-less equal probability.

(Il numero specifico qui è "obsoleto", la parte rilevante è che una generazione di chiavi sicure richiede una distribuzione uniforme.)

2. Come follow up è interessante saperne di più sugli attacchi generatori di numeri casuali .

3. E poi c'è questa domanda: Esempio di una backdoor inviata a un progetto open source?

4. E infine sul blog CloudFlare: Come la NSA (potrebbe avere) mettere una backdoor nella crittografia di RSA: un primer tecnico :

• A flaw in a random number generator allowed people to hijack Hacker News accounts.
• A broken random number generator in Android allowed attackers to hijack thousands of dollars worth of bitcoins.
• The version of OpenSSL on the Debian distribution had a random number generator problem that could allow attackers to guess private keys created on these systems

Combinando quanto sopra non è improbabile che alcune organizzazioni possano effettivamente avere la capacità di generare una chiave identica a una chiave generata prima in un'altra posizione da qualcun altro. È difficile mettere un numero su questa possibilità, ma è sicuramente più alto di "circa qualcosa che è aumentato al potere dell'infinito negativo".