Privacy Policy Cookie Policy Cifratura Xor in C – Parte 1 - Simone Sante Ruffo
You are here
Home > Programmazione > C/C++ > Cifratura Xor in C – Parte 1

Cifratura Xor in C – Parte 1

Introduzione

“La vita è il primo regalo, l’amore il secondo, e la comprensione il terzo.”

Marge Piercy

Benvenuti nel primo articolo di questa lunga ed interessante serie sui i metodi di crittografia più famosi . In questo articolo presenterò uno degli operatori più importanti, basilare per la maggior parte delle operazioni di crittografia e cifratura. Vedremo il potente “Xor”. Perché cosi potente lo capiremo piano piano ma intanto introdurrò acune applicazioni nelle questo operatore è utilizzato e implementeremo un metodo di cifratura abbastanza primitivo nel linguaggio piu fantastico di sempre, il C.

buon divertimento!.

Cifrache?

Ma il Grana Padano perché si chiama così? O perché esiste il Gazzettino Padano? […] È un modo per dire che se c’è questo termine, questa terminologia, è perché la Padania esiste.

Gianluca Buonanno

Iniziamo subito ad identrarci nel complicato mondo della crittografia chiarendo il significati dei termini qui utilizzati.

Per cifratura si intede il processo di trasformazione di un messaggio (o in generale: una informazione) in qualcosa di incomprensibile a occhi indiscretio, non autorizzati a riceverla. nel caso più semplice queste trasformazioni sono delle ‘rotazioni’ (ovvero la sostituzione della ‘lettera’ di un alfabeto con un’altra dello stesso alfabeto) in base a un singolo valore, detto chiave, che verrà utilizzato anche per rendere di nuovo chiaro il testo.

Per alfabeto si intende un insieme di simboli che combinati tra loro formano un messaggio. Un esempio è l’alfabeto utilizzato dai personal computer ovvero l’insieme composto dalle cifre binarie [0,1] o l’alfabeto utilizzato dagli umani che è composto invece da 26 lettere mentre l’alfabeto utilizzato dai giapponesi è composto da centinaia di simboli che rappresentano una o più parole. Esiste uno standard per i file di testo che è chiamato codice ASCII il cui albabeto invece è composto da gruppi di 8 bit che vengono interpretati dal computer come lettere, simboli o numeri. Ognuna delle lettere di questo articolo è un gruppo di 8 bit facente parte del codice ASCII

La chiave è invece una lettera, un numero, un simbolo o un testo che messo in relazione con il testo del messaggio tramite una funzione, permette di cifrare il testo e di decifrarlo se si utilizza la funzione inversa.

Quello che implementeremo noi è in meccanisco di cifratura tramite rotazione descritto sopra! Ma partiamo dall’inizio.

Operatore XOR

Conoscevate l’operatore Xor?, una funzione logica molto importante in quanto utilizzata in moltissime applicazioni: dall’networking, all’informatica, all’elettronica.
Lo Xor non è altro che l’or esclusivo, una operazione matematica che dati due bit in ingresso resituisce 1 se e solo se i due bit in ingresso sono diversi tra loro.

Potete immaginare lo Xor come una ‘scatola nera’ che, se riceve in ingresso 0 e 1, mi restituisce in uscita 1; se riceve 1 e 1 o 0 e 0, mi restituisce 0.

Per fare un paragone con la logica tradizionale, lo xor tra due affermazioni, è quella relazione vera se e solo se una sola delle due frasi è vera.
Dati in ingresso due bit, vediamo di cercare di capire come funziona.

Quella che ho disegnato sopra prende il nome di tabella di verità, una tabella che mi dice, in funzione dei bit di ingresso X1 e Y1, quale sarà il risultato dell Xor. Come potete vedere, se i due bit sono uguali viene restituito 0 altrimenti 1.

Funzionamento dell’algoritmo

Il principio di cifratura da noi implementato è semplice:

Prima di iniziare è bene ricordare una cosa.In un testo ogni carattere viene rappresentato, all’interno della macchina, utilizzando il codice ASCII cioè tramite una sequenza di 8 bit, ognuno dei quali può essere 0 o 1. Quindi, effettuare uno Xor bit a bit di due caratteri significa fare lo Xor tra i bit dei due caratteri presi uno a uno (prima si confronta rispettivamente il primo bit dei due caratteri in ingresso, poi il secondo e così via…) ottenendo in uscita alla nostra funzione, un’altro carattere i cui bit sono lo xor tra i bit dei caratteri in ingresso. Semplice no?

In questa operazione sfruttremo le due proprietà che rendono lo Xor un potente strumento in crittografia.

  • Se si fa lo Xor tra due caratteri si ottiene un carattere univoco per ogni coppia di caratteri in ingresso!
  • Se si rifà lo Xor tra il carattere ottenuto e uno dei due caratteri in ingresso ri-otteniamo l’altro dei due caratteri in ingresso.

