Home / Indice sezione

www.icosaedro.it

 Crittografia - Algoritmi a chiavi asimmetriche

Questa sezione è il vero cuore di tutto il discorso affrontato in questa serie di documenti. Come anticipato, la scoperta degli algoritmi a chiavi asimmetriche ha aperto la strada all'impiego diffuso delle tecnologie crittografiche. Analizzeremo nel dettaglio gli algoritmi più importanti, cioè quello di Diffie-Hellman e l'RSA in modo da toccare con mano come funzionano le cose. Faremo anche degli esempi numerici e vedremo come questi algoritmi si usano per crittare i messaggi e per generare firme digitali.

Questa sezione è anche quella che richiede la sforzo maggiore da parte del lettore, ma una volta compresi gli argomenti esposti, tutta la materia dovrebbe risultare meno "eterea", e le sue applicazioni più chiare anche per chi poi dovrà solo usare questi strumenti.

Indice

Algoritmo di Diffie-Hellman

Partendo da una idea di Ralph Merkle, nel 1976 Whitfield Diffie e Martin Hellman (in breve: D.-H.) esplorarono le possibilità teoriche e pratiche per consentire a due soggetti lo scambio di una chiave segreta attraverso un canale di comunicazione insicuro (v. [DIHE76] e [RSASEC00]). L'impresa parrebbe a prima vista impossibile, addirittura contradditoria. Eppure Diffie ed Hellman ci riuscirono: non solo teorizzarono la fattibilità e le implicazioni teoriche dei sistemi crittografici a chiavi asimmetriche, ma idearono anche un algoritmo in grado di realizzare queste teorie. Rimaneva un solo difetto: in conformità al Principio di Conservazione delle Grane, il problema dello scambio delle chiavi segrete tipico degli algoritmi a chiavi simmetriche, nei sistemi a chiavi asimmetriche viene sostituito dal problema della certificazione delle chiavi pubbliche. Vedremo però che questo problema può essere superato, e che complessivamente la soluzione a chiavi asimmetriche si presta bene ad un uso di massa.

Il modo più semplice per capire il meccanismo della crittografia a chiavi asimmetriche forse consiste nel vedere come funziona l'algoritmo proposto da Diffie-Hellman. Gli interlocutori sono il signor Aldo e il signor Bruno, in breve A e B. Questi due signori non si conoscono, non si sono mai incontrati prima, e non hanno mai concordato alcuna chiave segreta. Tuttavia essi vogliono comunicare fra di loro scambiandosi messaggi crittati via, diciamo, email.

I due signori, così come ogni altro soggetto interessato alla riservatezza dei propri messaggi, hanno installato e configurato un programma di crittografia che implementa l'algoritmo di D.-H. L'installazione del programma comporta la generazione di una chiave casuale che il soggetto deve mantenere segreta: chiameremo queste chiavi segrete dei due signori S_A e S_B. Una volta generata la chiave segreta, il programma calcola una chiave pubblica usando una ben precisa formula: chiameremo queste chiavi pubbliche dei due signori P_A e P_B. Queste chiavi vengono calcolate una volta per tutte in fase di configurazione del programma di crittazione. Ogni soggetto riporrà la massima cura affinché la sua chiave segreta rimanga tale, mentre darà massima diffusione possibile alla sua chiave pubblica, per i motivi che vedremo. La tabella qui sotto riassume tutti questi elementi.

Mentre le chiavi segrete vengono generate come numeri casuali, le chiavi pubbliche vengono calcolate da queste con la formula:

dove r è una costante fissata nell'algoritmo, mentre le parentesi quadrate indicano il resto della divisione per un certo numero m, anch'esso fissato nell'algoritmo; ad esempio se fosse m=7 allora [10]=3, perché 10 diviso per 7 fa 1 con resto 3. In genere queste costanti si dovranno rendere molto grandi per rendere sicuro l'algoritmo; più avanti faremo un esempio usando numeri più facilmente trattabili con una normale calcolatrice.

Un bel giorno, il sig. Aldo decide di contattare il sig. Bruno via email: tutto ciò di cui ha bisogno è l'indirizzo email del sig. Bruno e la sua chiave pubblica, che potrebbe trovare, ad esempio nella sua home page. Aldo deve crittare il messaggio usando un qualche algoritmo a chiave simmetrica, come ad esempio il DES: a questo scopo il programma genera una chiave di crittazione K usando questa formula:

2)    K = [P_B^S_A]

che si legge: il resto della divisione modulo m della chiave pubblica di B elevato alla potenza della chiave segreta di A. Osserviamo che K è calcolata sulla base delle chiavi di Aldo e Bruno, e che di conseguenza è specifica della comunicazione tra questi due soggetti.

Il messaggio crittato giunge infine a Bruno. A prima vista sembra che Bruno non abbia alcuna possibilità di decrittare il messaggio: la chiave di decrittazione, K, non può calcolarla perché non conosce la chiave segreta che il signor Aldo ha usato nella formula 2. Ed è proprio qui che salta fuori la geniale trovata di D.-H.: essi notano infatti che

