Introduzione allo Xor

From UIC

Introduzione allo Xor e alle altre operazioni logiche

1 Introduzione allo Xor e alle altre operazioni logiche

Infos
Author:	Quequero
Email:
Website:	http://quequero.org
Date:	18/02/2007 (dd/mm/yyyy)
Level:
Language:	Italian
Comments:	E Xor fu! Ho riscritto due volte questo tutorial perché è crashato il browser!!

Introduzione

Nel corso di questo tutorial impareremo uno dei cardini fondamentali dell'informatica, ovvero le operazioni logiche e l'algebra booleana. Studieremo un po' della matematica che c'è dietro ed introdurremo con degli esempi lo Xor, una funziona utilizzatissima ogni volta che si parla di crittografia e protezione dei dati.

Le operazioni logiche

Nell'algebra booleana vengono definite alcune operazioni fondamentali a tutti i tipi di calcolo informatico, e che quindi si avvalgono di un sistema di calcolo binario. Le operazioni fondamentali sono tre: AND, OR e NOT. Ed utilizzando una combinazione di AND e NOT, o NOT e OR è possibile definire qualunque operazione matematica, pensate alla potenza di tutto ciò!
L'operatore AND è quello che indica l'intersezione, pensate a due insieme (p e q) che si intersecano, il risultato di: p AND q sono tutti gli elementi che si trovano nell'intersezione. L'operatore OR indica gli elementi che si trovano nell'uno o nell'altro insieme, ma non al di fuori di essi, mentre l'operatore NOT indica tutto ciò che NON si trova in quell'insieme, per cui: NOT p indica tutti gli elementi che non si trovano nell'insieme p.
La simbologia utilizzata per indicare questi operatori è la seguente:

AND -->
OR -->
NOT -->

Tabelle di Verità

Per comodità possiamo definire delle tabelle di verità, cioe' delle tabelle che ci mostrano il risultato di queste operazioni, nel nostro caso applicate agli insieme binari.
La tabella di verità dell'AND è la seguente.

p	q	p AND q
0	0	0
0	1	0
1	0	0
1	1	1

Questa è la tabella dell'OR.

p	q	p OR q
0	0	0
0	1	1
1	0	1
1	1	1

E questa è la tabella del NOT.

p	NOT p
0	1
1	0

Equivalenza e leggi di De Morgan

Prima abbiamo detto che possiamo definire l'AND tramite la OR e la NOT, e la OR tramite l'AND e la NOT, ecco come:

p q = ((q p) (p q))
p q = (q p)

Ma a questo punto, per comodità, possiamo anche introdurre le leggi di De Morgan che affermano:

(p q) = (p) (q)
(p q) = (p) (q)

Lo Xor

Dopo di che possiamo passare finalmente allo Xor, che è poi l'acronimo di: eXclusive OR, ovvero OR Esclusivo, ed è così definito:

p	q	p XOR q
0	0	0
0	1	1
1	0	1
1	1	0

Lo Xor, almeno in informatica (nel caso di C/C++ e Java), viene indicato con questo simbolo: ^, ma bisogna stare attenti perché è lo stesso simbolo che viene utilizzato in matematica per indicare l'elevamento a potenza. Lo Xor necessita di 5 istruzioni logiche per essere implementato, e lo possiamo definire in almeno due modi:

p ^ q = (p q) (p q)
p ^ q = (p q) (p q)

Utilizzando le tabelle di verità che trovate poco sopra, vedrete che entrambe le definizioni sono equivalenti. Lo Xor gode sia della proprietà associativa che commutativa, e questo significa che:

p ^ q = q ^ p
(p ^ q) ^ r = p ^ (q ^ r) = p ^ q ^ r

Queste proprietà sono estremamente interessanti perché, se ci pensate, consentono di offuscare e deoffuscare un numero/stringa/dato. Proviamo a prendere l'equivalente esadecimale del carattere ASCII Q che corrisponde a: 0x51 ed applichiamogli le operazioni logiche fino ad ora definite, utilizzando come secondo operando un numero qualunque, ad esempio: 0x65 che corrisponde al carattere ASCII e:

Q AND e = 0x51 AND 0x65 = 0x41 (ASCII: A)
Q OR e = 0x51 OR 0x65 = 0x75 (ASCII: u)
Q XOR e = 0x51 XOR 0x65 = 0x34 (ASCII: 4)

Proviamo ora ad applicare nuovamente le stesse operazioni sui risultati ottenuti:

A AND e = 0x41 AND 0x65 = 0x41 (ASCII: A)
u OR e = 0x75 OR 0x65 = 0x75 (ASCII: u)
4 XOR e = 0x34 XOR 0x65 = 0x51 (ASCII: Q)

Guardate cosa è successo, soltanto nel caso dello Xor siamo riusciti a tornare indietro al numero originale, negli altri casi abbiamo perso informazione... Iniziate a capire perché lo Xor è utilizzato in crittografia? Vuol dire che possiamo offuscare un dato soltando xorandolo con una stringa di uguale lunghezza, e decifrarlo xorando il risultato con la stringa utilizzata per offuscarlo.

Il Cifrario di Vernam

