Quante iterazioni di Rabin-Miller dovrebbero essere utilizzate per generare primati sicuri crittografici?

13

Sto generando un primo sicuro a 2048 bit per una chiave di tipo Diffie-Hellman, p tale che p e (p-1) / 2 siano entrambi primi.

Quali poche iterazioni di Rabin-Miller posso usare su p e (p-1) / 2 e sono ancora sicuro di una chiave crittograficamente strong? Nella ricerca che ho fatto ho sentito tutto da 6 a 64 iterazioni per numeri primi normali a 1024 bit, quindi sono un po 'confuso a questo punto. E una volta stabilito, il numero cambia se si genera un numero primo sicuro piuttosto che uno normale?

Il tempo di calcolo è un premio, quindi questa è una domanda pratica - fondamentalmente mi sto chiedendo come scoprire il minor numero possibile di test che riesco a farla franca pur mantenendo allo stesso tempo una sicurezza praticamente garantita.

    
posta jnm2 13.06.2011 - 13:24
fonte

3 risposte

4

( t = 40 ) le iterazioni di M-R con basi randomizzate non sono necessarie per p (1024, t) < (2 ^ -80). Non più di 1/4 di valori dispari compositi sono SPRP su base casuale. Il ((1/4) ^ t) è estremamente pessimista e i documenti DLP , < a href="http://www.ams.org/journals/mcom/1996-65-213/S0025-5718-96-00695-3/S0025-5718-96-00695-3.pdf"> RBJ (quest'ultimo dimostrando anche la congettura di DLP: p (k, t) < (1/4) ^ t, per k > = 2, t > = 1), combina i risultati che dimostrano che ( t = 3 ) le iterazioni sono sufficienti per produrre: p(1024, t) < 2^-80 . Vedi anche: Manuale di crittografia applicata ch.4, tabella.4.4. Questo stesso valore ( t = 3 ) viene utilizzato per i valori a 1024 bit nella libreria OpenSSL.

    
risposta data 10.03.2012 - 21:19
fonte
15

Ho appena risposto alla stessa domanda su StackOverflow, quindi duplicherò la mia risposta qui (non penso che la duplicazione sia la strada da percorrere, forse la domanda dovrebbe essere migrata):

Supponiamo che tu scelga un primo p selezionando valori casuali fino a quando non ne colpisci uno per cui Miller-Rabin dice: quello sembra un numero primo. Usi n al massimo per il test Miller-Rabin. (Per un cosiddetto "sicuro primo", le cose non sono cambiate, tranne che esegui due test annidati.)

La probabilità che un numero casuale di 1024 bit sia primo è circa 1/900. Ora, non vuoi fare nulla di stupido in modo da generare solo valori dispari (un intero pari a 1024 bit è garantito non-prime) e, più in generale, esegui solo il test di Miller-Rabin se il valore non è "ovviamente" non primo, cioè può essere diviso per un piccolo primo. Quindi finisci col provare circa 300 valori con Miller-Rabin prima di colpire un numero primo (in media). Quando il valore non è primo, Miller-Rabin lo rileverà con probabilità 3/4 ad ogni round, quindi il numero di round Miller-Rabin che eseguirai in media per un singolo valore non primo è 1+ (1/4 ) + (1/16) + ... = 4/3. Per i 300 valori, ciò significa circa 400 round di Miller-Rabin, indipendentemente da ciò che si sceglie per n .

( Modifica: in realtà, per un non-scelto a caso, Miller-Rabin funziona meglio di così (vedi la risposta di @ Brett) e il numero medio di round sarà più vicino a 300 di 400. Non cambia sostanzialmente la mia argomentazione.)

Quindi, se si seleziona n , ad esempio 40, il costo implicito da n è inferiore al 10% del costo computazionale totale. Il processo casuale di selezione del primo è dominato dal test sui non-primi, che non sono influenzati dal valore di n che scegli. Ho parlato qui di interi a 1024 bit; per i numeri più grandi la scelta di n è ancora meno importante dato che i numeri diventano più spartani all'aumentare delle dimensioni (per gli interi a 2048 bit, il "10%" diventa "5%").

Quindi puoi scegliere n = 40 e accontentarti (o almeno sapere che ridurre n non ti comprerà comunque molto). D'altra parte, usare un n superiore a 40 non ha senso, perché ciò ti porterebbe a probabilità inferiori al rischio di un semplice calcolo errato. I computer sono hardware, possono avere guasti casuali. Ad esempio, una funzione di test di primalità potrebbe restituire "vero" per un valore non primo poiché un raggio cosmico (una particella ad alta energia che sfreccia attraverso l'universo ad alta velocità) si trova a colpire il transistor giusto al momento giusto, invertendo il restituisce il valore da 0 ("false") a 1 ("true"). Questo è molto improbabile, ma non meno probabile della probabilità 2 -80 . Vedi questa risposta StackOverflow per qualche altro dettaglio. La linea di fondo è che, indipendentemente da come ti assicuri che un numero intero sia primo, hai ancora un elemento probabilistico inevitabile, e 40 round di Miller-Rabin ti danno già il meglio che puoi sperare.

Per riassumere, usa 40 colpi.

    
risposta data 13.06.2011 - 14:04
fonte
1

Il fattore più importante nell'accelerare Miller-Rabin è utilizzare un semplice test di divisibilità su un set di piccoli numeri primi, e solo ricorrendo a Miller-Rabin se questo passa.

If a random k-bit odd integer n is divisible by a small prime, it is less computationally expensive to rule out the candidate n by trial division than by using the Miller-Rabin test. Since the probability that a random integer n has a small prime divisor is relatively large, before applying the Miller-Rabin test, the candidate n should be tested for small divisors below a pre-determined bound B."

link (4.1.1)

    
risposta data 28.09.2017 - 17:38
fonte

Leggi altre domande sui tag