3)    [P_A^S_B] = K

cioè il signor Bruno, una volta procuratosi la chiave pubblica del signor Aldo, può calcolare anche lui la chiave K usando la propria chiave segreta. Questa magica uguaglianza non è immediata da verificare, ma lo faremo fra qualche riga.

Intanto osserviamo alcuni aspetti che ci interessano di più al di là dell'aspetto matematico. Il signor Aldo ha calcolato la chiave di crittazione K usando una informazione pubblica (la chiave pubblica di B) e una informazione segreta (la propria chiave privata), ha usato K per crittare il messaggio e quindi ha buttato via questo K che non gli servirà più.
Il signor Bruno è riuscito a ricalcolare la stessa chiave di crittazione K sfruttando una informazione pubblica (la chiave pubblica di A) e una informazione segreta (la propria chiave segreta) usando una formula del tutto simile: le formule 2 e 3 differiscono solo per lo scambio delle lettere A e B. Eppure il risultato delle due formule è lo stesso, e cioè la chiave di crittazione K.
Un eventuale intruso che avesse intercettato il messaggio, non sarebbe in grado di calcolare K: pur conoscendo le chiavi pubbliche dei due interlocutori, non conosce nessuna delle chiavi segrete coinvolte, e non esiste formula in grado di ovviare a questa carenza di informazioni.
Inoltre, il signor Bruno riuscirà a calcolare la chiave K con la quale è stato crittato il messaggio, ma a parte questo non potrà in alcun modo calcolare la chiave segreta di Aldo, nè tantomeno Aldo potrà calcolare la chiave segreta di Bruno.

Vediamo come si dimostra l'uguaglianza della equazione 3.

[P_A^S_B] =

e sostituendo P_A col suo valore dato dalla 1:

[ [r^S_A]^S_B] =

e applicando il risultato dell'appendice A.3:

[ r^S_AS_B ] =

e l'applicazione al contrario del risultato A.3 porta a:

[ [r^S_B]^S_A] = [ P_B^S_A ] = K

Questo risultato ottenuto da D.-H. ha dimostrato come sia possibile lo scambio della chiave di crittazione tra due soggetti attraverso un canale di comunicazione insicuro, ed inoltre ha dimostrato quanto sia semplice un algoritmo in grado di fare tutto ciò. Inoltre dal loro lavoro pionieristico è nata una nuova branca della crittografia: la crittografia a chiavi asimmetriche. Da questo primo risultato a oggi molti altri algoritmi sono stati proposti e sono entrati nell'uso corrente, il più famoso di questi essendo l'RSA.

         S , P                         S , P         
          A   B                         B   A        
           |                             |           
           |                             |           
           V                             V           
       +-------+                     +-------+       
       | D.-H. |    X                | D.-H. |       
M ---->|   +   |- - - - - - - - - - >|   +   |----> M
       |  DES  |                     |  DES  |       
       +-------+                     +-------+       

         Aldo                          Bruno         

Esempio: fissiamo le costanti dell'algoritmo come r=10, m=17. Con numeri così piccoli i calcoli sono più semplici. Assegnamo le chiavi segrete dei signori Aldo e Bruno e poi calcoliamo le chiavi pubbliche usando la formula 1, e riportiamo tutti i dati nella tabella qui sotto:

La chiave di crittazione calcolata da Aldo con la formula 2 è:

K = [14²] = 9

mentre Bruno userà la formula 3 e calcolerà:

[15³] = 9 = K

ottenendo quindi la stessa chiave, come previsto: in questo modo i nostri due signori riescono a concordare una chiave di crittazione comune attraverso un canale di comunicazione insicuro e senza avere mai passato realmente questa chiave attraverso il canale insicuro. Caro lettore, se a questo punto hai le idee un po' confuse e infinite perplessità... bhe, è normale la prima volta! Rileggi attentamente questo paragrafo e prova l'esempio prima di passare oltre.

L'algoritmo di Diffie-Hellman è tuttora valido e utilizzato in varie applicazioni, per cui la fatica che abbiamo fatto per comprenderlo non è stata vana.

Pare che i servizi segreti britannici avessero scoperto la crittografia a chiavi pubbliche alcuni anni prima del lavoro di Diffie ed Hellman, o almeno così emergerebbe dal libro di [ELLIS70] pubblicato dal CESG, l'autorità nazionale britannica per l'uso della crittografia. Questa possibilità viene avanzata anche da [SINGH99]. Comunque sia, e indipendentemente da cosa sia stato effettivamente scoperto e poi occultato, questi lavori non risultano poi avere avuto alcun seguito pratico.

Algoritmo RSA (Rivest-Shamir-Adleman)

Circa un anno dopo il lavoro di D.-H., tre giovani ricercatori del MIT, di nome Rivest, Shamir e Adleman, inventarono l'algoritmo a chiavi asimmetriche che prende il nome dalle loro iniziali (v. [RSA78] e [RSASEC00]). A differenza di quello di D.-H., RSA esegue anche la crittazione del messaggio. Vediamo come procede il calcolo:

