Crittografia a chiave pubblica e curve ellittiche. Una panoramica per profani. Parte 1: basi di crittografia a singola e a doppia chiave
La #crittografia a chiave pubblica o a chiave asimmetrica è un'invenzione abbastanza recente. Ha meno di 50 anni. Prima avevamo solo una crittografia "classica", a chiave singola. Nella crittografia classica, la macchina cifrante utilizza la stessa chiave per cifrare e decifrare il messaggio. Questa chiave viene generata e condivisa tra le parti che devono scambiarsi i messaggi in maniera riservata, usando un canale di comunicazione non sicuro. Può essere anche una chiave usa e getta, generata, condivisa e usata per una singola sessione di scambio informazioni tra le due parti.
Questo approccio ha sempre avuto un ostacolo importante. La chiave deve essere condivisa prima tra le parti, usando un "Canale Sicuro", per poter essere usata per cifrare e decifrare i dati . Questo canale sicuro potrebbe non essere disponibile, oppure può avere dei costi molto elevati.
Whitfield Diffie e Martin Hellman negli anni '70 hanno inventato un algoritmo per risolvere il problema dello scambio chiavi utilizzando un "canale non sicuro". Un algoritmo decisamente innovativo. Questo algoritmo si basa su una cosiddetta "funzione trappola" o "funzione botola" (Trapdoor Function). Una operazione matematica molto semplice da percorrere in un verso, ma praticamente impossibile da invertire in tempi ragionevoli. Neppure usando risorse illimitate. Proprio come una botola, è molto semplice entrarci. Ma una volta entrati, è praticamente impossibile uscirne. In aritmetica abbiamo diversi problemi che presentano questa caratteristica. Uno di questi è il cosiddetto "problema del logaritmo inverso", utilizzato anche da Diffie e Hellman per i loro algoritmi di scambio chiavi.
L'aritmetica in modulo consiste nell'operare con numeri "mod r" (modulo r), dove r è un numero intero. Ovvero il risultato delle operazioni di base (addizioni, sottrazioni, moltiplicazioni, elevamenti a potenza, radici, inversi eccetera) viene sempre calcolato come resto della divisione per "r", detto appunto modulo. Un'operazione simile che chiunque fa quotidianamente è, per esempio, il calcolo dell'ora con l'orologio a lancette. L'ora indicata dalle lancette è sempre un numero "mod 12", ovvero un numero tra zero e 11. Passato mezzogiorno, l'ora indicata ricomincia da zero. Per esempio le "15 mod 12" sono le 3. Le "21 mod 12" sono le 9. E così via.
Vediamo una funzione botola tipica. Se prendo un numero A, un esponente X e un modulo r, posso scrivere:
A^X == B mod r
Si legge "A elevato a X è congruente (o coerente) con B mod r". Ci sono algoritmi molto efficienti e veloci per il calcolo di B, partendo da A, X e r. Anche quando questi numeri sono molto grandi. Da 500-600 cifre decimali ciascuno, per esempio. Invece non esistono algoritmi in grado di invertire l'operazione, ovvero dati A, B e r di calcolare X che soddisfi l'equazione.
LOG_A(B) == X mod r (Logaritmo in base A di B è coerente con X modulo r).
Anche altre "funzioni botola" possono essere utilizzate, come per esempio il prodotto tra due numeri primi molto grandi, da 250-300 cifre ciascuno. Moltiplicare tra loro questi numeri è molto semplice. Ma partendo da questo risultato, risalire ai due numeri primi di partenza è un'operazione impossibile da portare a termine in tempi brevi.
Recommended by LinkedIn
La crittografia a #chiavepubblica, o a chiave asimmetrica, si basa su problemi matematici come questi. Prima differenza con la crittografia "classica" a chiave singola: le chiavi non sono più associate a una o più sessione di scambio dati, ma agli attori. Ogni attore che partecipa allo scambio di informazioni cifrate ha la sua coppia di chiavi, chiave pubblica e chiave privata, personali. L'attore mantiene nel tempo le sue chiavi, senza aver mai bisogno di generarne altre. A meno che la chiave privata non venga compromessa. Oppure, col passare del tempo (e col progredire delle prestazioni delle macchine), la lunghezza delle chiavi non diventi insufficiente per garantire una robustezza e una sicurezza adeguate. In questo caso è meglio generarne una nuova coppia, magari più lunghe delle precedenti.
La chiave pubblica è, e deve essere, resa pubblica. Magari diffusa tramite elenchi pubblici, dove chiunque possa acquisirla e associarla con certezza all'attore proprietario.
La chiave privata invece deve essere tenuta riservata e nella disponibilità esclusiva del suo proprietario. La coppia di chiavi ha delle proprietà matematiche tali che ogni attore può, per esempio, cifrare un dato usando la chiave pubblica del destinatario. In questo modo il dato potrà essere decifrato esclusivamente usando la chiave privata del destinatario, corrispondente a quella pubblica usata per cifrarlo.
Prendiamo per esempio il problema dello scambio o condivisione di chiavi di cifratura di cui abbiamo parlato prima. Io posso generare una chiave di cifratura per una sessione e, per farla avere in modo sicuro alla mia controparte con la quale voglio scambiare dati cifrati, posso cifrarla usando la sua chiave pubblica. A questo punto gliela invio, cifrata. E sono sicuro che solo il legittimo destinatario, usando la chiave privata corrispondente, sarà in grado di estrarla correttamente. Ho quindi realizzato uno scambio di chiavi di cifratura, in maniera sicura, usando solo la chiave pubblica del destinatario.
Oppure posso realizzare la cosiddetta "#firmaDigitale" di un documento elettronico. Calcolo un hash, un "estratto" (digest) del documento e lo cifro usando la mia chiave privata. E mando questo risultato insieme al documento. Questo sarà la sua firma digitale. In questo modo chiunque potrà verificare autenticità e integrità del documento ricevuto usando la firma e la mia chiave pubblica. Dovrà ricalcolare l'estratto dal documento ricevuto, decifrare la firma con la mia chiave pubblica e confrontare i risultati.
In caso di confronto negativo, potrebbe significare che il messaggio è stato modificato dopo la firma. Oppure che la firma è stata falsificata. Ovvero non è stata generata con la chiave privata corrispondente alla chiave pubblica utilizzata per la verifica.
In caso positivo, il documento è integro (non è stato alterato dopo la firma) ed è autentico (posso essere stato solo io a firmarlo con la mia chiave privata). La firma digitale inoltre offre anche garanzia di "non ripudiabilità". Ovvero chi lo ha firmato, in futuro non potrà negare di averlo fatto. In quanto unico utilizzatore possibile di quella chiave privata. E' una conseguenza diretta dell'autenticità, ma aggiunge un'altra garanzia.
Nel prossimo articolo vedremo qualche dettaglio sull'algoritmo a chiave asimmetrica #RSA, e cosa sono e come funzionano le #curveEllittiche.
.
2yUn grosso contributo a DH lo diede anche Merkle per ammissione dello stesso Hellman: «The system (...) has since become known as 'Diffie-Hellman key exchange'. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie-Hellman-Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography.»