Newsgroup: it.comp.sicurezza.pgp
Titolo: Ancora su RSA e DSS/Diffie-Hellman

-----BEGIN PGP SIGNED MESSAGE-----
Non ci sono dubbi sul fatto che gli autori di PGP tendano ad
eliminare le chiavi RSA a favore delle DSS/DH.
Schumacher voleva mantenere la possibilita' di generare
chiavi RSa nella versioen internazionale, ma poi
misteriosamente alla fine l'ha disabilitata.
Penso che alla fine non sia riuscito a convincere
le controparti americane, ed anche il tempo eccessivo
per l'uscita della release internazionale (va bene
le difficolta' dello scanning, pero'...) possano
essere spieegate con il protarsi di "trattatative
su questo punto". Ma sono sono illazioni mie.
In ogni caso e' indispensabile gestire una fase
di transizione, in quanto la stragrande maggioranza
delle chiavi PGP esistenti e' RSA e non sara' facile
ne' breve sostituirle tutte, pensando oltre che ai
privati anche a servizi automatici come i remailer
per esempio.
Percio' almeno la possibilita' di *usare* le chiavi
RSA e' fondamentale che sia rimasta, e mi pare
troppo presto l'averla eliminata, a quanto leggo qui,
nelle versioni 5.5.x commerciali e freeware.
Ricordo ad ogni modo che la scelta di DSS/DH
non avviene per motivi di sicurezza ma
semmai per motivi di brevetto (Il brevetto del DH scade
quest'anno).
L'algoritmo RSA e quello DSS/DH hanno lo stesso grado di
sicurezza a parita' di lunghezza di chiavi.
Infatti l'algoritmo Diffie-Hellmann, il primo storicamente ad
aver implementato la crittografia a chiave pubblica nel 1976
(e che di fatto e' piuttosto un algoritmo di condivisione di
una chiave convenzionale), si basa sulla esponenziazione 
discreta (tutta la crittografia e' basata infatti sulla
aritmetica modulare). Per poter ricavare la chiave privata da
quella pubblica occorre allora fare l'operazione inversa,
chiamata logartimo discreto, che e' difficilissima da
effettuare e richiede migliaia di anni per lunghezze di chiavi
superiori al migliaio di cifre.
L'algoritmo RSA, inventato nel 1977 (un vero algoritmo di
crittografia a chiave publica, anche se poi di fatto in PGP
viene comunque impiegato per lo scambio di una chiave
convenzionale con la quale si codifica il messaggio),
invece e' basato su chiavi generate moltiplicando due numeri
primi. Per poter risalire alla chiave privata data la pubblica
occorrerebbe fattorizzare quest'ultima. Anche questa
operazione, ossia determinare i fattori primi di un numero con
migliaia di cifre richiede tempi e potenze di calcolo impossibili
agli effetti pratici.
Matematicamente, si puo' dimostrare che la potenza di calcolo
necessaria e' pressocche' uguale per l'operazione di logaritmo
discreto e per l'operazione di fattorizzazione, a parita' di
numero di cifre. I precisi affermano che occorra un 10% in piu'
per il logaritmo discreto.
L'algoritmo Diffie-Hellmann non era stato usato in precedenza
perche' presentava problemi teorici di sicurezza, non dal punto
di vista matematico, ma nel protocollo di scambio della chiave
convenzionale.
Nel 1992 ne e' stata realizzata una nuova versione che elimina
questo problema, ed e' quella in uso attualmente ed implementata
in PGP 5.0i.
Una nota sulla firma. PGP, ed in generale un algoritmo di
crittografia a chiave pubblica, permettono oltre alla
codifica/decofica anche la fondamentale funzione di
firma/verifica della firma. Ora, mentra RSA e' appunto un vero
e proprio algoritmo a chiave pubblica e quindi puo' essere
usato cosi' com'e' anche per firmare/verificare, il
Diffie-Hellman di per se' e' solo un protocollo di scambio
di una chiave convenzionale, per cui non permette da solo le
funzioni di firma e verifica della firma. Per questa ragione
nella implementazione in PGP gli e' stato affiancato
l'algoritmo "Digital Signature Standard" per la firma, e si
parla pertanto di algoritmo DSS/Diffie-Hellman.
Intrinsecamente, entrambi gli algoritmi RSA e
DSS/Diffie-Hellman possono generare chavi di qualunque
lunghezza. Solo per ragioni pratiche viene posto un
limite dal programma che li implementa, come PGP, in modo da
non permettere la generazione di chiavi troppo lunghe per
trattare le quali occorrerebbe un tempo eccessivamente lungo
sui computer di uso comune, come i PC.
Man mano che la potenza dell'hardware generalmente disponibile
aumenta, le versioni successive di PGP possono permettere
lunghezze maggiori. Il DSS/DH implementato in PGP 5.0i permette
di arrivare a chiavi di 4096; avendo fatto la scelta di non
generare piu' chiavi RSA, il limite alla lunghezza di queste
non e' ovviamente stato aggiornato e rimane percio' il 2048 di
PGP 2.6.3i.
Al momento attuale, si pensa che la lunghezza limite alla quale
una chiave si puo' cominciare a pensare che si possa forzare
e' 512.
Le chiavi di 1024 bit sono ancora impossibili da forzare,
occorrerebbero migliaia di anni per forzarne una anche con una
enorme rete dei migliori computer pensabili attualmente.
A maggior ragione quelle a 2048 (la difficolta' cresce
esponenzialmente, non linearmente, con la lunghezza).
Pero', volendo per ipotesi garantire la inviolabilita' di
messaggi codificati oggi anche per un futuro piu' o meno
remoto, allora piu' lunga e' la chiave e meglio e', se
questo non comporta rallentamenti eccessivi nelle operazioni.
Mi scuso con gli esperti di crittografia per le eventuali
imprecisioni contenute in questo messaggio, e sono a disposizioni
per ulteriori chiarimenti :-)
Ciao a tutti.
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQEVAwUBNIw3XsHFVX4P617JAQHhfQgAmsccavvPGQ4DY2p2g5DoixiSWQKTnMGM
XYRjxlnseJZj4QuvRwhk8W3vGQz5GC5jaw98N4DN5d4MK0t5y+m2+JJxE8K6uuyb
UNJSzuxM/gUoErgDtydZXi69j/pO94ZVd9U/vU+CRZJIfYqEI6lk5ACJL2BU3h/L
IDDEEeYn8lx3qJ24gAT3Tnr74SAFVJIcSbm1zxVebmhCUqEZvvTNYHVoVWvVoweg
oNMBf+hTrKZ7CcgwSezVSPfnR0XbCvVQNTKPA2qcKhtrvX48DsE0HduOhPqPFepH
43Tey95y1FetoxgLZGHPTjc8Iz7Mb6pZ3Bqr0zOC2pC4CF6hIA3Etw==
=fibV
-----END PGP SIGNATURE-----
Giorgio Chinnici <> Milano-Italy <> PGP Key available
mailto:
nim...@mail.serve.com
 <> 