Il signor Bruno configura il suo programma di crittazione: in questa fase vengono generati diversi valori. E' sottinteso che si tratta sempre di numeri interi e positivi.

1. Il programma genera a caso due numeri primi p,q diversi tra di loro.
2. Il programma sceglie a caso un numero K che sia primo rispetto a (p-1)*(q-1), cioè in modo che K non abbia fattori in comune con il numero (p-1)*(q-1) salvo l'unità.
3. Il programma sceglie a caso un numero S_B in modo che sia K*S_B-1 = t*(p-1)*(q-1) per un qualche numero t scelto a caso.

A questo punto il programma è configurato, e il signor Bruno può pubblicare la sua chiave pubblica P_B costituita dai due numeri p*q e K. Il numero S_B costituisce invece la chiave segreta di Bruno. I numeri p,q non serviranno più singolarmente, e il programma può scartarli, mentre terrà in memoria solo il loro prodotto.

Dobbiamo imporre anche un'altra restrizione: i messaggi M che si andranno a crittare con questo algoritmo devono essere sempre M<p e M<q. Come vedremo, nella pratica questa imposizione non costituisce alcuna limitazione all'algoritmo RSA.

Il signor Aldo desidera inviare un messaggio crittato al signor Bruno, in modo che solo il signor Bruno possa decrittarlo. Per crittare il messaggio M, il signor Aldo si procura la chiave pubblica del sig. Bruno, costituita dai numeri p*q e K, e quindi il suo programma di crittazione calcola il messaggio crittato X nel modo seguente:

4)    X = [M^K]

dove l'operazione di modulo si intende modulo p*q; tutte le operazioni di modulo che descriverò in questo paragrafo vanno intese modulo p*q. Osserviamo che Aldo ha usato entrambi i numeri che compongono la chiave pubblica di Bruno: K come esponente e p*q come modulo.

Quando il signor Bruno riceve il messaggio crittato X, per ottenere il messaggio in chiaro M esegue questo calcolo:

5)     [X^S_B] = M

dove, come abbiamo già detto, l'operazione di modulo si intende sempre modulo p*q. Quest'ultima uguaglianza è ciò che dovremo dimostrare adesso. Procediamo direttamente alla verifica:

[X^S_B] = [[M^K]^S_B]

Per via del risultato A.3 dell'appendice questa espressione si semplifica:

= [M^K*S_B]

Per via della condizione n. 3, si riscrive:

= [M^{t*(p-q)*(q-1)+1}]
= [M^{t*(p-1)*(q-1)}*M]
= [ [M^(p-1)*(q-1)]^t * [M] ]

Applichiamo il teorema di Eulero (v. appendice A.4) al primo fattore:

= [ 1^t * [M] ]
= [ [M] ]

Le due operazioni di modulo nidificate danno infine M, come si doveva dimostrare.

           P                             S           
            B                             B          
           |                             |           
           |                             |           
           V                             V           
       +-------+                     +-------+       
       |       |    X                |       |       
M ---->|  RSA  |- - - - - - - - - - >|  RSA  |----> M
       |       |                     |       |       
       +-------+                     +-------+       

         Aldo                          Bruno         

La figura 2 riassume tutti gli elementi coinvolti. Osserviamo che non abbiamo detto nulla sulle chiavi pubblica e segreta di Aldo: in effetti Aldo può inviare il messaggio crittato senza neppure avere configurato il proprio programma RSA.

Se Aldo vorrà a sua volta ricevere posta elettronica crittata con RSA da Bruno e da altri corrispondenti, dovrà generare le sue chiavi segreta S_A e privata P_A secondo le regole viste; ovviamente i numeri p,q,K generati dal programma di Aldo saranno diversi da quelli di Bruno (in effetti le chiavi vengono generate in modo casuale, per cui esiste la possibilità teorica che due soggetti possano avere due chiavi identiche; tuttavia lo spazio delle chiavi tipicamente utilizzato nella pratica è talmente ampio, e gli algoritmi di generazione di numeri casuali sono così sofisticati, che l'eventualità è estremamente remota).

Esempio: useremo numeri molto piccoli per facilitare i calcoli a mano, ben sapendo che nella realtà i programmi devono gestire numeri lunghi tipicamente un migliaio di cifre binarie, equivalenti a numeri decimali di oltre 300 cifre: questo dovrebbe spiegare perché a volte i tempi di calcolo sono un po' lunghetti...

Immedesimiamoci dunque nel programma di crittazione di Bruno, e percorriamo punto per punto tutti i passi necessari per generare le chiavi durante la fase di installazione.

1. Scegliamo i numeri primi p=3, q=11.
2. Siccome (p-1)*(q-1)=20, scegliamo K=3 che è primo rispetto a 20.
3. Per la chiave privata rimane S=((p-1)*(q-1)*t+1)/K=7 avendo posto t=1.

Dunque, riassumiamo le chiavi del sig. Bruno:

S_B = 7;
P_B = ( p*q=33, K=3 ).

Il signor Bruno avrà cura da una parte di mantenere segreta la chiave segreta, dall'altra parte renderà accessibile a chiunque la chiave pubblica, per esempio riproducendola nella propria corrispondenza, pubblicandola nel proprio sito WEB, o registrandola negli appositi server di chiavi.

Il signor Aldo intende inviare al sig. Bruno il seguente messaggio: M=16. Certo, si tratta di un messaggio ben striminzito ;-) Aldo si procura la chiave pubblica di Bruno ricavandola per esempio dalla sua home page. Per il calcolo del messaggio crittato X, Aldo usa i due numeri che compongono la chiave pubblica di Bruno: esegue prima l'elevamento a potenza K e poi estrae il resto modulo p*q:

