04/01/20

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)

alice-bob

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  {\ displaystyle \ land} B; A OR B con A {\displaystyle \lor } B)

A B A  {\ displaystyle \ land} B {\displaystyle \lor } B
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1

 

A  {\ displaystyle \ land} B vale 1 (è vera) solo se A,B sono entrambi vere.  Negli altri casi  vale 0.

{\displaystyle \lor } B Vale 1 se è vero A o è vero B oppure sono entrambi veri.Vale 0 solo se sono entrambi 0.

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 B

infatti 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.

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.