Quanti numeri primi ci sono (disponibile per la crittografia RSA)?

Question

Sto sbagliando nel pensare che la sicurezza della crittografia RSA, in generale, è limitata dalla quantità di numeri primi conosciuti?

Per rompere (o creare) una chiave privata, è necessario combinare la coppia giusta di numeri primi.

È impossibile pubblicare un elenco di tutti i numeri primi nell'intervallo utilizzato da RSA? O quella lista è sufficientemente grande da rendere improbabile questo attacco di forza bruta? Non ci sarebbero numeri primi "comunemente usati"?

Answer 1

RSA non seleziona da un elenco di numeri primi noti: genera un nuovo numero molto grande, quindi applica un algoritmo per trovare un numero vicino che è quasi certamente primo. Vedi this useful description of large prime generation):

Il metodo standard per generare grandi numeri primi è prendere un numero casuale preselezionato della lunghezza desiderata, ad una prova di Fermat (meglio con la base 2 in quanto può essere ottimizzato per la velocità) e poi applicare un certo numero di test Miller-Rabin (a seconda della lunghezza e del tasso di errore consentito come 2-100) per ottenere un numero che è molto probabilmente un numero primo. .

(Si potrebbe chiedere perché, in quel caso, non stiamo utilizzando questo approccio, quando cerchiamo di trovare i numeri primi più grandi La risposta è che il più grande primo has over 17 million digits noto - ben al di là anche i numeri molto grandi tipicamente utilizzato in crittografia).

Per quanto riguarda le possibili collisioni, le dimensioni delle chiavi moderne (a seconda della sicurezza desiderata) vanno da 1024 a 4096, il che significa che i numeri primi vanno da 512 a 2048 bit. Ciò significa che i tuoi numeri primi sono dell'ordine di 2^512: più di 150 cifre.

Possiamo stimare molto approssimativamente la densità dei numeri primi usando 1/ln(n) (vedere here). Ciò significa che, tra questi numeri 10^150, ci sono approssimativamente 10^150/ln(10^150) numeri primi, che funziona a 2.8x10^147 numeri primi tra cui scegliere, sicuramente più di quello che potresti inserire in qualsiasi elenco !!

Quindi sì, il numero di numeri primi in quell'intervallo è incredibilmente enorme e le collisioni sono effettivamente impossibili. (Anche se hai generato un trilione di possibili numeri primi, formando una combinazione di settilioni, la probabilità che due di loro siano lo stesso numero primo sarebbe 10^-123).

Answer 2

I numeri primi da utilizzare in RSA non sono solo grandi. Deve essere di 10 cifre o può essere di 100 cifre. Ciò a cui mi riferisco non è in miliardi o trilioni, ma qualcosa oltre a ciò che è difficile da esprimere o persino immaginare.

Quindi per rispondere alla domanda, tali numeri non possono essere conosciuti numeri primi.

Answer 3

Come una nuova ricerca emerge la risposta alla tua domanda diventa più interessante. In un recente articolo "Imperfetto Avanti Segreto: come Diffie-Hellman fallisce nella pratica" di David Adrian et tutti trovati @https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf accessibili il 16/11/2015 i ricercatori mostrano che anche se ci sono probabilmente un numero sufficiente di numeri primi disponibili per 1024 della RSA set di chiavi bit ci sono gruppi di chiavi all'interno dell'intero set che sono più probabilità di essere utilizzate a causa dell'implementazione.

Stimiamo che anche nel caso a 1024 bit, i calcoli siano le risorse dello stato nazionale plausibili di .Un numero limitato di gruppi standardizzati o viene utilizzato da milioni di server; eseguire precomputazione per un singolo gruppo a 1024 bit consentirebbe passivo intercettazioni sul 18% dei siti HTTPS popolari, e un secondo gruppo sarebbe consentire la decodifica del traffico al 66% delle VPN IPsec e al 26% dei server SSH . Una lettura approfondita delle perdite pubblicate dalla NSA mostra che gli attacchi dell'agenzia alle VPN sono coerenti con l'aver raggiunto tale interruzione . Concludiamo che passare a metodi di scambio di chiavi più forti dovrebbe essere una priorità per la comunità di Internet.

La ricerca mostra anche un difetto in TLS che potrebbe consentire a un utente malintenzionato di eseguire il downgrade della crittografia a 512 bit.

Quindi in risposta alla tua domanda ci sono probabilmente una quantità sufficiente di numeri primi nella crittografia RSA su carta, ma in pratica c'è un problema di sicurezza se ti nascondi da uno stato nazione.