X = [M^K] = [16³] = [4096] = 4

Quando Bruno riceve il messaggio crittato X=4 procede alla decrittazione:

[X^S_B] = [4⁷] = [16384] = 16 = M

e riottiene così il messaggio in chiaro inviatogli da Aldo.

Applicazione dell'RSA alla crittazione

Come abbiamo detto, esiste un limite alla dimensione del messaggio M; inoltre l'algoritmo RSA diventa tremendamente lento quando i numeri da trattare sono più lunghi di qualche migliaio di cifre binarie. Di conseguenza RSA viene utilizzato non per crittare il messaggio, ma per crittare la chiave di crittazione (detta chiave di sessione) usata per crittare il messaggio vero e proprio. Dunque nella realtà le cose funzionano così:

1. Aldo scrive un messaggio M.
2. Il programma di Aldo genera una chiave di sessione casuale C e la usa per crittare il messaggio M usando un algoritmo a chiavi simmetriche, per esempio DES.
3. Quindi Aldo invia a Bruno un messaggio di posta elettronica X che contiene la chiave di sessione C crittata con RSA, e il messaggio M crittato con DES. La figura 3 illustra la struttura in due parti del messaggio X risultante.

+--------------------------------+
| From: Aldo                     |
| To: Bruno                      |
| Subject: TOP SECRET!           |
+--------------------------------+
|            Parte 1:            |
|      chiave di sessione C      |
|        crittata con RSA        |
+--------------------------------+
|                                |
|                                |
|                                |
|            Parte 2:            |
|          messaggio M           |
|        crittato con DES        |
|                                |
|                                |
|                                |
+--------------------------------+

Una volta che il messaggio è arrivato, Bruno attiva il suo programma che esegue queste operazioni:

1. Dal messaggio di posta X ricava la parte che contiene la chiave di sessione crittata e il messaggio crittato.
2. Usa RSA per decrittare la parte della chiave di sessione, ed ottiene così la chiave di sessione in chiaro C.
3. Usa DES con la chiave C per decrittare la parte che contiene il messaggio, ed ottenere infine il messaggio in chiaro M.

Naturalmente tutti questi passaggi intricati vengono svolti automaticamente dal programma e, dettagli tecnici a parte, lo schema di figura 2 resta valido: l'unica differenza è che ora il messaggio X contiene il messaggio M crittato con DES e la chiave di sessione C crittata con RSA, e nelle due scatole c'è anche un algoritmo di crittazione a chiavi simmetriche.
Questo spiega perché nella realtà si usa RSA per gestire le chiavi, in combinazione con un altro algoritmo di crittazione a chiavi simmetriche che esegue la crittazione vera e propria. Questo concetto vale in generale per tutti gli algoritmi di crittazione a chiavi asimmetriche. Ecco perché i programmi permettono a volte di scegliere tra diversi algoritmi a chiavi asimmetriche e diversi algoritmi a chiavi simmetriche da usare in combinazione.

Applicazione dell'RSA alla firma digitale

La firma digitale di un messaggio, di un file o di un documento, permette di attestarne la paternità. Abbiamo visto che Bruno ha configurato il suo programma di crittazione RSA e ha generato le chiavi pubblica e privata. Usando la chiave pubblica di Bruno, chiunque può crittare un messaggio che solo Bruno potrà decrittare usando la corrispondente chiave privata, che solo Bruno conosce.

E' però vero anche il viceversa: Bruno può crittare un messaggio usando la sua chiave privata, e questo messaggio potrà essere decrittato da chiunque usando la sua chiave pubblica: siccome la chiave pubblica di Bruno è noto che appartiene a lui e solo a lui, è provato che il messaggio è stato crittato proprio da Bruno, unico a conoscere la chiave privata.

Sfortunatamente, il documento così firmato è crittato, e ciò può essere scomodo. Sarebbe più utile un meccanismo che separi la firma dal documento, in modo che il documento rimanga in chiaro. A questo scopo ritorna utile un algoritmo di digest. Vediamo come si produce la firma digitale:

