Informazione e entropia, il contributo di Shannon

Supponiamo di avere due palline, una bianca e una nera: qualcuno prende una delle due palline e la mette in un cassetto: quale situazione si può verificare quando si apre il cassetto?

Figura 1. Due palline, una bianca e una nera, un cassetto.

Quando apriamo il cassetto potremo trovare una pallina bianca oppure una pallina nera.

E se avessimo due cassetti, per ciascuno dei quali abbiamo a disposizione una coppia di palline (di cui una bianca e l’altra nera)? e se i cassetti fossero tre?

Figura 2. Quale è il numero delle possibili situazioni che si possono verificare con 2 e 3 cassetti?

Il bit – unità di informazione

L’informazione che possiamo associare al fenomeno di aprire un cassetto in cui possiamo trovare soltanto una pallina nera o una pallina bianca viene chiamata unità di informazione e è la stessa che possiamo associare a altri fenomeni, per esempio è l’informazione contenuta nel lancio di una moneta il cui risultato può essere testa oppure croce, è l’informazione contenuta in un cavo elettrico che può essere percorso o meno da un flusso di elettroni, ancora è il contenuto informativo che possiamo associare alla domanda “preferisci il mare o la montagna?”

L’unità di informazione corrisponde quindi all’informazione associata al verificarsi di uno tra due soli possibili eventi che siano equiprobabili.

Questa scelta tra due sole possibilità è una scelta binaria: bianco o nero, testa o croce, corrente non-corrente, mare o montagna, vero o falso, zero o uno.
Se indichiamo una possibilità con un 1 e l’altra con uno 0 allora possiamo parlare di binary-digit, abbreviato in bit.
L’unità minima di informazione corrisponde quindi a quella associata a 1 bit,

1 bit = 2¹, due possibili scelte

.

Il logaritmo come misura dell’informazione

Se abbiamo due scatole l’informazione sarà di 2 bit, con tre scatole avremo 3 bit di informazione e così via, ci aspettiamo, naturalmente, che il contenuto di informazione raddoppi, triplichi etc all’aumentare del numero di scatole, ma nel primo caso (1 cassetto) i casi possibili sono 2, nel secondo caso 4, nel terzo otto… il contenuto di informazione non sembra raddoppiare ma seguire una legge diversa!
I matematici ci insegnano che, se vogliamo misurare l’informazione in maniera appropriata, allora dobbiamo utilizzare una particolare funzione matematica, il logaritmo.

log₂(x) è quel numero y t.c. 2^y=x

.
Se usiamo il logaritmo e consideriamo la funzione

H = log₂n, con n pari al numero di casi possibili      (1)

allora per una scatola troviamo H(1)=1, per due scatole H(2)=2, per tre scatole H(3)=3 e così via, il contenuto informativo cresce come ci saremmo aspettati, per cui se vogliamo misurare in maniera corretta il contenuto di informazione associato a un fenomeno, dobbiamo utilizzare la funzione H.

Probabilità variabili, l’informazione di Shannon

Figura 3. Cosa succede la probabilità di trovare una pallina bianca o una nera non è più la stessa?

Adesso consideriamo il caso in cui abbiamo sempre una scatola ma stavolta la probabilità con cui possiamo estrarre una pallina bianca o nera non è più la stessa e cerchiamo di immaginare quale sarà la nostra sorpresa (saremo sorpresi?) nel caso in cui con P(bianco)=0.7 troveremo una pallina bianca; e che ne sarà della nostra sorpresa nel caso in cui, con P(bianco)=1, troveremo una pallina bianca?

Figura 3.1. Claude Elwood Shannon (sulla sinistra) con un prototipo di macchina per la simulazione del gioco di scacchi e (sulla destra) con il topo elettro-meccanico che esplora un labirinto, di fatto un primo esempio di machine learning.

A questa capacità di essere sorpresi pensava Claude Shannon, quando, ai Bells Telephone Laboratories, alla fine degli anni ‘40 del XX secolo, decise di formulare la sua legge dell’informazione.

Figura 3.2. Il sistema di comunicazione su cui lavora Shannon.

Shannon considera un sistema per la trasmissione a distanza di una sequenza di lunghezza s composta di n simboli e si domanda quale informazione si possa attribuire a ciascuna sequenza di simboli che viene generata dalla sorgente. Per tener conto di poter avere diverse possibilità p(i) associate a ciascuno degli n simboli che compongono la sequenza, con il vincolo che

Σ_i p(i)=1,

