Newsgroup: it.comp.sicurezza.varie
Titolo: Come calcola pgp i numeri primi

GP genera un numero primo di n bit nel seguente modo:
1. PGP genera innanzitutto un numero binario casuale costituito da due 1 seguiti
da (n - 2) cifre binarie casuali.
2. PGP utilizza un algoritmo molto efficiente (chiamato algoritmo 'Fast
sieving') per determinare il numero casuale.
3. Se l'algoritmo determina che il numero casuale generato non è primo, trova il
successivo numero dispari.
4. Se l'algoritmo determina che il numero è primo, PGP stampa un punto (.) e
utilizza il teorema piccolo di Fermat per controllare la sua primalità.
L'algoritmo di Fermat elimina almeno il 50% dei numeri primi trovati. Ogni volta
che questo test ha successo PGP stampa un asterisco(*).
Questo è quello che so io, qualcuno sa darmi maggiori informazioni in proposito'


No. Ma la procedura che hai descritto mi sembra un po' strana:
1. generare un numero in questo modo credo che sia piuttosto inefficiente;
sarebbe più pratico generarlo come un numero piuttosto che come stringa di
cifre che poi devono essere convertite in numero.
2 e 4. L'algoritmo chiamato "crivello d'Eratostene" ("sieve" per gli
anglofili) serve per verificare o trovare i numeri primi ma la versione
"standard" è inutilizzabile per scopi pratici.
Normalmente conviene verificare che il candidato numero primo non sia
divisibile per i primi 50 o 100 numeri primi trovati con il crivello (o
tabulati), poi, piuttosto che applicare il piccolo teorema di Fermat,
conviene testare la primalità del numero usando Miller-Rabin (è un test
probabilistico) che nel dichiarare che un numero è primo ha una bassissima
probabilità di sbagliare: per esempio l'errore che si commette nel
dichiarare primo un numero da 500 bits dopo 10 iterazioni del test è
0,5^119=1,5*10^-36, inoltre MR ha questa particolarità:
se il numero viene dichiarato composto esso è certamente composto, se è
primo
esso viene sicuramente dichiarato primo; invece, se il numero è composto
esso potrebbe essere dichiarato primo (ma con una probabilità piuttosto
bassa).
Osservando l'archivio zippato del codice sorgente di PGP, ho trovato il file
bnprime.c che credo venga utilizzato per generare i numeri primi.
Viene prima utilizzato sieve, poi viene usato il test di MR utilizzando i
numeri primi 2, 3, 5, 7, 11, 13, 17. Il fatto di usare come base solo i
numeri primi non dà la sicurezza che viene raggiunta utilizzando come base
anche alcuni numeri casuali.
La procedura utilizzata è spiegata all'interno del file stesso.
Cristiano

Cristiano ha scritto:

Ti ringrazio.
Non avresti da consigliarmi qualche libro o link per approfondire.

Non avresti da consigliarmi qualche libro o link per approfondire.
Su PGP non saprei cosa dirti, ma considerato che non conosci nemmeno
la netiquette (non si quota un messaggio intero per aggiungere due
righe!), ti consiglierei senza dubbio una ricerca con parola chiave
"netiquette", in italiano, oppure se vuoi risparmiare tempo
www.extremenews.net
, sezione FAQ.
Ciao e buona lettura!
                  Giovy  (
gi...@globoweb.it
)    ICQ #  54911070
                       Gestore delle FAQ di it.tlc.cellulari.omnitel
       WebMaster di Extreme - The Site  
www.extremenews.net
Globoweb Internet Solutions - Team Member   
www.globoweb.it