1. Bruno scrive il suo messaggio M, sia esso un email, un articolo, un libro, un file generico. Poi Bruno vuole applicare la firma digitale a questo messaggio, in modo da attestarne la paternità.
2. Bruno attiva la funzione di firma digitale del suo programma, che calcola il digest D del messaggio M; il digest viene crittato con la chiave segreta di Bruno ottenendo un certo digest crittato D', che costituisce la firma digitale: D'=[D^S_B] calcolata come al solito modulo p*q.
3. Bruno invia il messaggio M in chiaro e la firma D' al destinatario via email, oppure lo pubblica in un sito WEB, o lo archivia in qualche posto. Nella figura 4 riporto lo schema di un messaggio di posta elettronica inviato da Bruno ad Aldo, e corredato della sua firma digitale.

+--------------------------------+
| From: Bruno                    |
| To: Aldo, Maria, Giovanni      |
| Subject: Grande festa!!!!!     |
+--------------------------------+
| Carissimi colleghi,            |
| grande festa hawaiana stasera  |
| a teatro! di rigore abito a    |
| tema!!!! non mancate!!         |
| e' alle 8 precise!             |
|                                |
|              Vi aspetto!       |
| - Bruno                        |
|                                |
+--------------------------------+
|                                |
|       Firma digitale D'        |
|                                |
+--------------------------------+

Siccome il documento M di Bruno rimane in chiaro, chiunque ne venga in possesso è in grado di leggerlo immediatamente. Il signor Aldo, dopo avere letto il messaggio M di Bruno, desidera verificarne l'autenticità. Aldo conosce già la chiave pubblica di Bruno, perché l'ha già usata negli esempi di prima :-) In caso contrario, Aldo dovrà procurarsi la chiave pubblica di Bruno facendo una ricerca nei vari archivi di chiavi, oppure andando a visitare la home page di Bruno; Bruno potrebbe anche avere inserito copia della sua chiave pubblica nel documento M stesso, fornendo così ai suoi lettori uno strumento in più per una verifica incrociata che quella chiave pubblica appartiene proprio a lui. Quindi, dato il messaggio M, la firma digitale D' e la chiave pubblica P_B di Bruno, Aldo può finalmente verificare l'autenticità della firma digitale. Vediamo allora come si verifica la firma digitale:

1. Aldo dà in pasto al suo programma il messaggio M, la firma digitale D' e la chiave pubblica di Bruno P_B=(p*q,K), e attiva la funzionalità di verifica della firma.
2. Il programma decritta la firma digitale D' usando la chiave pubblica P_B: il risultato è il digest D del messaggio: D=[D' ^K] modulo p*q.
3. Il programma ricalcola il digest del messaggio M e lo confronta col digest D. Se i due digest sono diversi il messaggio M sicuramente non è stato firmato da Bruno, ed è perciò un falso; se invece i due digest sono uguali, abbiamo la prova che la firma appartiene a Bruno con un elevatissimo, praticamente certo, livello di sicurezza.

Messaggi firmati e crittati

La crittazione e la firma digitale si possono combinare: in questo modo il destinatario non solo ottiene un messaggio riservato, ma può anche verificarne con certezza la provenienza. Concettualmente non c'è nulla di nuovo rispetto agli algoritmi visti finora, si tratta solo di combinare gli ingredienti:

1. Il messaggio M viene corredato di firma digitale, come al solito.
2. Il messaggio completo di firma digitale viene a sua volta crittato con una chiave di sessione casuale C.
3. Viene composto un messaggio costituito dalla chiave di sessione C crittata con un algoritmo a chiavi asimmetriche, seguito dal messaggio crittato, a sua volta costituito dal messaggio vero e proprio M e dalla firma digitale del mittente.

Il destinatario ottiene quindi un messaggio crittato e firmato dal mittente, avendo coniugato così la riservatezza e l'autenticazione.

Come falsificare la firma digitale

Per capire meglio il significato della firma digitale, vediamo come un eventuale impostore potrebbe falsificare la firma di Bruno. In fondo l'impresa non sembra poi così difficile: basta scrivere un messaggio e poi generare una firma che, decrittata con la chiave pubblica di Bruno, ritorni il digest del messaggio stesso.

Primo tentativo: innanzitutto, il falsario si procura un messaggio firmato da Bruno, lo modifica, ricalcola il digest: a questo punto non può andare avanti, perché non conosce la chiave privata di Bruno, e quindi non può crittare il digest per produrre una firma valida.

Riprova, sarai più fortunato: il falsario riparte dallo stesso messaggio e tenta di modificarlo solo leggermente, sperando che il digest non cambi e che quindi non ci sia bisogno di ricalcolare la firma digitale. Sfortunatamente per lui, sappiamo che gli algoritmi digest sono studiati proprio in modo che sia praticamente impossibile creare o modificare un messaggio in modo che il nuovo messaggio abbia un digest predeterminato, sicché anche questo tentativo è destinato a fallire.