Shannon modifica la (1) così che l’informazione associata alla sequenza di simboli, l'informazione (o entropia) di Shannon, è:

H = - ∑_i p_i log(p_i) (1)      (2)

Informazione e entropia

La legge dell’informazione di Shannon ha la stessa forma dell'entropia nella seconda legge della termodinamica, una grandezza fisica che in un sistema isolato come il nostro universo può soltanto aumentare.
L’entropia è infatti una misura del disordine presente nell’universo e ci dice che questo, nel tempo, può soltanto aumentare. In pratica, a partire dalla condizione di ordine completo che corrisponde al big-bang, la successiva evoluzione e espansione dell’universo porta a una diminuzione dell’ordine, ovvero sia a un incremento del disordine, che corrisponde all’evoluzione del cosmo verso una condizione di stabilità termodinamica.

Produzione di simboli, sistemi stocastici

Immaginiamo di avere una macchina che genera sequenze di lunghezza s a partire da un insieme di n simboli.

Un sistema, che produce una sequenza di simboli secondo determinate probabilità, è un processo stocastico e, nel caso in cui le probabilità dipendono dagli eventi passati, una Catena di Markov (Markov Chain).

Quale è l’informazione associata a una sequenza generata da un sistema stocastico? Nei termini individuati da Shannon l’informazione è associata a quanta libertà di scelta si ha nel costruire un messaggio.

La misura dell’informazione è data da (3):

H = n log₂(s)      (3),

infatti all’aumentare del numero di simboli considerati ci aspettiamo che l’informazione, ovvero sia le possibili sequenze che possono essere generate, aumentino, d’altra parte ci aspettiamo anche che al raddoppiare della lunghezza della sequenza, raddoppi il contenuto di informazione.
La misura scelta per l’informazione, quella espressa in (3), risulta essere quella corretta.

Nel caso in cui le probabilità con cui vengono generati gli elementi della sequanza non siano uniformi, ovvero sia la probabilità di trovare un simbolo non è la stessa per ogni simbolo, la misura corretta è quella dell'entropia di Shannon,

H = - ∑_i p_i log(p_i) , con n pari al numero di casi possibili       (2)

.

Sequenze di simboli e linguaggi

Immaginiamo adesso di avere una macchina in grado di generare una sequenza di messaggi, di lunghezza s, a partire da n simboli corrispondenti a delle lettere dell’alfabeto. (I messaggi possono anche avere lunghezze variabili).
Consideriamo per esempio di avere a disposizione 5 simboli {A, B, C, D, E} e di voler generare messaggi di lunghezza 100:

• se la probabilità associata a ciascuna lettera è la stessa, un messaggio può essere del tipo:
  

  DBCABBBBEDADDEAEAADABDDCAEABCADBADBBBECEBDBBCEEACDACCECEBEDEDEDECCBDCABACDEACCDDBDEADBDDEAADCBDEEDAD

• se la proprietà associata a ciascun simbolo non è più la stessa, per esempio le probabilità scelte per i 5 simboli sono rispettivamente { 0.1, 0.4, 0.15, 0.2, 0.15 }, un messaggio generato è il seguente:
  

  CCCDCDBBBABDEBABEBADBABCDDDCEBACEBEABEBCEBBBDBDEDBBDCDDDBBDBACDCDCACBEBBBDCACEBBDBBCCAECAEBBBBBDAADC.

Il messaggio generato nel primo caso dalla macchina è una sequenza di simboli praticamente incomprensibile, caratterizzata da un elevato grado di sorpresa, i.e. elevato contenuto di informazione.
Nel secondo caso invece la sequenza risulterà più prevedibile, il suo contenuto di informazione è minore che nel caso precedente.

Se pensiamo alla lingua italiana, possiamo osservare come alcune lettere siano più ricorrenti di altre, alcuni dittonghi non compaiano quasi mai, le diverse sillabe hanno frequenze diverse e non si combinano con la stessa facilità le une con le altre: la lingua italiana ha una struttura, e questo ne riduce la sorpresa, ovvero sia il contenuto di informazione secondo Shannon.

Proprio questa struttura può essere utilizzata per creare una macchina, una Discrete Markov Chain in grado di generare un linguaggio di sintesi (artificiale) composto da una sequenza di parole ammissibili dal vocabolario della lingua italiana – senza però che a queste sia possibile associare una struttura semantica.

Per concludere consideriamo nuovamente una macchina in grado di generare una sequenza di messaggi a partire da un insieme di simboli, stavolta però ciascun simbolo che viene generato dipende dal simbolo che lo precede secondo una legge assegnata, seguendo lo schema illustrato in Figura..

