Come posso verificare la primalità di numeri estremamente grandi come quelli usati in RSA, in Linux?
RSA è garantito per l'utilizzo di numeri primi. In effetti, se i numeri non fossero numeri primi, le operazioni chiave di RSA semplicemente non funzionerebbero (con una probabilità schiacciante alta). Tuttavia, l'utilità della riga di comando di OpenSSL ha la capacità di verificare la primità di un numero utilizzando il test di primalità di Miller-Rabin, l'algoritmo di test standard per il controllo di primari di grandi dimensioni da utilizzare in crittografia:
OpenSSL> prime
No prime specified
options are
-hex hex
-checks <n> number of checks
-generate generate prime
-bits <n> number of bits
-safe safe prime
error in prime
OpenSSL> prime -generate -bits 256
315016830147073940139675761214468273143
OpenSSL> prime 315016830147073940139675761214468273143
ECFE08DCA281B26A5EDDE8DF7D2A33F7 is prime
OpenSSL> prime 10000000000000
9184E72A000 is not prime
Credo che il numero predefinito di controlli sia 64, ma puoi aumentarlo per migliorare la precisione utilizzando l'opzione -checks . Ogni controllo esegue un round di prova Miller-Rabin che individualmente ha una probabilità del 75% di rilevare che un numero composito è effettivamente composito. Specificamente, la possibilità di non identificare un numero composito come tale è 4 - n , dove n è il numero di round usati. Con il valore predefinito di 64 colpi, questo è 4 -64 , o 2 -128 . Per metterlo in prospettiva, se si inserisce un numero composito in 64 cicli di test di primalità della RM, la possibilità che sia falsamente etichettata come un numero primo è equivalente alla possibilità di indovinare correttamente una chiave di crittografia a 128 bit al primo tentativo. p>
Ho spiegato di più sui test di primalità in OpenSSL in un'altra risposta .