La crittografia a chiave pubblica

La chiave pubblica

Era il 1976 quando Diffie ed Hellman pubblicarono uno studio dal titolo "New Directions in Cryptography" nel quale per primo veniva illustrato il concetto di cifrario a chiave pubblica. Tale concetto si basa su un'assunto fondamentale: che si possa identificare un sistema di cifratura che utilizzi due chiavi distinte ed indipendenti, una per cifrare ed una per decifrare; e che queste chiavi godano della proprietà che non solo siano sostanzialmente differenti tra loro, ma soprattutto che dalla conoscenza di una non si possa in alcun modo risalire alla conoscenza dell'altra ( il viceversa non è necessario ).
Con queste premesse Diffie ed Hellman mostrarono che è possibile costruire un sistema di crittografia nel quale le chiavi di cifratura possono tranquillamente essere rese pubbliche: ed anzi, nel quale si auspica proprio la loro pubblicazione in una specie di elenco centralizzato, simile ad un elenco del telefono, di modo che chiunque possa inviare un messaggio cifrato a qualsiasi destinatario compreso nell'elenco avendo la certezza che lui e lui solo possa decifrarne il testo.
Vediamo come funziona in pratica questo ingegnosissimo meccanismo. Supponiamo che esistano gli utenti A, B..., ognuno dei quali si sia dotato delle chiavi dirette ( di cifratura ) A_d, B_d... e delle chiavi inverse ( di decifratura ) A_i, B_i,...; le chiavi inverse sono mantenute rigorosamente segrete da ciascun legittimo proprietario, mentre le chiavi dirette sono pubblicate in un elenco di libera consultazione.
Supponiamo ora che A voglia mandare un messaggio a B. Egli non fa altro che cifrarlo con la chiave pubblica diretta di B, B_d, ed inviarlo al destinatario. Per definizione, solo B conosce la chiave inversa B_i che gli consente di decifrare il testo: nessun altro, neppure lo stesso A che ha operato la cifratura ha modo di conoscere la chiave B_i o di derivarla dalla conoscenza della chiave B_d. Pertanto il messaggio è completamente al sicuro, e solo B può leggerlo. Ma c'è di più: dicevo in apertura che i sistemi a chiave pubblica consentono di "firmare" i propri messaggi in modo non solo certo e dimostrabile, ma soprattutto non alterabile o falsificabile. Ecco come. Supponiamo che A voglia mandare un messaggio a B facendo in modi che B abbia l'assoluta certezza che sia proprio A ad originare il messaggio. Per far ciò, A dapprima cifra il testo con la propria chiave inversa A_i, dopodiché lo cifra nuovamente con la chiave pubblica di B, ovvero B_d. Il risultato è un messaggio che solamente B può leggere, perché lui solo possiede la propria chiave inversa B_i, ma fatto importante, non può che essere stato originato da A perché lui solo conosce la propria chiave diretta A_i, con la quale il testo è stato cifrato la prima volta. Per leggere il messaggio, B deve sottoporlo a due facili operazioni: una decifrazione fatta utilizzando la propria chiave inversa B_i, seguita da una seconda decifrazione fatta utilizzando la chiave diretta A_d di A ricavata dall'elenco pubblico. Diabolicamente semplice ed efficace! Con questo schema tutto il problema della gesione delle chiavi viene ovviamente a cadere: infatti le chiavi inverse di ciascun corrispondente restano sempre segrete e non vendono mai trasmesse, dato che ciascuno provvede a generare la propria. Anche in caso di sostituzione non vi sono molti problemi: una volta generata una nuova coppia di chiavi, l'utente deve semplicemente provvedere a sostituire la propria chiave pubblica nell'elenco generale che si suppone gestito da una qualche entità centralizzata.

Le funzioni a trabocchetto

