Soluzione al quiz Romeo Giulietta e versione digitale.
Sulla soluzione al quiz c' è ben poco da dire, basta riportare il commento dei (bravi!) ragazzi di Francesco:
"Risposta dei ragazzi
R mette nella scatola l'anello, e la chiude con il lucchetto e la spedisce a G
G mette un secondo lucchetto e rispedisce il tutto a R
R toglie il suo lucchetto e spedisce la scatola ancora chiusa con il lucchetto di G
G apre il suo lucchetto e prende l'anello
Poi le ragazze hanno aggiunto che gli anelli non si regalano più, è roba da vecchi, e sono scappati tutti via ridendo... mi devo preoccupare? "
Come avevo anticipato, esiste una versione "digitale" del quiz, che è proprio analoga a quella vista sopra, ma che fa uso di serrature e chiavi booleane. Che parole difficili; in realtà possiamo semplificare per far comprendere a tutti questi concetti. Stiamo parlando di crittografia.
La crittografia è la scienza che si occupa di mascherare il passaggio di informazioni. Al mondo d'oggi tutto può essere trasformato in numeri; immagini, voci , codici di carte di credito, ecc. Si tratta di riuscire a trasferire tramite un canale di comunicazione (nel nostro caso la rete internet)questo scambio di informazioni in modo sicuro.
Useremo per la descrizione dei personaggi consolidati e standard nel campo della crittografia: Alice, Bob ed Eve. Eve rappresenta il nemico,il malintenzionato che spia le comunicazioni fra Alice e Bob, analizzando le sequenze di bit spedite tramite protocolli di rete.
Intanto cos'è una chiave? E' ciò che ci consente di cifrare e decifrare un messaggio . Ci sono vari metodi per cifrare attraverso delle chiavi . Noi ci occuperemo di chiavi casuali, e della loro elaborazione con il messaggio da scambiare tramite una operazione binaria detta XOR (OR esclusivo)
Abbiamo detto che tutto può essere trasformato in numeri, ma i numeri che il computer può elaborare a basso livello sono solo due : 1,0 ovvero vero o falso. Il nostro messaggio M può quindi essere identificato a livello macchina come una sequenza di bit:
M=1010001....01010111. Per cifrare questo messaggio usiamo una chiave casuale A e la funzione booleana XOR.
Cos'è una chiave casuale?
Nel nostro caso una sequenza di bit generati casualmente dal computer. Ci sono vari modi per generarla; gli eventi che possono causare la generazione possono essere i più vari: dal movimento del mouse alla digitazione dei tasti, a fenomeni più strettamente fisici utilizzando delle misure sui componenti elettronici.
Cos'è lo XOR?
Lo XOR è una operazione logica fra variabili che assumono solo due valori, 0,1 (vero o falso). Noi da qualche parte, abbiamo visto le operazioni AND e OR. Per definirle, basta dare i valori che esse assumono su tutte le coppie di combinazioni possibili.
Indichiamo dunque con A e B delle "variabili" che possono assumere solo i valori 0,1. Per AND e OR, abbiamo quattro combinazioni possibili per A,B:
( A AND B si indica anche con A 
| A | B | A B |
A B |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
A
A
Ma veniamo al nostro XOR, e alla sua tabella di verità:
| A | B | A XOR B | |
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
vediamo che differisce dall OR solo nella combinazione 1-1. A differenza dell' OR, lo XOR dà 1 (vero) solo se A,B sono diversi. Chiaramente lo XOR (come l'AND e l'OR) è una operazione commutativa; inoltre è associativa; se devo fare A XOR (B XOR C) posso allo stesso modo fare (A XOR B) XOR C e alla fine posso scrivere semplicemente A XOR B XOR C. Se ci sono più termini è la stessa cosa; posso fare l'operazione nell'ordine che più ci fa comodo. Per la dimostrazione basta scrivere le relative tabelle di verità, ma ve lo risparmio essendo una cosa molto noiosa.
Lo XOR bit a bit applicato a stringhe di ugual lunghezza
Per eseguire lo XOR su stringhe di bit, possiamo farlo su stringhe di uguale lunghezza:
| x | 1 | 1 | 0 | 0 | 1 |
| y | 1 | 0 | 1 | 0 | 0 |
| x XOR y | 0 | 1 | 1 | 0 | 1 |
La cosa strana di tale operazione, è che se applichiamo lo XOR due volte tenendo costante una delle due variabili torniamo alla stringa originale ! ovvero
x=XOR(XOR(x,y),y) 1)
| x | 1 | 1 | 0 | 0 | 1 |
| y | 1 | 0 | 1 | 0 | 0 |
| x XOR y | 0 | 1 | 1 | 0 | 1 |
| x=XOR(XOR(x,y),y) | 1 | 1 | 0 | 0 | 1 |
Bene, questa è la proprietà dello XOR che ci serve per risolvere il nostro problema, assieme alla commutatività e alla associatività.
Spediamo il messaggio
Ma torniamo al nostro caso; Alice e Bob vogliono spedirsi un messaggio in modo sicuro, e scelgono lo XOR come codifica e delle chiavi casuali. Tale messaggio, può ad esempio essere la combinazione di un lucchetto (nel nostro caso del quiz) . Per non far confusione con le espressioni con cui avremo a che fare, scriveremo lo XOR in rosso.
Supponiamo che il messaggio sia M. Alice lo converte in binario. Quindi crea una chiave binaria casuale A e fa lo XOR con M. Invia il risultato, M XOR A, a Bob. Quindi Bob crea la sua chiave casuale B e fa lo XOR con ciò che riceve da Alice, cioè M XOR A e invia il risultato, (M XOR A) XOR B, di nuovo ad Alice. Alice porta il risultato nella sua chiave per ottenere:
[( M XOR A) XOR B] XOR A = M XOR Binfatti sappiamo che x=XOR(XOR(x,y),y) per la 1)
Per la proprietà associativa, [( M XOR A) XOR B] XOR A= M XOR A XOR B XOR A ; se commutiamo gli ultimi due termini questo è uguale a M XOR A XOR A XOR B, ma pe la 1) M XOR A XOR A XOR B=M XOR B
Dopo di che Alice invia a Bob M XOR B. Bob fa lo XOR con la sua chiave B per decifrare il messaggio. Infatti , sempre per la 1),
M XOR B XOR B=M
Essendo A, B casuali,ogni messaggio inviato equivale a una stringa casuale. Anche se viene intercettato, non è di nessuna utilità per il malintenzionato. Vediamo che c'è un analogia con il problema tradizionale; anche qui vengono usate due chiavi per "aprire" (decodificare) il messaggio.