Diabolico tentativo con forbici e colla: il falsario sa che Bruno ha prodotto negli anni una grande quantità di documenti, e quindi una grande quantità di firme digitali, ciascuna con un digest diverso. Il falsario si procura quindi tutti questi documenti e ne memorizza la firma digitale e il digest in essa contenuto: è un lavoro noioso, ma un computer potrebbe farlo senza protestare. Al termine, il falsario viene a disporre di una certa quantità di digest e delle corrispondenti versioni crittate (le firme). Se Bruno è molto prolifico e produce una media di un documento al secondo senza mai riposarsi, nell'arco di 100 anni avrà prodotto ben 3 miliardi di documenti firmati. Il falsario riesce in qualche modo a venire in possesso di tutti questi documenti, e si ritrova una collezione di digest tra cui cercare: adesso le probabilità che un messaggio scritto a casaccio abbia un digest corrispondente a uno di quelli in elenco è aumentata di un fattore 3 miliardi rispetto all'unico messaggio sul quale si era cimentato nel tentativo precedente. Il falsario crea dunque il suo documento fasullo in tutta libertà, ne calcola il digest, e si augura di trovare un digest uguale tra quelli collezionati; quindi copia la firma digitale corrispondente e la allega al documento, creando una specie di messaggio di Frankenstein: fatto!
Sfortunatamente per il falsario, il digest tipico è lungo non meno di 128 b, che significano circa 340 miliardi di miliardi di miliardi di miliardi di combinazioni diverse: il campione di "soli" 3 miliardi di digest collezionati è al confronto assolutamente insignificante, e la probabilità di trovare un digest uguale nella sua collezione è praticamente nulla.

L'unica vera speranza per il falsario sarebbe trovare una debolezza negli algoritmi crittografici che gli consenta di ridurre in modo decisivo lo spazio delle chiavi o, addirittura, di invertire gli algoritmi stessi. Gli algoritmi oggi in uso non sembrano soffrire di simili debolezze.

Algoritmo di ElGamal

Proposto da Taher ElGamal nel 1985 [ELGAMAL85], questo algoritmo è simile al Diffie-Hellman. L'agoritmo per la crittazione è piuttosto diverso da quello per la firma digitale. Cominciamo a vedere passo-passo come funziona l'algoritmo di ElGamal per la crittazione:

1. Si scelgono con opportuni criteri due numeri m,r con m primo e 0<r<m; tutte le operazioni indicate nell'algoritmo sono resto modulo m. Questi due parametri li considereremo fissi dell'algoritmo.
2. Le chiavi private vengono scelte in modo che S_A<m, S_B<m.
3. Le chiavi pubbliche vengono calcolate esattamente come per D.-H.:

   P_A=[r^S_A]
   P_B=[r^S_B]

Crittazione: ora, Aldo vuole inviare un messaggio M a Bruno: il suo programma sceglie un numero h<m con h relativamente primo con (m-1), e calcola:

x₁=[r^h]
x₂=[P_B^h M]

e quindi invia a Bruno il messaggio crittato X=(x₁,x₂) composto dai due numeri x₁ e x₂ appena calcolati.

Decrittazione: Ricevuto il messaggio X, Bruno lo decritta così:

[x₁^-S_B x₂] = M

[x₁^-S_B x₂]
= [r^{-h S_B} P_B^h M]
= [P_B^-h P_B^h M] = M

Notare che Bruno riesce a decrittare il messaggio usando le informazioni contenute nel messaggio crittato X e la propria chiave segreta S_B: a differenza di D.-H., Bruno non ha necessità di procurarsi anche la chiave pubblica di Aldo.

Naturalmente, deve essere M<m, ma sappiamo che questa non è una limitazione dato che in realtà M non sarà il vero messaggio, ma la chiave di crittazione usata per crittare il messaggio vero e proprio con un algoritmo a chiavi simmetriche, esattamente come abbiamo spiegato per l'algoritmo RSA.

Per quanto riguarda la firma digitale, l'algoritmo di ElGamal è piuttosto diverso dal precedente. In questo caso, Aldo genera la firma così:

Il programma sceglie due numeri h,v tali che 0<h<m-1 con h primo rispetto N, e inoltre, posto u=[r^h], risulti M congruente a S_A u + hv modulo (m-1), cioè esiste un n tale che M = S_A u + hv + n(m-1). I due numeri u,v costituiscono la firma digitale del documento M.

La verifica della firma consiste nel verificare l'uguaglianza

r^M = [P_A^u u^v]

Dimostrazione di questa equazione:

[P_A^u u^v]
= [r^S_Au u^v]
= [r^M+n(m-1)-hv r^hv]
= [r^M+n(m-1)]

Per il teorema di Fermat (A.5) rimane [r^M].

Il brevetto per questo algoritmo è scaduto nel 1997.

Algoritmo di Schnorr per la firma digitale

Il metodo di Schnorr [SCHNORR91] essenzialmente è uguale ad ElGamal salvo che per l'introduzione di una funzione digest D. Si procede così:

Il programma genera un intero h<m, e calcola u=[r^h], dove l'operazione di modulo è come al solito intesa modulo m.
Quindi si calcola il digest del messaggio M e del valore u insieme: d=D(M,u).
Poi si calcola v=[S_A d + h].
La firma digitale del messaggio M è la coppia v,e.

