Nelle fasi di generazione della chiave RSA, cosa succede se due entità selezionano un fattore comune per generare n (cioè p*q1=n1 e p*q2=n2 ) risultante in gcd(n1,n2) <> 1 ?
Questo porterà a un problema che tutti possono calcolare p e q , rompendo così questo schema di crittografia:
gcd(n1,n2)=p
n1/p gives q1
n2/p gives q2
In che modo RSA garantisce che ciò non accada?
La protezione si chiama "fortuna". La probabilità che un tale evento si verifichi è sufficientemente bassa da poter essere trascurata. A condizione che le chiavi RSA siano generate correttamente.
Nel 2012 alcuni ricercatori hanno fatto uno studio interessante in cui hanno raccolto 11,5 milioni di chiavi RSA disponibili pubblicamente ( ad es. chiavi da certificati server SSL). Hanno scoperto che alcune chiavi erano ampiamente duplicate (il mio campionamento ha trovato lo stesso: apparentemente ci sono modem ADSL o via cavo ampiamente distribuiti che ospitano un server SSL, tutti con la stessa coppia di chiavi pubblica / privata). Hanno anche scoperto, ed è quello che corrisponde alla tua domanda, che la condivisione dei fattori tra le diverse chiavi RSA era rara ma non mai sentita. Ciò dimostra l'uso di un PRNG con scarsa capacità di semina.
In effetti, qualsiasi generazione di coppie di chiavi RSA pratiche produrrà numeri primi casuali eseguendo un PRNG seminato con un po 'di "casualità iniziale" . Se quel seme casuale iniziale non ha abbastanza entropia, allora il numero di possibili numeri primi che questo generatore può produrre è basso. Ad esempio, se il seme ha 40 bit di entropia, allora è sufficiente generare un milione di chiavi RSA o così per ottenere una collisione (due di queste chiavi utilizzano un fattore primo comune). Più in generale, se il seme ha entropia n bit, allora tutti dovrebbero essere al sicuro finché vengono generate meno di 2 chiavi n / 2 . Il PRNG corretto punta a n = 128 o più.
Sebbene non sia necessario temere un simile risultato con le chiavi RSA generate correttamente, questo fatto dimostra che un'adeguata semina PRNG non è facile e, soprattutto, è molto difficile accertare se un dato processo di semina sia adeguato o meno. Alcuni sistemi embedded e macchine virtuali rischiano di non avere abbastanza entropia "fisica" con cui lavorare.
Leggi altre domande sui tag encryption public-key-infrastructure rsa