Chiavi pubbliche e private
Come accennato nell'introduzione, i sistemi crittografici tradizionali, sviluppati fin dall'antichità, hanno tutti in comune un problema molto grave: ogni partecipante alla comunicazione deve possedere una "chiave segreta", e se questa viene a conoscenza di persone fuori dal gruppo, tutte le comunicazioni che al suo interno si svolgono sono potenzialmente in pericolo.
In altri termini, il problema deriva dalla simmetria delle operazioni di codifica e decodifica, cioè dal fatto che le informazioni necessarie per una operazione (chiave segreta) lo sono anche per l'altra. La soluzione consiste nel trovare algoritmi crittografici che richiedano due diverse parti di informazione, nessuna delle quali, da sola, sia sufficiente ad instaurare la comunicazione. Una di esse può essere resa pubblica (chiave pubblica) mentre l'altra è tenuta segreta a tutti (chiave privata). Il processo di comunicazione che ne risulta è asimmetrico rispetto a codifica e decodifica.
Il primo esempio di algoritmo con doppia chiave è dovuto a Diffie ed Hellmann (DH, 1976), e il primo vero sistema crittografico asimmetrico è opera di Rivest, Shamir e Adleman (RSA, 1978). Entrambi si basano sugli stessi metodi matematici, le funzioni esponenziali modulo N, ed entrambi usano una chiave pubblica ed una privata. Per cercare di capirli è però bene notare subito che si basano su due idee generali molto diverse, tanto che utilizzare i solo concetti di chiave pubblica e privata per spiegare il loro funzionamento in termini generali, oltre a non servire molto genera anche confusione.
In questo settore infatti si nota una difficoltà a trovare analogie e metafore adeguate per spiegare i concetti quando non si voglia entrare nei dettagli matematici di ciascun particolare algoritmo e protocollo. Tenteremo di rimediare a questo, anche rischiando di presentare immagini un po' forzate, perché è significativo capire bene i concetti generali, cioè la parte relativa al protocollo, al di là ed indipendentemente dallo specifico algoritmo utilizzato per realizzare concretamente la comunicazione.
Per questo chiameremo i sistemi simili ad RSA sistemi a "coppia di chiavi opposte", mentre quelli simili a DH sistemi con "chiave unica a doppio profilo". Nei primi il sistema di comunicazione è veramente asimmetrico, nei secondi invece l'asimmetria viene usata solo inizialmente per costruire una chiave segreta unica per la coppia di utenti che stanno comunicando. Si può notare a questo proposito che Diffie ed Hellmann avevano proposto solo un modo protetto per scambiarsi una chiave, da usare con poi con altri sistemi crittografici, e non direttamente un nuovo sistema, che comunque è facilmente ricavabile dal loro lavoro, come è stato mostrato da ElGamal (1985).
Nel seguito spiegheremo i concetti usando la metafora delle chiavi e, contemporaneamente, la notazione matematica delle operazioni reali nei due sistemi. Queste sono, come abbiamo detto, gli esponenziali modulo N, che indicheremo, per semplicità e per non perdersi in dettagli che momentaneamente non hanno importanza, con la solita notazione Xy. Modulo N significa che si considerano solo i numeri interi da 0 ad (N-1), e che se un'operazione fornisce un valore che non cade in questo intervallo, si prende come risultato il resto della divisione per N del valore originale. Per il momento basti sapere che le operazioni modulo N di tipo diretto (addizione, moltiplicazione, elevamento a potenza) hanno tutte le stesse proprietà delle corrispondenti operazioni tra numeri interi, e che le due inverse della potenza, cioè radice e logaritmo, sono entrambe operazioni "difficili" nel senso che interessa in crittografia, perché non è noto alcun algoritmo efficiente per effettuarle.
In questo senso l'esponenziale modulo N è quello che si dice in crittografia una funzione unidirezionale (one-way function), cioè una funzione facilmente calcolabile la cui inversione però risulta praticamente impossibile. Si deve notare che in realtà non esiste alcuna dimostrazione dell'unidirezionalità delle particolari funzioni usate in crittografia, per cui è sempre possibile, ed avrebbe esito catastrofico, che in futuro si trovi un modo facile per invertire una data funzione, mettendo in pericolo tutte le comunicazioni svolte usando gli algoritmi crittografici che la impiegano.
Precisamente, in DH si usa una base nota B, si sceglie una chiave (privata) x da cui si crea una chiave (pubblica) Bx. Passare da Bx a x essendo nota la base B è l'operazione nota come logaritmo in base B, che in questo caso viene detto logaritmo discreto. In RSA invece si rende noto un esponente E, e si comunica il messaggio m (in forma numerica), non direttamente ma in forma mE. Risalire ad m partendo da mE quando E sia noto corrisponde all'operazione chiamata radice, che potremmo dire discreta. Diciamo "potremmo" perché in realtà il termine "radice" non viene mai utilizzato, esattamente come d'uso nell'algebra moderna, potendosi sostituire "radice E-esima" con "potenza 1/E-esima". Questo corrisponde al fatto che il problema della "radice discreta" può essere trasformato in un problema di calcolo del reciproco che a sua volta viene trasformato in un problema di scomposizione in fattori primi. Quindi, mentre tipicamente si trova scritto che per DH il problema difficile è il logaritmo discreto, per RSA si dice che il problema è la fattorizzazione, invece di dire che è la "radice discreta".
Il paragrafo precedente comunque rappresenta una digressione rispetto all'argomento in discussione, e non è necessario a comprendere quanto seguirà.
Veniamo a DH. La metafora in questo caso è un processo in cui due persone fabbricano assieme una chiave (e relativa serratura) da usare poi per chiudere e aprire uno scrigno per scambiarsi contenuti segreti. Si pensi a quelle (rare) chiavi con due profili dentati: uno viene fabbricato da una persona, l'altro dall'altra. Per esempio pensiamo che Alice e Bob (nomi tradizionali di persona tradizionali in crittografia) vogliano comunicare. In precedenza entrambi hanno fabbricato, a partire da chiavi "vergini", cioè senza profili, le loro "mezze chiavi" tutte uguali e le hanno distribuite in giro (chiavi pubbliche):
chiave-vergine => aggiunta-profilo-Alice => mezza-chiave-Alice
Per comunicare in modo sicuro con Bob, Alice prende dalla sua raccolta di mezze chiavi quella di Bob e ci aggiunge il suo profilo:
mezza-chiave-Bob => aggiunta-profilo-Alice => chiave-completa-Alice-Bob
Con questa potrà chiudere uno scrigno e spedirlo a Bob, senza mandargli assieme anche la chiave (cosa che comprometterebbe la sicurezza), perché Bob potrà ottenere la chiave completa nello stesso modo. Infatti basterà che prenda dalla raccolta di mezze chiavi quella di Alice e ci aggiunga il suo profilo:
mezza-chiave-Alice => aggiunta-profilo-Bob => chiave-completa-Alice-Bob
Naturalmente si deve supporre che solo Alice sia in grado di creare il suo profilo e lo stesso per Bob. Questo vuole dire che dalla chiave pubblica liberamente distribuita (mezza chiave, con un solo profilo) nessuno può risalire alla chiave privata (processo di creazione di quel profilo). Per restare nell'analogia, si può pensare che le chiavi vengano profilate usando una macchina in cui si impostano certe leve e bottoni, ma che non si sappia, guardando un profilo, trovare l'impostazione della macchina che lo produce. Il processo di fabbricazione diventa quindi una funzione unidirezionale, facile da fare ma difficile da invertire.
Vediamo ora come si presenta DH nella realtà. Le chiavi vergini sono rappresentate dal numero usualmente indicato con g, di cui tutti dispongono. Alice sceglie un numero segreto A (chiave segreta) , corrispondente al processo di profilatura, con cui produce le sue chiavi pubbliche profilando le chiavi vergini, cioè elevando g alla potenza A:
g => elevamento-a-potenza-A => gA
Il valore gA può essere pubblicamente distribuito, perché da esso e da g non si riesce a calcolare A (dalla mezza chiave non si può risalire al processo di profilatura). Questo perché il problema del logaritmo discreto è un problema difficile.
Per comunicare con Bob, Alice prende la sua chiave pubblica gB (mezza chiave), e ci applica il suo processo di profilatura, elevandola alla potenza A:
gB => elevamento-a-potenza-A => (gB)A=k
Ottiene in tal modo la chiave completa k, che può utilizzare con un ordinario sistema crittografico per spedire messaggi a Bob. Questo d'altra parte dispone della chiave pubblica di Alice, gA, ed elevandola alla potenza B, cioè applicandogli il suo processo di profilatura ottiene:
gA => elevamento-a-potenza-B => (gA)B=k
Questo perché il "processo di profilatura" è commutativo:
(gB)A=gBA=gAB=(gA)B
come per i normali numeri interi.
Riassumendo, Alice e Bob creano una chiave completa "di coppia" k=gAB, tenendo segreta a tutti, compreso il partner, la loro chiave privata A, o B, e scambiandosi solo le loro forme pubbliche gA e gB, da cui nessuno può risalire ad A e B perché il problema del logaritmo discreto è difficile.
Passiamo ora ad RSA. Qui la metafora necessaria è completamente diversa: non c'è creazione di alcuna "chiave di coppia" ma solo una persona, diciamo Alice, che crea una "coppia di chiavi" e ne distribuisce una, detta pubblica, che gli altri (che non nominiamo perché ora non ha importanza chi siano), possono usare per spedire messaggi criptati ad Alice, che li decifra con l'altra chiave, privata. In questo caso c'è completa asimmetria del processo, perché le chiavi sono entrambe di Alice, e servono solo per la spedizione a lei (in realtà servono anche per le spedizioni di Alice verso gli altri, non per criptare bensì per autenticare i messaggi, ma questo si vedrà in seguito).
Pensiamo quindi ad una serratura che possa girare in due versi opposti, diciamo a destra e a sinistra, usando due chiavi diverse, che chiamiamo chiave destra e chiave sinistra. Se una serratura è stata girata a destra da una certa chiave, solo la sua chiave opposta potrà farla tornare a sinistra: le chiavi formano quindi delle coppie corrispondenti. Lo scrigno risulterà aperto solo con la serratura in posizione centrale, mentre se è girata a destra o a sinistra risulterà chiuso. E' facile ora capire come può fare una persona, diciamo Bob, a spedire scrigni che solo Alice potrà aprire: basta che sia stata distribuita pubblicamente una delle due chiavi di Alice, per esempio la destra, con la quale Bob può chiudere lo scrigno girando la serratura a destra. Solo Alice, che dispone della chiave sinistra, rimasta privata, potrà aprire lo scrigno girando a sinistra la serratura.
Naturalmente anche qui si presuppone che non si possa, disponendo semplicemente di una chiave destra, costruire la sua corrispondente sinistra, altrimenti tutti potrebbero aprire la serratura. E' da notare inoltre che non c'è alcuna differenza concettuale tra le due chiavi, e si può scegliere ognuna delle due per essere resa pubblica o tenuta privata.
Arriviamo quindi alle reali funzioni usate in RSA. Le chiavi (di Alice) sono due numeri, di solito indicati con E, che sta per "Encription" (chiave pubblica), e D, che sta per "Decription" (chiave privata). L'operazione di girare la serratura dello scrigno contenente il messaggio m, è l'elevazione di m (il messaggio viene trasformato in numeri) alla potenza E o D. Il fatto che abbiano effetto opposto sulla serratura è matematicamente espresso da:
(mE)D=m
(mD)E=m
cioè una apre ciò che l'altra chiude.
Quindi Bob, per spedire ad Alice un messaggio che solo lei può capire, usa la sua chiave pubblica E per chiudere (criptare) m:
m => mE
Il messaggio mE non può essere interpretato da nessuno tranne Alice perché passare da mE ad m disponendo di E è esattamente il problema della radice discreta, che è difficile. Invece Alice può semplicemente aprire con la sua chiave D (decrittare):
mE => (mE)D=m
e recuperare il messaggio.
Già che ci siamo, possiamo facilmente vedere il sistema di autenticazione RSA. Abbiamo detto che tutti dispongono della chiave pubblica di Alice, la chiave destra. Se Alice chiude in uno scrigno un messaggio con la chiave sinistra, non potrà pensare che resti nascosto perché chiunque può aprirlo con la chiave destra che è pubblica. Il fatto però che la chiave destra apra lo scrigno garantisce che è stata Alice a chiuderlo, con la chiave sinistra privata di cui solo lei dispone. Se qualcuno volesse aprire e modificare il messaggio potrebbe farlo, però non riuscirebbe più a richiudere, a sinistra, lo scrigno.
In pratica Alice spedisce il messaggio m in chiaro, non criptato perché ora lo scopo non è nasconderlo, e di seguito ci mette mD, che viene chiamata firma digitale. Alla ricezione Bob eleva la firma mD alla potenza E:
(mD)E=m1
Il fatto che m=m1 vuol dire che il messaggio è integro e proviene da Alice: si è raggiunta quindi l'autenticazione del documento.
Con questo l'argomento è concluso. Naturalmente quanto sopra non spiega esattamente come e perché funzionino gli algoritmi di Diffie ed Hellmann, e quelli di Rivest, Shamir e Adleman, cosa alla quale saranno dedicati altri articoli, ma espone completamente i due protocolli alla loro base, quelli che abbiamo chiamato metodo della "chiave unica a doppio profilo" e della "coppia di chiavi opposte". La cosa veramente importante è il protocollo, perché gli specifici algoritmi potrebbero essere sostituiti non appena si trovassero delle altre funzioni con le necessarie proprietà.