La verifica della firma consiste nel calcolare r^v e P_A.

Algoritmo DSA (Digital Signature Algorithm)

Nel 1994 il NIST, l'ente federale USA, nel quadro degli standard DSS (Digital Signature Standard) ha approvato l'algoritmo DSA come standard federale per la firma digitale (DSA non è utilizzabile per la crittazione). Usa un algoritmo inventato da David Kravitz e derivato da quello di Schnorr.

Generazione delle chiavi. La configurazione dell'algoritmo DSA richiede di fissare alcuni parametri e quindi di generare le chiavi segreta e pubblica:

• Si fissa un numero primo m da usare nelle operazioni di resto modulo, con 2⁵¹¹<m<2⁵¹².

• Si fissa un numero Q, divisore primo di m-1, con 2¹⁵⁹<Q<2¹⁶⁰.

• Si fissa un numero G, con 0<G<m-1.

• Si sceglie una chiave segreta S_A, con 0<S_A<Q.

• La chiave pubblica si calcola come P_A=G^S_A.

Generazione della firma digitale. Siccome nelle operazioni di modulo previste da questo algoritmo si usano moduli diversi nelle diverse fasi del calcolo, a differenza di quanto ho scritto finora qui indicherò esplicitamente il modulo impiegato come pedice della coppia di parentesi quadrate. Per la firma del messaggio M si procede così:

• Scegliere un numero h, con 0<h<Q.

• Calcolare u=[[G^h]_m]_Q.

• Determinare il valore di v risolvendo la relazione D(M) = [S_A u + h v]_Q, dove D() è la funzione digest scelta.

• La firma digitale di M è la coppia di numeri (u,v).

Verifica della firma digitale.

• Determinare w tale che w v = [1]_Q.

• Calcolare i = [D(M) w]_Q.

• Calcolare l = [u w]_Q.

• Calcolare t = [ [Gⁱ P_A]_m ]_Q.

• Verificare che sia t = u.

DSA è stato criticato dalla comunità crittografica per varie ragioni: la verifica della firma, una operazione senzaltro più comune della sua generazione, è particolarmente inefficiente ed è più lenta dalla generazione della firma stessa; l'iter di approvazione di questo standard da parte del NIST è stato piuttosto arbitrario e con un ampio contributo da parte di NSA; esistono alcuni particolari numeri primi che, se usati dal programma per la generazione della firma, possono indebolire l'algoritmo e, sebbene alcuni di questi numeri sono stati individuati, è plausibile che ve ne siano altri ancora da scoprire; il range dei parametri ammessi sembra piuttosto arbitrario.

Appendice

Dimostriamo alcune proprietà delle operazioni modulo m, dove m è un numero intero positivo. Tutti gli altri numeri che compaiono in forma simbolica sono numeri interi positivi.

• Per cominciare, la definizione la definizione di resto modulo m di un numero a:

  [a] = resto della divisione a/m

  Per non appesantire la notazione, ometterò di indicare il modulo, che dovrebbe essere chiaro dal contesto, altrimenti indicherò esplicitamente il modulo come pedice della prentesi quadrata:

  [a]_m = resto della divisione a/m

  Quindi, ad esempio, [17]₅=2 perché 2 è il resto della divisione di 17 per 5.

• Un altro modo di esprimere la stessa relazione:

  a = m*A + [a]

  dove A è la parte intera della divisione a/m.

• La prima proprietà che dimostreremo è piuttosto banale, ma ci serve per fare pratica con la notazione:

  A.1)    [[a] + [b]] = [a + b]

  La dimostrazione è diretta rappresentando i numeri a,b come a=m*A+[a], b=m*B+[b], essendo A,B le parti intere delle divisioni a/m,b/m:

  [[a] + [b]]
  = [ a - m*A + b - m*B ]

  Eseguendo la divisione per m del rimanente, i termini che hanno m come fattore danno contributo nullo al resto, e quindi si possono eliminare dall'espressione precedente. Quello che rimane dimostra il risultato.

• Vediamo come si comporta l'operazione di resto modulo nei confronti del prodotto, e dimostriamo che vale:

  A.2)    [a*b] = [ [a]*[b] ]

  La dimostrazione è diretta rappresentando i numeri a,b come a=m*A+[a], b=m*B+[b], essendo A,B le parti intere delle divisioni a/m,b/m:

  [a*b]
  = [ (m*A+[a])*(m*B+[b]) ]
  = [ m*m*A*B + m*A*[b] + m*B*[a] + [a]*[b] ]

  e siccome i termini che hanno m come fattore sono ovviamente divisibili per m, e danno quindi resto zero, rimane l'ultimo termine, come si voleva dimostrare.

• Vediamo come si comporta l'operazione di resto modulo rispetto all'elevamento a potenza, e dimostramo che (come sempre, t è intero):

  A.3)    [ [a]^t ] = [ a^t ]

  Anche qui si può procedere direttamente esprimendo [a]=a-m*A:

  [ [a]^t ]
  = [ (a - m*A)^t ]
  

  Lo sviluppo della potenza t del binomio produce molti termini che hanno m come uno dei fattori: questi termini sono divisibili per m, e quindi non contribuiscono al modulo. L'unico termine che rimane è a^t, come si voleva dimostrare.