Figura 4. Diagramma della catena di Markov e relative probabilità.

Un esempio di messaggio generato con questa macchina è il seguente:

BACCACCCAABACCACACABCABBCACCCCCCCABAAAACAAACABCCACCCCACBCACCBACBBCBCCCBCBBBBCBCCCACCCBCCABBACBBCBAAB

Il simbolo C risulta il più probabile e una volta che abbiamo una C risulta più frequente che sia seguita da un’altra C.

L’eredità di Shannon: messaggi come sequenze di bit

Il contributo di Shannon alla teoria delle comunicazioni è stato di fondamentale importanza e ha stabilito che le informazioni devono essere codificate come sequenze di bit prima di essere inviate dal tramettitore al ricevitore.
L’utilizzo di segnali basati su un sistema binario, su bit di informazione permette di applicare alla trasmissione di messaggi a distanza gli strumenti della logica booleana e delle operazioni base-2 (binarie).

Tra le applicazioni principali che avuto la logica binaria ci sono quelle, di fondamentale importanza per le comunicazioni, nel campo della crittografia.

Crittografia

Il termine crittografia deriva dal greco kriptos (segreto e graphein (scrittura), e si riferisce dunque a una scrittura segreta. Si tratta della capacità di scrivere messaggi utilizzando un codice che possa essere compreso solo dal destinatario.

Della crittografia nel corso dei secoli è stato fatto uso da diploimatici e militari, ma il quadro di riferimento cambia radicalmente con l’invenzione di sistemi per la trasmissione di informazioni a distanza, quali il telegrafo e la radio.
In particolare lo sviluppo delle comunicazioni senza filo, che possono essere intercettate da un man-in-the-middle, ha portato allo sviluppo di sistemi crittografici sempre più avanzati.

Chiave segreta, crittografia asimettrica

Tradizionalmente la crittografia richiede che mittente e destinatario concordino una chiave segreta: questo costituisce spesso un problema pratico perché implica che i due abbiano la possibilità di incontrarsi o comunque scambiarsi in maniera sicura la chiave.

Una forma di comunicazione che non prevede lo scambio di una chiave condivisa, è la crittografia a chiave-pubblica, o crittografia asimmettrica, che si basa sull’utilizzo di una coppia di chiavi: una chiave pubblica utilizzata per criptare il messaggio che si vuole inviare, e la corrispondente chiave privata, per decifrarlo.
La chiave pubblica è pubblica e può essere distribuita a altri o inserita in un registro di chiavi pubbliche^[1], mentre la chiave privata deve rimanere segreta.

Le due chiavi vengono generate dallo stesso algoritmo e sono matematicamente collegate tra di loro, anche se in pratica è statisticamente molto improbabile recuperare la chiave per decifrare (chiave privata) a partire da quella utilizzata per criptare (chiave pubblica).

Alice e Bob si scambiano un messaggio

Supponiamo che Alice e Bob vogliano scambiarsi un messaggio utilizzando un meccanismo di crittografia a chiave-pubblica, in particolare che Bob scriva un messaggio a Alice: Bob avrà a disposizione la chiave pubblica di Alice con la quale firmerà il messaggio che vuole inviare a Alice, Alice lo riceverà e utilizzerà la sua chiave privata per decodificarlo.
Se qualcun altro intercettasse il messaggio inviato a Alice e cercasse di decifrarlo, non ci riuscirebbe, perché non conosce la chiave privata di Alice e la probabilità di deciifrarlo è estremamente bassa (vedi cifrario RSA e SHA).

Il cifrario RSA

Nello sviluppo della crittografia asimmetrica un’innovazione importante avvenne nel 1978 con l’introduzione del primo cifrario a chiave pubblica, il cifrario RSA, che prende il nome dalle iniziale dei tre studiosi che lo hanno sviluppato.

Figura 5. Algoritmo per il calcolo della chiave pubblica e privata con cifrario RSA.

Questo cifrario è basato sull’utilizzo di funzioni matematiche che siano relativamente facili da calcolare (per criptare il messaggio) ma molto difficili da invertire (per decifrare il messaggio), per esempio si possono utilizzare:

• il prodotto di numeri primi che è facile da calcolare, mentre l’operazione inversa, la fattorizzazione di un numero, è molto più difficile;
• un aritmetica modulare, molto difficile da invertire.

Un cifrario di questo tipo viene detto asimmetrico, in quanto prevede che la chiave che si utilizza per criptare il messaggio non sia la stessa che viene utilizzata per decifrarla.
In particolare la chiave per cifrare, chiave pubblica, è disponibile in un archivio e viene utilizzata da chiunque voglia mandare un messaggio segreto all’intestatario della chiave. Una volta ricevuto il messaggio, l’intestatario della chiave pubblica, utilizzerà la sua chiave privata, che solo lui conosce, per decifrare il messaggio.

Hash crittografici

Figura 6. Esempi di funzioni di hash crittografici.

Un hash crittografico o CHF, Cryptographic Hash Function è una funzione matematica che permette di associare a un input, sia questo un messaggio o il contenuto di un file, una sequenza di n-bit (in generale 128 bit, oppure 256 o 512 bit) che ne è rappresentativa e la cui probabilità di essere generata è di 2^-n.
Un hash crittografico può essere utilizzato come impronta di un messaggio, perché è collegato in maniera univoca al messaggio che lo ha generato e non è praticamente riproducibile in maniera casuale^[2].

Particolare importanza riveste oggi la famiglia degli hash crittografici SHA, Secure Hash Algorithms, in particolare si utilizzano le funzione SHA-256 and SHA-512, che creano impronte di un messaggio rispettivamente di lunghezza 256 o 512 bit.

Le funzioni di hash crittografico, SHA o MD5, rivestono una particolare importanza nelle comunicazioni che avvengono utilizzando la rete Internet, per esempio ne fa uso il protocolo HTTPS/TLS che utilizziamo per visualizzare pagine web e scambiare dati tramite applicazioni web.

Digital signatures, firma digitale

A partire da un messaggio è così possibile ottenere un’impronta “sicura” del messaggio, infatti la probabilità di generare un hash identitico è molto improbabile^[2].
Il messaggio così trasformato può essere firmato con una firma digitale, che utilizza un algoritmo a chiave-pubblica, per esempio il metodo RSA: si firma l’impronta del messaggio con la propria chiave privata e chiunque conosca la nostra chiave pubblica potrà verificarne l’autenticità.

Blockchain

Una blockchain è un registro distribuito costituito da una lista crescente di blocchi che sono collegati assieme da hash crittografici.
Ogni blocco contiene un riferimento al blocco precedente, un timestamp e dei dati associati alla transazione.
Poiché ogni blocco contiene un riferimento al blocco precedente l’insieme dei blocchi costituisce una catena (chain).

Figura 7. Esempio di alcuni blocchi di una blockchain, ciascuno con l'hash di riferimento al blocco che lo precede e il timestamp della transazione.

Le transazioni registrate nella blockchain sono irreversibili perché ciascun blocco, essendo collegato a quello che lo precede, non è in pratica modificabile, perché modificare un blocco implicherebbe dover modificare tutti i blocchi precedenti.

Il termine blockchain compare per la prima volta nel white-paper pubblicato da un anonimo Sakoshi Nakamoto e costituisce il meccanismo di base con cui vengono registrati gli scambi nella criptovaluta bitcoin.

Bitcoin

Bitcoin è una valuta digitale che è stata progettata come mezzo di scambio per l’acquisto di beni e servizi tra pari (peer-to-peer), ovvero sia senza la necessità di intermediari che attestino la validità della transazione, quali per esempio una banca.

Figura 8. Il logo della criptovaluta Bitcoin.

Le transazioni che avvengono con i bitcoin vengono annotate su un registro pubblico (public ledger), che utilizza una blockchain per attestare la validità delle transazioni e rendere sicuro, immutabile, il contenuto del registro.
L’algoritmo di Bitcoin è un elemento importante nella validazione delle transazioni e nel mining di nuovi Bitcoin, dove i miners devono risolvere complicate prove matematiche (Proof of Work) per aggiungere blocchi alla blockchain e generare nuovi bitcoin e la validità dei dati è assicurata dall’utilizzo di funzioni di hash SHA-256.

Figura 9. Esempio di come avviene una transazione sulla blockchain di bitcoin.

Note

[1] Ci sono registri online dove uno può depositare la propria chiave pubblica, cpsì che altri possanon scrivergli un messaggio.

[2] Il termine molto improbabile indica che la probabilità di generare un hash identico utilizzando un insieme di computer attualmente disponibili è pressoché impossibile, nel senso che richiederebbe un tempo di calcolo estremamente lungo, molto più lungo del tempo in cui questo risultato risulterebbe utile.