Facciamo un esempio che chiarirà il tutto tutto:

Questi sono i due caratteri in ingresso:

01011010 e 00010101

Quello che farà il nostro algoritmo e prendere il primo bit dei due caratteri (in questo caso 0 nel primo carattere e 0 nel secondo) percui lo Xor restituirà 0 in quanto i due bit sono uguali, successivamente prendo il secondo bit dei due caratteri (1 e 0), lo Xor restituirà 1 in quanto i due bit sono diversi. Il processo viene ripetuto per tutti gli altri bit ottenendo come risultato finale il seguente carattere: 01001111.

Debolezze?

Come ogni buon algoritmo di crittografia, anche questo risponde al principio di Kerckhoffs che afferma: La sicurezza di un crittosistema non si deve basare sul tenere nascosto l’algoritmo utilizzato ma la chiave. Quindi la debolezza è che se si scopre la chiave è facile ottenere il messaggio originale. Avendo un numero abbastanza grande di messaggi lunghi da analizzare un crittoanalista può riuscire a tradurre la chiave provando statisticamente e vedere ogni lettera di quanti posti è stata trasportata. Trovata la chiave basta riapplicare lo Xor è il gioco è fatto. Naturalmente in questo caso lavoriamo su trasposizioni di un alfabeto di più di 100 caratteri. Se la chiave è adeguatamente lunga diventa comunque difficile, ma non impossibile, trovare il messaggio originale.

Realizziamo il nostro software

Anche in C i caratteri sono visti come insiemi di 8 bit (1 byte) per cui facendo lo Xor tra i e / , non faccio altro che dire al computer di eseguire lo Xor bit a bit tra i due caratteri, come mostrato precedentemente, ottenendo un terzo carattere.
Se rifaccio lo Xor tra il carattere ottenuto e / riottengo la i.

In C lo Xor bit a bit, in C lo si fa tramite l’operatore ‘^’.
Se quindi volessi fare lo Xor tra due caratteri mi basterà scrivere:

#include <stdio.h>

int main(){
  char password;
  char test[8];
  char testo_cifrato[8];
  int i;
 
 /*Chiedo di inserire un carattere in ingresso*/
 printf("Inserisci 8 un testo di otto caratteri\n");
 scanf("%8s",testo);
 printf("Inserisci una password di 1 carattere\n");
 scanf("%1s", password);
 
 /*Stampo il testo da cifrare*/
 printf("Il testo da cifrare è: %s, la password è:%s \n", testo, password);
 
 /*Esegui lo Xor tra tutti i carateri del testo e della password*/
 for(i=0;testo[i]='\0';i++){
   testo_cifrato[i]=testo[i]^password;
 }
 
 printf("Il testo da cifrare, la password e il testo cifrato in esadecimale sono: \n");
 
 /* Stampo il testo inserito in ingresso*/
 for(i=0;testo[i]!='\0';i++){
   printf("%c",testo[i]);
 }
 
 printf("\n");
 /* Stampo la password*/
 printf("%c \n", password);
 
 /* Stampo il testo cifrato in esadecimale (In esadecimale in quanto potrebbe
    contenere caratteri non stampabili) */
 for(i=0;testo_cifrato[i]!='\0';i++){
   printf("%x",testo_cifrato[i]);
 }
 printf("\n");
 
}

Si capisce subito che questo programma ha ancora dei difetti e può servire solo come esempio. Come fare se si vuole ottenere un algoritmo di crittografia Xor più complesso?
Potremmo intanto volere utilizzare una password più lunga, cosiché possa essere più difficile trovare il testo originale, ma potremmo addirittura cercare di rendere la chiave indipendente dalla password inserita e dal testo cifrato in modo da rendere un poco più sicuro il processo.

Un esempio di come si potrebbe aggiungere più entropia al processo di cifratura è mostrato in seguito.

Un fattore di sicurezza potrebbe essere dato dal permettere all’utente di inserire una password e un testo più lunghi.
Possiamo permettergli di inserire testi di lunghezza variabile, ma impostando comunque un limite massimo per evitare buffer overflow!.
Per fare ciò dobbiamo usare la malloc(),  funzione dichiarata nella libreria standard che quindi va inclusa all’inizio del progetto.

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

Il funzionamento è semplice. Chiediamo all’utente di quante cifre vuole che sia la password e dichiariamo un puntatore per dare il nome alla zona di memoria che ci serve (come attacare una etichetta grazie alla quale potere accedere e/o leggere il contenuto di una determinata zona di memoria).
Questo puntatore conterrà l’indirizzo del primo byte della zona di memoria allocata:

char *password; 

//Dichiaro un puntatore utilizzando l'operatore asterisco.
int n;

