Newsgroup: it.comp.sicurezza.pgp
Titolo: come determina i 2 numeri primi PGP

Ho studiato la crittografia a chiave pubblica a partire
dalla lettura, avvenuta un paio di anni fa, di un
articolo del 1979, su una vecchia rivista di
"Le Scienze". L'argomento fa anche parte 
del programma di Sistemi che svolgo presso un 
Istituto Tecnico. 
Ho potuto personalmente appurare che tutti
gli algoritmi coinvolti nella crittografia a 
chiave pubblica si "chiudono" in tempi ragionevoli,
anche  se i due numeri primi (in forma
decimale)hanno un centinaio di cifre.
In laboratorio 2 anni fa  abbiamo
anche utilizzato la versione del programma
PGP all'epoca disponibile. Fra l'altro quella
versione sembrava non consentisse l'uso della 
chiave privata per autenticare i messaggi. La 
cosa fu aggirata con l'attivazione del 
cosiddetto "protocollo a conoscenza zero": Alice
genera una parola che viene crittata con la 
chiava pubblica di Bob,  il signor X decritta,
con la sua chiave privata,
quello che ha ricevuto da Alice 
e lo rispedisce ad Alice, se la parola che 
Alice riceve e' quella che ha generato  
in partenza, vuol dire che il signor X 
e' proprio Bob. 
Quello che non ho ancora capito chiaramente
e' come PGP, o programmi similari, determinano
i due numeri primi, ognuno a un centinaio di cifre
decimali. Vengono forse scelti da una tabella,
o calcolati al momento? Il calcolo contestuale
mi sembra oneroso in termini di tempi di
elaborazione. Mi sembra di aver capito che
puo' farsi ricorso a delle formule che 
consentono un calcolo rapido di un numero
che ha solo una probabilita' molto elevata
di essere primo. 
 
Grazie dell'aiuto.
_________________________________________________________________________
la tua email gratuita e per sempre su 
http://www.freemail.it
 (anche POP3)
--
Posted from 
qma...@hermes.evo.it
 [194.184.29.10] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Sono Giovanni,
mi ha risposto Luigi Funes sul newsgroup
it.scienza
Luigi mi ha scritto.
Premetto che non sono il piu' qualificato a risponderti,
ma spero di darti uno spunto da approfondire...
In genere tutti i programmi che devono verificare
la primalita' di un numero, usano il test di
Montecarlo. In pratica, non si pretende di avere la
dimostrazione matematica che il numero in esame sia primo,
ma ci si accontenta di avere una probabilita' sufficientemente
grande che lo sia.
L'agoritmo esatto non saprei descrivertelo a memoria,
ma lo puoi trovare per esempio su "The art of computer
programming - vol.2 Seminumerical algorithm" di Knuth.
E' un algoritmo molto bello, semplice e geniale.
Ad ogni iterazione la probabilita' che il numero sia primo
aumenta velocemente, percio' in pochissimo tempo
si ottiene una "quasi certezza", al punto che diventa molto piu'
probabile che si verifichi un errore nell'hardware anche del
computer piu' affidabile, piuttosto che il numero non sia primo.
Da notare che se il test fallisce, allora il numero e' sicuramente
fattorizzabile.
Luigi
Di rimando gli ho risposto.
In teoria dunque per far viaggiare i soldi
su Internet basta dunque un foglio elettronico.
Se poi si usa PGP, tutto diventa piu' veloce
ed accessibile a tutti.
E dunque penso che non si possa escludere, che
al mondo, non ci siano gia' gruppi di persone
che si scambiano soldi e merce nel modo in cui
ho descritto nel mio post con oggetto:
"Funziona cosi' E-cash ?"
(post presente anche su it.comp.sicurezza.pgp)
indipendentemente
dai siti ufficiali, e/o che non lo si possa fare
in futuro.
Tutto questo mi affascina e un po' mi preoccupa.
Tutti al mondo possono coniare moneta virtuale
Cosa significhera' tutto questo nei rapporti economici
futuri ?
Saluti da Giovanni.