L'algoritmo della crittografia a chiave pubblica

Pensieri in codice. Idee dal mondo del software a cura di Valerio Galano. Buongiorno a tutti e ben ritrovati per un nuovo episodio di Pensieri in codice, il podcast in cui parliamo di argomenti presi dal mondo del software, di internet e della programmazione. Come è andata questa settimana senza pensieri in codice? Spero che a voi sia mancato ascoltare il podcast almeno quanto a me è mancato registrarlo. Come molti di voi già sapranno però ho trascorso il weekend a Milano perché nella giornata di sabato ho preso parte a quella bellissima manifestazione che è il festival del podcasting dove ho incontrato tanta bella gente sia podcaster che appassionati e dove ho anche stretto tante nuove amicizie. Se mi seguite anche sui social saprete inoltre che ho avuto l’occasione di presentare Pensieri in codice sul palco del festival nella categoria podcast emergenti e per questo ringrazio davvero di cuore le oltre 380 persone che hanno speso un po’ del proprio tempo per andare su Instagram a mettere il cuoricino e votare il podcast e che quindi mi hanno permesso di essere sul palco. E visto che questo progetto mi sta regalando sempre più soddisfazioni ne approfitto anche per ringraziare tutti voi che ascoltate gli episodi ogni settimana ed in particolare gli utenti del gruppo Telegram che sono persone meravigliose e con le quali abbiamo spesso conversazioni interessanti sia a tema informatico che non. Se tu che stai ascoltando non ti sei ancora iscritto allora ti consiglio di farlo immediatamente. Trovi il link in descrizione o sul sito pensieriincodice.it oppure puoi semplicemente andare su Telegram e cercare il gruppo Pensieri in codice. Ora però basta con l’introduzione e con i ringraziamenti e passiamo all’argomento di oggi cioè la crittografia a chiave pubblica. Tantissimi non avranno mai sentito nominare questo algoritmo né con il nome di crittografia a chiave pubblica ma nemmeno come crittografia simmetrica o crittografia a chiave pubblico privata o crittografia a coppia di chiavi. Tutti nomi che in realtà indicano fondamentalmente la stessa cosa. Stiamo parlando però di uno di quegli algoritmi che tutti ma proprio tutti utilizziamo ogni giorno e senza saperlo. E questo perché al di là dei suoi impieghi un po’ più tecnici e professionali come l’autenticazione delle firme digitali ad esempio, la crittografia a chiave pubblica è alla base del protocollo HTTPS e cioè quel protocollo versione sicura del normale HTTP che ci permette di scambiare informazioni private sul web senza che queste possono essere carpite da malintenzionati. Cerchiamo però di procedere con ordine e proviamo a capire innanzitutto a cosa serve questo algoritmo e poi come funziona. Come abbiamo già accennato negli episodi numero 10 e 18 in cui abbiamo parlato rispettivamente di data bridge e di crittografia in generale, la trasmissione di informazioni sul web e su internet è assimilabile alla spedizione di una serie di cartoline tramite il servizio postale. Si parla cioè di messaggi che potranno facilmente essere letti da chiunque ne entri fisicamente in possesso. Postini, addetti allo smistamento, impiegati eccetera. Detto questo se i dati che io voglio spedire hanno un minimo di rilevanza per me allora preferirei che non fossero consultabili da chiunque e in un meccanismo del genere in effetti tutti i dati che vengono scambiati tra il nostro pc e un qualsiasi sito web o tra due smartphone o più in generale tra due qualsiasi dispositivi fisici o virtuali che siano, vengono prima suddivisi in pacchetti e poi spediti attraverso una serie di nodi che via via li indirizzeranno verso il giusto destinatario. Ciascuno di questi nodi, che poi in realtà sono i router, i server e tutti i dispositivi che formano la rete internet, avrà però la facoltà di leggere il messaggio che sta smistando esattamente come un postino può leggere una cartolina che sta consegnando. Mentre però di norma noi non siamo soliti scrivere informazioni delicate su di una cartolina, quando navighiamo sul web abbiamo spesso bisogno di trasmettere informazioni sensibili come dati personali, password, numeri di carta di credito e codici identificativi. Pensiamo solo a quando per la prima volta abbiamo effettuato un acquisto su Amazon. Oltre al nostro nome e indirizzo abbiamo anche inviato al sito il nostro numero di carta di credito e tutti i dati sufficienti ad accreditarci le somme corrispondenti ai nostri ordini. Se chiunque nel percorso tra il nostro pc e il server di Amazon avesse potuto leggere tali informazioni, probabilmente oggi ci ritroveremo con delle belle somme mancanti dai nostri conti correnti. E il motivo per cui ciò non è accaduto, per cui nessuno ha potuto rubare i nostri dati, è proprio quell’algoritmo così semplice e al tempo stesso geniale che prende il nome di crittografia a chiave pubblica. Per capire come funziona l’algoritmo di crittografia a chiave pubblica dobbiamo procedere per gradi e provare a suddividere il problema della trasmissione sicura in problemi più semplici. Questa è una tecnica ampiamente utilizzata in programmazione e noi ne abbiamo già parlato nell’episodio numero 1. Innanzitutto diciamo che possiamo simulare il problema della trasmissione di un dato immaginando tre persone in una stanza. In realtà le persone potrebbero essere anche 30 milioni, ma per il nostro esempio ne bastano 3 e le chiameremo A, B e C. La persona A si trova nella condizione di dover comunicare a B il proprio numero di carta di credito ma senza farlo sapere a C. Purtroppo per lei però non può né scriverlo né bisbigliarlo all’orecchio di B. L’unica possibilità che ha è quella di parlare ad alta voce in modo che tutti nella stanza possano sentire. In questo esempio A rappresenta il nostro computer, B è il server di Amazon a cui dobbiamo inviare i nostri dati e C rappresenta il resto dei nodi del mondo che non deve in alcun modo poter intercettare tali dati. Bene, nel caso descritto il metodo più semplice per inviare il numero da A a B senza che C possa appropriarsene è quello di pronunciare il numero ad alta voce modificandolo secondo un criterio che solo A e B condividono, quindi in pratica criptandolo. Ad esempio per semplicità fingiamo che il numero di carta di credito da trasmettere sia 150. Per criptarlo supponiamo che A e B sappiano che il numero verrà inviato sommandovi la cifra 25. In questo caso A potrà pronunciare ad alta voce il numero 175 e B saprà che a questo numero dovrà sottrarre il numero concordato e quindi il vero valore sarà 150. In questo tipo di scambio di informazioni il numero concordato frammittente e destinatario che nel nostro esempio è 25 viene definito segreto condiviso. La persona C avrà dunque anche gli sentito pronunciare il numero 175 ma non essendo a conoscenza del segreto condiviso non saprà come decifrare l’informazione carpita e quindi non la potrà utilizzare. Ovviamente nella realtà i meccanismi di trasformazione dei dati sono molto più complessi però la logica di base della criptografia è quella descritta finora e la criptografia applicata al protocollo HTTP, cioè quel protocollo utilizzato dai browser per navigare sul web, ci porta al protocollo HTTPS che rende possibile interagire con i vari siti criptando la maggior parte delle informazioni trasmesse. Se il ragionamento fin qui risulta chiaro possiamo provare a salire di livello e tentare di risolvere un problema un tantino più complesso. Infatti se è pur vero che con quanto abbiamo visto nell’esempio precedente siamo in grado di criptare le comunicazioni tra due nodi abbiamo però dato per scontato che essi si conoscessero già e avessero avuto la possibilità di accordarsi sul segreto condiviso ma in realtà non sempre questo è vero. Da bravi programmatori noi dobbiamo considerare il caso peggiore che si possa presentare che poi in queste situazioni è anche quello che si verifica nella stragrande maggioranza dei casi e cioè che i due interlocutori non abbiano mai scambiato contatti prima d’ora. In questo caso essi saranno costretti a prendere accordi sul segreto da condividere ma dovranno farlo davanti agli occhi di tutti gli altri nodi e senza che questi ultimi siano in grado di capirlo. Se infatti un qualsiasi altro nodo entrasse in possesso del segreto condiviso questo sarebbe poi in grado di decifrare tutte le informazioni scambiate fra mittente e destinatario. In pratica ci serve un sistema di comunicazione che seppur perfettamente in chiaro produca un risultato valido solo per il mittente ed il destinatario ed è proprio in questo passaggio che è racchiusa la genialità dell’algoritmo a chiave pubblica. Per provare a capire come calcolare un segreto condiviso utilizzeremo il concetto dello scambio di vernici illustrato da John McCormick nel libro nove algoritmi che hanno cambiato il futuro. Come al solito vi lascio il link amazon in descrizione. Torniamo quindi all’esempio di prima. A, B e C sono sempre nella stanza solo che ora l’obiettivo di A e B è quello di stabilire un segreto condiviso senza che C possa carpire. Ora però le tre persone nella stanza hanno a disposizione un enorme numero di vernici colorate e un angolino sicuro nel quale possono mescolarle senza che gli altri possano vedere i loro movimenti. Innanzitutto A e B si accordano ad alta voce per un colore ad esempio il giallo che noi chiameremo colore pubblico o chiave pubblica volendo utilizzare la nomenclatura dell’algoritmo. Ovviamente essendo stato pronunciato ad alta voce il colore pubblico è conosciuto anche da C. Ora però sia A che B si regano al proprio angolo e mescolano in un recipiente uguali quantità del colore pubblico, il giallo, ed un altro colore a loro scelta che chiameremo colore privato. Supponiamo dunque che A scelga come colore privato il rosso e B invece scelga il blu. Ognuno dei due avrà quindi una propria miscela di colori pubblico privata rispettivamente giallo e rosso e giallo e blu. A questo punto è arrivato il momento di scambiarsi le miscele di colori ma siccome è necessario rispettare il criterio di visibilità da parte di tutti i nodi sia A che B preparano un po’ della propria miscela per C e poi se la scambiano. In questo modo A avrà la miscela di B, B avrà la miscela di A e C avrà la miscela di entrambi così da poter provare a individuare il segreto condiviso fra gli altri due. Una volta scambiate le due miscele però i due legittimi interlocutori avranno vita facile. Gli basterà infatti aggiungere il proprio colore privato alla miscela ricevuta per ottenere entrambi la stessa combinazione. C invece si troverà con due miscele perfettamente inutili. La persona A infatti avrà in mano la miscela giallo-blu di B e vi aggiungerà il proprio colore privato cioè il rosso ottenendo così la miscela giallo-blu-rosso. Allo stesso modo la persona B che avrà la miscela giallo-rosso di A aggiungerà il proprio colore privato il blu ottenendo così la miscela gialla-rossa e blu la stessa miscela di A. Alla fine del processo dunque A e B si troveranno con una miscela perfettamente identica e la chiameranno segreto condiviso. La persona C dal canto suo avrà due miscele incomplete e una miriade di possibili altri colori da poter combinare, troppi per provare a indovinare. Se poi anche provassi a mescolare le due miscele avute da A e B otterrebbe un colore composto da rosso, blu e due parti di giallo, quindi comunque un colore diverso dal segreto condiviso di A e B. Ovviamente anche in questo caso abbiamo semplificato un po’ il discorso ma la logica utilizzata dall’algoritmo a chiave pubblica è esattamente quella che abbiamo descritto. Se fin qui il ragionamento risulta chiaro non ci resta che affrontare l’ultimo passaggio che riguarda in particolare il fatto che ovviamente i computer non ragionano per vernici o per colori. Quello che abbiamo descritto fino ad ora era un esempio atto solo a capire il ragionamento alla base del processo, però funzionava. E funzionava principalmente per due motivi. Il primo è che la quantità di colori disponibile è abbastanza grande da impedire un approccio di forza bruta per indovinare il segreto condiviso. Il secondo motivo invece è che le vernici, una volta mescolate, non possono più essere separate. Considerando quindi che i computer possono ragionare solo in termini di numeri e calcoli, ora non ci serve altro che individuare degli strumenti matematici che abbiano le stesse caratteristiche delle vernici. E c’è che siano difficili da indovinare e che, una volta applicati, calcolarne l’inverso senza le giuste informazioni sia sufficientemente complicato dal punto di vista computazionale da renderlo virtualmente impossibile. E un risultato del genere si può ottenere attraverso due idee matematiche abbastanza comuni, che sono l’aritmetica dell’orologio e la notazione delle potenze. Entrambe sono idee che applichiamo quotidianamente. L’aritmetica dell’orologio infatti entra in gioco tutte le volte che calcoliamo le ore pomeridiane su di un classico orologio a lancette. Le 14 ad esempio sono le 2, cioè le 14 meno 12. Le 18 sono le 6 e così via. Se poi volessimo esprimere numeri più grandi potremmo astrarre il concetto e dire che 30 corrisponde a 4, cioè a 30 meno 12 meno 12. In questo caso avremo fatto due volte il giro completo dell’orologio e ci saremo fermati sul 4. Matematicamente parlando possiamo anche estendere ulteriormente il concetto cambiando anche il numero delle ore dell’orologio. Ad esempio potremmo considerare un orologio di 11 ore. In tal caso il numero 14 non corrisponderebbe più a 2, bensì a 3, cioè a 14 meno 11. La notazione delle potenze invece è semplicemente quella che ci permette di esprimere n prodotti di un numero base come quel numero elevato ad n. In pratica invece di dover dire 5 per 5 per 5 possiamo dire 5 alla terza. Combinando insieme questi due concetti si possono produrre dei calcoli dei quali sia quasi impossibile eseguire le operazioni inverse. Per capirlo proviamo a fare qualche esempio. Applichiamo la potenza di una base 6 elevato alla terza su di un orologio di dimensione 11. 6 alla terza fa 216, che su un orologio di dimensione 11 fa 19 giri e poi si ferma sul 7. Ora immaginiamo di applicare lo stesso calcolo. La base è sempre 6, l’orologio sempre di dimensioni 11, ma questa volta sappiamo già il risultato senza doverlo calcolare, e cioè 3. Voi riuscite a calcolare la potenza n della base 6 che ho utilizzato per arrivare al risultato 3? No? Beh, in realtà è perfettamente normale e questo non tanto perché non sia possibile tirare fuori un numero. In realtà perdendo un po’ di tempo potreste ottenere un n uguale 2 e sarebbe un valore corretto. Il problema è però che anche n uguale 12 è un valore valido per ottenere lo stesso risultato e continuando a provare ne potremmo trovare tantissimi altri. Ecco, questo vuol dire che abbiamo appena messo insieme un algoritmo matematico simile alla miscela tra due vernici, e cioè qualcosa di cui non è possibile ripristinare gli ingredienti originali. Riprendendo quindi l’esempio di A, B e C nella nostra stanza, la dimensione dell’orologio e la base della potenza diventano il nostro colore pubblico, o chiave pubblica. Quello cioè che A e B concordano ad alta voce. Il valore n di elevamento a potenza diventa il colore privato, quello cioè che A e B scelgono indipendentemente e che non dicono a nessuno, ma che utilizzano per calcolare la potenza e poi esprimerla per mezzo dell’orologio, ottenendo così un numero che va a rappresentare la miscela pubblico-privata. Questo risultato pubblico-privato potrà quindi essere comunicato ad alta voce e servirà ai legittimi interlocutori per calcolare il segreto condiviso. Al tempo stesso esso continuerà ad essere totalmente inutile per C, che non potrà utilizzarlo nonostante egli conosca anche la dimensione dell’orologio e la base della potenza. L’ultimissimo dettaglio a cui dobbiamo fare attenzione è che questo algoritmo va applicato a numeri particolarmente grandi. In questo modo potremo simulare la disponibilità di tantissime vernici colorate dell’esempio precedente e in questo modo saremo riusciti a soddisfare tutti i requisiti che ci eravamo posti. Bene ragazzi, siamo così giunti alla fine di questo episodio. Lo so che è stato un episodio un po’ più lungo del solito ma l’argomento non era proprio dei più banali e necessitava di un po’ di spiegazioni in più. A questo proposito spero di essere stato abbastanza chiaro ma in caso contrario vi esorto a farmelo sapere sia con un commento sia nel gruppo Telegram. Come al solito vi ringrazio di essere arrivati fin qui e vi invito a condividere il podcast con chi pensate possa essere interessato agli argomenti che trattiamo. Ora però non vi rubo altro tempo, vi saluto e vi do appuntamento al prossimo episodio.