Le proprietà dello Xor hanno permesso la creazione dell'unico sistema di cifratura realmente sicuro, cioe' il Cifrario di Vernam. Tutti i sistemi di crittografia utilizzati attualmente, si basano sull'utilizzo di problemi di difficili risoluzione, ad esempio RSAIl primo algorito di cifratura a chiave asimmetrica si basa sul fatto che è molto difficile scomporre in fattori un numero primo (di lunghezza adeguata ovviamente). Altri algoritmi, come El-Gamal, si basano sul problema del calcolo del logaritmo discreto, che è ancora più difficile da risolvere del sistema utilizzato da RSA. Tutti questi algoritmi basano la loro sicurezza su un problema difficile da risolvere... Ma non impossibile. Ecco quindi che saremo al sicuro fintanto che utilizzeremo chiavi abbastanza lunghe, e finché qualcuno non avrà computer abbastanza potenti, o ancora finché non saranno trovate delle soluzioni matematiche a questi problemi. Il cifrario di Vernam è invece intrinsecamente sicuro, e la sua sicurezza è stata dimostrata matematicamente, il funzionamento è banale: si prende una stringa casuale (la casualità è un requisito FONDAMENTALE) lunga quanto il testo da cifrare, e si xora il testo con la chiave, byte a byte. Se la stringa è casuale non ci sarà alcun modo, per un attaccante, di risalire al contenuto originale, ma bisogna stare attenti: se si utilizza due volte la stessa chiave, diventa possibile risalire alla chiave stessa analizzando i due messaggi cifrati. Ecco perché questo genere di cifrario viene anche chiamato OTP ovvero: One Time Pad, questo algoritmo è stato utilizzato durante tutta la guerra fredda e gli americani non riuscirono mai a decifrare i messaggi che inviavano i russi, ad eccezione di quelli che venivano cifrati con una chiave già utilizzata.

Applicazione Pratica

Proviamo ora a cifrare una stringa di qualche lettera, e poi introdurremo due programmi per fare gli esperimenti con lo Xor. Tanto per iniziare cifreremo il mio nick con la chiave: "Reverser", le operazioni di Xor potete portarle a termine con una normale calcolatrice. Iniziamo col traslare in esadecimale le stringhe che useremo come chiave e come testo.

ASCII: Q u e q u e r o
Hex: 51 75 65 71 75 65 72 6F

ASCII: R e v e r s e r
Hex: 52 65 76 65 72 73 65 72

E quindi xoriamole byte a byte.

51 75 65 71 75 65 72 6F ^ (Quequero)
52 65 76 65 72 73 65 72 = (Reverser)
-------------------------
03 10 13 14 07 16 17 1d

Il risultato non è stampabile in caratteri ASCII ma poco ci interessa, proviamo ora a ri-xorare il risultato con la chiave.

03 10 13 14 07 16 17 1d ^
52 65 76 65 72 73 65 72 = (Reverser)
-------------------------
51 75 65 71 75 65 72 6F (Quequero)

Ed ecco che abbiamo dimostrato anche la funzionalità del nostro cifrario di Vernam... Con una chiave decisamente poco casuale ;-).
In seguito vi allego due programmi per xorare dei dati, uno in assembler che avevo scritto molti anni fa, ed un altro in C che ho scritto ieri sera:

.286
.model small
.stack 100h

.DATA

Password db 04Ch ; poniamo il caso che questo sia il
; numero 5 xorato con un valore
; di 20h (è sparato a caso)

Bravo db ' Bravo!!! ', 0Dh, 0Ah, '$'
Errato db ' Hai sbagliato!!! ', 0Dh, 0Ah, '$'

; supponiamo anche di avere in eax il numero inserito da voi

.CODE

start:
mov ax, @data
mov ds, ax
mov es, ax
xor eax, 20h ; xora il numero inserito con 20h
cmp Password, eax ; è uguale alla nostra pass?
jne Errore ; No? esci dal prog
mov dx, offset Bravo ; Si? Digli che è bravo
mov ah, 09h ; e scrivi che ha azzeccato sullo schermo
int 21h
mov ah, 4ch ; torna al DOS
int 21h

Errore:

mov dx, offset Errato
mov ah, 09h ; mostra la stringa "hai sbagliato"
int 21h
ret

end start

Ed ecco il sorgente in C, in input prende soltanto stringhe in ASCII, ma serve solo a scopo dimostrativo e visto che c'è il sorgente, potete modificarlo come volete :).

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int i, key_len, string_len;
char *key, *string;

key = NULL;
string = NULL;

if(argc < 3){
printf("Simple Xorer, coded by Quequero. http://quequero.org\n");
printf("Usage: %s <xor key> <string to xor>\n", argv[0]);
printf("\t<xor key> can't be shorter than <string to xor>\n");
printf("\tExample: %s Reverser Quequero\n", argv[0]);
return 0;
}

key_len = (int)strlen(argv[1]);
string_len = (int)strlen(argv[2]);

// La chiave non può essere più corta della stringa
if(key_len < string_len){
printf("Key can't be shorter than the target string.\n");
return 0;
}

// Alloca lo spazio necessario alla chiave e alla stringa
key = (char *)malloc(key_len);
string = (char *)malloc(string_len);

if(key == NULL || string == NULL){
printf("Error calling malloc().\n");
return 0;
}

strncpy(key, argv[1], key_len);
strncpy(string, argv[2], string_len);

printf("Target string: %s\nXor key: %s\nXored string: ", argv[2], argv[1]);

// Xoriamo e mostriamo il risultato
for(i = 0; i < string_len; i++)
printf("0x%02x ", string[i] ^ key[i]);

printf("\n");

free(key);
free(string);
return 0;
}

Note Finali

Come abbiamo detto lo Xor è un'operazione ampiamente utilizzata in campo crittografico, se siete curiosi di approfondire queste tematiche, potete dare uno sguardo al mio paper su RC4, ed a quello sugli OTP. In quest'ultimo viene spiegato in dettaglio come implementare il cifrario di Vernam, e come effettuare la crittanalisi di due messaggi cifrati con la stessa chiave.

Il Bug dello Xor

Dalle definizioni date sopra appare evidente che: p ^ p = 0, non ci sarebbe nulla di strano... Ma qualcuno ci ha trovato addirittura un bug :), se volete farvi due risate, leggete la pagina riguardo al bug dello xor :).

Buono xor a tutti :).