Per generare una coppia di chiavi RSA a 2048 bit, è necessario generare due numeri primi grandi con una lunghezza di 1024 bit. Per quanto ne so, OpenSSL sceglie un numero casuale a 1024 bit e inizia a cercare un numero primo attorno ad esso. Come può OpenSSL verificare se il numero è primo o meno così rapidamente?
Il test per la primalità è molto più semplice rispetto alla fattorizzazione integer.
Ci sono diversi modi per testare la primalità, come il deterministico Setaccio di Eratostene e il probabilistico Miller-Rabin test di primalità . OpenSSL utilizza diversi test per verificare la primalità. Prima sottopongono il numero ai controlli deterministici, tentando la divisione del candidato con un numero di piccoli numeri primi, poi una serie di test di primalità di Miller-Rabin. La stragrande maggioranza dei candidati primi vengono scartati con il primissimo test di primalità. Tutti i candidati che li superano sono soggetti a ulteriori round di test, ognuno dei quali aumenta la certezza che è un primo.
Quando si usano i test di Miller-Rabin, un numero composito ha una probabilità del 75% di essere rilevato come tale ad ogni round, quindi dopo soli 64 round di test, la probabilità che un numero composito non venga rilevato è un incredibile 2 < sup> -128 . In altre parole, il test ha una probabilità 4 -n di un falso negativo, dove n è il numero di round di test. Esistono anche molti modi molto più lenti per verificare se un numero è primo con completa certezza , come ad esempio Test di primalità di Agrawal-Kayal-Saxena , ma per scopi crittografici, essere davvero, davvero sicuro è sufficiente, quindi tendono a non essere usati.
Per impostazione predefinita, OpenSSL tende ad essere extra paranoico e fa alcuni altri test, in particolare per un primo sicuro . Quindi, quando viene trovato un primo, p , controlla anche se (p - 1) / 2 è primo. Questo è importante per specifiche applicazioni di numeri primi come Diffie-Hellman dove i primati sicuri prevengono certi attacchi.
Questo è possibile ad alta velocità perché verificare che un numero intero sia un numero primo con un margine di errore estremamente basso è significativamente più semplice rispetto al factoring, e perché i primi non sono che non comuni (è facile per trovare un gran numero di numeri primi incrementando un numero e testando la primalità). Il test di primalità di Miller-Rabin è molto efficiente. Il test dimostra la compositeness se x n - 1 ≢ 1 (mod n) (il Fermat test ), e testando se x (n-1) / 2 e (mod n) è una non banale radice quadrata di 1 mod n dove n è il numero intero sottoposto a test e x è un testimone casuale che soddisfa l'intervallo < em> 1 < x < n .
L'implementazione pseudocodice del test preso da Wikipedia è:
Input: n > 3, an odd integer to be tested for primality;
k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
pick random integer a in the range [2, n − 2]
x ← ad mod n
if x = 1 or x = n − 1 then
continue WitnessLoop
repeat r - 1 times:
x ← x2 mod n
if x = 1 then
return composite
if x = n − 1 then
continue WitnessLoop
return composite
return probably prime
Vedi questa risposta di Crypto.SE sulla generazione di chiavi RSA e FIPS 186-4 standard, sezione 5.1.
Leggi altre domande sui tag cryptography openssl rsa