• La funzione di Eulero E(m) di un numero intero m è il numero di numeri minori di m che non hanno fattori in comune con m, salvo che l'unità. Una definizione equivalente, forse di uso più immediato per i nostri scopi: E(m) è il numero di numeri minori di m il cui sviluppo in fattori primi non ha fattori in comune con lo sviluppo in fattori primi di m. Per esempio, E(6)=2 perché i numeri 1 e 5 non hanno fattori in comune con 6 eccetto che 1.

• Il teorema di Eulero, che non dimostreremo, afferma che se M,m sono due numeri interi senza fattori in comune, allora

  [ M^E(m) ]_m = 1

  dove E(m) è la funzione di Eulero calcolata in m, mentre l'operazione di resto modulo si intende modulo m.

• Osservazione 1: se p,q sono due numeri primi diversi, allora

  E(pq) = (p-1)(q-1)

  Per dimostrare questo risultato, ragioneremo al contrario: quanti sono i numeri minori di pq che hanno fattori in comune con pq? sono tutti e soli i multipli di p (in numero di q-1) e i multipli di q (in numero di p-1). I numeri minori di pq che non hanno fattori in comune con pq sono tutti i rimanenti, e cioè

  E(pq) = (pq-1) - (q-1) - (p-1) = (p-1)(q-1)

• Osservazione 2: se p è un numero primo, allora

  E(p) = p-1

  cioè tutti i numeri da 1 a p-1 non hanno fattori in comune con p. Dimostrazione: se un numero minore di p avesse un fattore in comune con p, allora p non sarebbe primo.

• Per dimostrare l'algoritmo RSA ci serve questo risultato: siano p,q due numeri primi diversi fra di loro, e sia M<p, M<q. Allora:

  A.4)    [M^(p-1)*(q-1)]_pq = 1

  La dimostrazione è diretta sfruttando i risultati precedenti:

  [M^(p-1)*(q-1)]_pq =

  e per l'osservazione 1 fatta prima,

  [M^E(pq)]_pq

  e siccome per l'ipotesi M<p, M<q, e i numeri p,q sono primi, ne segue che M non ha fattori in comune con pq, quindi si può applicare il teorema di Eulero, che dà il risultato.

• Per la dimostrazione dell'algoritmo di ElGamal ci serve questo risultato (noto come teorema di Fermat): se i numeri a,p con p primo non hanno fattori in comune, allora

  A.5)    [a^p-1]_p = 1

  Dimostrazione: è diretta per via della osservazione 2 sostituendo p-1 = E(p) ed applicando il teorema di Eulero.

Bibliografia

I documenti RFC, che costituiscono la documentazione ufficiale di Internet, sono reperibili in www.rfc-editor.org.

• [DIHE76] W. Diffie, M. Hellman, "New directions in cryptography", in "IEEE Transactions on Information Theory", vol. 22 (1976), pp. 644-654.
• [ELLIS70] J. H. Ellis, "The Possibility of Secure Non-Secret Digital Encryption", CESG Report (gennaio 1970)
• [RSA78] R. L. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", in "Communications of the ACM", vol. 21 (1978), n. 2, pp. 120-126.
• [RSASEC00] RSA Laboratories, "RSA Laboratories Frequently Asked Questions About Today's Cryptography, Version 4.1", RSA Security Inc., 2000 (disponibile su www.rsasecurity.com).
• [ELGAMAL85] T. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Transactions on Information Theory, v. IT-31, n. 4, luglio 1985, pp. 469-472.
• [SCHNORR91] C. Schnorr, "Efficient signature generation by smart cards", Journal of Cryptology, n. 4 (1991), pp. 161-174.
• [RFC2313] B. Kaliski, "PKCS #1: RSA Encryption Standard version 1.5", RFC 2313 (1998).
• [RFC1750] D. Eastlake, S. Crocker, J. Shiller, "Randomness Reccomendations for Security", RFC 1750 (1994).
• DSA: FIPS PUB 186.
• C. Giustozzi, A. Monti, E. Zimuel, "Segreti spie codici cifrati", Apogeo (1999), ISBN 88-7303-483-7.
• S. Singh, "Codici & Segreti", Rizzoli (1999), ISBN 88-17-86213-4.
• S. Garfinkel, "PGP: Pretty Good Privacy", O'Reilly & Associates, Inc. (1995), ISBN 1-56592-098-8.
• [SCHNEIER95] B. Schneier, "Applied Cryptography", John Wiley & Sons Inc. (1995), ISBN 0-471-11709-9.

Argomenti correlati

• tt - Mail e News Client - Programma che supporta la crittazione e la firma digitale.
• Le mie chiavi pubbliche.
• Virtual Private Network - Uso delle tecniche crittografiche per costruire canali di comunicazione sicuri.

Still no comments to this page. Use the Comments link above to add your contribute.