La costruzione teorica elaborata da Diffie ed Hellman è molto bella ma ci si può chiedere come possa essere realizzata in pratica. Infatti essa non dà nessun indizio su come possa essere effettivamente costruito un sistema di cifratura asimmetrico basato su due chiavi indipendenti. Ma agli inizi del 1977 un gruppo di ricercatori del MIT formato da Rivest, Shamir e Adleman, basandosi su un precedente lavoro di Pohlig ed Hellman, riuscì ad identificare un algoritmo idoneo all'implementazione pratica dello schema proposto da Diffie ed Hellman. Tale algoritmo che divenne subito noto col nome di RSA dalle iniziali dei suoi ideatori in quanto sfrutta ad arte la complessità computazionale di alcuni problemi di teoria dei numeri per definire una speciale funzione non computazionalmente invertibile, mediante la quale costruire la chiave di cifratura e decifratura.
Una funzione come quella usata nell'algoritmo RSA ( che per la cronaca è coperto in USA da un brevetto esclusivo ) è stata definita pittorescamente "trapdoor function", ovvero "funzione a trabocchetto". Con questo termine si intende una funzione f(x) tale che dato un qualsiasi X è "facile" calcolare il valore diretto Y=f(X) ma dato un qualsiasi Y è impossibile calcolare il valore inverso X=f^-1(Y). Il perché una funzione si chiami "trabocchetto" è chiaro: essa funziona proprio come un trabocchetto, nel quele è facile entrare ma dal quale è impossibile tornare indietro a meno che non si conosca il "trucco" che apre la porta segreta. Da notare che ho racchiuso tra virgolette i termini "facile" e "impossibile" in quento essi non vanno intesi in senso assoluto ma in senso computazionale: ovvero il calcolo della funzione inversa è teoricamente possibile ma in pratica non si conosce alcun sistema efficiente per farlo, tanto che un potente elaboratore impiegerebbe qualche milione di anni per giungere al risultato. Da qui discende che il sistema RSA pur non essendo invulnerabile in senso teorico lo è in senso pratico, ed anzi in modo molto forte.
In particolare il gruppo del MIT ha scelto per la sua funzione trabocchetto un classico problema della Teoria dei Numeri che sembra essere computazionalmente intrattabile; quello della fattorizzazione dei numeri primi. In pratica, mentre esistono molti metodi assai veloci per decidere se un numero è primo, non si conosce alcun metodo veloce per scomporre un numero nei suoi fattori primi. Così data una coppia di numeri primi di qualche centinaio di cifre ciascuno è molto facile e veloce calcolare il loro prodotto, viceversa dato solo questo risultato la ricerca dei suoi fattori primi può durare realmente milioni di anni. Ecco dunque la nostra ideale funzione trabocchetto, facile da percorrere in un verso ma pressoché impossibile da percorrere nell'altro! Purtroppo non mi è possibile in questa sede il modo elegante in cui il problema della fattorizzazione è stato utilizzato da Rivest, Shamir e Adleman per realizzare una trasformazione crittografica non invertibile. La cosa ha a che vedere con l'elevamento a potenza e l'aritmetica modulare, e richiederebbe una trasformazione leggermente troppo tecnica per queste pagine. Il succo del discorso sta comunque nel fatto che una delle chiavi è appunto contruita da una coppia di numeri primi molto grandi ( qualche centinaia di cifre ) e l'altra dal loro prodotto.
Certo, oggi come oggi nessuno a dimostrato che il problema della fattorizzazione sia realmente intrattabile, e teoricamente esiste ancora la remota possibilità che prima o poi si trovi un algoritmo veloce che per la scomposizione in fattori primi. In tal caso tutta la costruzione dell'RSA ovviamente cadrebbe. Tuttavia nessuno ritiene realmente possibile che ciò avenga, e l'algoritmo RSA viene oggi considerato uno dei più sicuri disponibili.
C'è anche da dire che l'RSA non è il solo algoritmo di crittografia a chiave pubblica: nel corso degli anni sono state proposte diverse altre funzioni trabocchetto alcune delle quali ( ad esempio quella basata sul "problema del fusto" ) piuttosto ragionevoli da implementare in sistemi reali. Nessuno di questi sistemi alternativi ha tuttavia raggiunto l'affidabilità dell'RSA, anche perché gli stessi autori dell'RSA non hanno mancato di pubblicare sulla letteratura crittografica analisi approfondite di tali sistemi alternativi evidenziandone ogni minimo difetto. Comunque nella remota ipotesi che in futoro l'RSA dovesse rivelarsi intrinsecamente debole sarà sempre possibile ricorrere a qualcuno di questi altri sistemi, o eventualmente ad altri che verranno studiati. La strada è ormai aperta e la ricerca è ancora in corso.

La crittografia a chiave pubblica.

