==============================================================================
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
--------------------[ previous ]---[ index ]---[ next ]---------------------
--------------[ CRiTT0SiSTEMi A CHiAVE PUBBLiCA : [DH76] & RSA ]--------------
---------------------------------[ del0rean ]---------------------------------
---Introduzione
L'intento di questo articolo e' di trattare due dei piu' comuni crittosistemi
a chiave pubblica: Diffie & Hellman 76 [DH76] e RSA, descriverne il
"funzionamento" mediante l'illustrazione degli algoritmi che sono alla base di
questi due sistemi, le possibili implementazioni, le differenze.
Do per assunto che gran parte di Voi affezionati ( ;) ) lettori sappiate
cosa sia la crittografia a chiave pubblica, sia perche' prima di me
qualcun'altro ha gia' trattato l'argomento proprio su queste "colonne", sia
perche' suppongo che tutti voi facciate largo uso di PGP, che altro non e'
che il piu' noto software di crittografia a chiave pubblica.
---Cosa e' un crittosistema a chiave pubblica?
Prima di tutto un piccolo glossario:
Testo in chiaro ( o plaintext ) = testo da cifrare.
Testo cifrato ( o cyphertext o cryptogram ) = secondo voi? ;)
La cifratura avviene mediante un algoritmo ( cypher ) che fa uso di una o
piu' chiavi ( key ).
Un insieme finito di chiavi viene detto spazio delle chiavi ( keys space ).
Un crittosistema e', quindi, un set di chiavi e algoritmi.
La crittografia a chiave pubblica nasce nel 1976 ad opera di due
personaggi di nome Diffie - Hellman che introducono un concetto molto
semplice, ma geniale nello stesso tempo.
Lo schematizzo cosi:
E = encyphering key / pubblica D = decyphering key / privata
m = messaggio ( o plaintext )
per ogni m D( E(m) ) = m
- Applico al messaggio ( plaintext ) m la chiave E che e' pubblica ed
ottengo E(m).
- Solo il destinatario ( che aveva in precedenza distribuito
la sua E ) puo'ottenere nuovamente m, cioe' il messaggio in
chiaro applicando D, la chiave privata, a E(m) ottenendo cosi' m!
Questo tipo di procedimento viene detto asimmetrico, il motivo e'
facilmente intuibile, se paragonato ai crittosistemi simmetrici, dove la
chiave e' una sola ( talvolta ne possono esistere di diverse, ma comunque
ricalcolabili da una chiave "madre" ) uguale sia per il mittente sia per
il destinatario, da mantenere assolutamente segreta; non adatta, quindi,
al trasferimento di dati su canali poco sicuri,poiche' lo scambio della
chiave potrebbe essere intercettato e tutta la sicurezza di un crittosistema
"inattaccabile" andrebbe perduta.
La forza dei crittosistemi a chiave pubblica risiede nel fatto che la
funzione D(E(m)) = m e' _teoricamente_ invertibile, ma praticamente non lo
e', se si utilizzano chiavi ( quindi D ed E ) di grandezze dell'ordine di
150/200 cifre. Tutto cio' si basa su teorie dei numeri, in particolare
quelli primi, che attualmente sono molto difficili da fattorializzare,
poiche' richiedono molta potenza di calcolo, tempo, money, ma soprattutto
perche' non esistono algoritmi matematici in grado di fattorializzare
qualsiasi numero primo. Ovvio che parlo di numeri primi mooooooooolto grossi.
---Algebra modulare. - L'operatore "mod"
Come abbiamo visto questi algoritmi si basano su teorie matematiche ben
precise, in particolare teorie appartenenti alla matematica del finito o
discreta.
Per comprendere appieno il "segreto" che si nasconde dietro questi
concetti bisognerebbe conoscere un po' di algebra modulare, ma credo che
non sia questo il luogo per fare una lezione ;). Cmq per adesso ci basta
sapere la funzione dell'operatore - mod - .
Siano a e b due interi positivi. a mod b = resto intero della divisione
a/b. Esempio: 9 mod 4 = 1 oppure 5*5 mod 24 = 1 o anche 3*12 mod 50 = 36
Abbastanza chiaro! :)
---Diffie & Hellman [DH76]
Diffie & Hellman sono i teorizzatori della crittografia a chiave pubblica,
poi messa in pratica da tre scienziati di nome Rivest Shamir Adelmann (RSA).
Nel 1976 D&H inventarono il protocollo che mi accingo a descivere, che
effettivamente non e' proprio un algoritmo a chiave pubblica, bensi' un
pratico metodo per generare e scambiare chiavi da utilizzare ad esempio in
un crittosistema simmetrico.
Questo protocollo viene spesso assimilato ad altri a chiave pubblica poiche'
sostanzialmente e' un "predecessore", poiche' e' stato inventato dalle
stesse menti della crittografia a chiave pubblica e poiche', cosa piu'
importante, perche' fa uso di "numeri pubblici".
Ma andiamo con ordine e vediamo cosa intendo con "numeri pubblici" :).
Siano X e Y i due soggetti interessati allo scambio di dati.
Siano (ecco i famosi numeri :) ) "P" e "g" due numeri che soddisfino le
seguenti proprieta':
- P deve essere un numero primo abbastanza grande ( 100-200 cifre )
- g deve appartenere all'insieme dei numeri naturali e g < P
- (g,(P-1)) = 1 g e P primi fra loro
- P e g uguali per i due soggetti X ed Y ( o comunque non segreti )
X Y
sceglie a < P sceglie b < P
g^a mod P = H g^b mod P = K
H
invia H a Y ------------> /* _unico_ scambio */
<------------ invia K a X
K
K^a mod P H^b mod P
K^a mod P = CHIAVE = H^b mod P /* Tadaaaa! */
Una sorta di handshake, col vantaggio che un "terzo uomo nel mezzo" conosce
P, puo' sniffare g, H e K ma per risalire alla CHIAVE deve ricavare "a" o
"b" rispettivamente da H e K. Questo problema viene chiamato comunemente
"problema del logaritmo discreto".
Problema, questo, assai difficile da risolvere soprattutto se si usano
numeri primi molto elevati [ vedi Appendice ] .
---RSA ( Rivest Shamir Adelmann )
Algoritmo introdotto lo stesso anno del [DH76] che ha avuto molta fortuna.
Attualmente molto utilizzato worldwide, per esempio nel PGP, nel Netscape,
solo per citarne due, molto piu' utilizzato di altri risalenti alla stessa
"epoca" tipo El Gamal ( che nome fiiiigo ) oppure l'algo della curva
ellittica.
Procediamo!
Il mittente ha bisogno di due chiavi: quella pubblica ( [E]ncyphering ) e
quella privata ( [D]ecyphering ).
--Come si generano queste chiavi?
- si scelgono due numeri primi "p" e "q" molto grandi
- p != q ( p diverso da q )
- n = p*q
- f(n) = (p-1)*(q-1)
- si sceglie "e" naturale intero minore di f(n)
- (e,f(n)) = 1 cioe' devono essere primi tra loro
- si calcola "d" l'inverso di "e" oppure lo si ricava da e*d=1mod(p-1)(q-1)
Abbiamo cosi' ottenuto la coppia (n,e) che e' la chiave pubblica e "d" che
e' la chiave privata. Schematizzando:
- (n,e) chiave pubblica / Encyphering key
- d chiave privata / Decyphering key
A questo punto p,q,f(n) vanno distrutti, o comunque bisogna fare in modo
che non si possa risalire a questi tre numeretti, quindi numeri
assolutamente casuali. Accenno solamente al fatto che, numeri realmente
casuali non esistono (almeno nel mondo dei calcolatori) e quelli di cui
parliamo o di cui facciamo uso vengono definiti _pseudo casuali_ .
Non si puo' calcolare d conoscendo solo "n" e "a", o meglio, lo si puo'
fare ma bisognerebbe fattorializzare "n" per risalire a "p" e "q".
Se "n" e' notevolmente grande, come ho gia' detto, e' una bella impresa
sia perche' e' necessaria una potenza di calcolo inaudita e un tempo
enorme ( assimilabile all'eta' dell'universo ;) ) sia perche' _non_
esistono algoritmi _pubblici_ capaci di fattorializzare qualsiasi numero
primo. Forse qualche matematico assoldato da qualche governo sara' in
grado :) ( Conspiracy is my bread :) )
Dopo questo mio strippo procediamo nel mostrare come si cifra:
X Y
e' in possesso di
(n,e) di X con la quale cifra il
testo "t" ottenendo C
C = t^e mod n
C
<---------------- invia C
decifra con "d" C
t = C^d mod n
Non eccessivamente complesso, ma geniale !
Questo tipo di algoritmi asimmetrici danno un livello di sicurezza veramente
elevato, molto maggiore di uno simmetrico. Viene, infatti eliminato
il rischio che venga sniffata la chiave. Pero' non sono "perfetti" .
Diciamo che il problema fondamentale e' che, attualmente, sono troppo
lenti per essere usati per cifrare grossi messaggi o stream di dati.
Una soluzione "provvisoria" a questo problema e' quello di usare algoritmi
asimmetrici insieme a quelli simmetrici che sono molto piu' veloci ( DES -
BLOWFISH - IDEA ) e pratici. Sostanzialmente si usa l'RSA per scambiare le
chiavi dell'algoritmo simmetrico. Questo tipo di implementazione viene
usata in un gran numero di software e costituisce una buona soluzione per
le smart card.
Un altro possibile problema sarebbe quello dell'autenticazione. Chi mi
garantisce che la chiave pubblica che sto usando e' realmente della
persona a cui sto scrivendo? Beh... diciamo che questo problema si puo'
aggirare abbastanza agevolmente "firmando" le chiavi, anche con lo stesso
RSA... ma questo e' un altro discorso :)
--- Appendice
Abbiamo parlato di numeri primi molto grandi. Ma grandi quanto?
Attualmente ( Maggio / Giugno ) la chiave piu' piccola consigliata dai
laboratori RSA e' di 768/1024 bit. Perche' chiavi di questa grandezza?
Perche' il 3 Maggio, all'Eurocrypt '99 tenutosi a Praga, Shamir ha
annuciato di aver proggettato un device opto-elettronico chiamato TWINKLE:
"The Weizmann INstitute Key Locating Engine" ( Weizmann Institute in
Israele dove Shamir "opera" ;) ) potente quanto 100/1000 PC nel processo
di fattorizzazione di numeri primo definito " sieving " ( una sorta di
setaccio ). Questi chippettini che in quantita' costerebbero circa 5000$
l'uno, lavorerebbero, secondo il comunicato degli RSAlabs, alla folle
velocita' di 10GHz ( w000h0w! ) e sarebbero in grado di crackare una
chiave di 512 bit in 5/6 settimane, se usati in numero ed in parallelo.
Per crackare una chiave di 768 bit servirebbe 6000 volte questo tempo.
---Url
Ovviamente riguardo la crittografia esistono migliaia di siti che
andrebbero visitati, non li sto ad elencare, comunque un buon punto di
partenza e' www.rsa.com dove troverete una descrizione piu' dettagliata
del TWINKLE e del sieve process.
del0rean
Big Propz to : Orda people!, my s0ftpj peeps, bELFaghor : pheeeer this one! :P
--------------------[ previous ]---[ index ]---[ next ]---------------------
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
==============================================================================