printf("Di quanti caratteri deve essere la password?\n");
scanf("%d",&amp;amp;amp;amp;amp;amp;amp;n); 

//Salvo la cifra inserita dall'utente in n
password=malloc(sizeof(char)*n);

/* Alloco una zona di memoria delle dimensione di un char (sizeof()
che restituisce la dimensione in byte di un tipo di dato ad esempio il char)
per n che è il numero di caratteri che devo
salvare e a questa zona di memoria do il nome di password (in verità non è proprio il nome della zona di memoria
ma questo ci permetterà di capire
il concetto base quindi per ora diciamo cosi! XD) */

Possibili miglioramenti

Questa soluzione non è molto elegante, specialmente se non si ha fiducia dell’utente, poiché esso potrebbe inserire un valore di caratteri molto grande e mandare il software crash poiché la memoria del PC non è infinita.

Per ragioni di sicurezza è quindi importante dare un valore massimo di dimensione alla password inseribile, il che si può fare, ad esempio, chiedendo di inserire una password di massimo n cifre, con n stabilita da noi oppure chiedendo di quante cifre deve essere la password e poi controllare che il valore inserito sia minore di un determinato valore massimo con un semplice if, comunque nelle prossime lezioni vedremo come migliorare anche questi aspetti.

Questi sono i due metodi più semplici e veloci quindi quelli che utilizzeremo nel nostro articolo.

Un’altra soluzione, che unisce i vantaggi delle due precedenti, potrebbe essere quella di utilizzare una variabile temporanea da disallocare successivamente e che può contenente al massimo n cifre, fargli inserire una password che deve contenere al massimo n cifre e una volta che l’utente inserisce la password contare le cifre inserite e allocare solo lo spazio richiesto (Ma come fai a capire la dimensione della stringa inserita o a limitare il numero di caratteri inseriti per non dovere generare un vettore infinito e causare buffer overflow? vedremo anche questo!).

Intanto vediamo come farà il nostro algoritmo a gestione una password di più di un carattere.
La soluzione è molto semplice, si scorrono uno a uno i caratteri del testo e della password e si fa lo Xor come prima ma vediamo come rendere tutto un po’ più sicuro.

Creazione della chiave

In C una stringa è un vettore percuì alla posizione di ogni carattere viene anche associato un valore intero positivo detto “indice”.
Possiamo codificare il valore decimale del carattere della password per selezionare un valore da una stringa di caratteri ed utilizzare quel catattere per fare lo Xor con il testo in chiaro, mi spiego meglio.

La chiave di crittografia non sarà il carattere della nostra password ma, tramite una funzione, associeremo ad ogni carattere della nostra password un altro carattere preso da una stringa da noi generata in questo modo.

char key(char carattere){
return "01NS23H5Q9acOd%ghijl;opq:sWtev8w=xzAB<CDE9FJKL#MPrRm6bTkU@^VXZn!£$/(>uyé*ç°Y§_[f·}~`4IòàÈè^?{}"[(int)chiave-33];
}

Come funziona?? prendo il carattere, lo passo alla funzione, questa trasforma il valore del carattere in un intero e seleziona il carattere della stringa la cui posizione corrisponde a quell’intero.

Il problema è che la stringa contiene 96 caratteri percui per selezionare un carattere della stringa devo inserire un indice che va da 0 a 95 mentre i caratteri dati ad input alla funzione hanno valore numerico che va da 33 a 126, devo quindi sottrarre 33 così che l’indice nell’intervallo 0 – 93 (ne saltano 2 ma poco importa in questa prima versione).
Il return non fa altro che restituirmi il carattere della stringa corrispondente alla posizione inserita in ingresso.

Cosi, richiamando questa funzione, ogni volta, abbiamo un carattere collegato alla nostra password ma allo stesso tempo diverso da quello della password stessa.

Anticipazioni

Nella funzione Xor, che vedremo la prossima volta, ho aggiunto, per facilità di gestione del progetto, un controllo che verifica il carattere restituito prima di salvarlo nella stringa, se tale carattere non è un carattere scrivibile, ma un carattere di gestione del formato come spazio o carrage return, rieffettua lo Xor con un altro carattere della password.
Vedremo questo al prossimo appuntamento.

Saluti.

Argomento (0 / 0)
Leggibilità (0 / 0)
Completezza (0 / 0)
Simone Sante Ruffo
Diplomato al liceo scientifico, si è laureato in ingegneria informatica e delle telecomunicazioni e sta proseguendo ora gli studi in Ingegneria Elettronica per prendersi la laurea magistrale. Appassionato di informatica, telecomunicazioni ed elettronica gli piace studiare, conoscere, progettare e risolvere problemi
http://simonesanteruffo.it

Lascia una recensione

Please Login to comment

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

  Subscribe  
Notificami
Top