Il problema di trasmettere informazioni riservate con la sicurezza che il loro cadere in mani "avverse" non comporti "problemi" è uno dei classici problemi che i militari di tutti i tempi hanno affrontato. Uno degli approcci è quello di condividere una chiave segreta, che consente di cifrare e di decifrare i messaggi. Il problema è che se tale chiave cade in mani "avverse" la riservatezza delle comunicazione cifrate viene completamente a cadere. C'è chi sostiene che uno dei motivi della crisi tedesca nella seconda guerra mondiale sia stato la caduta in mani alleate del cifrario Enigma.

L'algoritmo di cifratura può essere assai robusto. Ma se il meccanismo prevede lo scambio della chiave, questo diventa il punto debole: è sufficiente intercettare la chiave per decifrare ogni messaggio.

La crittografia a chiave pubblica risolve proprio questo problema, e rende possibile risolvere tutti gli altri sopra elencati.

A base della crittografia a chiave pubblica è il fatto che esistono funzioni matematiche asimmetriche, tali per cui è molto più semplice calcolarle in una direzione che nell'altra.

Se un numero molto grande è il prodotto di due numeri primi molto grandi, è estremamente difficile ricavare i due numeri primi dall'analisi del loro prodotto.

Sapere che 35=5*7 non richiede grandi sforzi, ma quali sono i fattori di un numero di 200 cifre decimali?

"Estremamente" difficile significa che se i due numeri primi P e Q sono composti da 100 cifre ognuno, il prodotto di 200 cifre che risulta dalla loro moltiplicazione non può ricondurre a P e Q in meno di alcune migliaia di anni con il computer più potente oggi esistente.

La parte "pubblica" della chiave consiste del prodotto PQ di due numeri primi di grandi dimensioni e di un fattore X del prodotto XY tale che XY = 1mod ((p-1)(q-1)). La parte "privata" della chiave consiste nell'altro fattore Y.

Il mittente prende il proprio messaggio, lo trasforma in un numero considerando la sequenza di bit come rappresentazione di un numero binario, e lo eleva alla potenza X. Poi divide il risultato per il prodotto PQ e spedisce il resto di questa divisione, che costituisce il messaggio cifrato.

Il destinatario eleva il messaggio alla potenza Yesima e divide il risultato per PQ. Si può dimostrare che questo processo restituirà sempre il numero di partenza.

Ciò che rende la cosa dirompente, ed il motivo per cui il tutto viene chiamato "crittografia a chiave pubblica", è che si può tranquillamente rendere pubblico sia PQ che X, (mantenendo segreto Y) senza che esista la possibilità materiale di ricavare Y e quindi di decifrare il messaggio. Il problema della segretezza della chiave di cifratura sparisce. Non dovrò mai condividere con nessuno la chiave che mi consente di decifrare i messaggi che mi vengono inviati, e posso dare a tutti la chiave che genera i messaggi cifrati che solo io potrò decifrare.

La firma digitale .

Un ulteriore vantaggio di questo schema è la nozione di "firma digitale". Se voglio inviare un messaggio cifrato a Pippo, elevo il testo "in chiaro" alla X potenza utilizzando il numero X che Pippo ha reso pubblico, divido per il prodotto PQ che Pippo ha reso pubblico anch'esso, e spedisco il risultato.

Se però, prima di eseguire questi passaggi, elevo il testo alla MIA Y potenza (segreta) , e divido per il MIO prodotto PQ, dopo la decifratura il contenuto del messaggio sarà "garbage". A meno che non venga prelevata la mia chiave Pubblica ed elevato il messaggio alla MIA X potenza, in altre parole ... decifrato il messaggio che ho cifrato con la mia chiave privata utilizzando la mia chiave pubblica.

A questo punto, chi riceve il mio messaggio ha la prova che esso è decifrabile soltanto con la mia chiave pubblica. Ciò significa che esso è stato cifrato con la mia chiave segreta, e che, conseguentemente, IO ne sono l'autore.

Dopo quanto è stato brevemente sopra esposto, risulta chiara la risoluzione di una serie di problemi molto grossi. Un ulteriore dettaglio è l'utilizzo, a fini di performance tuning, di algoritmi "ibridi": cifro il messaggio con una crittografia a chiave segreta (p. Es. DES, TRIPLO DES o IDEA), che è più efficiente della crittografia a chiave pubblica. Prendo la chiave segreta, la cifro con algoritmi a chiave pubblica, metto la chiave così cifrata in testa al mio messaggio e invio il tutto. Il destinatario riceve il messaggio cifrato, usa la propria chiave segreta per decifrare la chiave condivisa (DES, TRIPLO DES o IDEA) che io ho utilizzato per cifrare il messaggio e usa la chiave condivisa per decifrare il messaggio.

