Considerate le varie lunghezze delle coppie di chiavi RSA (1024, 2048, 4096) quali sono le probabilità che due utenti abbiano generato la stessa chiave privata esatta?
Considerate le varie lunghezze delle coppie di chiavi RSA (1024, 2048, 4096) quali sono le probabilità che due utenti abbiano generato la stessa chiave privata esatta?
Innanzitutto, ciò che conta non è avere due chiavi private identiche, se uno dei numeri primi è lo stesso nel modulo (che fa parte della chiave pubblico ), è facile recuperare rapidamente la chiave privata completa.
( Aside - Breve primer RSA : in RSA per una chiave privata n bit, la chiave pubblica è composta da un esponente, in genere e = 65537 e un modulo, N, che è il prodotto di due numeri primi n / 2-bit La chiave privata è costituita dall'esponente privato d (calcolato da d = e -1 mod (p-1) (q-1) che viene trovato in modo efficiente utilizzando l'algoritmo euclideo esteso) e il modulo, N. La coppia pubblica consente la crittografia di un messaggio, m, in un testo cifrato, c, tramite l'elevazione a moduli: c = m e mod N, e il privato la chiave consente la decodifica tramite m = c d mod N. Questo funziona a causa di una parte fondamentale della teoria dei numeri: il teorema di Eulero e come calcolare i totienti.
Se due moduli condividono un fattore, puoi prendere il massimo comun divisore dei due moduli in modo efficiente (utilizzando l'algoritmo di Euclid) e trovare il fattore condiviso. Sia i due moduli condividono un fattore primo q, quindi N 1 = p 1 q e N 2 = p 2 q, quindi gcd (N 1 , N 2 ) = q. Con il fattore primo trovato, è banale trovare l'altro fattore primo (p 1 = N 1 / q) e ricreare l'esponente privato. Uno studio 2012 ha esaminato 4,7 milioni di moduli RSA distinti e ha trovato fattori condivisi in 12720 (cioè lo 0,3% di le 4,7 milioni di chiavi RSA trascinate dal web sono interrotte dalla loro analisi). (Il documento ha trovato anche molti altri problemi con RSA in pratica, come le chiavi condivise utilizzate su entità apparentemente diverse.)
Ora, la scelta di numeri primi identici è una probabilità estremamente bassa se la macchina ha un'elevata quantità di entropia iniziale e non vi è alcun difetto nella generazione del numero casuale. Entrambe queste ipotesi non sono sempre vere; vedi le chiavi di Debian OpenSSL del 2006-2008 e noti che molte persone creano le chiavi per sistemi su macchine (virtuali) nuove di zecca che non hanno avuto abbastanza tempo per stabilire un sacco di entropia.
Approssimativamente, la forza di un tasto a 1024 bit si basa sulla scelta dei due numeri primi a 512 bit che comprendono il modulo. Con il teorema dei numeri primi ci sono approssimativamente (2 512 / ln 2 512 - 2 511 / ln 2 511 ) ~ 10 151 numeri primi 512 bit distinti. Dal paradosso del compleanno, dovresti aspettarti di avere una collisione di un numero primo che mostri più di una volta con una probabilità del 50% circa, dopo aver generato sqrt (10 151 ) ~ 10 75 numeri primi distinti. Cioè se qualche governo generasse un miliardo di numeri primi a 512 bit al secondo per computer e usasse un miliardo di computer e facesse funzionare per un miliardo di anni avrebbe generato solo circa 10 34 numeri primi, e il la probabilità di una collisione con una chiave esterna sarebbe essenzialmente zero, la stessa possibilità di giocare a Powerball esattamente 10 volte in settimane consecutive e comprare esattamente un biglietto e vincere il jackpot ogni volta senza imbrogliare. (Non ha probabilità significative di una singola collisione principale fino a quasi 10 40 = 1000000000000000000000000000000000000000000 volte vengono generati più numeri primi).
Tuttavia, come mostra il documento del 2012, questo non è vero nel mondo reale poiché le chiavi RSA sono generate in pratica da metodi imperfetti ad almeno lo 0,3%.
Leggi altre domande sui tag rsa