http://www.serve.com/nimrod
   Mere words! Was there anything so real as words?
   (Oscar Wilde - The Picture of Dorian Gray)

anche decidere di utilizzare la libreria RSAREF, più efficiente.
Peccato che per farlo sotto Win 95 uno debba avere Microsoft Visual C
installato.


m.pal...@flashnet.peste.it
 wrote:
 >potranno decidere di abilitare la creazioni di chiavi RSA e potranno
 >anche decidere di utilizzare la libreria RSAREF, più efficiente.
La libreria veloce e` RSAREF.
-- 
ciao, | [Per rispondere togli "toglimi" dal mio indirizzo.]
Marco | * The Internet is full. Go away.  -- Joel Furr *

l'autorizzazione a Ståle Shumacher per distribuire PGP5.0i?
Ottimo quesito. Non lo so :-) Potrei scrivere a Schumacher
a tal proposito, magari se ha tempo mi risponde.
Chiarita la questione, mettere su una versione siffatta
su diversi siti pronta per essere scaricata non sarebbe un problema.
Ciao :-)
Giorgio Chinnici <> Milano-Italy <> PGP Key available
mailto:
nim...@mail.serve.com
 <> 
http://www.serve.com/nimrod
Visitate Nimrod/PGP 
http://www.serve.com/nimrod/pgp.html
Sito PGP in italiano costantemente aggiornato ed esteso

per il logaritmo discreto.
Ho forti dubbi che esista una dimostrazione rigorosa del fatto che i
due problemi <fattorizzazione> e <logaritmo discreto> hanno la stessa
complessita' intrinseca.
Dopotutto non si e' ancora riusciti a dimostrare che la complessita'
intrinseca del problema <fattorizzazione> e' esponenziale (traduzione:
dimostrare che non esistono algoritmi che risolvono il problema
<fattorizzazione di chiave pubblica RSA di lunghezza N> in un numero
di passi p(N) non inferiormente limitato da una funzione esponenziale
di N); si sa solo che i migliori algoritmi che sono stati trovati
hanno una complessita' esponenziale, ma questo non esclude che domani
mattina un matematico trovi un algoritmo di complessita' minore
(polinomiale, lineare...).
Probabilmente quello che dici tu e' che i migliori algoritmi noti per
la <fattorizzazione> e il <logaritmo discreto> hanno la stessa
complessita'.
----------------------------------------------------------------------
Marco Coletti
Network Administrator, Webmaster, Computer Consultant
PGP public key:
http://keys.pgp.com:11371/pks/lookup?op=get&exact=on&search=0x96A79061
finger://
mail.eurofin.it/marco.coletti
Fingerprint: 9F E5 80 61 F6 9F 05 2D  EA 53 6F 2D 82 8B C7 C2
----------------------------------------------------------------------