Crittografia a chiave pubblica

Il problema storico della crittografia classica si può riassumere in questo modo: per potere cifrare un messaggio si deve scegliere una chiave (segreta) con cui effettuare la cifratura. Questa è difatti l'idea base della tecnica crittografica: mediante l'utilizzo di una chiave, rendere incomprensibili delle informazioni a chiunque non disponga di quella chiave. Se Alice vuole inviare il messaggio codificato al destinatario Mad Hatter, ha il problema di fare avere a quest'ultimo la chiave segreta, con la quale egli potrà decodificare il messaggio. Se però Mad Hatter sta all'altro capo del mondo e non c'è un canale sicuro per trasmettere la chiave, questo sistema non può funzionare, perché la chiave può essere intercettata.
Il problema viene risolto brillantemente dalla crittografia a chiave pubblica, alla cui base sta un'idea semplice e geniale. Ogni utente genera, mediante una funzione di PGP, una coppia di chiavi. L'algoritmo matematico che effettua questa operazione è tale che:

• un messaggio codificato con una chiave della coppia può essere decodificato solo con l'altra chiave della stessa coppia;

• non è materialmente possibile, data una chiave della coppia, ricavare l'altra. Ogni utente tiene per sé una chiave della propria coppia, denominata chiave segreta, e diffonde il più possibile l'altra, denominata chiave pubblica.
  Questo risolve tutti i problemi posti sopra:

• Privacy:
  Alice vuole inviare un messaggio a Mad Hatter, e codifica quel messaggio usando la chiave pubblica di quest'ultimo. Solo Mad Hatter, che ha la corrispondente chiave segreta, è in grado di decodificare e leggere il messaggio.

• Autenticazione del mittente
  Alice codifica il suo messaggio con la propria chiave privata. Chiunque, avendo accesso alla chiave pubblica di Alice, può decodificare quel messaggio. Se la decodifica riesce, si è allora sicuri che esso è stato scritto da Alice, l'unica a possedere la corrispondente chiave segreta. Alice ha posto la sua ìfirmaî elettronica sul messaggio.

• Autenticazione del mittente e del messaggio
  È possibile autenticare, facendo un passo in più, oltre al mittente anche il contenuto del messaggio. Alice effettua un ìhashingî del suo messaggio. Si tratta di una funzione unidirezionale, che a partire da un certo messaggio ricava un valore di lunghezza fissa, detto hash, che caratterizza il messaggio: una sorta di "e;checksum"e;. Se il messaggio viene alterato, l'hash non corrisponde più. Alice attacca allora in fondo al suo messaggio il corrispondente hash. Alice può codificare con la propria chiave privata ("e;firmare"e;) tutto l'insieme, oppure lasciare il messaggio vero e proprio in chiaro e firmare solo l'hash. Chiunque può decodificare l'insieme ricevuto o il solo hash con la chiave pubblica di Alice, ed è così sicuro del fatto che il messaggio proviene da quel mittente. Se inoltre, una volta effettuata la decodifica, messaggio ed hash si corrispondono, si è sicuri che nessuno dei due è stato alterato in qualche maniera. In pratica, la firma elettronica realizzata dal PGP effettua sempre l'autenticazione sia del mittente sia del messaggio. Essa ha dunque le stesse funzioni della firma ordinaria su un documento cartaceo.

• Trasmissione della chiave
  Col sistema di crittografia a chiave pubblica non c'è una sola chiave segreta usata per entrambe le funzioni di codifica e decodifica, per cui non si pone il problema di dovere trasmettere quella chiave. Ogni utente deve semplicemente tenere al sicuro la propria chiave segreta, e può diffondere senza alcun problema la propria chiave pubblica. Anzi, più questa viene diffusa e meglio è.
  Il PGP consente di effettuare tutte queste funzioni mediante semplici comandi. È possibile avere varie funzioni insieme. Due procedure comuni sono per esempio:

• (per la corrispondenza privata) firmare un messaggio e contemporaneamente codificarlo per un certo destinatario;

• (per i messaggi pubblici o privati) effettuare l'hash di un messaggio e firmarlo per autenticarne il mittente ed il contenuto, ma lasciando il messaggio stesso in chiaro; questa procedura viene comunemente chiamata firma in chiaro.